Программа научилась принимать правильное решение​ в покере

Обновлено 28/10/2021

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

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

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

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

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

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

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

Наконец мы подошли к результату, который получили авторы статьи в Science. Для некоторого достаточно малого ε авторы предъявили ε-равновесие Нэша (ε настолько мало, что человеческой жизни не хватит на проверку отличия ε-равновесия Нэша от равновесия Нэша. 

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

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