Как алгоритм "Monte Carlo Tree Search" помог чистому шахматному ИИ стать чемпионом

После предыдущего поста про сверхсложные задачи для ИИ у меня возникла дискуссия с читателем Ежика по поводу шахматного ИИ. Мы пытались выяснить, использует ли Альфа-зеро — наилучший, на данный момент, шахматный ИИ — таблицы шахматных комбинаций для оценки позиции и выбора хода? В частности мы говорили о таблицах шахматных окончаний Налимова — использовала ли их нейросеть на этапе обучения игре в шахматы или нет?

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

Silver D. et al. (2016)

Mastering the game of Go with deep neural networks and tree search.

https://doi.org/10.1038/nature16961

Silver D. (2018)

A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play.

https://doi.org/10.1126/science.aar6404

Как настоящие джентльмены, мы должны научным статьям доверять. Если так, то получается, что Альфа-зеро при рождении являла собой "tabula rasa" — чистую доску, на которой были записаны лишь правила шахматной игры и некоторые начальные оценочные функции. Всему остальному она научилась, сыграв сама с собой огромное количество партий.

А стать наилучшем ИИ по игре в шахматы, а также Го и другие игры, ей помог алгоритм Monte Carlo Tree Search (MCTS) — то бишь метод случайного поиска в дереве (если, конечно, я правильно перевел название алгоритма). Вот давайте его немного и рассмотрим.

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

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

Представим каждую позицию узлом дерева. В его корень поместим текущую позицию. От нее проведем ветки к позициям возникающим после каждого хода, получив одноуровневое дерево с листьями.

А вот дальше мы не будем продолжать построение дерева от каждого узла, а выберем только один из листов случайным образом. А от него просчитаем партию до конца, каждый раз выбирая ходы случайным образом (вот он метод Монте-Карло!). В конце-концов мы получим какой-то исход, которому припишем целое число: -1 (проигрыш), 0 (ничья), 1 (выигрыш).

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

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

Для улучшения точности MCST и экономии времени расчетов применяют несколько подходов. Например, распараллеливают процесс построения дерева. Либо выбирают новый ход не случайно, а на основе некоторой оценочной функции. Такую оценочную функцию может выдавать нейросеть, натренированная на реальных сыгранных партиях. То есть нейросети скармливают позиции из сыгранных игр и подстраивают ее веса так, чтобы она правильно предсказывала исход игры, возникшей из данной позиции. Именно такой подход использует Альфа-зеро — она оценивает позицию на доске и выдает распределение вероятностей выигрышей для каждого возможного хода. Только она не использует данные о ранее сыгранных партиях. Для обучения она играла сама с собой и самостоятельно строила свою оценочную функцию.

Более подробно о MCST и Альфа-зеро читайте в статьях:

Поиск по дереву методом Монте-Карло и крестики-нолики.

https://habr.com/ru/articles/330092/

Метод Монте-Карло для поиска в дереве.

https://habr.com/ru/articles/282522/

Monte Carlo Tree Search – beginners guide.

https://int8.io/monte-carlo-tree-search-beginners-guide/

A step-by-step look at Alpha Zero and Monte Carlo Tree Search

https://joshvarty.github.io/AlphaZero/

AlphaGo Zero explained in one diagram.

https://medium.com/applied-data-science/alphago-zero-explained-in-one-diagram-365f5abf67e0

Напоследок следует упомянуть проект Лила чесс-зеро (Leela Chess Zero).

https://en.wikipedia.org/wiki/Leela_Chess_Zero

Его инициатор — бельгийсикй программист Жан-Карло Паскутто. Он возмутился, что Дипмайнд не выложила код Альфа-зеро в открытый доступ, и решил самостоятельно воспроизвести методику, описанную в статье.

К сожалению, у него не было мощных суперкомпьютеров, способных быстро выполнять MCTS, а на своих ресурсах он бы обучал нейросеть играть в шахматы несколько тысяч лет. "Это слишком долго", — сказал Жан-Карло, и решил распараллелить задачу среди неравнодушных пользователей интернета. В результате появился открытый шахматный ИИ движок LCZero.

https://lczero.org

Вы и сейчас можете подключиться к обучению Лилы, зайдя на сайт проекта и загрузив на комп специальный клиент:

https://github.com/LeelaChessZero/lc0

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

Вопрос закрыт, имхо)

Источник: github.com

Комментарии: