Об искусственном интеллекте в покере



Покер давно привлекает исследователей самых различных мастей от любителей до серьезных ученых. И, не секрет, что столь пристальное внимание к покеру коррелирует с ростом популярности онлайн гэмблинга, который бурно развивался в 00-х годах. На сегодняшний день человек уже уступил лимитный хедс-ап Техасский Холдем машине, в то время как в безлимитных и многоместных покерных дисциплинах человек все еще берет верх. Наибольший вклад в проблему построения сильного компьютерного покерного интеллекта, вне всякого сомнения, внесла исследовательская группа из университета Альберты, а предложенное ими семейство алгоритмов поиска равновесных стратегий является на сегодняшний день самым модным и часто используемым средством при построении покерных агентов. Но обо всем по порядку.

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

О сложности покера для машинного обучения


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



В рассматриваемом нами варианте покера порядка 1018 игровых ситуаций, что делает эту задачу, мягко говоря, не решаемой в лоб, поскольку требует совершенно немыслимых вычислительных ресурсов. Однако следует заметить, что некоторые карточные комбинации эквивалентны между собой, так, например, на префлопе стартовая комбинация из двух тузов A♥A♦ абсолютно идентична любой другой паре тузов. Таким образом, рассматривая первый круг торговли, на котором у игроков всего по две карты на руках, мы можем выделить всего 169 различных неэквивалентных двухкарточных комбинации. Но даже после выделения эквивалентных классов карточных комбинаций Техасский Холдем имеет порядка 1014 различных игровых состояний, требующих для своего хранения десятки петабайт памяти, не говоря уже о времени, которое будет затрачено на то, чтобы все это обучить игре в покер. Стоит ли после этого заикаться про вариации покера для 3-х и более игроков?

Обычным делом в случаях, когда исходная игра слишком велика для непосредственного изучения, является переход к абстрактной игре (абстракции), объединяющей в своих игровых состояниях близкие в стратегическом смысле состояния полной игры. Другими словами, при анализе и решении игры некоторые состояния исходной игры трактуются как неразличимые. В качестве примера построения абстракции в покере, рассмотрим префлоп, где, как известно, лучшими стартовыми комбинациями являются пара тузов AA и одномастные сочетания туза с королем AKs. Совершенно очевидно, что стратегии розыгрыша этих карт на первом кругу торговли несильно будут отличаться друг от друга, поэтому можно без зазрения совести объединить эти две пары карт в один абстрактный класс стартовых комбинаций. Указанный трюк можно повторить и для других карточных комбинаций, получив в итоге, как вы уже догадались, «абстрактный» покер с меньшими запросами к вычислительным ресурсам.

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

Рассмотрим теперь основные концепции построения стратегических профилей для игры в покер.

Экспертные системы

Самые первые покерные агенты являлись экспертными системами или наборами правил if-then для различных игровых ситуаций. Такие правила вбивались ручками с помощью самих игроков и/или получались с помощью анализа большого количества реальных игровых раздач. Как бы то ни было, недостаток такого подхода очевиден — искусственный оппонент легко эксплуатируется после выявления слабых мест. Разумеется, эти слабые места всегда можно подкорректировать добавлением новых записей в базу правил, но это влечет за собой ряд неприятностей, связанных с растущей сложностью поддержки, отладки и снижающейся производительностью системы в целом.

На сегодняшний день покерные агенты данного типа в чистом виде практически не используются ввиду их легкой эксплуатируемости. Наиболее известные представители этого класса ботов: первые версии Loki и Poki, FellOmen и широко известный в узких кругах Shanky Bot.

Эксплуататоры

Основная концепция покерных ботов-эксплуататоров основана на построении контр-агентов к известным оппонентам, использующих их слабые места для получения максимальной прибыли от игры. Как правило, используются либо моделирование поведения оппонента в той или иной игровой ситуации, либо заранее посчитанные стратегические профили под определенного оппонента.

