Компьютеры впервые выиграли в покер

Все фишки для игры в покер могут вскоре перейти к компьютерам. Новый алгоритм сделал первый большой шаг в понимании игры в покер — популярной карточной игры, в которую играют более 150 миллионов человек по всему миру, найдя решение в версии с двумя игроками, известной под названием лимитированный Техасский холдем.

Прошло почти два десятилетия с тех пор, как компьютер фирмы IBM под названием Deep Blue победил чемпиона мира по шахматам Гарри Каспарова. С этого потрясающего момента в 1997 году, компьютерные алгоритмы находили решения для игр, таких как «Четыре в ряд» и шашки, анализируя все возможные варианты игры, и выясняя идеальную стратегию для каждого хода, с самого начала каждой партии. В будущем программы смогут, возможно, даже освоить древнюю игру Го. Однако компьютеры сталкиваются с серьезной проблемой, играя в покер, из-за того, что каждый игрок имеет две скрытых карты, в которых содержится информация, неизвестная оппоненту. Найдя решение в «игре с неполной информацией», такой как покер, компьютерные алгоритмы также могли бы справляться с различными ситуациями в  реальном мире, содержащими аналогичные уровни неопределенности.

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

Берч с соавторами изложил реализацию своего алгоритма в статье, опубликованной 8 января 2014 в очередном номере журнала Science. В области компьютерных наук говорят, что это только «слабое» решение конкретной версии Техасского холдема, в которой участвует только два игрока, размеры ставок фиксированы и ставка повышается на фиксированное значение. Но, все равно, это очень хорошо, так как, со статистической точки зрения, практически невозможно отличить решение, полученное алгоритмом от реальной игры в покер. В статье описывается эксперимент, симулирующий 200 игр в покер, продолжительностью в 1 час по 12 часов ежедневно в течение 70 лет.

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

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

Но с помощью предыдущих версий алгоритма CFR никогда, в действительности, не пытались найти решение полной игры лимитированного Техасского холдема или каких-либо других версий игры в покер, потому что для этого требуется огромный объем памяти — около 262 терабайт!

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

Алгоритм CFR+ улучшает некоторые моменты предшествующих алгоритмов CFR. Первое изменение состоит в том, что улучшенный алгоритм использует несколько иной метод минимизации сожаления, чтобы выбрать наилучшую стратегию на каждом шаге. Другое изменение касается пропуска обычного шага усреднения последней стратегии по всем предыдущим стратегиям. Алгоритм использует только самую последнюю стратегию.

«Алгоритм переходит от трех шагов к двум шагам» — объясняет Берч. «Мы выбрасываем последний шаг.»

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

Эта эффективность позволила Берчу и его коллегам, попытаться найти решение полной игры в лимитированный Техасский холдем, а не только его упрощенного варианта. Применяя сжатие, они сократили требования к объему памяти до величины менее 11 терабайт для хранения гипотетических значений и всего 6 терабайт для вычисления основной стратегии. Они также распределили требуемую память на кластере, сотоящим из 200 вычислительных узлов и хранили значения на локальных дисках каждого узла. Каждый узел включал 24 2.1 ГГц ядра AMD, 32 Гб оперативной памяти и 1 ТБ локальный диск.

Расчет нового лучшего компьютернего решения для лимитированного Техасского холдема все еще занимает около 68,5 дней требуя аппаратное обеспечение, занимающее в пространстве объем нескольких холодильников. На самом деле, компьютерная техника было распределена на стойках в большом здании исследовательского университета, в общей сложности включая 1500 машин.

Близкая к идеальной стратегия «Цефей», найденная при помощи алгоритма CFR+ для лимитированного Техасского холдема, показала несколько тенденций и стратегий, которые могут представлять особый интерес для игроков в покер. Например, Цефей подтвердила общую покерную мудрость, что дилер имеет значительное преимущество в лимитированном Техасском холдеме. (Это не имеет значения в реальной игре, потому что игроки по очереди становятся дилером)

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

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

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

Сборная Канады надеется использовать алгоритм CFR+ алгоритм для нахождения решения в более сложных версиях покера с большим количеством игроков, или других аналогичных сложных играх. Похожий алгоритмический подход может оказаться полезным в приложениях теории игр для реального мира. Например, алгоритм может помочь разработать стратегии для служб безопасности, при распределении определенных ресурсов — может быть, использовать кинологов с собакой для обнаружения бомбы или патрульный катер береговой охраны в некоторых регионах в разное время дня чтобы не быть предсказуемым.

«Так же, как и в покере, вы должны блефовать, чтобы играть отлично» - говорит Берч, - «Если вы не блефуете, противник или злоумышленник может этим воспользоваться."

Поиграть в покер против алгоритма Цефей можно на сайте Университета Альберты.

Источник: IEEE Spectrum

[add_ratings]