В журнале Science вышла статья, где описывается принцип работы системы искусственного интеллекта Libratus. В начале года она победила в 20-дневном покерном турнире и выиграла у профессиональных игроков в покер фишек на сумму более 1,7 миллиона долларов.

Активное развитие технологий машинного обучения привело к созданию алгоритмов, которые справляются со многими задачами лучше людей. Особое внимание в этом году получили программы, которые научились обыгрывать людей в играх с неполной информацией — традиционно это считалось невозможным. В январе 2017 года система искусственного интеллекта Libratus победила в турнире по техасскому холдему, который сегодня считается наиболее популярной разновидностью покера. Во время турнира, который длился 20 дней, алгоритм заработал более 1,7 миллиона долларов в фишках. В новой статье Ноэм Браун (Noam Brown) и Туомас Сандхолм (Tuomas Sandholm), разработчики Libratus, описали, как работает алгоритм.

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

Чтобы научиться делать это, Libratus играл против самого себя, используя измененную версию алгоритма Monte Carlo Counter-factual Regret Minimization (MCCFR). С его помощью для каждого действия вычислялось значение сожаления — то, насколько игрок сожалеет о том, что он не сделал определенный шаг в прошлом. Во время симуляции MCCFR выбирал «исследователя», который должен был анализировать все возможные действия и постоянно обновлять значение сожаления. При этом его противник играл согласно стратегии, которая выстаивается на основе уже имеющихся данных. В конце «исследователю» давалась награда за каждое действие, благодаря которой он понимал, какой ход был хорошим, а какой — нет. После каждой партии игроки менялись ролями. В классическом варианте компьютер обычно исследует все гипотетические действия, чтобы выяснить размер награды за них; здесь же он пропускал «неинтересные» ходы, которые имели низкое значение сожаления, что позволило быстрее усовершенствовать его работу.

Для следующих этапов игры использовался второй модуль Libratus. Он создавал детальную стратегию для конкретного этапа игры, руководствуясь при этом плановой стратегией, разработанной в начале. Каждый раз, когда противник совершал не предусмотренное системой ИИ действие, она разыгрывала «мини-игру», где учитывался ход соперника. Это позволяло корректировать стратегию в режиме реального времени.

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

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

Значимая победа компьютера над профессиональными игроками в игре с полной информацией произошла в 2015 году: тогда программа AlphaGo обыграла Фаня Хуэя в го — настольной игре, где противники стремятся огородить наибольшую территорию на игровой доске с помощью камней черного или белого цвета. А уже в 2017 году усовершенствованная версия AlphaGo победила другого известного игрока, Ли Седоля, которого относят к сильнейшим в мире. Теперь AlphaGo Zero научилась играть и в другие настольные игры.

Автор: Кристина Уласович