1.8 Нетранзитивность игр

Одна из проблем метода вскарабкивания связана с транзитивностью отношения "более сильный - более слабый" игровых программ. Если программа A чаще всего выигрывает у программы B, а та в свою очередь чаще всего выигрывает у программы C, то последняя может чаще всего выигрывать у программы A. То есть транзитивность этого отношения стоит под вопросом. Программа, играющая на среднем уровне, может в силу стечения обстоятельств иметь, скажем, всего одну, но очень эффективную стратегию против гораздо более сильной программы и постоянно её обыгрывать. При этом эта стратегия не действует против других более сильных программ. Такие примеры существуют в жизни. Так, величайшего шахматиста Александра Алёхина, очень часто обыгрывал шахматист значительно менее высокого уровня Лайош Асталош. Известны и другие случаи подобного "везения", в том числе и в командных играх, что говорит о том, что это свойство нетранзитивности не является результатом каких-то психологических феноменов, а присуще самим играм, в особенности сложным позиционным.

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

1.9 Обзор литературы и существующих программ.

В последние годы в мире был опубликован ряд статей и монографий, посвященных применению искусственного интеллекта (AI) в логических играх, в частности в нардах.

В работе [13] G. Tesauro “TD-Gammon, a self-teaching backgammon program” отмечается, что программа по игре в нарды (backgammon), реализованная с использованием нейронной сети, добилась высоких результатов при игре с лучшими игроками-людьми, используя параметры, полученные при игре сама с собой. Нейронная сеть использовалась для оценки качества позиций. Программа оценивала все доступные за один ход позиции и выбирала тот ход, который вел к наилучшей позиции. Параметры нейронной сети модифицировались с помощью алгоритма TD.

В работе [14] J.Pollack & A.Blair “Co-Evolution in the successful learning of backgammon strategy” рассматривают эволюционный подход к настройке весов нейронной сети, оценивающей позиции в нардах. В работе предлагается использовать упрощенный вариант генетических алгоритмов. Констатируется достижение достаточно высоких результатов несмотря на некоторые огрехи в методике.

В работе [15] M. Buro “Efficient approximation of backgammon race equities” предлагается использовать статистические методы и динамическое программирование для оценки вероятности выигрыша позиции в нардах. В работе сообщается об обоснованности применения данных методов.

Также в последнее время был выпущен ряд программ для PC и для мобильных устройств.

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

Также был выпущен ряд игр для телефонов, поддерживающих J2ME фирмами gameloft, ZingMagic. Их отличает хорошая графика и приемлемый уровень игры.