Статистическая победа

Напомним, что 8 мая 2015 года в казино Rivers в Питтсбурге «статистической ничьей» завершился марафонский матч по дубликатному покеру между командой во главе с Дугласом Полком и ботом Клодико, разработанным в университете Карнеги – Меллон. Прошло чуть больше полутора лет, и новый бот, сконструированный в том же университете, убедительно разгромил новую четвёрку мастеров хэдз-апа, пусть и ослабленную отсутствием в её рядах главных забойщиков первого матча Бьорна Ли и Дага Полка.

Над алгоритмами Либратуса работали профессор Туомас Сандхольм и его аспирант Ноам Браун. По оценке Николая Яковенко (чьей статьёй мы беззастенчиво пользовались при работе над новостью – в авторе удачно сочетается компетентность и в покере, и в программировании), Сандхольм входит в топ-5 специалистов по искусственному интеллекту. Соперниками машины выступили Джейсон «PremiumWhey» Лес, Донг «Donger Kim» Ким, Джимми «ForTheSwaRm» Чоу и Даниэль «dougiedan678» МакОлэй. По мнению Дага Полка, все они входят в топ-10 или топ-15 сильнейших игроков в безлимитный холдем один на один в мире.

Матч игрался по дубликатному холдему (игроков делили на пары, расклады против компьютера внутри каждой пары были зеркальными). Каждый из четырёх человек играл по 30,000 раздач. Все раздачи начинались со стеком 20,000 при блайндах 50/100, фишки в олл-инах делились по эквити. Общий призовой фонд для игроков составил $200,000, которые делились в зависимости от результата – люди получали какие-то деньги в любом случае, но стараться было выгодно.

Матч начался 11 января. Бот моментально захватил лидерство и после нескольких тысяч сыгранных раздач вёл с винрейтом 25 бб/100. Первый же день матча показал, что Либратус играет намного сильнее своего предшественника Клодико. По мнению разработчика Клодико Сэма Ганцфрида, программисты смогли решить главные проблемы предыдущего бота – неумение учитывать влияние мёртвых карт (card removal) и слабую игру против необычных сайзингов.

Примерно в этот момент Яковенко сделал удивительно точный прогноз, предположив, что игроки, чьей главной силой является умение быстро приспосабливаться к любому сопернику, сумеют выправить положение и значительно сократить разрыв, но из-за утомления не смогут поддерживать идеальную форму и проиграют матч с лузрейтом в районе -15 бб/100.

Именно так всё и было. После шести дней борьбы люди уступали всего 2 бб/100, но в следующие две недели выигрывал только Либратус.

Итог матча: бот выиграл 1,766,250 фишек – почти 90 стеков – с винрейтом 14.7 бб/100. Винрейт, в пределах которого матч могли признать ничейным, составлял от -4 до 4 бб/100.

Как и в первом поединке, хуже всех сыграл Джейсон Лес, проигравший половину всех фишек. Донг Ким, закончивший первый матч в небольшой плюс, на этот раз остался в небольшом минусе. Дебютанты противостояния с компьютером Даниэль МакОлэй и Джимми Чоу не смогли удачно заменить Дага Полка и Бьорна Ли. Возможно, в идеальном составе человеческая команда могла помечтать о статистической ничьей, но это слабое утешение. Как показывает опыт шахмат и го, периоды, когда человек сражается с компьютером на равных, длятся недолго и быстро сменяются полной доминацией искусственного интеллекта.

Покерные программы высокого уровня ищут равновесные стратегии по Нэшу. В игре, для которой программировался Либратус, количество возможных вариантов составляет 10 в 165-й степени, но таким гигантским это число делает в первую очередь разнообразие возможных размеров ставки – от минимальной ставки до олл-ина на каждой улице, и каждая последовательность является уникальной и должна учитываться отдельно.

Расчёты можно значительно упростить, введя ограничения по сайзингам. Ранее покерные программисты шли ещё дальше, не рассматривая каждую комбинацию карманных карт как уникальную, а группируя их по схожим признакам. Либратус, однако, последнего упрощения не признавал – для него каждая комбинация карманных карт была уникальной, что позволяло использовать в стратегии эффект мёртвых карт. Но ограничение по рассчитываемым сайзингам было необходимым и для него. Именно поэтому во второй половине матча, потеряв надежду выиграть «нормальным способом», игроки перешли на отчаянные меры, пытаясь опенрэйзами в 6 бб и прочими диковинными приёмами отыскать слабое место в броне Либратуса. Однако это привело лишь к росту разрыва в уровне игры между людьми и машиной и более крупному поражению сборной команды.

