Стратегические игры. Доступный учебник по теории игр
Шрифт:
Анализ методом обратных рассуждений дерева игры на рис. 3.6 , а также стрелки в узлах d, e, f и g показывают, что оптимальная стратегия Талии – НВВН.
Теперь выводы нашего анализа методом обратных рассуждений можно представить в виде описания стратегического выбора, сделанного каждой участницей игры: Эмили выберет Н из двух имеющихся у нее стратегий, Нина – НВ из четырех доступных стратегий, а Талия – НВВН из шестнадцати стратегий. Когда каждая из участниц анализирует следующие ветви и узлы дерева игры, чтобы составить прогноз конечных результатов текущих действий, она вычисляет оптимальные стратегии других участниц игры. Эта конфигурация стратегий (Н в случае Эмили, НВ – Нины и НВВН – Талии) представляет собой равновесие в данной игре, полученное методом обратных рассуждений.
Мы
В итоге мы имеем три разные концепции:
1. Список доступных стратегий для каждого игрока, который, особенно для игроков, вступающих в игру на более поздних этапах, может быть очень длинным, поскольку необходимо перечислить их действия в ситуациях, соответствующих всем возможным предыдущим ходам других игроков.
2. Оптимальная стратегия, или исчерпывающий план действий, для каждого игрока. Эта стратегия должна описывать лучший выбор игрока в каждом узле, в котором, согласно правилам игры, игрок делает ход, даже если многие из этих узлов так и не будут достигнуты на фактическом пути игры. По сути, такое описание – это прогноз игроков, сделавших предыдущие ходы, относительно того, что бы произошло, если бы они предприняли другие действия, а значит, оно представляет собой важную часть определения их наилучших действий в предыдущих узлах. Совокупность оптимальных стратегий всех игроков образует равновесие обратных рассуждений.
3. Фактический путь игры в равновесии обратных рассуждений, найденный посредством объединения оптимальных стратегий всех игроков.
4. Преимущества порядка
В равновесии обратных рассуждений в игре «уличный сад» Эмили получает наилучший исход (выигрыш 4) благодаря возможности сделать первый ход. Решив не вносить вклад в создание сада, Эмили перекладывает бремя ответственности на двух других участниц игры, каждая из которых может получить следующий лучший исход только при условии, что обе выберут вариант «внести вклад». Большинство людей, не имеющих опыта ведения стратегических игр, придерживаются мнения, будто преимущество первого хода должно присутствовать во всех играх. Однако это не так. Во многих играх второй ход более выигрышный. Представьте себе стратегическое взаимодействие между двумя компаниями, продающими аналогичные товары по каталогам, скажем, Land’s End и L.L. Bean. Если бы одна из них выпустила каталог первой, вторая еще до выпуска своего каталога обрела бы шанс узнать, какие цены установила первая компания, и смогла бы предложить на свои товары более низкие цены, получив в результате огромное конкурентное преимущество.
Преимущество первого хода зависит от способности игрока взять на себя обязательство в связи с выгодной позицией и вынудить других игроков приспосабливаться к нему; преимущество второго хода обусловлено гибкостью адаптации игрока, делающего ход вторым, к выбору других игроков. Что важнее в той или иной игре, обязательство или гибкость, определяется ее конкретной конфигурацией стратегий и выигрышей; общего правила здесь нет. На протяжении всей книги мы будем встречать примеры преимуществ обоих типов. Основная мысль (противоречащая общепринятому мнению) состоит в том, что преимущество не всегда получает игрок, который ходит первым. И она настолько важна, что мы сочли необходимым подчеркнуть ее с самого начала.
Когда в игре есть преимущество первого или второго хода, каждый игрок может попытаться манипулировать порядком игры, чтобы обеспечить себе выгодную позицию. Тактические приемы такой манипуляции – это стратегические ходы, которые мы рассмотрим в главе 9 .
5. Увеличение
В разделе 3 мы говорили о том, что увеличение количества игроков усложняет анализ игр с последовательными ходами. В данном разделе мы рассмотрим еще один тип сложности, возникающий в результате добавления в игру дополнительных ходов. Самый простой способ сделать это в игре с двумя участниками – разрешить им чередовать ходы более одного раза. В итоге дерево игры разрастается таким же образом, как и дерево игры со многими участниками, но последующие ходы делают те же игроки, что и на более ранних этапах игры.
Многие широко распространенные игры, такие как крестики-нолики, шашки и шахматы, и есть стратегические игры с двумя участниками и чередующимися последовательными ходами. Использование дерева игры и анализа методом обратных рассуждений теоретически позволяет их «решить», то есть определить равновесный исход игры методом обратных рассуждений, а также равновесные стратегии, обеспечивающие такой исход. К сожалению, по мере того как игра усложняется, а стратегии становятся все запутаннее, поиск оптимальной стратегии тоже затрудняется. В таких случаях на помощь приходят стандартные компьютерные программы вроде упомянутой в главе 2 Gambit.
Начнем с игры в крестики-нолики, самой простой из вышеупомянутых, и рассмотрим ее более легкий вариант, в котором каждый из двух игроков (Х и 0) пытается первым заполнить двумя своими символами любой столбец, ряд или диагональ в игре на поле два на два. У первого игрока четыре возможных действия или позиции, в которых он может поставить крестик. Второй игрок имеет три возможных действия в каждом из четырех узлов принятия решений. Когда первый игрок получает право сделать второй ход, у него есть два варианта действия в каждом из 12 (4 x 3) узлов принятия решений. Как показано на рис. 3.7, даже у этой мини-игры в крестики-нолики очень сложное дерево игры. Хотя на самом деле оно не такое уж сложное, поскольку игра гарантированно закончится, после того как первый игрок сделает второй ход. Тем не менее на этом дереве 24 концевых узла, и их необходимо проанализировать.
.
Рис. 3.7. Сложное дерево простой игры в крестики-нолики на поле два на два
Это дерево служит здесь иллюстрацией того, насколько сложным может быть дерево даже в случае простых (или упрощенных) игр. Как оказалось, применение метода обратных рассуждений к анализу мини-игры в крестики-нолики позволяет быстро найти равновесие. Из такого анализа следует, что любой выбор первого игрока на втором ходе приводит к одному и тому же исходу игры. Здесь нет оптимального действия; любой ход так же хорош, как и остальные. Стало быть, когда второй игрок делает первый ход, он тоже видит, что любой возможный ход даст тот же результат, поэтому может с одинаковым успехом выбрать любой из трех вариантов в каждом из четырех узлов принятия решений. И наконец, то же самое верно и для первого игрока, делающего первый ход: любой вариант выбора равноценен остальным вариантам, а значит, он гарантированно победит в игре.
Хотя у этой версии игры в крестики-нолики весьма занимательное дерево, ее решение не представляет особого интереса. Первый игрок всегда выигрывает, поэтому выбор, сделанный обоими игроками, никак не влияет на конечный результат. Многим из нас больше знакома версия «три на три» игры в крестики-нолики. Для того чтобы проиллюстрировать ее деревом игры, нам пришлось бы показать, что первый игрок имеет девять возможных действий в начальном узле, у второго игрока восемь вариантов действий в каждом из девяти узлов принятия решения. На втором ходе у первого игрока семь возможных действий в каждом из 8 x 9 = 72 узлов, тогда как у второго игрока на втором ходе – шесть возможных действий в каждом из 7 x 8 x 9 = 504 узлов. Эта закономерность продолжается до тех пор, пока дерево не прекратит стремительно разрастаться, поскольку определенные комбинации ходов приводят к победе первого игрока, после чего игра заканчивается. Однако минимум до пятого хода победа невозможна. Для того чтобы нарисовать полное дерево этой игры, понадобится огромный лист бумаги или очень мелкий почерк.