Libratus и «непопулярная» лучшая диссертация NIPS 2017
Libratus — это компьютерная программа с искусственным интеллектом, предназначенная для игры в покер, в частности, в безлимитный техасский холдем. Его создатели, профессор Туомас Сандхольм и его студент Ноам Браун из CMU, намерены сделать его похожим на другие приложения, не относящиеся к покеру.
В январе 2017 года Libratus сразился с четырьмя профессиональными игроками в покер, ловко обыграв их всех и выиграв почти все фишки в игре. Затем, в ноябре 2017 года, статья, написанная в соавторстве с Ноамом Брауном и Туомасом Сандхольмом, «Безопасное и вложенное решение эндшпиля для игр с несовершенной информацией», получила награду NIPS 2017 за лучшую диссертацию.
Тем не менее, этот тезис не вызвал особенно бурных споров среди китайских экспертов по искусственному интеллекту. Возможны три причины отсутствия энтузиазма:
- Значительное количество математического жаргона. Весь раздел статьи полностью занят определениями математических символов. После того, как математические определения закончились, оставшаяся часть статьи представляет собой длинное доказательство теоремы. При первом чтении диссертация кажется бесконечным туманом математики.
- Отсутствие популярной темы. В настоящее время две горячие темы в области машинного обучения — это глубокое обучение и обучение с подкреплением. Тем не менее, основными темами этой статьи являются теория игр и исследование операций.
- Универсальность методологии. У некоторых читателей сложилось впечатление, что алгоритм Libratus можно применить только к техасскому холдему или, в лучшем случае, его можно распространить на другие настольные игры. Читатели считают, что алгоритм имеет ограниченные перспективы применения.
8 ноября 2017 года у меня была возможность встретиться с профессором Туомасом Сандхольмом на конференции AI World 2017, организованной AI Era, где он выступил с программной речью. Разговаривая за ужином, профессор Сандхольм объяснил мне, что с точки зрения применения алгоритм Libratus не ограничивает приложение только азартными играми. Пользователи могут использовать его для переговоров, аукционного ценообразования, принятия инвестиционных решений и многого другого.
Изображение 1. 8 ноября Туомас Сандхольм (в центре) прибыл в Пекин для участия в AI World 2017. Он находится с основателем и генеральным директором AI Era Ян Цзином (слева) и автором этой статьи доктором Дэн Каном.
Понимание методологии алгоритма Libratus
С точки зрения методологии алгоритм Libratus представляет собой сочетание теории игр и исследования операций. Марковский процесс принятия решений и динамическое планирование составляют теоретическую основу обучения с подкреплением. Несмотря на то, что источники разные, в конечном итоге они сойдутся.
Я считаю, что столкновение алгоритма Libratus с обучением с подкреплением и глубоким обучением станет удивительным шагом вперед для ИИ.
Джон фон Нейман однажды сказал: «Жизнь не похожа на го, где вы можете видеть все части на доска. Реальная жизнь полна блефа, обмана и домыслов о том, что происходит в умах других. Это теория игр, которую я изучаю».
Четыре ключевых понятия Libratus Thesis
Чтобы понять документ Libratus, вам нужно понять четыре ключевые концепции.
- Стратегия равновесия Нэша
- Контрфактический лучший ответ
- Абстракция
- Конец игры
В следующих разделах я описал эти четыре компонента тезиса Libratus.
Стратегия равновесия Нэша: не давайте противнику легких побед
Libratus в настоящее время может играть в покер только вдвоем. Однако будущие улучшения алгоритма и добавление большего количества графических процессоров могут позволить ему играть против нескольких противников одновременно.
При игре в техасский холдем каждому игроку сначала раздается рука из двух карт, а затем покерный дилер последовательно открывает еще пять карт. Есть четыре раунда ставок, после которых игроки сравнивают свои руки, чтобы увидеть, кто выиграет.
Изображение 2. Игра в покер техасский холдем
Угадать две карты в руке оппонента может быть очень сложно. Общедоступная информация включает в себя пять общих карт, а также историю ставок обеих сторон. Однако ваши оппоненты не обязательно будут делать ставки строго в соответствии со своей рукой. Вместо этого они будут смешивать тактики, предназначенные для того, чтобы обмануть вас.
Как Libratus определяет стратегию ставок своего оппонента?
На самом деле Libratus не спекулирует на стратегии ставок своего оппонента.
Чтобы быть более конкретным, единственная цель Libratus — достичь стратегии равновесия Нэша. Нэш был известным математиком и героем фильма «Игры разума». Цель стратегии равновесия Нэша состоит в том, чтобы не дать вашему противнику легких побед.
Стратегия равновесия Нэша — это стратегия пассивной защиты, а не стратегия активного нападения. Он не пытается спекулировать на стратегии оппонента.
Например, если стратегия оппонента состоит в том, чтобы слепо и бездумно уравнять вашу ставку, несмотря ни на что, равновесие Нэша предписывает вам не повышать ставки, когда наша рука хорошо, чтобы воспользоваться стратегией вашего противника. Он делает это после того, как сыграет несколько рук, в которых узнает план игры вашего оппонента.
Но что мешает вашему оппоненту найти уязвимости в стратегии равновесия Нэша? Теоретически Стратегия равновесия Нэша гарантирует, что после того, как вы сыграете несколько рук и устраните потенциальные факторы удачи, у противника не останется абсолютно никаких уязвимостей, которые можно было бы использовать.
Вопрос в том, строго ли Libratus придерживается стратегии равновесия Нэша. Цель математических доказательств, занимающих такой большой раздел этой статьи, состоит в том, чтобы доказать, что, по крайней мере, в техасском холдеме один на один алгоритм Libratus является близким приближением к стратегии равновесия Нэша.
Как найти наиболее оптимальную стратегию ставок?
Поскольку стратегия равновесия Нэша не пытается определить стратегию оппонента, мы можем использовать рекурсивную машинную теорию игр для анализа всех возможных комбинаций рук и поиска наилучшей возможной стратегии ставок.
Чтобы определить наиболее оптимальную стратегию ставок, начните с создания таблицы ставок с семью столбцами и несколькими строками.
Столбец 1: Две карты в нашей руке.
Столбец 2: Общие карты, уже лежащие на столе, из которых не более пяти.
Столбец 3: История ставок каждой стороны
Столбец 4: Разместите все оставшиеся фишки. Мы можем использовать третий столбец (история ставок) для расчета значения в четвертом столбце (наши оставшиеся фишки). Четвертый столбец включен просто для удобства.
Столбец 5: Две карты в руке нашего противника
Столбец 6: Фишки, которые мы планируют делать ставки в следующем раунде
Столбец 7: ожидаемая прибыль от стратегии в шестом столбце.
Первые четыре столбца — это входные данные, называемые в статье «ситуацией» (Information Set, InfoSet). Последние три столбца являются выходными данными, а именно оценкой скрытой информации, стратегией и прогнозируемой выгодой.
При наличии достаточной вычислительной мощности мы сможем рассчитать все возможные ситуации (InfoSet).
- Столбец 1, наша рука (префлоп) имеет (5252)/(21) = 1326 возможных комбинаций.
- Столбец 2, первые три общие карты, имеют (504948)/(321) = 19 600 возможных комбинаций. Затем идут следующие две общие карты (терн и ривер). В сумме получается 19 600 + 19 600 47 + 19 60047 * 46 = 43 316 000 возможных комбинаций.
Если мы сложим возможные комбинации в первом и втором столбцах вместе, мы получим в общей сложности 1 326 * 43 316 000 = 57 437 316 000 комбинаций.
Возможных комбинаций значений в третьем столбце, истории ставок, еще больше. Это означает, что таблица очень большая, фактически 10165 строк в дипломной работе. Этот объем данных просто слишком велик. Даже с помощью самого мощного компьютера, доступного в настоящее время, обработка всех чисел заняла бы несколько десятилетий.
Однако, если бы у нас было достаточно вычислительной мощности для обхода таблицы, мы могли бы рассчитать среднюю прибыль от каждой стратегии ставок для каждой комбинации карт. Например, после того, как участники открыли пятую общую карту (ривер), рука оппонента могла составить одну из (4544)/(21) = 990 комбинаций карт. Кроме того, первые три раунда ставок (префлоп, флоп, терн) могут принимать любую из N различных форм. В этот момент, во время нашего раунда ставок, каждая стратегия ставок, например, ставка ва-банк, может принести одну из 990N возможных прибылей. Среднее значение этих 990 N значений прибыли является средним значением стратегии ставок.
Столкнувшись с определенной комбинацией карт, мы можем затем рассчитать среднюю прибыль от каждой возможной стратегии ставок и выбрать стратегию с самым высоким средним значением. Вы, должно быть, задаетесь вопросом, является ли стратегия ставок с самой высокой средней прибылью стратегией равновесия Нэша? Нет, это не так.
Почему? Видите ли, если рука нашего оппонента слабая, например, тройка червей и шестерка треф, то шансы на то, что он поставит крупную сумму, довольно малы.
Тогда как мы должны рассчитать вероятность стратегия ставок оппонента?
Эта проблема усложняется тем, что оппонент определяет свою стратегию ставок не только своими картами и общими картами, но и нашей историей ставок и своей оценкой наших карт.
Контрфактический лучший ответ: популярный алгоритм поиска стратегии равновесия Нэша
Counterfactual Best Response (CBR) — это алгоритм поиска стратегии равновесия Нэша, который в последнее время пользуется большой популярностью.
В Counterfactual Best Response есть три основных элемента:
- Моделирование
- Сожалеть
- Итерация
Перед лицом игровой ситуации (InfoSet) или данных в первых четырех столбцах нашей таблицы ставок мы начинаем с предположения, что мы используем случайный подход с равной вероятностью для выбора нашей стратегии ставок. Мы используем этот метод, когда проходим серию циклов торговли и ставок, рассчитывая наши выигрыши или проигрыши после каждого раунда.
После нескольких миллионов раундов мы уже охватим широкий спектр игровых ситуаций.
Затем мы вступаем в фазу сожаления. Сожаление относится к ситуации, когда мы прекращаем использовать случайные ставки и вместо этого выбираем конкретную стратегию, например, уравнивание ставки оппонента в каждой игровой ситуации.
Эта фаза также включает в себя определенную игровую ситуацию или установленное значение для каждого из четырех столбцов в нашей таблице ставок. После раскаяния следующие открытые общие карты не меняются. Однако и наша стратегия ставок, и стратегия ставок нашего оппонента меняются.
Затем мы повторно моделируем предыдущие раунды. Во время повторной симуляции руки обоих игроков, карты на столе, их порядок сдачи и ставки до фазы сожаления остаются неизменными. Тем не менее, ставки после фазы сожаления действительно меняются. На каждом этапе ставок, кроме стратегии, указанной на этапе сожаления, другие стратегии ставок остаются неизменными.
Как только это моделирование завершено, мы можем рассчитать среднюю прибыль от стратегии сожаления.
Двигаясь дальше, переключитесь на другую стратегию сожаления, которую можно использовать в той же игровой ситуации. Например, если в предыдущей фазе сожаления использовалась стратегия колла, то для следующей симуляции мы могли бы переключиться на стратегию рейза и повторно смоделировать предыдущие игровые ситуации. Таким образом, мы можем рассчитать среднюю прибыль для второй стратегии сожаления.
После запуска достаточного количества этих симуляций мы можем рассчитать среднюю прибыль для каждой стратегии сожаления в различных игровых ситуациях. Затем мы повторяем описанный выше процесс, чтобы подтвердить результаты различных стратегий.
Наконец, мы используем эти данные для обновления таблицы ставок (отображение действий). Чтобы использовать данные, начните с очистки пятого столбца в таблице, убедившись, что вы не считаете две карты в руке противника. В седьмой столбец введите среднюю прибыль по каждой стратегии ставок.
Это был первый раунд симуляции и сожаления. Затем мы начинаем второй раунд симуляции.
Во время второго раунда моделирования мы сначала предполагаем, что противник все еще использует вероятность случайного равенства для выбора своей стратегии ставок. Затем мы выбираем нашу стратегию ставок в соответствии с обновленной таблицей ставок.
Когда мы сталкиваемся с новой игровой ситуацией или другими значениями в первых четырех столбцах, мы используем следующий метод для выбора стратегии ставок:
- Мы начинаем с поиска всех соответствующих строк в нашем обновленном столбце ставок в соответствии со значениями в первых четырех столбцах, которые представляют текущую ситуацию.
- В нашей обновленной таблице шестой столбец — это стратегия ставок, а седьмой столбец — средняя прибыль по каждой стратегии. Затем мы переходим к выбору стратегии ставок в соответствии со средней прибылью. Чем выше средняя прибыль, тем выше вероятность того, что мы выберем соответствующую стратегию ставок.
Теперь, когда мы определили руки, порядок раздачи и начальную историю ставок игроков для второго раунда симуляции, мы можем начать фазу сожаления. Следующим шагом является создание еще одной записи таблицы ставок с соответствующей ей стратегией ставок и средней прибылью при различных игровых ситуациях.
В третьем раунде симуляции мы используем вторую версию таблицы ставок, а оппонент использует первую версию. После нескольких раундов моделирования мы можем сгенерировать нашу третью таблицу ставок.
Последний этап заключается в повторении этого процесса снова и снова. После нескольких итераций моделирования таблица ставок, с которой мы остаемся, будет близким приближением к стратегии равновесия Нэша.
Упростите игровую ситуацию, чтобы свести к минимуму требуемую вычислительную мощность
Как мы упоминали в предыдущем разделе, только два столбца в таблице ставок содержат максимум 57 437 016 000 различных комбинаций значений. Добавление всех возможных комбинаций истории ставок приведет к 10165 возможным комбинациям значений.
Кроме того, мы должны выполнить несколько миллиардов симуляций, когда используем контрфактический лучший ответ для поиска стратегии равновесия Нэша.
Огромный объем данных в таблице ставок в сочетании с миллиардами симуляций, необходимых для метода контрфактического наилучшего ответа, означает, что весь процесс требует абсурдного количества вычислительной мощности, которую было бы в лучшем случае невероятно сложно произвести.
Одним из очевидных решений было бы создание меньшего стола для ставок путем упрощения игровой ситуации посредством абстракции.
Например, представьте, что у вас есть две пары. Одна пара — это восьмерка червей и восьмерка пик, другая пара — восьмерка бубен и восьмерка треф. Для целей покера они равноценны. Таким образом, мы можем взять каждую комбинацию из двух восьмерок, (43)/(21) = всего 6 комбинаций и сжать их в одну строку в таблице ставок.
Однако расчеты значений карт должны быть четкими. Например, является ли пара восьмерок более ценной, чем восьмерка и девятка? Предполагая, что 5 общих карт оказались 7, 10, валет и две нерелевантные карты, вы можете объединить 8 и 9 с общими картами, чтобы создать стрит от 7 до валета. В то время как пара восьмерок по-прежнему остается парой восьмерок.
Изображение 3. Ценность пар зависит от ценности карт.
Следовательно, когда мы вычисляем ценность пары карт, мы не можем просто смотреть на их собственную внутреннюю ценность, но также должны учитывать их ценность в сочетании с общими картами после того, как эти карты будут раскрыты.
Мы должны абстрагировать не только значения карт, но и ставки. Вы можете сделать это, сведя их к четырем типам — «фолд», «колл», «рейз» и «олл-ин». После прохождения этого процесса абстракции количество комбинаций данных в нашей таблице значительно сокращается. Как только мы сократим объем данных, с которыми нам нужно работать, расчет контрфактического наилучшего ответа станет гораздо более возможным.
Эндшпиль, проблемы вне дерева и повторное решение
Упрощение игровой ситуации также может привести к просчетам. Например, мы можем ошибочно приравнять пару семерок к паре восьмерок. Как бы то ни было, если обе стороны продолжают делать ставки и ни одна из сторон не сбросит карты, их карты неизбежно будут показаны, и в этот момент пара семерок проиграет паре восьмерок, даже если разница между ними невелика. Это то, что мы называем проблемой вне дерева.
Когда мы сталкиваемся с проблемой вне дерева, мы можем решить ее, заменив абстракцию разрешением.
Основная концепция разрешения заключается в том, чтобы перевернуть истории ставок игроков, чтобы они соответствовали данным о руке оппонента и ее вероятности.
Например, если вы представляете свою руку как h1, а h2 представляет руку вашего оппонента. Кроме того, оба игрока делают ставки, используя стратегию Counterfactual Best Response. Затем мы можем рассчитать вероятности различных ставок, просматривая соответствующую информацию в нашей таблице ставок.
Если наша рука на префлопе — пара восьмерок, а рука оппонента — пара тузов, то вероятность того, что мы сделаем рейз в первом круге торговли, достаточно высока, а вероятность выигрыша близка к нулю. выигрыша нашего соперника намного выше.
Теперь, учитывая конкретную историю ставок, мы можем использовать таблицу ставок для расчета вероятности различных стратегий ставок на следующем шаге. История ставок — это просто серия ставок, а вероятность истории ставок — это произведение серии вероятностей.
Вычисляя вероятности истории ставок, мы можем не только оценить карты в руке нашего оппонента, но также мы можем рассчитать степень отклонения между оптимальной стратегией ставок нашего оппонента и его реальной стратегией. Мы можем рассчитать вероятность того, что наш оппонент блефует.
Как только мы угадали карты нашего оппонента и вероятность того, что он блефует, ре-решение в конце игры становится довольно простым. На самом деле это не что иное, как сравнение нашей руки с рукой оппонента, расчет наших шансов на победу, а затем использование этих данных для определения суммы ставки.
Вывод
Внедрение такой системы ИИ, как Libratus, является одним из многих способов, с помощью которых ИИ меняет наше понимание человеческого интеллекта. Я надеюсь, что эта статья помогла вам понять, как работает Libratus, и он сможет превзойти своих конкурентов. Я уверен, что со временем мы увидим подобные программы и для других игр.
Ссылка:
