Специалисты по теории игр из Университета Альберты в Канаде создали программу, которая способна победить в покере любого человека. Речь идет о «слабом решении» задачи, которое оставляет только теоретическую возможность одолеть программу за такое время игры, которое существенно превосходит время жизни человека. Работа исследователей опубликована в Science, кратко о ней можно прочитать в редакционной статье журнала.

Решить задачу максимизации выигрыша удалось для самого распространённого вида покера — техасского холдема, в варианте игры один-на-один («хедзап») и лимитированными ставками. В холдеме каждому игроку раздается по две секретные карты («рука»), а еще пять карт являются открытыми и общими — каждый игрок может включать их в собственные комбинации. После раздачи «руки» игроки торгуются, повышая ставки на каждом раунде, или выходят из игры. Для данной комбинации правил существует 3,16 × 1017 элементарных состояний игры и 3,19 × 1014 точек, где игроку надо принимать решение.

Решить задачу математикам удалось за счет использования метода «минимизации сожаления». При этом каждому принятому решению в игре приписывается некий вес, который описывает ошибочность этого решения с точки зрения результата данной партии. Компьютеру требуется провести множество игр (принимая решения поначалу случайно), прежде чем удастся собрать достаточное количество оценок веса для этих решений. Объем этих данных настолько большой (262 терабайта), что авторам пришлось даже разработать специальный алгоритм их сжатия. Метод «минимизации сожаления» был известен с 2006 года, однако в новой работе ученые внесли в него несколько поправок — например, обеспечили ретроспективную переоценку весов.

Сложность решения задачи покера, равно как и ее практическая значимость, вытекает из того, что покер относится к играм с ограниченной информацией. В шахматах или шашках все игроки имеют полную информацию о текущем состоянии игры и ее истории. В покере (и в большинстве практических задач, например, в инвестировании и в медицине) известна только часть информации, на основании которой требуется принять решение. Такие игры считаются гораздо более трудными для анализа вычислительными методами. Авторы надеются, что новый алгоритм, получивший название CFR+, найдет применение и в других задачах при принятии решений с ограниченной информацией. Они уже начали разработку системы для работы с данными о диабете.