Дерево игры в нарды

Применение методов искусственного интеллекта в переборных алгоритмах

Одной из сложных позиционных игр, исследуемых в настоящее время на предмет построения играющей программы, является игра в короткие нарды (backgammon), которую мы в дальнейшем будем называть просто нарды. Это игра двух противников. В нее играют шашками на одномерном поле с 26 игровыми полями. Начальная позиция заключается в некоторой исходной расстановке шашек на игровых полях. Ходом игрок передвигает какие-то из своих шашек в одном направлении. Направления движения шашек разных игроков противоположны. Цель игры - первым вывести свои шашки на заключительное поле или сгруппировать их поближе к этому полю. Возможность игрока передвигать шашки определяется броском двух кубиков. Существует 36 равновероятных комбинаций выпадения кубиков, из них 21 принципиально разная. В сети Интернет можно найти большое количество материалов по нескольким различным подходам к программированию игрока в нарды. Некоторая систематизация этих материалов произведена авторами "J.B.Pollack, A.D.Blair. Coevaluation of a backgammon player". Среди описанных здесь подходов - реализация самообучения по методу взбирания на холм, подробное рассмотрение которого содержится в главе 3 данной работы.

В статье "Б.Ф.Мельников, А.Н.Радионов. О выборе стратегии в недетерминированных антагонистических играх. - Программирование (РАН), 1998, N5, с.98-99" подробно описан один из подходов к данной задаче. Его суть вкратце в следующем. Игра, по аналогии с подходом из книги "Г.М.Адельсон-Вельский, В.Л.Арлазаров, М.В.Донской. Программирование игр. - М.: Наука, 1978", описывается посредством дерева игры. Далее также по аналогии определяются оценки позиций, применяется а,b-эвристика. Кроме того, вводится такое новое понятие, как функция риска. Программа, построенная авторами статьи, добилась реальных успехов.

Так как нарды в большой степени отличаются от игр, подобных шахматам, то некоторые подходы из "Г.М.Адельсон-Вельский, В.Л.Арлазаров, М.В.Донской. Программирование игр. - М.: Наука, 1978" не применимы в отношении нард. Основным отличием нард от шахмат является недетерминированность. Ее привносит в нарды стохастический фактор, обусловленный бросанием кубиков. Этот фактор значительно усложняет исследование нард, но в то же время делает его более актуальным. Ведь подавляющее большинство явлений и процессов в действительности так или иначе связано с явлениями случайными, описываемыми вероятностно. В результате дерево игры в нарды - дерево недетерминированной игры. В связи с этим возникает потребность в дополнительном анализе дерева игры в нарды.

А.В.Мосеев, underwood.narod.ru, 1999 год