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

• Название: Стратегические игры. Доступный учебник по теории игр
• Автор: Авинаш Диксит
• Жанр: Прочая научная литература
• Год: 2017
• ISBN: 978-5-00100-813-2

Доступный учебник по теории игр, который завоевал заслуженную популярность благодаря наглядным примерам и упражнениям, а также доступному изложению, не требующему от читателей серьезной математической подготовки.

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

На русском языке публикуется впервые.

---

5. Увеличение количества ходов

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

Многие широко распространенные игры, такие как крестики-нолики, шашки и шахматы, и есть стратегические игры с двумя участниками и чередующимися последовательными ходами. Использование дерева игры и анализа методом обратных рассуждений теоретически позволяет их «решить», то есть определить равновесный исход игры методом обратных рассуждений, а также равновесные стратегии, обеспечивающие такой исход. К сожалению, по мере того как игра усложняется, а стратегии становятся все запутаннее, поиск оптимальной стратегии тоже затрудняется. В таких случаях на помощь приходят стандартные компьютерные программы вроде упомянутой в главе 2 Gambit.

А. Крестики-нолики

Начнем с игры в крестики-нолики, самой простой из вышеупомянутых, и рассмотрим ее более легкий вариант, в котором каждый из двух игроков (Х и 0) пытается первым заполнить двумя своими символами любой столбец, ряд или диагональ в игре на поле два на два. У первого игрока четыре возможных действия или позиции, в которых он может поставить крестик. Второй игрок имеет три возможных действия в каждом из четырех узлов принятия решений. Когда первый игрок получает право сделать второй ход, у него есть два варианта действия в каждом из 12 (4 × 3) узлов принятия решений. Как показано на рис. 3.7, даже у этой мини-игры в крестики-нолики очень сложное дерево игры. Хотя на самом деле оно не такое уж сложное, поскольку игра гарантированно закончится, после того как первый игрок сделает второй ход. Тем не менее на этом дереве 24 концевых узла, и их необходимо проанализировать.

.

Рис. 3.7. Сложное дерево простой игры в крестики-нолики на поле два на два

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

Хотя у этой версии игры в крестики-нолики весьма занимательное дерево, ее решение не представляет особого интереса. Первый игрок всегда выигрывает, поэтому выбор, сделанный обоими игроками, никак не влияет на конечный результат. Многим из нас больше знакома версия «три на три» игры в крестики-нолики. Для того чтобы проиллюстрировать ее деревом игры, нам пришлось бы показать, что первый игрок имеет девять возможных действий в начальном узле, у второго игрока восемь вариантов действий в каждом из девяти узлов принятия решения. На втором ходе у первого игрока семь возможных действий в каждом из 8 × 9 = 72 узлов, тогда как у второго игрока на втором ходе – шесть возможных действий в каждом из 7 × 8 × 9 = 504 узлов. Эта закономерность продолжается до тех пор, пока дерево не прекратит стремительно разрастаться, поскольку определенные комбинации ходов приводят к победе первого игрока, после чего игра заканчивается. Однако минимум до пятого хода победа невозможна. Для того чтобы нарисовать полное дерево этой игры, понадобится огромный лист бумаги или очень мелкий почерк.

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

Б. Шахматы

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

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

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

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

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

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