Стратегические игры. Доступный учебник по теории игр. Авинаш Диксит

еще одна игра с двумя участниками, в которую играют на доске восемь на восемь клеток. Каждый игрок имеет по 12 круглых фигур, или шашек, разного цвета (рис. 3.9), и игроки по очереди передвигают их по диагонали, перепрыгивая (и захватывая) шашки противника, когда это возможно. Как и в шахматах, игра заканчивается и игрок А выигрывает, если у игрока Б не остается шашек или ему некуда ходить. Кроме того, партия может завершиться вничью, если оба игрока согласятся, что ни один из них не может победить.

      Рис. 3.9. Шашки

      Хотя сложность шашек меркнет на фоне шахмат (количество вероятных позиций в шашках приблизительно равно квадратному корню из количества позиций в шахматах), существует 5 × 10²⁰ возможных позиций, так что о построении дерева игры не может быть и речи. Если исходить из здравого смысла и результатов чемпионатов мира по шашкам за многие годы, то хорошая игра должна приводить к ничьей, но это не было доказано. Однако спустя какое-то время программисту из Канады все же удалось получить такое доказательство – компьютерную программу Chinook, которая способна обеспечить гарантированную ничью.

      Chinook появилась в 1989 году, а в 1992-м впервые сразилась с чемпионом мира по шашкам Марионом Тинсли (проиграв со счетом 4:2 при 33 ничьих), а затем еще раз в 1994 году (когда во время серии ничьих у Тинсли пошатнулось здоровье). В период с 1997 по 2001 год работа над программой была приостановлена, поскольку ее создатели ждали усовершенствования компьютерных технологий. И наконец весной 2007 года Chinook продемонстрировала беспроигрышный алгоритм игры в шашки, использующий комбинацию анализа методом обратных рассуждений с конца игры и прямого анализа игры с исходной позиции наряду с эквивалентом функции промежуточной оценки для отслеживания лучших ходов в базе данных, включающей все возможные позиции на доске.

      Создатели Chinook называют полную игру в шашки «слабо решенной»; они знают, что могут обеспечить ничью, и у них есть стратегия ее достижения с исходной позиции. Для всех 39 × 10¹² возможных позиций с наличием 10 или менее шашек на доске они описывают игру как «строго решенную». В этом случае они знают, что могут не только сыграть вничью, но и достичь ее из любой позиции, сформировавшейся после того, как на доске останется не более 10 шашек. Этот алгоритм сначала решил эндшпиль с 10 шашками, а затем вернулся к началу игры, чтобы найти те ее пути, на которых оба игрока делают оптимальный выбор. Механизм поиска, включающий комплексную систему оценки каждой промежуточной позиции, неизбежно приводил к тем позициям с 10 шашками, которые гарантировали ничью.

      Следовательно, наша надежда на будущее анализа методом обратных рассуждений небеспочвенна. Мы знаем, что в действительно простых играх можем найти равновесие посредством вербальных рассуждений без необходимости рисовать дерево игры в явной форме. В играх среднего уровня сложности процесс вербальных размышлений затрудняется, но можно нарисовать дерево игры и использовать его в ходе анализа