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 измеряют именно скорость отсечения.