Принятие решения в системах с моделированием оппонента сводится к многократному проигрыванию «виртуальных» раздач с различными исходами для определения наиболее выгодного решения. Адекватность таких покерных агентов обусловлена адекватностью модели оппонента. Но, когда речь заходит о моделировании решений человека, всегда невольно вспоминается гадалка Шеннона, которая угадывает действие игрока в девяти случаях из десяти. Чаще всего для моделирования живых оппонентов используются нейросети, которые, как сообщают некоторые источники, могут давать ~80-90% надежность предсказания действий игрока. Это обстоятельство делает данный вид покерных ботов наиболее привлекательным для игры в онлайн казино, так как современные GPU-технологии позволяют легко и быстро построить модель оппонента и вычислить выгодное решение.

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

Для любого бота-эксплуататора существует один недостаток. Он заключен в необходимости реализации начальной стратегии, так как очевидно, что невозможно смоделировать и эксплуатировать оппонента после десятка раздач. Более того, речь идет о десятках тысяч раздач с конкретным противником, прежде чем эксплуатация начнет приносить свои плоды. Обычно, во время набора статистики на оппонента используются покерные боты другого типа. При игре с людьми на начальном этапе очень часто используется подход, при котором эксплуататор заранее обучается по истории раздач против группы игроков, объединенных общими характеристиками, такими как частота захода в игру, желание идти на вскрытие и так далее. Затем, по мере наигрывания игровых раздач, характеристики человека-оппонента проясняются все сильнее и сильнее, что позволяет эксплуататору быстрее и адекватнее подобрать и дообучить соответствующую контр-стратегию.

Качество игры эксплуататоров намного превосходит экспертные системы, так как они способны выявить слабые места последних. Их эффективность против произвольных оппонентов во многом определяется тремя факторами — начальной стратегией, набранной статистике на оппонента и адекватности используемой модели. Самыми известными ботами этого класса являются BRPlayer и Vexbot, знакомый многим по Poker Academy.

Равновесные стратегии

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

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

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

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

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

На сегодняшний день существует несколько эффективных алгоритмов поиска равновесия в больших абстракциях покера. Самыми популярными из них являются алгоритмы, основанные на минимизации сожаления. Это семейство алгоритмов активно разрабатывается исследовательской группой университета Альберты и заслуживает отдельного рассмотрения. Отмечу лишь, что с помощью одного из таких алгоритмов был обучен покерный бот Slumbot, в котором первые три круга торговли представлены безо всякой абстракции. Этот бот занял первое место в прошлом году на Annual Computer Poker Competition.

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

Вместо заключения

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


