ИИ: блеф, отъем денег у населения и победа над неопределенностью

30.01.2017

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

Покер часто пренебрежительно называют азартной игрой, выигрыш в которой зависит исключительно от случая, но его на сегодняшний день в законодательном порядке признали официальным видом спорта в целом ряде стран (за исключением России). Самое интересное для нас и машин в том, что в покере выигрышные стратегии можно спрогнозировать при помощи теории вероятности. И самое главное, покер — это игра с неполной информацией, в отличие от шахмат, шашек, нард, где оба игрока видят положение всех фигур на доске. Ранее ИИ не мог победить там, где присутствует элемент неопределенности. Так что же изменилось?

Самые большие игры

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

В фантастике роботы часто бьются с роботами («хорошие» против «плохих»), но в реальности чемпионаты машин, за исключением всем известных механических «боев», привлекают мало зрителей. Поединки ботов между собой лишены эмоциональности, духа состязаний, и представляют интерес только для узкой аудитории специалистов. То ли дело борьба с людьми! К 2016 году компьютеры смогли выиграть (или найти математическое решение выигрышных позиций) у человека в две дюжины интеллектуальных игр: ним, крестики-нолики, призрак, четыре в ряд, гомоку (15х15), мельница (с 9 фишками), лентомино, овалху, кварто, тико, пангки, рендзю (без дебютных правил), авари (семейство манкала), магараджа, «тигры и козы», фанарона, английские шашки, «три мушкетера», хекс (8х8), калах (6х6), китайские палочки, пентаго, го (5х5 и классическая игра против Ли Седоля).

Не все из этих игр могут быть вам знакомы, но о каждой можно написать отдельную статью с драматической главой о борьбе с машинами. Пожалуй, одним из самых интересных и напряженных противостояний (помимо всем известных перипетий с игрой «го») стала битва за шашечную корону. Подробнее об этом периоде можно прочитать в нашей первой статье из цикла об ИИ, а сейчас просто вспомним одно интересное число: английские шашки — самая большая из игр, полностью решенных до настоящего времени. Размер ее поискового пространства 5×10²⁰. Для того чтобы найти решение, в течение 18 лет сеть персональных компьютеров (от 50 до 200 штук) произвела 10¹⁴ вычислений.

Если вы читали наши предыдущие статьи на тему ИИ, то уже знаете, что в сложных играх машина не побеждает полным перебором всех возможных комбинаций ходов. Одно только оценочное минимальное количество неповторяющихся шахматных партий, вычисленное в 1950 году американским математиком Клодом Шенноном, составляет приблизительно 10¹¹⁸. Для сравнения — количество атомов в наблюдаемой Вселенной составляет по разным оценкам от 4×10⁷⁹ до 10⁸¹, то есть в 10⁴⁰ раз меньше числа Шеннона.

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

Какое место покер занимает на фоне других достойных игр? Возьмем для примера самую популярную на сегодняшний день разновидность покера — техасский холдем с лимитированными ставками. Лимитный холдем в силу ограниченных ставок весьма зависим от математики и хорошо подходит для алгоритмизации: для игры один на один в нем существует порядка 10¹⁸ игровых ситуаций. Если будем учитывать, что некоторые карточные комбинации эквивалентны между собой (например, два туза разной масти будут идентичны любой другой паре тузов), получим порядка 10¹⁴ различных игровых комбинаций. Для сравнения, в безлимитном холдеме их 10¹⁶⁰, а в игре «го» вариантов развития 10¹⁷⁰.

10¹⁴ — кажется, что это очень мало по сравнению с шахматами и куда более простыми английскими шашками. Сложность в том, что в покере игроки не знают карт оппонента, и не знают, какую комбинацию составят их собственные карты на следующем ходе.

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

Боты против человечества

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

