2.5 Таблицы вероятностей.

Для усиления игры программы были опробованы таблицы вероятностей. Для игры нарды можно построить два типа таких таблиц: двусторонние и односторонние. Двусторонние таблицы содержат предварительно просчитанные вероятности победы. Например для шести и менее фишек, находящихся в доме есть 924 возможных позиции, всего 924*924 = 853,776 возможных позиций для каждой из которых нужно хранить вероятность победы. Наибольшая проблема таких таблиц – экспоненциальный рост размера с увеличением числа фишек и полей. Так, для упомянутой таблицы объем занимаемой памяти можно оценить шестью мегабайтами, что выходит за рамки ограничений мобильных устройств.

Значительная экономия может быть достигнута при использовании односторонних таблиц в которых хранятся вероятности вывода всех фишек в данной позиции за n ходов - . Предположим, что для игроков A и B в текущей позиции нам известны распределения и , тогда вероятность того что игрок A выведет все свои фишки первым будет рассчитываться по формуле: . Число позиций состоящих из 15 фишек на 6 полях равно 54,264 и такая таблица будет занимать в памяти примерно 1.4 мегабайта, что гораздо ближе к ограничениям для существующих мобильных устройств.

Как оказалось, прирост качества игры от использования такой таблицы оказался незначительным, что может быть объяснено ее небольшим размером и тем, что только порядка 1-2% позиций в игре оценивается по ней.

Но можно применить похожие принципы для генерации выборки для обучения нейронной сети. Так, чтобы получить оценку вероятности выигрыша из данной позиции можно сформировать некоторый набор позиций. И для каждой из этих позиций провести по N партий, между двумя равными сильными игроками. Причем, под числом побед белых над черными можно понимать оценку данной позиции. На сгенерированной таким образом выборке можно обучить нейронную сеть и получить оценочную функцию высокого класса. Можно повторять этот процесс итеративно для улучшения качества оценки.

2.6 Снижение размерности. Гипергаммон.

Одним из способов изучения особенностей игры является снижение размерности. Так, существует разновидность игры нарды – гипергаммон. Гипергаммон – вариант нард в котором каждый игрок имеет по три фишки и игра ведется на обычной доске. Дальнейшее упрощение – рассмотрение только одной стороны, в котором рассматривается процесс вывода фишек без взятий.

2.7 Разделение игрового процесса на фазы.

Игровой процесс в большинстве игр можно достаточно формально разделить на фазы. Для нард можно выделить следующие фазы: позиции близкие к начальной, фаза контакта (характеризуется большим числом взятий) и фаза разрыва контакта (когда единственная цель - как можно быстрее вывести свои фишки). Для каждой фазы характерна определенна стратегия, и соответственно для общего повышения качества оценки позиции, можно предварительно классифицировать оцениваемую позицию и применять разные оценочные функции.

Наиболее простой и наглядной для анализа представляется фаза разрыва контакта для которой верно следующее утверждение: перед любой из своих фишек нет фишек противника. Этот случай хорош тем, что можно рассматривать процесс вывода фишек только одним из игроков - для другого полученные результаты можно применять автоматически. Частным случаем этой фазы является стадия непосредственного вывода фишек с последних шести полей.

Для исследования этой фазы игры удобно построить полную таблицу позиций для небольшого числа фишек (пять – шесть фишек) и посчитать математическое ожидание числа ходов, необходимых для вывода всех фишек из этой позиции в случае игры наилучшим образом. В работе была построена такая таблица методом динамического программирования. Полученные результаты хорошо обобщаются и на большее число фишек.

Такая таблица занимает значительные объемы памяти (мегабайты) поэтому ее хранение для оценивания позиций неэффективно. Также невозможно использование таких данных для оценивания других позиций (контакта). Для этого нужно аппроксимировать эти данные некоторой функцией. В работе использовалось несколько видов функций: сумма расстояний до выхода плюс сумма квадратов расстояний, формула с частным от деления тех же самых параметров, нейронная сеть. Для настройки параметров этих функций использовался метод наименьших квадратов

Для сравнения была построена точно такая же таблица на основе эвристического алгоритма, двигающего дальнюю фишку (подробное описание этого алгоритма). После сверки каждой позиции, выяснилось, что максимально различие в числе ходов составляет не более 3%. Таким образом можно говорить, что такой алгоритм может быть применен для оценки позиции для фазы разрыва контакта практически без ущерба для качества игры по сравнению с оптимальным вариантом. Такой вариант также хорош своей простотой, легкостью реализации и нетребовательностью к аппаратным ресурсам.