Рис. 1. Игра хедз-ап (heads-up) в покер. За столом двое игроков и крупье, сдающий им карты. Фото с сайта pokernews.com

В начале 2015 года в журнале Science вышла статья, в которой было объявлено об успешном завершении работы компьютерной программы, просчитывавшей одну из версий покера — хедз-ап в лимитном техасском холдеме. Программа научилась принимать правильное решение в каждом из примерно 3,19×10¹⁴ возможных состояний игры. Найденная таким образом стратегия на длинной дистанции должна обыгрывать остальные стратегии. Одним из результатов анализа стало доказательство того, что дилер имеет преимущество перед вторым игроком. Авторы статьи предлагают ведущим профессиональным игрокам в покер опробовать стратегию на практике и убедиться в ее оптимальности.

Техасский холдем (texas hold'em) — самая популярная разновидность покера. Игра ведется стандартной колодой из 52 карт. В начале каждого розыгрыша игроки получают по 2 карты (карманные карты). Они смотрят на свои карты, после чего происходит первый раунд торговли. Игрока, который начинает торговлю, называют дилером (или игроком на кнопке, см. Button (poker)), после каждого розыгрыша дилером становится следущий по кругу игрок. Во время торговли игрок может повысить ставку (raise), уравнять ставку соперника (call) или отказаться от дальнейшего участия в розыгрыше и сбросить карты (fold). В итоге после раунда торговли каждый оставшийся в розыгрыше игрок поставил на кон одну и ту же сумму денег. Далее для всех открываются три общие карты (flop), после чего происходит второй раунд торговли. После этого открывается еще одна карта (turn), происходит третий раунд торговли. Наконец, открывается пятая общая карта (river), и происходит последний, четвертый раунд торговли. Если в какой-то момент в игре остается только один игрок, он забирает весь банк. Если после четвертого раунда торговли в игре остается более одного игрока, то они вскрывают свои карманные карты и сравнивают получившиеся 5-карточные комбинации, которые каждый может построить из личных и общих карт. Тот, у кого комбинация лучше, забирает банк.

Комбинации в покере Комбинация составляется из двух карманных карт, которые раздаются игрокам в начале игры, и пяти общих карт, которые выкладываются на стол в процессе игры. В комбинации участвуют пять карт из этих семи. Комбинации перечислены по убыванию старшинства. Роял-флеш (royal flush) — частный случай стрит-флэша, старший из всех возможных, состоит из 5 старших (туз, король, дама, валет, десять) карт одной масти. Стрит-флеш (straight flush) — любые пять карт одной масти по порядку. Каре (four of a kind) — четыре карты одного достоинства. Фул-хаус (full house) — тройка и пара. Флеш (flush) — пять карт одной масти. Стрит (straight) — пять карт по порядку любых мастей. Сет (three of a kind, set) — три карты одинакового достоинства. Две пары (two pairs) — две пары карт. Пара (pair) — две карты одного достоинства. Старшая карта (high card) — у игрока нет ни одной из перечисленных выше комбинаций.

Хедз-ап (heads up) означает, что играют только два игрока. Лимитный покер — это версия игры, в которой ставки можно повышать на фиксированную величину, причем повышать ставку можно не более чем заранее оговоренное число раз. Поэтому лимитный техасский холдем — это конечная игра. Последовательные игры в теории игр принято задавать с помощью деревьев. Вершинам дерева будут соответствовать различные состояния игры. Каждой вершине приписано имя игрока, которому в этой вершине принадлежит ход. Ребрам, исходящим из этой вершины, соответствуют действия, которые может совершить этот игрок. Одним из участников игры является «природа» — так в теории игр называют искусственного игрока, выполняющего роль генератора случайных чисел. «Природа» случайным образом решает, какую карту сдать игрокам или открыть на столе.

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

Любую конечную последовательную игру с совершенной информацией можно просчитать с конца, используя алгоритм обратной индукции. Рассмотрев одну подыгру самого последнего уровня (то есть такую подыгру, на которой после принятия любого решения игра заканчивается и игроки подсчитывают полученные платежи), можно найти оптимальное действие игрока, которому принадлежит ход на этой подыгре. Далее точно так же можно найти оптимальные действия игроков на всех подыграх последнего уровня. После этого, зная, как будут вести себя рациональные игроки на подыграх последнего уровня, можно перейти к анализу игр предпоследнего уровня, и так далее. Рано или поздно, точно получится добраться до подыгры, совпадающей со всей игрой, после чего можно найти в ней оптимальное действие игрока, которому принадлежит первый ход. Таким образом, будет найдено оптимальное поведение всех игроков в любой возможной ситуации и будет выяснено, чем заканчивается игра при правильных действиях всех игроков. Именно так в 2007 году были просчитаны шашки — оказалось, что при правильной игре обеих сторон в шашках партия обязательно закончится вничью (J. Schaeffer et al., 2007. Checkers is solved).

Покер меньше шашек по количеству возможных состояний игры. Однако покер, в отличие от шашек, является игрой с несовершенной информацией. Это делает невозможным прямое применение алгоритма обратной индукции: если игрок в какой-то момент не знает, в какой из вершин он находится, то он не сможет найти однозначно оптимальное решение. Тем не менее такую игру можно переписать в виде матрицы (нормальная форма игры): по горизонтали можно выписать все стратегии первого игрока, по вертикали — все стратегии второго игрока, после чего в полученной матрице можно найти равновесие Нэша. Теоретически. Здесь нас поджидает еще одна проблема: полученная матрица для покера будет очень большой. Сложность нахождения равновесия Нэша с помощью алгоритма линейного программирования растет экспоненциально при росте количества состояний игры, поэтому для сложных игр вроде покера метод неприменим. Приходится отказаться от идеи прямого сведения дерева к матрице. Вместо этого авторы используют специальную модификацию критерия Сэвиджа (см. Regret (decision theory)), предназначенную для решения игр с несовершенной информацией за линейное время от числа состояний игры. Алгоритм просматривает с конца информационные множества и приписывает им тот или иной штраф в зависимости от сыгранной стратегии. После этого алгоритм минимизирует набранный штраф.

Еще одна трудность в решении покера состояла в том, что в нем ожидаемые платежи игроков выражаются не обязательно целыми числами — сравните с шашками, в которых возможны всего 3 исхода! Поскольку речь идет о вычислении платежей компьютером, то авторам пришлось приближать бесконечные десятичные дроби с заданным уровнем точности ε. Но тогда нельзя использовать стандартное определение равновесия Нэша, ведь погрешность вычисления может помешать ответить на вопрос, выгодно ли кому-либо из игроков отклоняться от того или иного профиля игры. Авторы используют концепцию ε-равновесия Нэша, в соответствии с которой профиль стратегий называется ε-равновесием Нэша, если ни один из игроков, отклоняясь от этого профиля стратегий, не может увеличить свою полезность более чем на ε. В частности, любое равновесие Нэша является ε-равновесием Нэша.

Наконец мы подошли к результату, который получили авторы статьи в Science. Для некоторого достаточно малого ε авторы предъявили ε-равновесие Нэша (ε настолько мало, что человеческой жизни не хватит на проверку отличия ε-равновесия Нэша от равновесия Нэша). На рис. 2 приведены действия игроков на первом ходу в этом профиле стратегий. Слева для любой стартовой комбинации двух карт указаны первые действия дилера (зеленая клетка — «повышать», красная — «сброс»), справа приведен ответ второго игрока, если дилер на первом ходу повысил ставку (зеленый цвет — «повышать», синий — «уравнивать», красный — «сброс», смешанные цвета соответствуют возможности смешивать с различными вероятностями несколько своих стратегий). В этом профиле дилер очень часто блефует — повышает ставку с плохой картой, а второй игрок достаточно часто вынужден сбрасывать свою карту, не будучи в силах распознать, блефует ли дилер. За счет этого дилер на длинной дистанции обыгрывает второго игрока.

Рис. 2. Оптимальные действия игроков на первом ходу. Каждая клетка таблицы соответствует одному из 169 вариантов карманной пары: в каждой масти 13 карт, при этом в покере конкретная масть не важна, а важно лишь, одной ли масти карманные карты (это увеличивает шансы на составление флеша); одномастным парам соответствуют клетки над главной диагональю (идущей из левого верхнего угла в правый нижний) таблицы (Suited), разномастным — клетки под этой диагональю. Цветами обозначены действия игроков: красный — сбросить карты, синий — уравнять ставку, зеленый — поднять ставку; смешанные цвета соответствуют сложным вариантам, при которых игрок может с некоторыми вероятностями принимать разные решения. Слева — первый ход первого игрока, справа — ответный ход его оппонента в том случае, если первый игрок поднял ставку. Рисунок из обсуждаемой статьи в Science

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

Можно ли заработать, играя найденную стратегию? Да, если уметь воспроизводить действия, которые предписывает совершать стратегия в каждой позиции. Вряд ли на это будет способен человек — не хватит памяти. А вот против компьютера играть в лимитный хедз-ап теперь бесполезно. Скорее всего, это означает, что скоро лимитный хедз-ап покер пропадет с покерных сайтов — будет очень сложно проверять, что человек не использует специальные программы, помогающие найти оптимальные ответы. Однако игрокам в покер расстраиваться рано. Даже если про все вариации лимитного покера однажды всё станет известно, останется безлимитный покер (можно делать ставки любого размера), который не является конечной игрой. Из-за этого решить безлимитный покер модификациями алгоритма обратной индукции уже вряд ли получится…

Источник: M. Bowling, N. Burch, M. Johanson and O. Tammelin. Heads-up limit hold’em poker is solved // Science. 2015. V. 347. P. 145–149.

См. также:
А. В. Захаров «Теория игр в общественных науках» — хороший учебник по теории игр.

Дмитрий Дагаев
«Элементы»