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

3. Фактический путь игры в равновесии обратных рассуждений, найденный посредством объединения оптимальных стратегий всех игроков.

В равновесии обратных рассуждений в игре «уличный сад» Эмили получает наилучший исход (выигрыш 4) благодаря возможности сделать первый ход. Решив не вносить вклад в создание сада, Эмили перекладывает бремя ответственности на двух других участниц игры, каждая из которых может получить следующий лучший исход только при условии, что обе выберут вариант «внести вклад». Большинство людей, не имеющих опыта ведения стратегических игр, придерживаются мнения, будто преимущество первого хода должно присутствовать во всех играх. Однако это не так. Во многих играх второй ход более выигрышный. Представьте себе стратегическое взаимодействие между двумя компаниями, продающими аналогичные товары по каталогам, скажем, Land’s End и L.L. Bean. Если бы одна из них выпустила каталог первой, вторая еще до выпуска своего каталога обрела бы шанс узнать, какие цены установила первая компания, и смогла бы предложить на свои товары более низкие цены, получив в результате огромное конкурентное преимущество.

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

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

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

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

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

.

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

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

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

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

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