В 1991 году в Альбертском университете (Канада) началась разработка программы Polaris, предназначенной для игры в холдем один на один. После 16 лет работы над проектом, представлявшим собой комбинацию нескольких покерных ботов, учитывающих целое семейство алгоритмов поиска равновесных стратегий, в 2007 году состоялся матч против нескольких покерных профессионалов. По условиям игры, человеку и компьютеру раздавали одни и те же карты, поэтому влияние случайности в игре свели к минимуму. Сначала Polaris ощутимо выигрывал, но после анализа нескольких партий игроки нашли повторяющиеся особенности игры программы и смогли победить.

В июле 2008 года Polaris смог наконец-то выиграть чемпионат между людьми и машиной. Общий счет сессий составил 3 победы, 2 поражения, 1 ничья. Однако эта победа не стала началом эры доминирования машин и гибели онлайн-покера. Как уже упоминалось, «машинный покер» играется при ряде ограничений, которые не соблюдаются в реальных онлайн-играх людей.

Первым серьезным испытанием для людей стал турнир 2015-го года, в котором четверым из ТОП-10 лучших игроков в техасский холдем противостояла программа Claudico. В соревновании Brains Vs. Artificial Intelligence люди оказались сильнее.

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

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

Машина зарабатывает в играх

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

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

В среднем, размер платы за игру в покер составляет 5 % и не может превышать 3–5 у.е. за 1 игру. Рэйкбэк является достаточно большой статьей прибыли для ботов: за счет него можно играть в 0 с людьми, но при этом зарабатывать за счет процентов от покер-рума. Наличие ботов, успешно играющих против новичков — это факт. Но они никак не влияют на глобальный рынок развития искусственного интеллекта.

Холистическая победа на поле неопределенности

После успехов Tartanian7 в университете Карнеги-Меллона приступили к созданию нового, гораздо более совершенного покерного бота — Libratus. В то время как программа DeepStack из конкурирующего Альбертского университета показала весьма неплохие результаты в предварительных тестах, Libratus в январе 2017 года выступил против настоящих покерных профессионалов. Вычисления в процессе разработки Libratus заняли 15 млн ядро-часов (Claudico обошлась 2–3 млн ядро-часов. В процессе игры Libratus использует мощности суперкомпьютера Bridges (1.35 петафлопс/сек).

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

11 января стартовал турнир, в котором Libratus суммарно играет 120 тыс. раздач в безлимитный техасский холдем один на один. Игра идет на виртуальные деньги, но приз за победу — 200 000 долларов — абсолютно реален для четверых профессиональных игроков в покер, двое из которых уже имели опыт игры против бота, выиграв в 2015 году у Claudico. Чтобы исход соревнований не оказался слишком случайным, каждый матч дублируется так, чтобы игрок А получал карты, которые получил компьютер в партии с игроком В и наоборот.

Libratus с самого начала вырвался вперед, в первый же день выиграв у людей, и более чем вдвое увеличив отрыв во второй. Чем дольше длится игра, тем больше ИИ получает информации об игроках, позволяющей ему становиться сильнее. Каждый раз, когда люди замечали недочеты в стратегии программы, она узнавала об этом, и корректировала свою игру на следующий день. В конце предыдущей недели Libratus уже выиграл почти 800 000 долларов. К 30 января выигрыш перевалил за миллион долларов.

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

Как на самом деле работает Libratus? Ответа на этот вопрос пока нет. Ученые не будут раскрывать секрет, каким образом выигрывает программа, как минимум до конца турнира. Мы знаем, что в основе программы лежит специально созданный алгоритм по вычислению оптимальных стратегий для игр с неполной информацией. Используется также новая технология достижения равновесия Нэша — стратегия, когда ни один из игроков не увеличит свой выигрыш изменив стратегию, если другой, в свою очередь, стратегию не меняет.

А не уничтожит ли Libratus онлайн-покер?

Стандартом для исследований является техасский холдем, однако использованные методы разработки не являются привязанными к одному виду покера. В целом создать подобного бота можно и для других видов (и не только), но самое главное — ученые получат действующий инструмент решения проблем в области неопределенности. А это не только большой класс других игр (человек до сих пор побеждает компьютер в первую часть StarCraft), но и множество реальных задач во всем мире.

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

Источники: