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

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

Однако большинство из вас знают, как в худшем случае добиться хотя бы ничьей в игре в крестики-нолики на поле три на три. Так что есть простое решение этой игры, которое можно найти посредством обратных рассуждений, и истинный стратег способен существенно снизить сложность игры в ходе его поисков. Оказывается, как и в версии игры «два на два», многие возможные пути на дереве игры со стратегической точки зрения идентичны. В частности, девять начальных ходов могут быть только трех типов: вы ставите крестик на угловую позицию (четыре возможных варианта), на боковую позицию (также четыре возможных варианта) и на центральную позицию (один вариант). Использование этого метода для упрощения дерева игры поможет снизить уровень сложности задачи и приведет вас к описанию оптимальной равновесной стратегии, полученной методом обратных рассуждений. К примеру, мы могли бы показать, что игрок, который ходит вторым, может гарантированно добиться как минимум ничьей, сделав надлежащий первый ход и постоянно блокируя в дальнейшем попытки первого игрока выставить три символа в ряд [24] .

24

Если

первый игрок ставит первый символ на центральную позицию, второй игрок должен поставить первый символ на угловую позицию. Далее второй игрок может обеспечить ничью, заняв третью позицию в любом ряду, столбце или диагонали, которую пытается заполнить первый игрок. Если первый игрок сначала ставит символ на угловую или боковую позицию, то второй игрок может гарантировать ничью, сперва поставив свой символ в центр, а затем придерживаясь того же метода блокирования. Обратите внимание, что если первый игрок выбирает угловую позицию, второй игрок – центральную позицию, а затем первый игрок выбирает угол, противоположный первоначальному ходу, то второй игрок не должен выбирать оставшиеся углы, чтобы обеспечить хотя бы ничью. Подробное описание такой исчерпывающей условной стратегии в игре крестики-нолики можно найти в онлайн-комиксе на странице http://xkcd.com/832/.

Б. Шахматы

Хотя сравнительно простые игры, такие как крестики-нолики, решаемы методом обратных рассуждений, выше мы показали, насколько быстро повышается сложность дерева игры даже в играх с двумя участниками. Поэтому при анализе более сложных игр вроде шахмат находить полное решение становится гораздо труднее.

В шахматах в распоряжении игроков (условно называемых «белые» и «черные») имеются наборы из 16 фигур разной формы, которые передвигаются по шахматной доске восемь на восемь клеток (рис. 3.8) в соответствии с заданными правилами [25] . Белые ходят первыми, черные – вторыми, и так далее по очереди. Все ходы видны другому игроку, и ничего не оставлено на волю случая, как в карточных играх, где карты перетасовываются и сдаются. Кроме того, шахматная партия должна заканчиваться за конечное число ходов. Согласно правилам, при троекратном повторении одной и той же позиции в течение игры объявляется ничья. Ввиду наличия конечного количества способов разместить 32 фигуры (или меньше, если некоторые фигуры побиты) на 64 клетках шахматной доски, партия не может продолжаться бесконечно долго без возникновения подобной ситуации. Поэтому в принципе шахматы поддаются полному анализу методом обратных рассуждений.

25

Описание правил игры в шахматы и много другой информации о шахматах можно найти в «Википедии».

Рис. 3.8. Шахматная доска

Однако этот анализ так и не проведен. Шахматы не «решены» так, как в свое время крестики-нолики, а причина в том, что, несмотря на простоту правил, шахматы – чрезвычайно сложная игра. Из начальной позиции набора фигур, показанных на рис. 3.8, белые могут сделать любой из 20 ходов [26] , а черные – ответить любым из 20 ходов. Следовательно, из первого узла исходят 20 ветвей, каждая ведет ко второму узлу, из которого исходят еще 20 ветвей. Всего после двух ходов образуется 400 ветвей, и каждая ведет к узлу, из которого исходят очередные ветви. Общее же количество возможных ходов в шахматах составляет, по примерным оценкам, 10¹²⁰, то есть единицу со 120 нулями. Суперкомпьютеру, в тысячу раз превышающему ваш ПК по быстродействию и выполняющему один триллион операций в секунду, понадобилось бы более 10¹⁰⁰ лет, чтобы проверить все ходы [27] . Астрономы отводят нам менее 10¹⁰ лет до того момента, когда Солнце превратится в красный гигант и поглотит Землю.

26

Белые могут сделать ход любой из восьми пешек либо на одну, либо на две клетки вперед или одним из двух коней (на клетки a3, c3, f3 или h3).

27

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

Получается, что хотя для игры в шахматы теоретически можно найти всеобъемлющее решение методом обратных рассуждений, ее полное дерево может оказаться слишком сложным для того, чтобы реализовать такое решение на практике. Что делать игроку в данной ситуации? Знакомство с историей попыток запрограммировать компьютер на игру в шахматы поможет нам многое об этом узнать.

Когда стало ясно, что компьютеры способны выполнять сложные вычисления в науке и бизнесе, многие математики и программисты решили, что вскоре компьютерная шахматная программа победит именитых гроссмейстеров. Но это произошло не так быстро, хотя компьютерные технологии развивались стремительными темпами, тогда как человеческое мышление несколько поотстало. В конце концов в декабре 1992 года немецкая компьютерная программа под названием Fritz2 выиграла у чемпиона мира Гарри Каспарова несколько блицпартий. Согласно обычным правилам, каждому игроку предоставляется 2,5 часа на выполнение 40 ходов, и люди дольше удерживали превосходство. Команда специалистов, финансируемая компанией IBM, вложила немало усилий и ресурсов в разработку специализированного компьютера (получившего название Deep Blue) для игры в шахматы и соответствующего программного обеспечения. В феврале 1996 года Deep Blue выступил в роли противника Гарри Каспарова в матче из шести партий и произвел сенсацию, выиграв первую партию, но Каспаров быстро выявил его слабые места, улучшил контрстратегии и мастерски выиграл остальные партии. На протяжении следующих 15 месяцев команда IBM совершенствовала аппаратное и программное обеспечение компьютера, после чего в мае 1997 года модифицированный Deep Blue выиграл у Каспарова очередной матч из шести партий.

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

При обдумывании хода в шахматах крайне трудно (для обоих: и людей, и компьютеров) заранее предвидеть исход игры. Но как насчет того, чтобы просчитать часть ходов, скажем 5-10, вперед и проанализировать игру в обратном порядке из этой позиции? Игра необязательно должна закончиться в рамках этого ограниченного периода; иными словами, узлы, которых вы достигнете через 5-10 ходов, не будут концевыми. Однако в соответствии с правилами игры выигрыши указываются только для концевых узлов. Следовательно, необходим некий косвенный способ присвоения правдоподобных выигрышей неконцевым узлам, поскольку вы не можете проанализировать все дерево игры методом обратных рассуждений с самого конца. Правило, согласно которому присваиваются промежуточные выигрыши, называется функцией промежуточной оценки.

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

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

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

Именно на стадии миттельшпиля на первый план выходит искусство игры в шахматы. У лучших шахматистов развивается интуиция, которая позволяет им распознавать хорошие возможности и избегать скрытых ловушек на уровне, с которым компьютерным программам сложно конкурировать. Программисты обнаружили, что в большинстве случаев компьютеры трудно обучить тем навыкам распознавания образов, которые люди развивают и используют инстинктивно, – например, когда они узнают лица и связывают их с именами. Искусство ведения игры на стадии миттельшпиля в шахматах – это распознавание и оценка комбинаций столь же загадочным способом. Именно в этом состояло самое большое преимущество Каспарова перед Fritz2 или Deep Blue. Это также объясняет, почему компьютерные программы показывают более высокие результаты в игре с людьми в блицпартиях или партиях с ограниченным временем обдумывания ходов: человеку просто не хватает времени, чтобы применить свое искусство ведения игры на стадии миттельшпиля.

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