Дерево решений программы DeepStack в хедс-апе (игре один на один) безлимитного холдема на префлопе и флопе
Пионер современной теории игр Джон фон Нейман говорил: «Реальная жизнь вся состоит из блефа, из маленьких приёмов обмана, из размышлений о том, каких действий ожидает от тебя другой человек. Вот что представляет игра в моей теории» (цитата из 13-й серии документального сериала «Возвышение человечества»).
Другими словами, Джон фон Нейман предвидел, что для создания сильного ИИ компьютер должен научиться играть в игры с неполной информацией, которые наиболее соответствуют человеческому поведению в реальной жизни. Такие игры как покер.
Настольные игры — традиционная область экспериментов в сфере искусственного интеллекта. С каждым годом ИИ обыгрывает человека в разные игры. Сначала сдались шашки, потом шахматы, затем видеоигры Atari, последней пала игра го. Но всё это игры с полной информацией, в которых все игроки имеют полную информацию о состоянии игры. Покер — совершенно другое дело.
Учёные давно пытаются разработать программу, которая бы могла обыгрывать человека в безлимитном Texas Holdem. В отличии от других применений слабого ИИ, здесь успешная разработка окупится мгновенно, потому что ежедневно в онлайновых покер-румах разыгрывают банки на миллиарды долларов.
Джон фон Нейман говорил, что покер восхищает его, и это совершенно неудивительно, учитывая уникальные особенности этой игры с неполной информацией. У каждого игрока есть только часть информации о состоянии игры — и он действует, исходя из этой частичной информации, а также оценивая действия других игроков.
Раньше ИИ добивался некоторого успеха только при игре в лимитный холдем, самый примитивный вариант игры с ограниченным шагом повышения ставок. В лимитном варианте у игрока есть всего лишь 1014 вариантов развития. Для сравнения, в безлимитном холдеме таких вариантов уже 10160. Кстати, в игре го вариантов развития 10170, но там игра с полной информацией, то есть принципиально более простая задача.
Игры с неполной информацией требуют совершенно более сложного уровня рекурсивного мышления, чем игры с полной информацией. Здесь правильное действие ИИ зависит в том числе от информации, которую ИИ получил от действий оппонента. Но информация, которую выдал оппонент, в свою очередь, является производной функцией от предыдущих действий ИИ и той информации, которую ИИ своими действиями выдал оппоненту. Это и есть рекурсивное мышление, с которым имеет дело программа DeepStack. И справляется она очень неплохо, судя по результатам игр с профессионалами (см. таблицу).
Результаты программы в хедс-апах с профессиональными игроками
Архитектура программы DeepStack показана на иллюстрации. Программа переоценивает свои действия на каждом этапе, когда от неё требуется принятие решения. Для расчёта вэлью каждой ставки используется дерево предвидения (lookahead tree), значения для подветок которого вычисляются с использованием нейросети, заранее обученной на случайных игровых ситуациях.
Структура нейросети демонстрирует, что на входе подаётся размер банка, открытые карты и диапазоны игроков (возможные комбинации, с которыми игрок мог войти в игру таким образом, каким он в неё вошёл (колл, рейз, 3-бет и т.д.), вероятность каждой комбинации). Нейросеть состоит из семи полностью соединённых скрытых слоёв. Выходные значения затем обрабатываются другой нейросетью, которая проверяет, что действия удовлетворяют ограничению на нулевую сумму.
Особенностью программы является то, что она активно сопротивляется анализу своей стратегии со стороны оппонента. Другими словами, программа использует равновесие Нэша — ключевое понятие теории игр. Под равновесием Нэша подразумевается набор стратегий, котором ни один участник не может увеличить выигрыш, изменив свою стратегию, если другие участники своих стратегий не меняют. С точки зрения антагонистической игры в покер основной задачей DeepStack является поиск равновесия Нэша, то есть минимизация возможности эксплуатации своей стратегии другим игроком для получения им прибыли. Абсолютно все разработанные до сегодняшнего дня покерные программы легко эксплуатировались после прощупывания их стратегии с помощью техники LBR (local best-response) — см. недавний обзор самых современных ботов для покера.
Так вот, DeepStack совершенно не эксплуатируется с помощью LBR. Вкупе с реальными результатами, которые показал бот в игре с профессионалами, остаётся только один вопрос: зачем разработчики опубликовали информацию об этой архитектуре в открытом доступе?
Научная работа опубликована 6 января 2017 года на сайте arXiv.org, где выкладываются статьи до выхода в официальном журнале.
Группой разработчиков руководит профессор информатики Майкл Боулинг из Университета Альберты (США).
Группа разработчиков DeepStack
Кафедра покерных ботов в Университете Альберты (Computer Poker Research Group) создана ещё в 90-е годы, первым созданным здесь ботом был Loki в 1997 году. Потом были Poki (1999), PsOpti/Sparbot (2002), Vexbot (2003), Hyperborean (2006), Polaris (2007), Hyperborean No-Limit (2007), Hyperborean Ring (2009), Cepheus (2015) и, наконец, венец творения — DeepStack.
В ближайшее время программу DeepStack проверят в играх с более опытными профессионалами, которые гораздо выше уровнем, чем ребята из таблицы в начале статьи. Начиная с этих выходных программа будет играть на турнире в питтсбургском казино, куда ожидается приезд нескольких профессионалов мирового класса. За 20 дней DeepStack должна сыграть около 120 000 рук. Это достаточно много, чтобы довольно точно оценить качество программы.
На данный момент DeepStack сыграл 44 852 руки против профессионалов добровольцев, отобранных Международной федерацией покера. Игроки получали денежные призы за хорошую игру (первый приз $5000 CAD), так что люди играли в полную силу. Тем не менее, программа в хорошем плюсе.
Комментарии (43)
Forest_Gump
13.01.2017 03:13-4Честно говоря, те же шахматы мне кажутся намного сложнее, чем покер. По сути рывок в сложности от 10^14 к 10^160 происходит только за счет снятия лимита на размер ставки. При такой логике, если разрешить в шахматах делать ставки и учитывать результат в деньгах по итогам нескольких партий, то сложность шахмат улетит в небеса.
Tembl44
13.01.2017 08:30+6При введении ставок в шахматы вводная для компьютера информация не меняется никак. В покере это часть игры и информация для анализа меняется радикально в зависимости от ставок.
NINeOneone
13.01.2017 10:12Другое дело что все многообразие ставок можно объединить в несколько групп (не больше десятка я думаю) в зависимости от того, что человек (правильнее видимо сказать игрок) хотел этой ставкой сказать — вроде «у меня очень сильная рука», или «у меня не много, но думаю у тебя не больше» и так далее.
Tembl44
13.01.2017 10:34Есть ещё две переменных: стэки игроков (их деньги). И от них зависит чуть ли не больше, чем от флопа.
itwasntme
13.01.2017 11:55+2насколько я помню у ранних версий deep Blue самая основная проблема была в жертвах фигур с стороны реального игрока, хотя это и довольно обыденный ход в шахматах, а тут пол игры построено если не на полном блефе с пустой рукой, то уж точно на часто не обоснованных ставках.
446156835
13.01.2017 13:06Каждому бет сайзину соответствует часть сбалансированного диапазона, и интерпретировать указанным выше образом ставку определенного размера не выйдет. А объединение всего многообразия ставок в определенное количество групп приведет к малообсчитанности некоторых узлов решений, и как следствие, реакция ИИ на ставку, размер которой находится внутри обобщенной группы, будет не оптимальной.
Karnah
13.01.2017 10:37+3Я эту ситуацию вижу немного по-другому.
В шахматах это не увеличит сложность, так как там сложность зависит от количества возможных ходов на шахматной доске. Вся информация известна всем в равной степени. Увеличении ставки не даст дополнительной информации о положении дел на шахматной доске. Мне кажется, что блеф в шахматах не самый популярный ход.
В покере информация ограничена. Единственное, что доступно — свои карты, открытые карты, выражение лица соперника (для «живых» игр) и его размер ставки. То есть алгоритму необходимо узнать как можно больше информации исходя из поведения игрока, то есть повышает ли он ставки и если да, то на сколько.
Это мои выводы, если я не прав — прошу меня поправить
Falstaff
14.01.2017 10:56Вы удивитесь. :) В теории всё так, шахматы — игра с полной информацией. Но в реальных человеческих шахматах (с биологическими игроками и ограниченным временем на партию) невозможно посчитать все варианты до самого конца — разве что в определённых малофигурных эндшпилях ещё можно — так что полную информацию использовать не получится. Так что блеф — это в шахматах очень популярно: «подкрутить», сделать не самый сильный ход, но зато ведущий к осложнениям (особенно если соперник играет на флажке и все варианты посчитать не успеет), сделать некорректную жертву и получить атаку, где психологически сложно за доской опровергать рисковые варианты и хочется просто укрепиться (здравствуй, Таль), сделать, зная противника или наблюдая за его поведением, объективно не самый сильный, но самый неудобный для него ход… Наконец, просто поймать на домашнюю заготовку, о которой противник не знает.
В общем, психологический элемент в шахматах тоже играет роль (вроде бы даже две школы исторически имелось — советская, с упором на объективную силу ходов, «играю против фигур», и ласкеровская, с упором на человеческий элемент). Пока ещё игра не просчитана от первого хода до мата (или ничьей, кто знает), я думаю, что было бы интересно искать усиления шахматных движков, дав им дополнительную информацию о поведении, характере и привычках соперника.
DEmon_CDXLIV
13.01.2017 11:40+1В Теории Большого Взрыва была серия, где они посчитали шахматы слишком простой игрой и сделали гибрид шахмат, D&D и карточной игры. Ну или вспомнить первоначальные правила шахмат, где очередность хода определялась броском кубика.
gadzhi15
13.01.2017 12:08+1еще там были шахматы на троих)
Ovolyn
13.01.2017 12:35+1А также гибрид шахмат и армреслинга
losse_narmo
13.01.2017 12:49Шахбокс же (шахматы + бокс)
Ovolyn
13.01.2017 14:18Ну, это хоть и реально существующее соревнование, но в сериале этого не было. Не представляю героев, занимающихся боксом (не считая Пенни).
По поводу 3-х мерных шахмат понравилась победная издевка Шелдона «Ну как тебе быть отстойным на стольких уровнях сразу?»
DEmon_CDXLIV
13.01.2017 12:57Там еще были трехмерные шахматы :) Я к тому, что в шахматы легко можно привнести много случайности
molnij
17.01.2017 09:43Случайность — это в квантовых шахматах :)
GlukKazan
17.01.2017 12:10В них тоже нет. Не стоит путать случайность и недетерминизм. Случайность есть в "Шахматах втёмную", в "Герцоге", либо разнообразных вариантах игры с бросанием костей. В "Квантовых шахматах", как и в "Квантовых крестиках-ноликах" никакой случайности нет.
molnij
17.01.2017 14:20+1Хм, тогда я не понимаю разницы.
В шахматах втемную я вообще не вижу ни случайности ни недетерминизма. Это очень крутой пример игры с неполной информацией, однако все ходы однозначны и определённы. Вы можете предполагать наличие или отсутствие фигуры на какой-то клетке, но её состояние при этом всё равно определено (и зафиксировано рефери\программой) и не зависит ни от какого случайного фактора.
В квантовых шахматах вы свертку делаете по сути бросанием кости — и тут от меня ускользает расхождение в этом случае между недетерминизмом и случайностью — вроде и там и там вы из множества доступных состояний в момент броска случайным образом разрешаете одно — аналогично в любой карточной игре или игре в кости вы в момент броска\открытия карты разрешаете какое-то неопределенное состояние в уже состоявшееся — на мой взгляд это очень близко к свертке квантового состояния.GlukKazan
17.01.2017 15:07«Шахматы втёмную» — игра с неполной информацией. Согласен, не вполне правильно считать её игрой с элементами случайности (напротив, игры с бросками костей следует считать разновидностью игр с неполной информацией). Тут моя неточность в формулировках. По «Квантовым шахматам» тоже мог ошибиться. В «Квантовых крестиках-ноликах» коллизии вполне однозначно разрешаются противником допустившего их игрока, без всяких случайностей. Если в «Квантовых шахматах» используется броски костей — это безусловно случайность. Кстати, есть ещё одна довольно любопытная возможность. В некоторых играх (таких как Selus) возникают ситуации «гонок», связанные с одновременным выполнением хода двумя игроками. Видимо, это тоже можно рассматривать как некий элемент рандомизации.
xfather
13.01.2017 10:09+1А теперь представьте, если добавить программе чтение микродвижений лица и тела, величину зрачков, температуру тела и частоту пульса. Думаю вход во все казино Лас-Вегаса был бы закрыт. :)
Dendroid
13.01.2017 10:45+5Ага, конечно. Скоро такие программы будут сидеть во всех казино Лас-Вегаса с той стороны стола.
basilbasilbasil
13.01.2017 10:32+2То есть теперь не будет проблем с доступом в онлайн-казино? По причине отсутствия их.
zim32
13.01.2017 11:17+2Когда дойдет до таких ботов, просто уберут покер. Или не датут вывести средства если будете много выигрывать. Скажут что есть подозрение на фрод и все. Или с той стороны стола тоже будут такие же боты. У них денег больше чем у вас на такие вложения и мощности.
Mitch
14.01.2017 17:45Вообще то покер румы уже очень много лет борятся с ботами, которые успешно катают в плюс с NL.
Причем разными методами, включая письма счастья с требованиям к некоторым про игрокам показать себя и свое окружение камерой продолжая играть «в обычном стиле».
9AlexYa
13.01.2017 10:40В отличии от других применений слабого ИИ, здесь успешная разработка окупится мгновенно, потому что ежедневно в онлайновых покер-румах разыгрывают банки на миллиарды долларов.©
верните мне мой 2007 ой. и ФТП и Гаса Хансена и Исилдура((((
ну и ХА кеш умер уже в 2012ом ((
а прога эт прорыв и очень круто. Интересно, как можно будет сами алгоритмы потом на практике применять.
savostin
13.01.2017 10:43+4Кафедра покерных ботов в Университете Альберты
Красота, такую бы в каждый универ. Хотя кустарные лаборатории покера уже и так есть в каждом ;)
PavelGatilov
13.01.2017 12:55Угу, наша кустарная лаборатория покера была в общежитии №3, в 206-ой комнате, каждый четверг. Вот только до написания ботов руки не доходили.
4ebriking
13.01.2017 13:35Ага, и лекции там — теорвер с матстатистикой, да психология во всех ипостасях, ну и алгоритмы всякие. И экзамены — с автозачислением во все чёрные списки всех казино… Правда в них же и трудоустройство. (ну плюс программирование игровых атоматов по всему миру разной стпени легальности). Нормальная профессия, нормальная работа, нормальная кафедра, но наверное курса со второго предложение «сыграть в покер» — будет из серии «приходите вы на пляж — а там станки, станки»…
Necrozyablo
13.01.2017 10:57+410^160 цифра взятая с потолка, для предания себе значимости.
Все ставки можно разложить в 10 ну максимум 100 групп.
Писал бота и для шахмат и для покера и для го(евы, вова, д2, д3). В шахматы и покер боты играли вполне, а вот для го так и не смог написать.
stifff
13.01.2017 14:32вот для го так и не смог написать
а для перечисленного в скобочках?Necrozyablo
13.01.2017 14:51Ну в Еве был торговый и майнинговый(группой) бот
В вове акционный и рыбалка
В д2 просто локация вырезалка.
В д3 простой фармитель кувшинов( когда д3 ток вышла) потом скрипты для ботов что есть
В линейке тоже скрипты для масс управления ботами.
446156835
13.01.2017 12:48В отличии от других применений слабого ИИ, здесь успешная разработка окупится мгновенно, потому что ежедневно в онлайновых покер-румах разыгрывают банки на миллиарды долларов.
Бот пишется в безрейковой среде, в онлайн покере же рейк взимается => равновесие в нем не достижимо.
Не говоря о том что для игры с большим количеством участников, чем два, он бесполезен.
А 44к рук против каких-то ноунеймов это вообще лол, так как квадратичное отклонение при стратегии бота едва ли меньше сотни бб на сто рук, и результат при такой выборке против разных оппонентов не может быть статистически значимым.
И в 2015 году уже проходил матч людей против Claudico в котором компьютер уступил, сейчас же проходит матч реванш, и следить за этим можно на твиче. Или тут.
redpax
13.01.2017 14:08-2«Но всё это игры с полной информацией, в которых все игроки имеют полную информацию о состоянии игры. Покер — совершенно другое дело. » Это не верное утверждение.
Zul_Kifl
13.01.2017 14:36+1И в чем его ошибочность?
redpax
13.01.2017 14:48-2ГО просчитать до конца пока нет мощностей, там ИИ работает тоже с неполной информацией.
Zul_Kifl
13.01.2017 14:50+1При чем здесь мощности? ИИ полностью известна ситуация на доске — значит это игра с полной информацией.
GlukKazan
13.01.2017 15:24Го — игра с полной информацией (мощности компьютеров к этому определению отношения не имеют).
Кстати, если интересно, есть корейские варианты игры с неполной информацией.
Dum_spiro_spero
14.01.2017 04:07+2Так… Шахматы — всё. Го — всё. Покер… всё.
Во что бы поиграть-то…
— Выскажу предположение.
Программа неким образом строит модель блефа человека. А это проще чем просчитывать ходы. В том смысле, что блеф-действия человека достаточно ограниченны — это трудно, надо притворяться, что-то изображать, и т.п… См. шикарный рассказ А.С. Грина «Серый автомобиль».GlukKazan
14.01.2017 10:15А как возможность поиграть во что-то связана с тем фактом, что «Шахматы — всё»?
Вы обязательно с суперкомпьютером собрались играть? Так с человеком интереснее.
napa3um
14.01.2017 14:12> но там игра с полной информацией, то есть принципиально более простая задача
Если вариантов больше, чем способен перебрать решатель в разумное время, то игра с полной информацией может быть сведена к модели с неполной информацией (выбор векти перебора потенциально наиболее «трудной» для просчёта противником принципиально не отличается от выбора ставки с наиболее невыгодным соотношением рисков для противника — в обоих случая используются или явные эвристики о поведении противника, или неявные статистические о возможных его ответных ходах). В этом смысле и покер, и го находятся в одном и том же классе задач — задачи с невозможным полным перебором всех вариантов на существующем на текущий момент вычислителе (а что из этого «сложнее» — неясно, ибо с обоих сторон сидят игроки с одинаковыми ограничениями).
ThunderCat
Где то так примерно…