Для игры на префлопе и флопе Либратус использовал заранее рассчитанную на суперкомпьютере базовую стратегию, однако на тёрне и ривере программа подключала второй модуль – солвер, рассчитывавший равновесные стратегии. Конечно, расчёт всех возможных линий и сайзингов с нахождением математически точного баланса для тёрна и ривера делал бы невозможной игру в реальном времени, но программисты нашли решение. Оказалось, чтобы приблизиться к правильному ответу, достаточно посчитать 50-100 случайных действий сторон. Либратус использовал минимизацию гипотетических потерь методом Монте-Карло (Monte Carlo Counterfactual Regret Minimization), чтобы приблизиться к неэксплуатируемой стратегии. (Подробности методов можно найти в научной статье, вышедшей сразу после окончания матча.) Вычислительные мощности предоставлял питтсбургский суперкомьютер. Во время матча боту требовалось около 20 секунд для большинства решений на тёрне. По словам Ноама Брауна, программа могла бы работать быстрее, если бы использовала мощности датацентра Google.

Во второй половине матча игроки обнаружили, что программа внезапно изменила поведение на префлопе – вместо минирэйзов и лимпов перешла к рэйзам 2.5х и фолдам. Изменилась и её игра на постфлопе, правда, эти изменения формализовать было сложнее. Удачные подстройки к стратегии бота жили не больше одной сессии – на следующий день Либратус избавлялся от найденных у него слабых мест.

По словам профессора Сандхольма, бот мог применять несколько различных вариантов стратегии и оптимизировал их параметры между сессиями, по ночам. Можно сказать, по ходу матча его игра усиливалась, так как отставку получали менее эффективные против соперников модификации.

Успех команды Сандхольма значимее для программирования, чем победы машин в шахматах или го. Дело в том, что шахматы и го относятся к марковским процессам – лучшее решение в позиции не зависит от того, каким путём возникла эта позиция. Покер не является марковским процессом, точно так же, как и жизнь. Приёмы, использованные программистами университета Карнеги – Меллон, могут найти разнообразное практическое применение, выходящее далеко за пределы покерного мира.

Джейсон Лес и Донг Ким комментировали происходящее не только в прямом эфире на Twitch.tv, но и в колодце на Reddit.

Публикуем некоторые наиболее интересные вопросы и ответы из этой темы.

Играет ли компьютер как очень сильный человек, или его стиль – нечто совершенно нечеловеческое?

Джейсон:
– Как очень сильный человек, но способный оказывать гораздо большее давление, не выходя за пределы корректной игры, чем кто-либо из известных мне людей.

Кого напоминает вам стиль ИИ?

Джейсон:
– Многое в стиле ИИ напоминает мне игру Дага Полка. Но сходство условное – стиль машины уникален. Либратус использует смешанные стратегии во всех линиях и с любыми сайзингами, поэтому понять его диапазоны исключительно сложно. Мы собрали статистику по частоте, с которой он делает то или иное действие, но получить на выходе что-то конкретное практически невозможно.

Рады ли вы, что после противостояния со Скайнет снова сможете играть против обычных людей? Серьёзный вопрос: улучшит ли матч против Либратуса вашу стратегию? Станете ли вы чаще использовать овербеты, например?

Джейсон:
– После Либратуса матч с любым человеком будет для нас лёгкой прогулкой.

Джейсон и Донг:
– Мы точно начнём чаще овербетить, но для этого потребуется немалая исследовательская работа. Как только ваши овербеты становятся менее сбалансированными, они моментально превращаются в грубую ошибку.

Если бы у вас был год на изучение истории раздач, смогли бы вы обыграть нынешнюю версию ИИ? Или хотя бы сыграть с ней на равных?

Джейсон:
– Думаю, если нам дать бесконечное время на подготовку и возможность играть в любое время по своему желанию, мы сможем приблизиться к Либратусу. Но не думаю, что сможем обыграть его.

Расскажите о самой глупой раздаче ИИ в этом матче.

Джейсон:
– Я открылся с парой валетов, он заколлировал. Флоп 8x 7x 2x радуга, я поставил контбет примерно 2/3 банка, и он поставил олл-ин почти 200 бб с Kx Tx разномастными. Не уверен, что это точно глупо, но шок был приличный.

Чаще ли вы блефовали против бота, чем против человека?

Джейсон:
– Точно нет. Блефы нужно выбирать очень осторожно, поскольку на Либратуса не влияют эмоции.

Донг:
– Некоторые люди выкидывают 100% комбинаций в определённых ситуациях или никогда не блефуют в других. Но бот не соблюдает неписанных законов человеческого покера.

На какой улице бот играет сильнее всего?

Донг:
– На тёрне.

Я играю мидстейкс 6-макс. Когда начинать паниковать? Не появятся ли через полгода за каждым столом по три русских бота?

Донг:
– Тебе повезло! Решить игру для 6-макс намного сложнее – больше ситуаций, больше игроков... На твоём месте я бы играл дальше.

Джейсон:
– Этот ИИ запрограммирован для игры один на один. Боты, играющие 6-макс, далеко не такие продвинутые (хотя могут играть довольно успешно). Думаю, до настоящей паники у тебя ещё есть несколько лет, но всё же соблюдай осторожность.

Сайт матча (https://www.riverscasino.com/pittsburgh/BrainsVsAI/)

Каналы на Twitch.tv:

https://www.twitch.tv/libratus_vs_jasonles

https://www.twitch.tv/libratus_vs_dongkim

https://www.twitch.tv/libratus_vs_jimmychou

https://www.twitch.tv/libratus_vs_danielmcaulay