алгоритма Stockfish. В августе 2020 г. код Stockfish NNUE был объединён с основной веткой и стал официальной частью движка[1971].

Появление Stockfish NNUE свидетельствует о том, что шахматы, несмотря на распространённое мнение, по всей видимости, ещё далеки от «ничейной смерти», а существующие программы далеки от теоретического предела эффективности.

6.2.3.6 Игры с неполной информацией: карточные игры

Прогресс в игровом ИИ, наметившийся благодаря успехам в области глубокого обучения, затронул не только настольные игры. Фокус исследований постепенно стал смещаться в сторону игр с большими размерами поисковых пространств. Отдельной непростой задачей всегда было создание систем ИИ для игр с неполной информацией. В этих играх размер поискового пространства растёт за счёт того, что количество способов разрешения неопределённости может быть достаточно большим. В карточных играх вам почти всегда неизвестны карты противника, а значит, при полном переборе вы должны включить в рассмотрение все потенциальные сочетания карт, которые могут быть у него на руках. Поверье о том, что машины никогда не научатся блефовать, было, возможно, даже более распространено, чем поверье о том, что машинам никогда не удастся одолеть человека в го. Например, в телесериале «Звёздный путь: Следующее поколение» андроид лейтенант-коммандер Дейта, познакомившись с игрой в покер, изначально полагает, что игра достаточно проста и может быть освоена при помощи простой математической стратегии, однако сталкивается с большими трудностями, пытаясь постичь искусство блефа.

В 1920-е гг., когда фон Нейман впервые занялся вопросами теории игр, именно покер стал для него первым объектом исследования. Почему покер, а не шахматы, которые всегда считались стратегической игрой? Британский математик, биолог и историк науки Джейкоб Броновски приводит ответ фон Неймана на этот вопрос: «Нет‑нет, шахматы — это не игра. Шахматы — это хорошо определённая форма вычислений. Возможно, вы не сможете найти все ответы, но в теории должно быть решение, правильная процедура для любой позиции. Реальные игры совсем не такие. Реальная жизнь не такая. Реальная жизнь состоит из блефа, из маленьких тактик обмана, из вопросов себе о том, что другой человек думает о том, как я собираюсь поступить. И это как раз то, чем являются игры в моей теории»[1972].

Количество точек принятия решений в такой разновидности покера, как безлимитный техасский холдем один на один (Heads-up no-limit Texas hold’em, HUNL), превышает 10160 (для сравнения: количество игровых состояний в го составляет примерно 2,08 × 10170, а в шахматах — около 1047). Хотя HUNL и отстаёт от го по этому показателю на целых десять порядков, но на логарифмической шкале эти игры расположены фактически по соседству и на огромном расстоянии от шахмат.

В 2015 г. исследователи из канадского Альбертского университета в Эдмонтоне представили систему «Цефей» (Cepheus), предназначенную для игры в более простой вариант покера — лимитированный холдем один на один (Heads-up limit hold’em, HULHE). Вычислительно HULHE гораздо проще HUNL: в этой игре «всего» примерно 3,19 × 1014 точек принятия решений (1,38 × 1013, если убрать симметричные случаи).

Стратегия «Цефея» очень близка к равновесию Нэша для HULHE, поскольку математическое ожидание выигрыша оптимальной контрстратегии составляет только 0,000986 единицы ставки (так называемого большого блайнда, big-blind) за игру. Этот результат позволил создателям «Цефея» заявить[1973] на страницах журнала Science, что HULHE «по существу» решён (для того чтобы преодолеть дистанцию от решения «по существу» до полного решения, нужно уменьшить математическое ожидание проигрыша до нуля больших блайндов за игру).

Создатели «Цефея» так определили понятие игры, «решённой по существу» [essentially solved]: «Если игра в течение всей жизни не позволяет статистически достоверно отличить её от решённой с 95%-ной достоверностью». Под «игрой в течение всей жизни» в данном случае понимается игра со скоростью 200 игр в час по 12 часов в день без выходных на протяжении 70 лет.

«Цефей» стал детищем Исследовательской группы по компьютерному покеру (Computer Poker Research Group, CPRG), созданной в 1991 г., участником (до 2004 г. — руководителем) которой является хорошо знакомый нам создатель шашечной программы Chinook Джонатан Шеффер.

За время своего существования группа создала несколько сильных компьютерных программ для игры в техасский холдем. Первой из них стала программа Poki, в основу которой была положена симуляция игр методом Монте-Карло. В 2007 г. новая программа группы, Polaris, на конференции AAAI сыграла с двумя профессионалами-людьми: Филом Лааком и Али Эслами. Из четырёх матчей Polaris выиграл один, один свёл вничью и проиграл дважды; то есть в целом люди выиграли соревнование с небольшим отрывом. В 2008 г. обновлённая версия Polaris одержала победу над командой людей-профессионалов во втором соревновании по покеру между людьми и машинами.

В 2017 г. группа представила[1974] систему DeepStack, предназначенную для игры в HUNL. В качестве оценочной функции в этой программе используется глубокая нейронная сеть (семь слоёв по 500 нейронов, функция активации — PReLU — одна из модификаций ReLU с обучаемыми параметрами). Обучающая выборка для этой сети формировалась путём псевдослучайной генерации множества состояний игры (наборы карт, размер банка) с последующим их разрешением. Фактически нейронная сеть в DeepStack используется для аппроксимации результатов Монте-Карло-симуляций, что позволяет существенно сократить вычислительные затраты.

Для оценки силы игры DeepStack авторы программы использовали пул профессиональных игроков в покер, привлечённых для этой цели Международной федерацией покера. В пул вошли 33 добровольца из 17 стран. В общей сложности было сыграно 44 852 игры, при этом 11 игроков смогли выполнить просьбу организаторов и провести по 3000 игр. Итоговый выигрыш DeepStack составил 492 миллиблайнда (почти половина минимальной ставки) за игру, что составило более четырёх стандартных отклонений от нуля. Это означает, что можно с очень высокой степенью уверенности говорить о превосходстве DeepStack над противостоящим ему пулом игроков.

Если рассчитать результат только по тем игрокам, которые совершили по 3000 игр (11 человек), то DeepStack выиграл у них всех в среднем 429 миллиблайндов за игру, а если сделать поправку на фактор удачи, то победы над десятью игроками из одиннадцати были одержаны со статистически значимым преимуществом и лишь над одним — со статистически незначимым (70 миллиблайндов за игру).

В том же году система Libratus, созданная в Университете Карнеги — Меллона, уверенно одолела четырёх ведущих мировых игроков в HUNL[1975]. Матчи проходили в реальном времени в ходе 20-дневного турнира, а расчёты во время игры производились на новом суперкомпьютере Bridges в Питтсбургском суперкомпьютерном центре.

Наследником Libratus стала Pluribus — система, которая в 2019 г. смогла одержать победу при игре в HUNL с шестью игроками, играя против пяти игроков, входящих в состав мировой покерной элиты