Согласно данным исследования, опубликованного на днях в журнале Science, ученые Университета Альберты разработали компьютерную программу, названную Цефей, оснащённую стратегией игры близкой к идеальной.

Статистический анализ программы показывает, что она абсолютно непобедима в долгосрочной перспективе.

По словам Майкла Боулинга, ученого Университета Альберты и соавтора исследования: «Эта программа не обязательно должна выигрывать каждую руку, но в долгосрочной перспективе она не может проигрывать: она будет играть либо в ноль, либо в плюс».

Решение такой игры, как покер – огромное достижение в области вычислительных технологий. Простые игры, как крестики-нолики, легко решаемы, и большинство людей понимают, как побеждать или играть вничью в крестики-нолики спустя несколько раундов. Другие игры, например, шахматы и шашки, которые предлагают тысячи возможных сценариев, намного сложнее. Тем не менее, даже такие игры не настолько сложны, как покер, ведь покер это игра с ограниченной информацией – вы не знаете карт вашего оппонента. «В шахматах и шашках вся информация находится перед вами», говорит Боулинг, «но в покере это не так. И так как информация ограниченна, разработка стратегии превращается в довольно сложную задачу.

Алгоритм работы нового бота довольно прост. Во время игры он ищет в своей базе данных предварительно рассчитанные ситуации и выбирает наиболее оптимальную линию розыгрыша. Создание самой базы данных, тем не менее, было далеко не простым занятием. «На этапе обучения программа начала с произвольной игры против самой себя», то есть «она не знала, что делает и просто следовала правилам игры», объясняет Майкл Йохансон, ученый из Университета Альберты и соавтор исследования. Пока компьютер играл против себя, он становился все умнее и обновлял свою стратегию.

Для принятия решения программа рассчитывала все возможные опции. Например, она могла подумать: «Что, если я сделаю рейз вместо того, чтобы сыграть произвольно, насколько больше или меньше дeнeг я выиграю?» Если она приходила к выводу, что во втором случае она будет проигрывать, она возвращалась к варианту рейза и рассчитывала, сколько дeнeг она может выиграть в этом случае. Эта сумма сохранялась как величина сожаления, которая рассчитывалась для каждого решения в каждой ситуации. Таким образом, в каждой раздаче программа выбирала то решение, максимальное сожаление которого минимально.  Постоянно обновляясь, Цефей, в конце концов, дошел до уровня, называемого «идеальной игрой».

Для этапа подготовки потребовалось 70 дней и 200 компьютеров, каждый из которых был снабжен 32 Гб оперативной памяти и 24 центральными процессорами.

Спустя 70 дней игра Цефея была практически идеальной. «Мы могли продолжить обучение, и он мог стать умнее», говорит Боулинг, «но мы остановились на этом этапе, так как уже не могли отличить игру от идеала». «Даже если мы потратим на обучение программы всю жизнь, она не стает от этого ценнее, и все это будет лишь новым академическим достижением и не более того».

Дальнейшее обучение Цефея не увеличило бы заметным образом успешность программы.

Цефей смог даже показать, что игрок, принимающий решение последним на постфлопе, имеет небольшое преимущество над вторым игроком, и это преимущество было оценено в 0,88 блайнда за сто рук.

11 лет покера

Майкл Боулинг входил в команду исследователей, которые  впервые начали разрабатывать похожую программу в 2003 году. Тогда, по его словам, создание программы, которая могла бы решить ХА игру в техасский холдем было самым последним, о чем они вообще могли подумать. Вместо этого они работали над созданием программы, которая могла бы побеждать самых лучших игроков лимитного покера для двух человек «самой простой разновидности покера». Тогда в 2008 их попытки увенчались успехом, и свет увидела программа «Полярис», которая еще год назад проигрывала профессиональным игрокам - Филу Лааку и Али Ислами. Но когда разработчики улучшили ее, он выиграла три из шести матчей и сыграла вничью в четвертом.

«Тогда мы добавили в программу возможность подстраиваться и эксплуатировать человеческие слабости», говорит Боулинг. В этом было ее отличие от Цефея, так как его главная цель – это оптимальная игра.

После того как Полярис смогла обыграть лучших игроков, Боулингу и его команде пришлось думать о том, что делать дальше. И они решили взяться за HU Limit Texas Hold'em. Кто-то сделал расчеты и сказал, что для того, чтобы просто сохранить этого решение, им потребуется четыре петабайта дискового пространства [4000000 гигабайт]. Боулинг решил было сдаваться, но другие исследователи настояли на покупке петабайтных дисков.

В конце концов, для решения игры не потребовалось четыре петабайта. "Мы кое-чему научились во время работы», говорит Боулинг, "это как взять все пики и черви и закачать их в базу как одномастные", поэтому финальный размер решения снизился до 520 терабайт. Исследователи выяснили, как сжимать базу данных таким образом, чтобы программа имела быстрый доступ к стратегии. «На самом деле было очень много технических моментов по части баланса», говорит Боулинг, «если бы игра была немного больше, и все происходило немного медленнее, мы, возможно, так и смогли бы осуществить это».

Теперь, когда исследователи решили HU Limit Texas Hold'em, они хотят начать работу над решением других видов покера, таких как безлимитный хедз-ап. Конечно, характер игры не представляет возможности для ее решения, однако можно создать программу, которая смогла бы обыгрывать лучших в мире игроков. То же самое касается и лимитного холдема с тремя игроками. Нет такой стратегии для игр более чем 2х человек, которая бы не была убыточной в случае, если два игрока объединятся против третьего. «Сговор противоречит природе конкурентных игр, но дать его определение довольно сложно», говорит Боулинг, «некоторые люди могут делать это, даже не осознавая». Тем не менее, испытывая Цефей против двух других компьютеров, против которых он выбирал хорошие стратегии, исследователи не могут быть уверенны, что эти стратегии были оптимальными.

Что касается 6max и других игр для более чем 2х человек, нельзя найти равновесие, но можно построить недоминируемую стратегию, однако на её расчеты потребуется очень много времени и ресурсов. Так что в настоящее время решение безлимитного холдема не представляется реальным. То же самое можно сказать и про ХАСнГ. Оптимальный пуш-фолд можно рассчитать довольно быстро, но если брать в расчет постфлоп, решение протсо нереально.

Сфера применения Цефея не ограничивается только покером. Исследователи уже думают над возможностью его применения для оптимизации правительственных и коммерческих стратегий безопасности, то есть сделать их «неэксплуатируемыми». Например, он мог бы составлять графики патрулей или контрольно-пропускных пунктов таким образом, чтобы помешать противнику эксплуатировать оборонительную стратегию. Программа также может помогать подстраивать наиболее оптимальное лечение для больных сахарным диабетом. В случае изменения их диеты или уровня активности, программа могла бы вычислять оптимальное решение в условиях неопределенности.

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