Теоретику удалось взломать популярную игру покер

Компьютер научился вводить определенную дозу блефа в свою игру.

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

Это серьезный шаг вперед, когда компьютерная программа может обыграть лучших игроков из людей, с тех пор как знаменитый компьютер Deep Blue от IBM обыграл Гарри Каспарова в 1997 году, который на тот момент был действующим чемпионом мира по шахматам. Программа для покера была разработана ученым Майклом Боулингом и его коллегами из Университета Альберты в Эдмонтоне, Канада, при помощи финского разработчика программного обеспечения Оскари Таммелина. Программа играет идеально. Что это означает?

Это означает, что отдельно взятый вариант покера (холдем HULHE) можно считать решенным. Алгоритм описан в статье в журнале Science.

Стратегия, которую вычислили авторы, настолько близка к совершенству, что "сделает бессмысленную дальнейшую работу над этой игрой", говорит Эрик Джексон, исследователь компьютерного покера в Менло-Парке в Калифорнии.

"Я думаю, это будет сюрпризом для экспертов. То, что эта игра так быстро разрешилась", — добавляет Джексон.

Ранее уже решались другие популярные игры. В 2007 году команда из того же отделения университета Альберты — в том числе и Нил Берч, соавтор последнего исследования — взломала шашки.

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

В покере основная сложность заключается в огромном количестве возможных путей развития, которые предлагает игра. Боулинг и его коллеги занимаются одной из самых популярных форм покера — техасский холдем (Texas hold’em). С двумя игроками игра становится типа "хедс-ап", когда любой проигрыш игрока — выигрыш оппонента, а также имеет фиксированный размер ставок и фиксированное число подъемов ставок (raise). Есть примерно 3,16 х 10^17 состояний, в которых может оказаться HULHE, и порядка 3,19 х 10^14 возможных точек, в которых игрок должен принять решение.

Боулинг и его коллеги разработали свой алгоритм, который должен был делать выводы на основе своего опыта, пока не достигнет чемпионского уровня (сыграв более 1500 игр). Сначала он принимает решения случайно, но затем подключает к каждому решению значение "сожаления", в зависимости от того, насколько плохим оно было.

Эта процедура, известная как контрфактуальная минимизация сожаления, была широко принята на ежегодном соревновании по компьютерному покеру Annual Computer Poker Competition, проводимому с 2006 года. Боулинг и его коллеги улучшили ее, позволив алгоритму по-новому оценивать решения, которые считались плохими в предыдущих тренировочных раундах.

Другим важным нововведением стало обращение огромного количества информации, которую нужно хранить, использовать и вырабатывать стратегию на ее основе — порядка 262 терабайт. Такой объем данных требует слишком много "места на диске". Ученые использовали метод сжатия, который уменьшил этот объем до 11 терабайт и добавили всего 5% времени, необходимого для расчетов операций.

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

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

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

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

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