Поделиться публикацией
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама
Комментарии 28
  • +5
    Как-то мало и поверхностно. Статья, по-хорошему, тянет на вступление к большой статье или к циклу.
    • +2
      Вообще-то это был пробный шар. Рассмотрение деталей по каждому подходу заняло бы очень много места, а некоторые вопросы требуют разной подготовки читателя, как то не хотелось все лепить в одну публикацию. Все же лучше по отдельности.
    • +1
      Вообще довольно интересно! Надеюсь это все-таки вступление к циклу статей.
      • 0
        С удовольствием почитаю еще. Сам в покер почти не играю (по крайней мере в онлайне так, изредка с друзьями играем в реале на небольшие деньги), но тема мне интересна именно в теоретическом смысле.

        Любопытнейшая игра в плане внутриигровой механики, воспринимается многими только как очередной вариант некоего «форекса» — разводилова для лохов.
        • +4
          Вы уж извините за оффтопик, но не могу не похвастаться :)
          • 0
            Похвастаться ботом?
            • +2
              Человек с ником «Военный» дает ссылку на то, что человек с ником «Военный3» выиграл чемпионат по онлайн-покеру. Думаю что если там и был бот, то наврядли мы об этом узнаем )
          • 0
            Я правильно понимаю, что ещё пару лет и в покер в интернете будут играть исключительно боты против ботов, живому человеку с ними конкурировать будет невозможно, как сейчас невозможно в шахматах?
            • 0
              Он-лайн казино очень строго следят за ботами. В частности, есть прецеденты, когда ботов выявляли по их статистическим характеристикам. Написать сильный покерный ИИ одно, а вот создать полностью систему с обходом безопасности софта казино — другое дело.
              • 0
                А как они доказывают, что ты слушаешься советов бота? Я ведь и сам могу строго играть по стратегии, без каких-либо отклонений.
                • +1
                  Если вас будет не один, а скажем так, четверо, и ваши характеристики будут слишком уж похожими — то вывод напрашивается сам собой.
                  • 0
                    Спасибо, логично.
                    • 0
                      Либо вы четверо строго играете по одной стратегии.
                      • 0
                        Четкая стратегия хороша только на низком уровне игры, потом ее в любом случае приходится модифицировать и подстраивать под оппонентов и собственный стиль. В НЛ, во всяком случае, про ФЛ не знаю.
                        • 0
                          Абсолютно с вами согласен, но я имею ввиду, что такие четкие стратегии существуют и существуют люди, особенно новички, которые педантично им следуют.
                          • 0
                            Я не думаю, что кто-то будет писать бота, чтобы играть, условно, 4 стола на НЛ20, как играют новички — просто профита не будет. Даже если и напишет, то, в общем-то, наплевать, никакого влияния на покер этот бот не окажет. А чтобы увеличить доход бота, нужно либо подниматься по лимитам (и усложнять стратегию), либо открывать еще столы, но 20 столов без отклонения от стратегии человек играть не может, так что…
                • +1
                  Просто тогда будет другое увлечение — тотализатор на ботов :)
                  • +2
                    Отличный вопрос! Интересно мнение автора, со своей стороны (я немножко знаком с покером и очень-очень поверхностно — с покерными ботами) мне это видится так:

                    а) С одной стороны, написать бота, который будет «делать поле» (то бишь сильнее большинства игроков) на микролимитах, очень просто, но и доходы там мизерные.
                    б) Средние лимиты, полагаю, самая доходная область для ботоводов. Да, там можно делать деньги и, как мне видится, не нужно создавать мегамозг, чтобы получить успешный результат.
                    в) На скайстейкс все сложнее. Во-первых, там собраны действительно очень сильные игроки, которые способны подстроиться под оппонента и эксплуатировать самые маленькие уязвимости его стратегии, а у бота они, скорее всего, будут. Да, конечно, бот со своей стороны тоже будет выискивать слабости покерпро и подстраиваться под них, но тут см. ситуацию с равновесием Неша. Есть и еще один аспект — покерная топ-сцена довольно мала и все мало-мальски значимые персонажи и события постоянно находятся на виду. Появление нового очень сильного игрока вызовет огромный интерес к его персоне и механизмам игры.
                    г) И еще вот какой аспект. На покере зарабатывают прежде всего владельцы покеррумов, и зарабатывают очень большие деньги. Если в какой-то момент боты начнут угрожать популярности покера, думаю, борьба с ними развернется нешуточная.
                    • +1
                      Ну чтож, отвечаю по пунктам:
                      а) На микролимитах народ как правило учится играть в покер. Зарабатывать на этих лимитах в онлайн казино сложно из-за рейка, который съедает практически весь доход.
                      б) Средние лимиты это доходная часть не только для ботоводов, но и для «регуляров», которые зарабатывают себе на жизнь игрой в покер с посредственными игроками. «Регуляры» очень опасны для ботов, поскольку это опытные игроки и странности в поведении оппонента могут привлечь их пристальное внимание с дальнейшим разбирательством. Плюс ко всему даже на этом уровне регуляры хорошо знакомы друг с другом и избегают игр между собой. Поэтому появление «звезды» вызовет такой же ажиотаж, как и на высоких лимитах.
                      в) Насчет игры на высоких лимитах ничего не скажу, не думаю, что в мире есть пользователи ботов, которые рискнули бы сюда сунуться. Но есть другой аспект игры с профессионалами, а именно — соревновательный, как это было с Polaris'ом.
                      г) По моим скромным подсчетам дневной профит покер-румов составляет порядка 1 миллиона долларов (если верить цифрам из интернета), то ясное дело, они будут заинтересованы в отсечении сильных ботов. Но с другой стороны есть два момента — слабые и средние боты могут играть практически на одном уровне с людьми, что увеличивает доход рума за счет того, что растет количество раздач на «равных», а рейк снимается в любом случае. А второй момент — населенность казино. Большое количество игроков в нем создает очень хорошее впечатление у тех, кто пришел поиграть.
                      • –2
                        Статья хорошая, но сильно сомневаюсь в вашем умении играть в покер, иначе не спорили бы ни с одним из пунктов JustRoo.

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

                        не имеет ничего общего с действительностью.
                        • +3
                          Я не спорил ни с одним из пунктов JustRoo, лишь высказал свое мнение, как меня и просили.

                          Что касается второй части вашего замечания — возможно вы и правы насчет AA и AKs, мне бы следовало привести в качестве примера стартовые пары AA и KK, но в голову почему-то только этот случай пришел. Как бы то ни было, на мой взгляд в лимитном холдеме разница между AA и AKs не столь велика, как если бы это было в безлимитных дисциплинах, где возможен уход в ва-банк на префлопе.
                  • 0
                    Ребята, советую для бота посмотреть стартовые комбинации покера, там есть обьединение по группам и позициям за столом и даютса трактовки рук. Ах да, забываете что есть такой вариатив как масть. И таки да, ГДЕ ФОЛД на всех уровнях торговли?! Особенно на безлимите вскрытие карт происходит редко, чаще всего отсеиваються после флопа или турна. Вообще если писать бота для низких лимитов, то за счет бонусов казино можно взять немного в карман. С турнирным покером не все так радужно.
                    • 0
                      Поясню насчет фолда — я действительно опустил некоторые терминальные истории на схеме. Дело в том, что если игра закончилась до вскрытия, то боту больше не нужно принимать решение. Например, обе истории 'crc' и 'crf' содержат в себе 'cr', при этом, после 'crc' у нас происходит переход на следующую улицу, где покер-боту снова надо принимать решения, а вот после 'crf' для бота игра закончилась и новой информации после этой истории в игре не появится.
                    • 0
                      А как боты играют в MTT (турнирный покер)? MTT не так легок для ботов. Т.к. по факту, ты играешь на фантики, которые не сопоставить с деньгами. Будучи чип-лидером большую часть игры, ты можешь не получить ни чего. Это не кэш, где выиграл 2 стартовых стека и вышел из-за стола.
                      • 0
                        Про ботов и турнирный покер мало могу рассказать, но, насколько мне известно, принципиально покерные ИИ для кэша и турниров мало чем отличаются. Различия лишь в том, что в случае с турнирами целесообразно использование нескольких различных покерных агентов, чтобы можно было производить стратегические манипуляции.
                        • 0
                          Разница в поведении на разных стадиях турнира. Учитывается ли вес количества фишек на ранней стадии, на «bubble», на «bubble»-финального стола и на самом финальном столе разный. Всегда была интересна эта тема.
                          Не верю я, что тот самый «jahma darma», известный еще как feruell, в лимитный покер за год заработал 9 миллионов $ не используя бота.
                          • 0
                            Feruell хорошо играет в лимит, да.
                            Но для лимита уже написали Polaris бота, которого не может обыграть ни один покер-про лимитчик ;)
                      • 0
                        В полезные ссылки стоит еще добавить эту.

                        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.