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

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

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

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

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

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

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

Здесь I обозначает информационное состояние игрока. Каждое S_i является возможным полным состоянием партии. Игрок не знает, какое именно из них является настоящим, но знает, что некоторые состояния невозможны, поскольку противоречат уже увиденным картам или предыдущим действиям.

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

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

Здесь N_{возможных}(t) обозначает количество состояний, совместимых с информацией игрока после момента t. Каждый новый достоверно известный факт может только исключить некоторые варианты, но не создать заново уже невозможные состояния.

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

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

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

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

Здесь A является выбранным действием, p_i - вероятностью соответствующего будущего состояния, а V(S_i | A) - оценкой этого состояния после выполнения действия. Оптимальным в рамках такой модели будет действие, имеющее наибольшую ожидаемую ценность.

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

Предположим, что после раздачи у игрока отсутствует определённая карта, а эта карта ещё не была замечена на столе. Она может находиться у любого из других игроков или оставаться в колоде. Если затем один из противников использует карту того же достоинства, это изменяет вероятности расположения остальных неизвестных карт. Поэтому информация должна обновляться после каждого хода.

Начнём с простейшего случая, когда известно N неизвестных карт, из которых K принадлежат некоторому интересующему нас классу, например являются козырями определённой группы, а у рассматриваемого противника находится H карт. Если предположить, что все допустимые распределения неизвестных карт между игроками равновероятны, то вероятность того, что противник не имеет ни одной из этих K карт, определяется отношением количества способов выбрать его руку только из остальных N-K карт к общему количеству способов выбрать H карт из N.

Следовательно, точная вероятность наличия у противника хотя бы одной из интересующих нас карт равна единице минус вероятность полного отсутствия таких карт. Здесь используются биномиальные коэффициенты

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

Пусть H теперь обозначает не конкретную руку противника, а некоторую гипотезу о её составе, а E - всю наблюдаемую историю партии: уже вышедшие карты, последовательность атак и отбоев, решения игрока брать карты или продолжать защиту и другие достоверно известные события. Тогда нас интересует не первоначальная вероятность гипотезы P(H), а условная вероятность P(H|E). Она определяется формулой Байеса:

Здесь P(H) является исходной вероятностью рассматриваемой руки, P(E|H) показывает, насколько вероятно было бы наблюдать полученную историю, если бы у противника действительно находилась именно эта рука, а P(E) является полной вероятностью наблюдаемой истории. Следовательно, после каждого действия противника первоначальное распределение вероятностей может изменяться.

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

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

В полном виде задача определения вероятности конкретного события в руке противника поэтому сводится к суммированию апостериорных вероятностей всех совместимых рук. Если G обозначает событие "рука противника содержит хотя бы одну нужную карту", то:

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

Именно поэтому Дурак является игрой с неполной, а не просто случайной информацией. Случайность определяет начальное распределение карт и последующее появление карт из колоды, однако действия игроков изменяют доступную информацию и влияют на дальнейшее состояние игры.

Отдельной задачей является определение ценности карты. В обычном понимании можно считать туза более сильным, чем короля, короля более сильным, чем даму и так далее. Но для стратегического анализа этого недостаточно. Ценность карты зависит от её положения в текущей игре.

Вместо постоянной ценности следует рассматривать функцию:

Она показывает ценность карты c при конкретном состоянии S. Одна и та же карта может быть очень полезной в начале партии, почти бесполезной в середине и снова приобрести высокую ценность в конце. Например, карта может быть нужна для подкидывания, для безопасного отбоя или для сохранения определённого достоинства в руке.

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

Именно поэтому анализ руки как простой суммы «силы» отдельных карт даёт неправильные результаты. Необходимо учитывать комбинации и взаимное влияние карт.

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

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

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

Отсюда следует общий принцип: хороший ход определяется не только результатом текущего обмена картами, но и изменением вероятностей будущих состояний.

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