Программа научилась принимать правильное решение в каждом из примерно 3,19×1014 возможных состояний игры. Найденная таким образом стратегия на длинной дистанции должна обыгрывать остальные стратегии.
Одним из результатов анализа стало доказательство того, что дилер имеет преимущество перед вторым игроком. Авторы статьи предлагают ведущим профессиональным игрокам в покер опробовать стратегию на практике и убедиться в ее оптимальности.
Хедз-ап (heads up) означает, что играют только два игрока. Лимитный покер — это версия игры, в которой ставки можно повышать на фиксированную величину, причем повышать ставку можно не более чем заранее оговоренное число раз. Поэтому лимитный техасский холдем — это конечная игра. Последовательные игры в теории игр принято задавать с помощью деревьев. Вершинам дерева будут соответствовать различные состояния игры. Каждой вершине приписано имя игрока, которому в этой вершине принадлежит ход. Ребрам, исходящим из этой вершины, соответствуют действия, которые может совершить этот игрок. Одним из участников игры является «природа» — так в теории игр называют искусственного игрока, выполняющего роль генератора случайных чисел. «Природа» случайным образом решает, какую карту сдать игрокам или открыть на столе.
Последовательные игры можно разделить на два вида: игры с совершенной информацией (см. Perfect information) и игры с несовершенной информацией. В играх с совершенной информацией каждый игрок всегда знает, в какой вершине дерева он находится и что происходило до этого. В играх с несовершенной информацией игрок может быть не уверен в том, в каком состоянии находится игра. Покер — пример игры с несовершенной информацией: игрок, не знает, какие карты находятся на руках у его соперника. Каждый может наблюдать общие карты и совершаемые действия в момент торговли, однако карты соперника в момент торговли известны не будут.
Любую конечную последовательную игру с совершенной информацией можно просчитать с конца, используя алгоритм обратной индукции. Рассмотрев одну подыгру самого последнего уровня (то есть такую подыгру, на которой после принятия любого решения игра заканчивается и игроки подсчитывают полученные платежи), можно найти оптимальное действие игрока, которому принадлежит ход на этой подыгре. Далее точно так же можно найти оптимальные действия игроков на всех подыграх последнего уровня. После этого, зная, как будут вести себя рациональные игроки на подыграх последнего уровня, можно перейти к анализу игр предпоследнего уровня, и так далее. Рано или поздно, точно получится добраться до подыгры, совпадающей со всей игрой, после чего можно найти в ней оптимальное действие игрока, которому принадлежит первый ход. Таким образом, будет найдено оптимальное поведение всех игроков в любой возможной ситуации и будет выяснено, чем заканчивается игра при правильных действиях всех игроков. Именно так в 2007 году были просчитаны шашки — оказалось, что при правильной игре обеих сторон в шашках партия обязательно закончится вничью (J. Schaeffer et al., 2007. Checkers is solved).
Покер меньше шашек по количеству возможных состояний игры. Однако покер, в отличие от шашек, является игрой с несовершенной информацией. Это делает невозможным прямое применение алгоритма обратной индукции: если игрок в какой-то момент не знает, в какой из вершин он находится, то он не сможет найти однозначно оптимальное решение. Тем не менее такую игру можно переписать в виде матрицы (нормальная форма игры): по горизонтали можно выписать все стратегии первого игрока, по вертикали — все стратегии второго игрока, после чего в полученной матрице можно найти равновесие Нэша. Теоретически. Здесь нас поджидает еще одна проблема: полученная матрица для покера будет очень большой. Сложность нахождения равновесия Нэша с помощью алгоритма линейного программирования растет экспоненциально при росте количества состояний игры, поэтому для сложных игр вроде покера метод неприменим. Приходится отказаться от идеи прямого сведения дерева к матрице. Вместо этого авторы используют специальную модификацию критерия Сэвиджа (см. Regret (decision theory)), предназначенную для решения игр с несовершенной информацией за линейное время от числа состояний игры. Алгоритм просматривает с конца информационные множества и приписывает им тот или иной штраф в зависимости от сыгранной стратегии. После этого алгоритм минимизирует набранный штраф.
Еще одна трудность в решении покера состояла в том, что в нем ожидаемые платежи игроков выражаются не обязательно целыми числами — сравните с шашками, в которых возможны всего 3 исхода! Поскольку речь идет о вычислении платежей компьютером, то авторам пришлось приближать бесконечные десятичные дроби с заданным уровнем точности ε. Но тогда нельзя использовать стандартное определение равновесия Нэша, ведь погрешность вычисления может помешать ответить на вопрос, выгодно ли кому-либо из игроков отклоняться от того или иного профиля игры. Авторы используют концепцию ε-равновесия Нэша, в соответствии с которой профиль стратегий называется ε-равновесием Нэша, если ни один из игроков, отклоняясь от этого профиля стратегий, не может увеличить свою полезность более чем на ε. В частности, любое равновесие Нэша является ε-равновесием Нэша.
Наконец мы подошли к результату, который получили авторы статьи в Science. Для некоторого достаточно малого ε авторы предъявили ε-равновесие Нэша (ε настолько мало, что человеческой жизни не хватит на проверку отличия ε-равновесия Нэша от равновесия Нэша). На рис. 2 приведены действия игроков на первом ходу в этом профиле стратегий. Слева для любой стартовой комбинации двух карт указаны первые действия дилера (зеленая клетка — «повышать», красная — «сброс»), справа приведен ответ второго игрока, если дилер на первом ходу повысил ставку (зеленый цвет — «повышать», синий — «уравнивать», красный — «сброс», смешанные цвета соответствуют возможности смешивать с различными вероятностями несколько своих стратегий). В этом профиле дилер очень часто блефует — повышает ставку с плохой картой, а второй игрок достаточно часто вынужден сбрасывать свою карту, не будучи в силах распознать, блефует ли дилер. За счет этого дилер на длинной дистанции обыгрывает второго игрока.
