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

Диксит Авинаш

В последнее время компьютеры начали накапливать больше знаний. В процессе модификации Deep Blue в 1996–1997 годах специалисты IBM заручились поддержкой экспертов по шахматам для улучшения функции промежуточной оценки в своих программах. Консультанты много раз играли в шахматы с компьютером, отмечали его слабые места и подсказывали, как изменить функцию оценки, чтобы устранить дефекты. Deep Blue явно пошел на пользу вклад экспертов и их тонкое мышление, ставшее результатом многолетнего опыта и знания сложных взаимосвязей между фигурами на шахматной доске.

Если люди, постепенно формулируя свои глубинные знания, передают их компьютерам, то на что рассчитывать шахматистам, не получающим от ПК аналогичной помощи? В момент первой встречи с Deep Blue

в 1997 году Каспаров был поражен человеческим или даже сверхчеловеческим качеством игры компьютера. Он даже увидел в одном из его ходов «руку Бога». А ведь ситуация может усугубиться еще сильнее: способность компьютеров просчитывать ходы методом грубой силы стремительно повышается, причем одновременно, хотя и медленнее, они обретают тонкость мышления, свойственную человеку.

Абстрактная теория шахмат гласит, что это конечная игра, которая может быть решена методом обратных рассуждений. Шахматы зачастую требуют искусства ведения игры, опирающегося на опыт, интуицию и тонкие суждения. Плохо ли это с точки зрения использования метода обратных рассуждений в процессе анализа игр с последовательными ходами? Мы считаем, что нет. Теория действительно не позволяет найти полное решение игры в шахматы, но дает возможность достаточно далеко продвинуться в этом направлении. Упреждающий анализ нескольких ходов – важный аспект подхода, подразумевающий сочетание просчета ходов методом грубой силы и основанной на знаниях оценки промежуточных позиций. По мере увеличения вычислительной мощности компьютеров будет возрастать и роль просчитывания ходов методом грубой силы, а значит, и область применения теории обратных рассуждений.

Данные исследований игры в шашки, о чем мы расскажем ниже, говорят о том, что решение игры в шахматы все же может быть найдено.

В. Шашки

Невероятное количество компьютерных и человеко-часов ушло на поиск решения игры в шахматы. С не меньшим упорством исследователи работали и над решением несколько более простой игры – в шашки, и в 2007 году объявили, что оно найдено [28] .

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

28

Наш рассказ основан на следующих статьях, опубликованных в журнале Science: Adrian Cho, Program Proves That Checkers, Perfectly Played, Is a No-Win Situation, Science, vol. 317 (July 20, 2007), pp. 308–309; Jonathan Schaeffer et al., Checkers Is Solved, Science, vol. 317 (September 14, 2007), pp. 1518–22.

Рис. 3.9. Шашки

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

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

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

Следовательно, наша надежда на будущее анализа методом обратных рассуждений небеспочвенна. Мы знаем, что в действительно простых играх можем найти равновесие посредством вербальных рассуждений без необходимости рисовать дерево игры в явной форме. В играх среднего уровня сложности процесс вербальных размышлений затрудняется, но можно нарисовать дерево игры и использовать его в ходе анализа методом обратных рассуждений. Иногда при анализе дерева игры умеренной сложности имеет смысл прибегнуть к помощи компьютера. В более сложных играх, таких как шашки и шахматы, мы можем нарисовать только часть дерева игры, поэтому должны применять сочетание двух методов: 1) просчет ходов, строящийся на логике обратных рассуждений; 2) эмпирическая оценка промежуточных позиций на основе опыта. Вычислительные возможности существующих алгоритмов подтверждают тот факт, что даже некоторые игры этой категории поддаются решению при наличии соответствующего времени и ресурсов.

К счастью, большинство стратегических игр, с которыми мы сталкиваемся в области экономики, политики, спорта, бизнеса и в повседневной жизни, гораздо проще по сравнению с шахматами или даже шашками. В них может быть несколько игроков, которые ходят по несколько раз, и даже большое количество игроков и большое количество ходов. Однако у нас есть шанс нарисовать приемлемое дерево для игр, последовательных по своей сути. Логика обратных рассуждений остается в силе; и часто так бывает, что стоит вам освоить этот метод, и вы легко выполняете необходимый логический анализ и решаете игру даже без построения дерева игры в явной форме. Кроме того, именно на этом промежуточном уровне сложности (между простыми примерами, которые мы решили в данной главе, и нерешенными играми вроде шахмат) могут пригодиться такие компьютерные программы, как Gambit; это открывает перспективу применения теории к решению многих игр на практике.

6. Фактические данные, касающиеся метода обратных рассуждений

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