Для оценки позиций программа eXtreme Gammon (далее - XG) использует алгоритм нейронной сети. В информатике нейронные сети были попыткой имитировать то, как работает мозг. Это большой черный ящик с определенным количеством входов и выходов. В середине находится пучок нейронов.
В XG на вход сети подается около 150 данных о позиции. В ответ сеть выдает пять вероятностей:
- простого выигрыша
- выигрыша марсом
- выигрыша коксом
- проигрыша марсом
- проигрыша коксом
Для работы нейронную сеть необходимо обучить. Если использовать "биологическую" терминологию, то входные нейроны соединяются аксонами со всеми скрытыми нейронами, которые соединяются с выходными нейронами.
Обучение заключается в том, что нейронная сеть получает входные данные и сравнивает выходные данные с известными значениями, а затем корректирует размер аксона и пороговые значения, чтобы выходные данные были ближе к ожидаемым значениям.
Такой алгоритм оказался очень эффективным для игры в нарды, хотя и имеет некоторые ограничения. Например, редкие позиции могут быть оценены неправильно, а также все вероятности не учитывают значение куба.
В последней версии программы нейронная сеть содержит оценки более 1,1 млрд позиций.
Как вычисляется оценка позиции?
Значение оценки позиции в нардах называется эквити. Это значение показывает размер ожидаемого выигрыша для ходящего игрока, которое может принимать любые значения от -3 до +3.
Без учета куба эквити (Cubeless Equity) вычисляется сложением всех вероятностей игрока и вычитанием из полученной суммы всех вероятностей соперника. Результат делим на 100. Напр. посчитаем эквити по данным на картинке:
48,41 + 11,94 + 0,39 - (100 - 48,41) - 11, 51 - 0,36 = -2,7
-2,7 / 100 = -0,027 (на картинке значение N)
Для расчета эквити с кубом и в матчах применяются более сложные формулы. Они описаны в документации к XG.
Глубина анализа
Как говорилось выше, некоторые позиции нейронная сеть не может оценить правильно. Для уменьшения этой проблемы используется увеличение глубины анализа.
Сначала XG "спрашивает" у нейронной сети оценку текущей позиции. Это глубина - 1 полуход (ply). Затем XG обращается к нейронной сети за оценкой позиций, которые получатся после лучшего хода и каждого из 21 возможных бросков костей. Средняя оценка этих позиций будет результатом анализа на глубине 2 полухода.
Можно увеличивать глубину бесконечно, но требуется все больше и больше времени на выполнение этих операций:
- 1 полуход - 1 оценка
- 2 полухода - 21 оценка
- 3 полухода - 441 оценка
- 4 полухода - 9261 оценка
- 5 полуходов - 194481 оценка
Чем глубже анализ, тем точнее оценка позиции. Но, как мы видим, анализ на глубину 5 полуходов потребует в 200 тыс. раз больше времени, чем анализ на 1 полуход. Приемлемой глубиной по критерию "время-точность" считается 3 полухода.
Как уменьшается сила игры программы?
Чтобы игра с программой была интересна не только для мастеров, но и для простых любителей, в нее встроено несколько уровней игры.
Для игры на слабых уровнях, например Distracted (рассеянный) или Beginner (начинающий), XG выполняет следующие шаги:
- Получает от нейронной сети оценку на минимально возможной глубине (1 полуход)
- К полученной оценке добавляется случайное значение (так называемый "шум", то есть искажение)
Для знатоков статистики: используемое в XG распределение шума является нормальным распределением с математическим ожиданием равным 0 и со среднеквадратичным отклонением, основанном на текущем значении и уровне (чем слабее уровень, тем выше среднеквадратичное отклонение).
Заключение
Комбинация нейронной сети и глубины анализа делает оценку позиций очень точной, что объясняет силу программы.
Есть и другие преимущества, которыми обладает программа: она никогда не устает и не отвлекается. Но у нее есть и ограничения, такие как необычные позиции или "эффект горизонта".
