X&O : метрики качества алгоритма
Чтобы улучшать качество алгоритма игры компьютера против человека, для начала нужно определить, что является качественной характеристикой.
Алгоритм устроен так, что оценка рейтинга каждой позиции постоянно уточняется, по мере расчёта дочерних позиций. Пока дочерние позиции не рассчитаны, то для оценки текущей используем количество двоек, троек и четвёрок для каждого из игроков (см. определения тут), помножая их на определённый вес и суммируя, как это определено в Evaluator.c Если же дочерние позиции уже рассчитаны, то выбираем дочерний ход с наиболее высоким рейтингом, меняем его знак на противополжный (т.е. помножаем на -1) и используем в качестве рейтинга текущей позиции.
Выберем несколько метрик, которые будут характеризовать этот процесс уточнения. Для простого начала, будем оценивать только то, как изменяется рейтинг первого хода (это ход крестиком в центральную клетку игрового поля), по мере расчёта 6 миллионов его дочерних ходов (т.к. при запуске программы, если игра находится в ожидании, дерево вариантов вырастает только до 6 миллионов, для экономии памяти).
Наиболее важные метрики качества связаны с отбраковыванием игровых вариантов. Обозначим количество узлов, абсолютное значение рейтинга которых превысило R на момент, когда дочерних узлов было более N, как Cull_N_R.
Очевидно, что при достаточно больших значениях N и R, такие значения будут характеризовать уровень брака (чем больше значение, тем хуже алгоритм). При большом значении N, ожидается что узел не должен отбраковываться (иначе получаем ситуацию, когда мы тратим много ресурсов на расчёт неперспективного узла).
| LAR | 0 | FRD | LD | LD + FRD | |
| Cull_400_8k / Cull_400_16k | 155 / 296 | 588 / 175 | 632 / 180 | 823 / 263 | 1204 / 326 |
| Cull_2k_8k / Cull_2k_16k | 43 / 60 | 340 / 18 | 378 / 56 | 321 / 33 | 490 / 49 |
| Cull_10k_8k / Cull_10k_16k | 6 / 0 | 47 / 0 | 51 / 1 | 30 / 2 | 36 / 7 |
| Cull_50k_8k / Cull_50k_16k | 0 / 0 | 0 / 0 | 0 / 0 | 0 / 1 | 0 / 1 |
| Cull_250k_8k / Cull_250k_16k | 0 / 0 | 0 / 0 | 0 / 0 | 0 / 0 | 0 / 0 |
| Update frequency | 61,4% | 51.7% | 50% | 77,8% | 80,8% |
| Max childs updated | 0.18M | 1.9M | 2.7M | 5.8M | 5.9M |
| Update count | 51 | 75 | 67 | 524 | 611 |
| Skip count | 32 | 70 | 66 | 149 | 145 |
| Avg Diff | 63 | 49 | 55 | 6 | 5 |
| Avg Abs Diff | 151 | 131 | 144 | 196 | 224 |
| max path length | 25 | 20 | 20 | 13 | 13 |
| Rating | 3311 | 3817 | 3817 | 3339 | 3203 |
Фичи исследуемой программы:
- LAR (Legacy Average Rating) - при вычислении нового рейтинга узла в расчёт берётся также его старое значение (См. Expander.cpp, строка cursor->rating = (TRating)(0.4*(double)oldRating-0.6*(double)max_rating);).
- 0 - старая версия кода, но с отключенным LAR.
- LD (Logariphmic Distribution) - выбор узла на основе распределения: 50% дочерних узлов у лучшего варианта, 25% у второго, 12.5% у третьего и т.д. (См. функцию Builder::chooseNodeToExpand и этот коммит).
- FRD (Far Rating Decrease) - если лучший рейтинг дочернего узла слишком велик по модулю, тогда немного уменьшаем его модуль при переносе на родительский узел. Таким образом, с высокорейтинговых узлов берём небольшое пенальти за каждый ход, чтобы повысить мотивацию для выигрывающего игрока выиграть максимально коротким путём, а для проигрывающего - максимально оттянуть окончание игры. (См. строчки №136-137 в Relator.cpp, if (max_rating < -27000) max_rating += 3; else ...).
Метрики:
- Cull_N_R - наш основной набор метрик, см. выше.
- Метрики для первого узла, который соответствует единственному ходу крестиков в центр поля. Тут надо понимать, что добавление дочерних узлов вызывает цепную реакцию обновления всех родителей. У непосредственного родителя увеличивается счётчик totalChilds, а также изменяется рейтинг - теперь он считается как рейтинг лучшего дочернего хода, но со знаком "минус", поскольку дочерний ход принадлежит оппоненту. Далее, у всех узлов-прародителей вызывается аналогичное обновление, увеличивающее счётчик totalChilds, а рейтинг может поменятся, только если новый вычисленный рейтинг их дочернего узла признан самым высоким из всех дочерних узлов.
- Update frequency - как часто обновляется рейтинг первого узла, когда был обновлён рейтинг одного из его дочерних узлов.
- Max childs updated - какое максимальное значение totalChilds было у первого узла, когда его рейтинг обновился в последний раз.
- Update count - сколько раз обновился рейтинг первого узла после обновления рейтинга одного из его дочерних узлов.
- Skip count - сколько раз НЕ обновился рейтинг первого узла после обновления рейтинга одного из его дочерних узлов.
- Avg Diff - средняя разница между старым и новым рейтингами, при его обновлении.
- Avg Abs Diff - средняя разница по модулю между старым и новым рейтингами, при его обновлении.
- max path length - финальная высота дерева (после вычисление 6 миллионов узлов).
- Rating - финальный рейтинг первого узла (после вычисление 6 миллионов узлов).
Вывод
Изначально предполагалось что фича LD улучшит направленность перебора, и качество игры. Но, исходя из полученных значений, об этом сложно сделать однозначный вывод. Возможно, выбранные метрики не являются хорошим показателем, и качество игры нужно испытывать непосредственно, пытаясь обыграть алгоритм. Особое внимание также обращает то, что фича FRD, казалось бы, вообще не должна влиять на силу алгоритма, при расчёте равновесных позиций. Однако, как видим, она имеет сильное влияние на метрики, и на этот счёт требуется отдельный дополнительный анализ.
Улучшенные метрики
Хотя предыдущий эксперимент не смог дать внятного результата, сдаваться так сразу не стоит. Лучше проявить настоящий исследовательский дух. Ведь уже имея в руках Cull_N_R метрики, достаточно легко их можно попытаться подстроить, для получения более интересных данных. Во-первых, изменим сетку для значений числа N. Нас более всего интересует пограничный интервал значений, при котором отбраковывание перестаёт происходить. Поэтому выберем значения 2k, 4500, 7k, 10k, 14k. Во-вторых, теперь будем считать узел отбракованным, только если его рейтинг упал ниже числа -1*R. Другими словами, мы теперь не будем работать с абсолютным значением рейтинга, то есть не будем отбраковывать узлы, рейтинг которых вырос выше чем R. В этом случае ожидается что отбраковано будет примерно вдвое меньше узлов чем в предыдущем эксперименте. Однако тут важным моментом является разобраться со случаями, где количество отбракованных узлов было равно единице.
| 0 | FRD | LD | LD + FRD | |
| Cull_2k_8k / Cull_2k_16k | 167 / 15 | 199 / 44 | 271 / 24 | 338 / 29 |
| Cull_4500_8k / Cull_4500_16k | 106 / 1 | 90 / 4 | 30 / 2 | 108 / 15 |
| Cull_7k_8k / Cull_7k_16k | 67 / 0 | 72 / 4 | 13 / 3 | 43 / 1 |
| Cull_10k_8k / Cull_10k_16k | 26 / 0 | 23 / 1 | 13 / 2 | 15 / 0 |
| Cull_14k_8k / Cull_14k_16k | 21 / 0 | 28 / 0 | 17 / 1 | 20 / 8 |
| Update frequency | 51,7% | 50,3% | 77,8% | 80,8% |
| Max childs updated | 1.9M | 2.7M | 5.9M | 5.9M |
| Update count | 75 | 67 | 524 | 611 |
| Skip count | 70 | 66 | 149 | 145 |
| Avg Diff | 49 | 55 | 6 | 5 |
| Avg Abs Diff | 131 | 144 | 196 | 224 |
| max path length | 20 | 20 | 13 | 13 |
| Rating | 3817 | 3817 | 3339 | 3203 |
Выводы
- Сразу обращает на себя внимание что при отсутствии механизма LD параметр Max childs updated остаётся далеко ниже шести миллионов. Это значит, что рейтинг первого хода перестаёт обновлятся уже после 1.9 М (или 2.7 М, при наличии FRD) вычисленных дочерних узлов. Таким образом, вычисление оставшихся не приводит к уточнению рейтинга текущего (первого) хода, что выглядит нехорошо; вычисление явно начинает идти по какому-то специфическому длинному пути сомнительной нужности, о чём нам также говорит увеличенный max path length.
- Неожиданно оказывается что FRD слишком существенно влияет на метрики отбраковывания. Хотя этот механизм вовсе не призван на них влиять вообще, а нужен только для того, чтобы выигрывать было выгоднее как можно более коротким путём. Чем короче путь до выигрыша, тем меньше пенальти. Пенальти составляет 3 рейтинговых очка за ход. Поэтому выглядит логичным снизить его до минимального значения - единица, чтобы максимально ограничить его влияние на метрики (а значит и на выбор направлений переборов).
- Параметр N недостаточно велик, было бы интересно исследовать значения около 20k-30k.
Дубль три
Итак, изменим фичу FRD на FRD-1. А также выберем другой набор для значений N:
| 0 | FRD-1 | LD | LD + FRD-1 | |
| Cull_4k_8k / Cull_4k_16k | 132 / 1 | 113 / 9 | 49 /3 | 148 / 15 |
| Cull_7k_8k / Cull_7k_16k | 67 / 0 | 72 / 4 | 13 / 3 | 43 / 1 |
| Cull_10k_8k / Cull_10k_16k | 26 / 0 | 23 / 1 | 13 / 2 | 15 / 0 |
| Cull_14k_8k / Cull_14k_16k | 17 / 0 | 20 / 0 | 17 / 0 | 20 / 4 |
| Cull_20k_8k / Cull_20k_16k | 4 / 0 | 8 / 0 | 0 / 1 | 0 / 4 |
| Update frequency | 51% | 50% | 77.8% | 80.8% |
| Max childs updated | 1.9M | 2,7M | 5.9M | 5.9M |
| Update count | 75 | 67 | 524 | 611 |
| Skip count | 70 | 66 | 149 | 145 |
| Avg Diff | 49 | 55 | 6 | 5 |
| Avg Abs Diff | 131 | 144 | 196 | 224 |
| max path length | 20 | 20 | 13 | 13 |
| Rating | 3817 | 3817 | 3339 | 3203 |
Вывод
- LD режим выглядит явно предпочтительнее режима 0. Уже при количестве потомков от 7 тысяч и выше стабильно наблюдается снижение количества брака.
- FRD по-видимому имеет неприятный side- эффект, заметно увеличивающий количество брака. Возможно, это баг. Эта фича требует дополнительных исследований и доработки.
- Подобрать хорошие метрики качества - трудная задача, поэтому проще всего её поручить было бы искусственному интеллекту. Вот что ИИ смог рассказать: https://share.google/aimode/RhG5RvLdxIAYT09N4. Как видим, метод "Скорость сходимости и отсечения (Search Efficiency)" хотя и упоминается, но ничего не сказано конкретно об использованном в этой статье методе, хотя метрики Cull_N_R измеряют именно скорость отсечения.
Update
Исследуя глубже legacy код, в какой-то момент обнаруживаются признаки задвоения фичи FRD:
- См. строчки №136-137 в Relator.cpp, if (max_rating < -27000) max_rating += 3; else ... - Эту фичу обозначим как FRD-R_27
- См. строчки №164-176 в TNode.cpp, if (newRating > 16384) { rating = newRating - 1;} else if (newRating < -16384) { rating = newRating + 1; } Эту фичу обозначим как FRD-TN_16
| 0 | FRD-TN_16 | FRD-TN_27 | FRD-R_27 | FRD-R_16 | |
| Cull_7k_8k / Cull_7k_16k | 44 / 72 | 22 / 4 | 19 / 5 | 132 / 37 | 51 / 20 |
| Cull_12k_8k / Cull_12k_16k | 3 / 76 | 10 / 1 | 4 / 1 | 18 / 12 | 1 / 11 |
| Cull_16k_8k / Cull_16k_16k | 18 / 0 | 11 / 0 | 1 / 3 | 1 / 5 | 15 / 3 |
| Cull_24k_8k / Cull_24k_16k | 0 / 0 | 0 / 0 | 0 / 1 | 2 / 1 | 71 / 0 |
| Cull_36k_8k / Cull_36k_16k | 1 / 0 | 0 / 1 | 2 / 1 | 0 / 1 | 0 / 0 |
| Update frequency | 83% | 77,4% | 72.6 | 76.8% | 82.5% |
| Max childs updated | 5.94M | 5,86M | 5,97M | 5.97 | 5.58M |
| Update count | 627 | 511 | 461 | 404 | 476 |
| Skip count | 128 | 149 | 174 | 122 | 101 |
| Avg Diff | 3 | 6 | 5 | 7 | 6 |
| Avg Abs Diff | 191 | 201 | 167 | 192 | 192 |
| max path length | 12 | 13 | 13 | 12 | 13 |
| Rating | 2396 | 3339 | 2685 | 3102 | 3339 |
Вывод(ы)
- FRD-R и FRD-TN - неравнозначные места в коде для ренализации фичи FRD, как показали эксперименты.
- TODO - Нужно проаналазировать по структуре кода, в чём их различие.
- Впервые поймали доказанный случай, когда Cull_36k по нулям. (То есть, 36 тысяч дочерних вариантов достаточно, чтобы всё поддерево не отбраковывалось.) Причём, таким свойством облада
- По крайней мере, такого не происходит при подсчёте первых 6 М вариантов.
- TODO - Нужно проверить на бóльшем количестве.
- По крайней мере, такого не происходит при подсчёте первых 6 М вариантов.
Увеличиваем количество 6M ⟶ 30M
| 0 | FRD-R_4 | FRD-R_5 | FRD-R_6 | FRD-R_8 | FRD-R_16 | |
| Cull_9k_8k / Cull_9k_16k | 373 / 401 | 191 / 183 | 232 / 154 | 194 / 101 | 178 / 70 | |
| Cull_18k_8k / Cull_18k_16k | 297 / 253 | 29 / 56 | 156 / 89 | 50 / 16 | 133 / 50 | |
| Cull_36k_8k / Cull_36k_16k | 121 / 72 | 2 / 1 | 2 / 33 | 2 / 5 | 44 / 13 | |
| Cull_72k_8k / Cull_72k_16k | 4 / 41 | 0 / 0 | 0 / 0 | 0 / 0 | 0 / 0 | |
| Cull_144k_8k / Cull_144k_16k | 0 / 0 | 0 / 0 | 0 / 0 | 0 / 0 | 0 / 8 | |
| Update frequency | 76,84% | 79,87% | 82,17% | 87,83% | 87,26 | |
| Max childs updated | 19,92M | 19,47M | 19.90M | 19,58M | 19,77M | |
| Update count | 979 | 885 | 968 | 1025 | 747 | |
| Skip count | 295 | 223 | 210 | 142 | 109 | |
| Avg Diff | 2 | 2 | 2 | 2 | 5 | |
| Avg Abs Diff | 190 | 197 | 216 | 203 | 200 | |
| max path length | 13 | 13 | 14 | 14 | 14 | |
| Rating | 2817 | 2499 | 2571 | 2878 | 3911 |
Вывод(ы)
- как видим, FRD-R_16, зависло, расссчитав всего лишь чуть менее 20 миллионов вариантов. Число Cull_36k оказалось великó.
Подстраиваем остальные константы так, чтобы рассчёт вёлся до 30 миллионов и снова тестируем.
| 0 | FRD-R_5 | FRD-R_6 | |
| Cull_9k_8k / Cull_9k_16k | 393 / 411 | 440 / 444 | 345 / 186 |
| Cull_18k_8k / Cull_18k_16k | 303 / 260 | 230 / 345 | 243 / 122 |
| Cull_36k_8k / Cull_36k_16k | 123 / 75 | 51 / 96 | 35 / 51 |
| Cull_72k_8k / Cull_72k_16k | 7 / 41 | 9 / 2 | 64 / 67 |
| Cull_144k_8k / Cull_144k_16k | 0 / 0 | 0 / 0 | 39 / 2 |
| Update frequency | 74,94% | 82,6% | 79,5% |
| Max childs updated | 29,94M | 29,22M | 29,86M |
| Update count | 1220 | 1064 | 1069 |
| Skip count | 408 | 224 | 275 |
| Avg Diff | 1 | 2 | 1 |
| Avg Abs Diff | 190 | 202 | 215 |
| max path length | 13 | 13 | 14 |
| Rating | 1924 | 2313 | 1737 |
Вывод(ы)
- Режим FRD-R_5 выглядит наиболее эффективным. Именно этот вариант и будем пушить в репозиторий на гитхабе.
В качестве дополнительного тестирования, попробовал поиграть против компьютера, играя за первого игрока (за крестиков). Сыграл три раза, выиграть смог только один раз (во второй раз). Заметил, что когда выигрывал, собираясь создать, или создав "вилку" из двух "троек", алгоритм поставил "полузакрытую четвёрку", вынудив меня потратить один ход на то, чтобы её заткнуть. Таким образом, можно сделать вывод, что фича FRD работает, заставляя алгоритм тянуть время в случае проигрышной ситуации.
Сдедующей доработкой кода будет сохранение и восставление игровых узлов в (из) файл(а).
Bugfix
Очередное исправление пришло откуда не ждали. Оказалось, что узлы в Cull_N_R многократно дублируются, потому что их рейтинг может как выходить за пределы числа R, так и снова возвращаться назад. А потом снова выходить за пределы, и, соответственно снова попадать в файл xo.dat и снова учитываться в статистике. Поэтому добавляем код в Relator.cpp,
node->fixedRating = true;
в то место, где регистрируем для узла событие Cull_N_R. Таким образом, узео однажды отбракованный, так и будет им оставаться в последствии.
И второе исправление, тоже в файле Relator.cpp, в функции getChild. Сделаем чтобы центровой ход (в клетку 112) не рассматривался как дочерний ход какого-то другого хода. Это исправление назовём BF-112. Впрочем, как выяснилось, второе исправление не влияет на метрики.
if (childMove == 112) return NULL;
Третье - это доработка для функции expand. Теперь, если нам угрожает "шах" на каком-то ходе, то рассматриваем только дочерние варианты, которые его нивелируют. А также, наоборот, если можем построить 5, или открытую четвёрку, то рассматриваем только такие варианты. Эту доработку назовём EXP.
| FRD-R_5 | FRD-R_5 + EXP | ||
| Cull_9k_8k / Cull_9k_16k | 19 / 43 | 14 / 8 | |
| Cull_18k_8k / Cull_18k_16k | 12 / 10 | 2 / 3 | |
| Cull_36k_8k / Cull_36k_16k | 2 / 2 | 1 / 0 | |
| Cull_72k_8k / Cull_72k_16k | 0 / 0 | 0 / 0 | |
| Cull_144k_8k / Cull_144k_16k | 0 / 0 | 0 / 0 | |
| Update frequency | 86.27% | 7,9% | |
| Max childs updated | 29,99M | 28,94M | |
| Update count | 1382 | 1926 | |
| Skip count | 229 | 22309 | |
| Avg Diff | 1 | 0 | |
| Avg Abs Diff | 224 | 207 | |
| max path length | 15 | 21 | |
| Rating | 2646 | 1552 |
Вывод(ы)
- Улучшение EXP показало себя очень хорошо. Значительно сократилось кооличество отбраковываемых узлов. Также заметно увеличилась высота дерева вариантов (параметр max path length), что как раз соответствует ожиданиям.
Следующий этап доработок будет связан с возможностью сохранять накопленные данные в файл, для дальнейшего переиспользования. Ему посвящается отдельная глава.