Ёжик в матане

Как алгоритм "Monte Carlo Tree Search" помог чистому шахматному ИИ стать чемпионом.
-------
После предыдущего поста про сверхсложные задачи для ИИ у меня возникла дискуссия с читателем Ежика по поводу шахматного ИИ. Мы пытались выяснить, использует ли Альфа-зеро — наилучший, на данный момент, шахматный ИИ — таблицы шахматных комбинаций для оценки позиции и выбора хода? В частности мы говорили о таблицах шахматных окончаний Налимова — использовала ли их нейросеть на этапе обучения игре в шахматы или нет?
Если ответить кратко, то мы этого не знаем. Потому что Дипмайнд — разработчик Альфе-зеро — не выложила в открытый доступ код алгоритма, а всего лишь опубликовала его описание в статьях.
Silver D. et al. (2016)
Mastering the game of Go with deep neural networks and tree search.
doi.org/10.1038/na...
Silver D. (2018)
A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play.
doi.org/10.1126/sc...
Как настоящие джентльмены, мы должны научным статьям доверять. Если так, то получается, что Альфа-зеро при рождении являла собой "tabula rasa" — чистую доску, на которой были записаны лишь правила шахматной игры и некоторые начальные оценочные функции. Всему остальному она научилась, сыграв сама с собой огромное количество партий.
А стать наилучшем ИИ по игре в шахматы, а также Го и другие игры, ей помог алгоритм Monte Carlo Tree Search (MCTS) — то бишь метод случайного поиска в дереве (если, конечно, я правильно перевел название алгоритма). Вот давайте его немного и рассмотрим.
--------
Как и все монтекарловские алгоритмы, MCTS до безобразия прост, эффективен, но требует невообразимого количества ресурсов для достижения хороших результатов.
Шахматный ИИ, как и человек, выбирает следующий ход, используя дерево ходов, возможных из текущей позиции. Так как возможных ходов обычно много, и на каждом следующем уровне количество ходов катастрофически увеличивается, то просчитать все варианты ходов не под силу никакому суперкомпьютеру. Поэтому шахматные алгоритмы используют различные приемы, оптимизирующие выбор наилучшего хода. MCTS как раз и является таким приемом.
-------
Представим каждую позицию узлом дерева. В его корень поместим текущую позицию. От нее проведем ветки к позициям возникающим после каждого хода, получив одноуровневое дерево с листьями.
А вот дальше мы не будем продолжать построение дерева от каждого узла, а выберем только один из листов случайным образом. А от него просчитаем партию до конца, каждый раз выбирая ходы случайным образом (вот он метод Монте-Карло!). В конце-концов мы получим какой-то исход, которому припишем целое число: -1 (проигрыш), 0 (ничья), 1 (выигрыш).
Запомним этот результат в листе (узле), с которого мы начали случайное построение дерева. И теперь опять случайным образом выберем один из листов, и от него просчитаем партию до конца, опять же случайным образом выбирая каждый ход.
После многократных повторений этой процедуры и пересчета значений в начальных узлах, мы припишем начальным ходам числовые значения — баллы, равные сумме реультирующих балов всех партий, построенных после этого хода случайным выбором ходов. Каждый балл, соотнесенный к общему количеству партий, покажет вероятность того, что данный конкретный ход приведет к выигрышу. Очевидно, чем больше случайных партий мы просчитаем, тем точнее эти веса будут отражать реальные вероятности выигрышей.

www.group-telegram.com/sa/math_hedgehog.com/1712

626 viewsJan 7 at 09:06

Как алгоритм "Monte Carlo Tree Search" помог чистому шахматному ИИ стать чемпионом.
-------
После предыдущего поста про сверхсложные задачи для ИИ у меня возникла дискуссия с читателем Ежика по поводу шахматного ИИ. Мы пытались выяснить, использует ли Альфа-зеро — наилучший, на данный момент, шахматный ИИ — таблицы шахматных комбинаций для оценки позиции и выбора хода? В частности мы говорили о таблицах шахматных окончаний Налимова — использовала ли их нейросеть на этапе обучения игре в шахматы или нет?
Если ответить кратко, то мы этого не знаем. Потому что Дипмайнд — разработчик Альфе-зеро — не выложила в открытый доступ код алгоритма, а всего лишь опубликовала его описание в статьях.
Silver D. et al. (2016)
Mastering the game of Go with deep neural networks and tree search.
doi.org/10.1038/na...
Silver D. (2018)
A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play.
doi.org/10.1126/sc...
Как настоящие джентльмены, мы должны научным статьям доверять. Если так, то получается, что Альфа-зеро при рождении являла собой "tabula rasa" — чистую доску, на которой были записаны лишь правила шахматной игры и некоторые начальные оценочные функции. Всему остальному она научилась, сыграв сама с собой огромное количество партий.
А стать наилучшем ИИ по игре в шахматы, а также Го и другие игры, ей помог алгоритм Monte Carlo Tree Search (MCTS) — то бишь метод случайного поиска в дереве (если, конечно, я правильно перевел название алгоритма). Вот давайте его немного и рассмотрим.
--------
Как и все монтекарловские алгоритмы, MCTS до безобразия прост, эффективен, но требует невообразимого количества ресурсов для достижения хороших результатов.
Шахматный ИИ, как и человек, выбирает следующий ход, используя дерево ходов, возможных из текущей позиции. Так как возможных ходов обычно много, и на каждом следующем уровне количество ходов катастрофически увеличивается, то просчитать все варианты ходов не под силу никакому суперкомпьютеру. Поэтому шахматные алгоритмы используют различные приемы, оптимизирующие выбор наилучшего хода. MCTS как раз и является таким приемом.
-------
Представим каждую позицию узлом дерева. В его корень поместим текущую позицию. От нее проведем ветки к позициям возникающим после каждого хода, получив одноуровневое дерево с листьями.
А вот дальше мы не будем продолжать построение дерева от каждого узла, а выберем только один из листов случайным образом. А от него просчитаем партию до конца, каждый раз выбирая ходы случайным образом (вот он метод Монте-Карло!). В конце-концов мы получим какой-то исход, которому припишем целое число: -1 (проигрыш), 0 (ничья), 1 (выигрыш).
Запомним этот результат в листе (узле), с которого мы начали случайное построение дерева. И теперь опять случайным образом выберем один из листов, и от него просчитаем партию до конца, опять же случайным образом выбирая каждый ход.
После многократных повторений этой процедуры и пересчета значений в начальных узлах, мы припишем начальным ходам числовые значения — баллы, равные сумме реультирующих балов всех партий, построенных после этого хода случайным выбором ходов. Каждый балл, соотнесенный к общему количеству партий, покажет вероятность того, что данный конкретный ход приведет к выигрышу. Очевидно, чем больше случайных партий мы просчитаем, тем точнее эти веса будут отражать реальные вероятности выигрышей.

BY Ёжик в матане