Карточные игры
Карточные игры интересны не только тем, что они часто бывают связаны с денежными ставками, но и по многим другим причинам. Количество различных вариантов карточных игр чрезвычайно велико, но в данной главе мы сосредоточимся на таких вариантах, в которых карты тасуют случайным образом в начале игры и каждый игрок получает на руки карты, которые он не показывает другим игрокам. К таким играм относятся бридж, вист, "Червы" и некоторые виды покера.
На первый взгляд может показаться, что карточные игры полностью аналогичны играм с жеребьевкой: раздача карт происходит случайным образом, а сами карты определяют, какие ходы могут быть сделаны каждым игроком. Однако в картах вся жеребьевка происходит с самого начала! Это замечание будет обсуждаться ниже более подробно и будет показано, что такая особенность рассматриваемых карточных игр весьма полезна на практике. Вместе с тем, это замечание одновременно является совершенно неправильным по очень интересным причинам.
Представьте себе, что два игрока, МАХ и MIN, разыгрывают какую-то реальную раздачу по четыре карты в бридже с двумя игроками, в котором открыты все карты. На руках находятся следующие карты, и игрок МАХ должен ходить первым:
MAX: V б ? б * 9 8 MIN: V 4 А 2 * 10 5
Предположим, что игрок МАХ ходит с карты * 9. Теперь должен ходить игрок MIN, который может выбросить карту * 10 или * 5. Игрок MIN кладет карту * 10 и забирает взятку. Затем очередь хода переходит к игроку MIN, который ходит картой А 2. У игрока МАХ масти пика нет (и поэтому он не может забрать эту взятку), следовательно, он обязан выбросить какую-то другую карту. Очевидным вариантом является карта ? 6, поскольку две другие оставшиеся карты являются старшими. Теперь, какой бы картой не ходил игрок MIN во время следующего розыгрыша, игрок МАХ возьмет две оставшиеся взятки и игра окончится ничьей, при двух взятках у каждого игрока. С использованием подходящего варианта минимаксного поиска (см. упр. 6.12) можно легко показать, что фактически ход картой * 9, сделанный игроком МАХ, был оптимальным.
Теперь заменим карты на руках игрока MIN и вместо карты v 4 введем карту ? 4:
MAX: V б ? б * 9 8 MIN: ? 4 А 2 * 10 5
Рассматриваемые два случая являются полностью симметричными: ход игры будет одинаковым, за исключением того, что при розыгрыше второй взятки игрок МАХ выбросит карту v 6. Игра снова окончится ничьей при двух взятках у каждого игрока, и ход картой * 9 является оптимальным.
До сих пор все шло хорошо. А теперь скроем одну из карт игрока MIN и допустим, что игрок МАХ знает, что у игрока MIN на руках либо первая раздача (с картой v 4), либо вторая раздача (с картой ? 4), но он не знает, какая именно из них. Игрок МАХ рассуждает следующим образом.
Ход картой * 9 является оптимальным решением в игре против первой и второй раздачи на руках игрока MIN, поэтому теперь этот ход должен быть оптимальным, поскольку известно, что на руках у игрока МШ имеется один из этих двух вариантов раздачи.
На более обобщенном уровне можно сказать, что игрок МАХ использует подход, который может быть назван "усреднением по прогнозам". Идея его состоит в том, чтобы при наличии карт на руках у противника, которые не видны игроку, оценивать каждый возможный вариант действий, вначале вычисляя минимаксное значение этого действия применительно к каждой возможной раздаче карт, а затем вычисляя ожидаемое значение по всем раздачам с использованием вероятности каждой раздачи.
Если читатель посчитает такой подход разумным (или если он не может судить о нем, поскольку не знаком с бриджем), то ему следует поразмыслить над приведенным ниже рассказом.
Первый день. Дорога А ведет к куче золотых слитков; дорога в ведет к развилке. Если вы от развилки пойдете налево, то найдете гору драгоценностей, а если пойдете направо, то попадете под автобус.
Второй день. Дорога А ведет к куче золотых слитков; дорога В ведет к развилке. Если вы от развилки пойдете направо, то найдете гору драгоценностей, а если пойдете налево, то попадете под автобус.
Третий день. Дорога А ведет к куче золотых слитков; дорога в ведет к развилке. Если вы от развилки выберете правильное направление, то найдете гору драгоценностей, а если неправильное, то попадете под автобус.
Очевидно, что в первые два дня решение выбрать дорогу В не лишено смысла, но в третий день ни один человек в здравом уме не выберет дорогу В. Однако именно такой вариант подсказывает метод усреднения по прогнозам: дорога В является оптимальной в ситуациях, возникающих в первый и второй дни, поэтому она оптимальна и в третий день, поскольку должна иметь место одна из двух предыдущих ситуаций. Вернемся к карточной игре: после того как игрок МАХ пойдет картой * 9, игрок MIN заберет взятку картой * 10. Как и прежде, MIN пойдет с карты А 2, но теперь игрок МАХ окажется перед развилкой на дороге без каких-либо указаний. Если игрок МАХ выбросит карту v 6, а у игрока MIN все еще будет оставаться карта v 4, то эта карта у 4 станет козырной и игрок МАХ проиграет игру. Аналогичным образом, если игрок МАХ выбросит карту ? 6, а у игрока MIN все еще будет оставаться карта ? 4, игрок МАХ также проиграет. Поэтому игра с первым ходом картой * 9 ведет к ситуации, в которой игрок МАХ имеет 50%-ную вероятность проигрыша. (Для него было бы гораздо лучше вначале сыграть картами v 6 и ? 6, гарантируя для себя ничейную игру.)
Из всего этого можно извлечь урок, что при недостатке информации игрок должен учитывать, какую информацию он будет иметь в каждый момент игры. Недостаток алгоритма, применяемого игроком МАХ, состоит в том, что в нем предполагается, будто при каждой возможной раздаче игра будет развиваться так, как если бы все карты оставались видимыми. Как показывает данный пример, это вынуждает игрока МАХ действовать таким образом, как будто неопределенность разрешится, когда настанет время. Кроме того, в алгоритме игрока МАХ никогда не принимается решение, что нужно собирать информацию (или предоставлять информацию партнеру), поскольку этого не требуется делать в рамках каждой отдельной раздачи; тем не менее в таких играх, как бридж, часто бывает целесообразно сыграть такой картой, которая помогла бы кое-что узнать о картах противника или сообщить партнеру о своих собственных картах. Такие стереотипы поведения формируются автоматически оптимальным алгоритмом ведения игр с неполной информацией. Подобный алгоритм выполняет поиск не в пространстве состояний мира (под этим подразумеваются карты, находящиеся на руках у игроков), а в пространстве доверительных состояний (представлений о том, кто какие карты имеет и с какими вероятностями). Авторы смогут объяснить этот алгоритм должным образом в главе 17 после разработки всего необходимого вероятностного инструментария. А в данной главе необходимо также остановиться на одном заключительном и очень важном замечании: в играх, с неполной информацией лучше всего выдавать противнику как можно меньше информации, а наилучший способ сделать это чаще всего состоит в том, чтобы действовать непредсказуемо. Вот почему санитарные врачи, посещая для проверки предприятия общественного питания, не сообщают заранее о своих визитах.