AlphaZero. Нейронная сеть играет в шахматы

A0 относится к области обучения с подкреплением (по-английски reinforcement learning, RL).
Как правило, всегда выделяется среда которая взаимодействует как-то с агентом.
Аналогия из реальной жизни: среда - дороги с ПДД, агент - человек, который водит машину.

Для того чтобы обучаться, нужно задать среду и агента. В шахматах среду задать очень просто, закодить правила не составляет труда. В случае с дорогами наоборот, это сделать сложно. Проблемы в реалистичном описании среды - одна из причин, почему reinforcement learning пока редко встречается на практике.

Теперь про агента. Он в A0 состоит из 2 частей: нейронная сеть + алгоритм поиска. Нейронная сеть - это то что улучшается в процессе обучения, а алгоритм поиска MCTS был известен науке давно, он здесь фиксирован.
Каждая возникающая позиция в процессе поиска оценивается нейронкой ровно 1 раз. Алгортим MCTS занимается всем остальным, т. е. выбирает следующую наиболее "интересную" позицию для оценки нейронкой и затем уточняет промежуточные результаты для некоторых уже оцененных позиций.

P. S. Вот пример как люди оригинально попытались подойти к проблеме реалистичного описания среды, чтобы научить компьютер водить: они просто взяли игру GTA 5.
https://www.youtube.com/watch?v=rvnHikUJ9T0
Можете посмотреть что получилось

Как улучшить игру движка при помощи нейронной сети (ИНС - искусственная нейронная сеть). Полная аналогия с адвансом.

1. берём шахматный движок.
2. Берём первые линии, примерно одинаковые по оценке ходы.
Например,
Ход Лf1 - e1 имеет оценку 0.34
Ход Лa1-d1 имеет оценку 0.32
3. Оба хода предлагаем для анализа ИНС. По сути -речь идёт о статистическом анализе.
4. ИНС видит, что у чёрных слон на c5, у белых пешка на f2 и король на g1. В таких позициях статистически ладью на f1 лучше оставить, если есть другие схожие ходы. ИНС хорошо видит статистику.
5. ИНС принимает решение - снизить оценку ходу Лf1-e1 до 0.3 и повысить оценку ходу Лa1-d1 до 0.35
6. Принимается решение сделать ход Ла1-d1
7. Тактика при этом не ослабевает, она вся рассчитана на первых двух пунктах обычным движком.

Итог:
если говорить о том, что Шахматный движок + ИНС сильнее, чем просто шахматный движок - то ДА, это возможно на сегодняшний день. Для этого ИНС не нужно иметь возможность научиться ходить ладьёй. Зато мы имеем дело с добавлением обучаемой интуиции в классические переборные шахматные алгоритмы.

Пробуем один Dense слой с одним выходом, у которого все веса равны единице без активации. Тогда
result = 1*x1 + 1*x2 + 1*x3 + 1*x4 + 1*x5 + 1*x6 = x1 + x2 + x3 + x4 + x5 + x6
В точности требуемое вами поведение.

Как обучить такую нейросеть? По сути надо много-много примеров ходов с оценками Stockfish и изменение оценки на выходе.Возникает вопрос, откуда это брать?

Кроме того, как показывает практика, AlphaZero намного сильнее в оценке динамики на много ходов за горизонтом Stockfish, посему оценку некоторых ходов придёться менять значительно.

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

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

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

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

Я прошу прощения. Это больше матметоды
Надо формализовать задачу как c = F(a;b), где F - искомая функция.
Если мы ищем функцию, например, умножить (а;b), то она с высокой долей вероятности найдется с помощью регрессионного анализа. Например, с помощью метода наименьших квадратов - это даже я знаю. И тогда 2500+1200 будет вполне себе нормальный результат.

Вон на хабре пример находится
https://habr.com/post/307004/

Можно искать вещи более сложные, с помощью разложения функции в ряд Тейлора или Фурье. Но это уже чуть-чуть матана надо.

И вообще по запросу "регрессионный анализ нейронные сети" находится много чего. Например, нелинейные зависимости (не архисложно ни капли)

—- добавлено: 21 дек 2018, опубликовано: 21 дек 2018 —-

P.S ВСЕ элементарные функции можно представить в виде экспоненты или натурального логарифма на поле комплексных чисел. Погонять нейросеть на нахождение коэффициентов к этой функции - дело нетрудное...

Я краем глаза читал, что на вход нейросети подаются только последние 8 ходов без никаких тэгов «возможно»/«невозможно». А на выходе чуть меньше 10000 выходов, где перемешаны и возможные и невозможные ходы. Просто значения невозмных ходов игнорируются уже дальше алгоритмом игры.

—- добавлено: 21 дек 2018 —-

Например, строим LSTM по всем игровым событиям

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

Это называется маскингом. Если бы там был какой-нибудь attention (механизм внимания), то это было бы разумно. Но его там нет, так что никаких масок на вход не подаётся.

Разработчики АльфаЗеро пишут следующее:

Только число возможных ходов в шахматной позиции не 1500, а 4672. Забыл уже за год цифру.

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

Кстати, ваше предложение насчет разного кодирования белопольного и чернопольного слона, в текущей архитектуре не понятно как реализовать. Насколько я понимаю на входе нейронной сети у АльфаЗеро и Лилы фигура вообще никак не кодируется, кодируются только возможные ходы этой фигуры. А ходы у белопольного и чернопольного слона одинаковые - по диагонали в четырех направлениях.

Так это выход нейросети, а не вход. Получаем на выходе распределение вероятностей для 4672 возможных ходов, которое потом используется в поиске.

Это вход нейросети: https://arxiv.org/pdf/1712.01815.pdf

Но выход нейросети такой же. Только на входе у всех возможных ходов стоят единицы. А на выходе вместо единицы какие-то значения рассчитанные нейронной сетью от 0 до 1. Для хороших ходов большие, для плохих - меньшие.

—- добавлено: 21 дек 2018 —-

Хотя для начала можно попробовать просто сделать слой, который будет задавать белая клетка или черная. Может этого хватит для того, чтобы нейронная сеть что-то начала понимать про разноцветность слонов.

Всё-таки это выход. Прочитайте внимательнее, про возможные ходы в input-е ничего не сказано.

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



Тут белую пешку c4 можно снять, можно оставить — список возможных ходов никак не измениться.

Подраздел, из которого взята цитата, начинается со слов: "The input to the neural network..." Input это что по-вашему? Вход или выход?

—- добавлено: 21 дек 2018 —-

Хороший вопрос. Вероятно потенциальные возможные ходы задают. С учетом рентгенов. То есть для клетки c4 в слое отвечающем на ход вперед на одну клетку будет стоять единица. А отличать реально возможные ходы от потенциальных нейронка сама учится.

А может вы и правы. Начинается подраздел:

То есть тут и о входе и о выходе идет речь. И цитата похоже к выходу относится.

Тогда я всё неправильно понимал. На входе именно шахматная позиция. Для каждой клетки 12 слоев указывают наличие фигуры (белая пешка, белый конь, белая ладья и т.д.). А как фигуры ходят нейронка сама учится.

Тогда идея с белопольным и чернопольным слоном легко реализуется. Просто количество слоев на входе для клетки увеличится с 12 до 14.

В Альфа Зеро выход задает все потенциально возможные ходы для всех фигур в шахматах. Шахматы игра простая, поэтому это всего 73 хода для каждой клетки. Для сравнения возьмем современную пошаговую игру с очками действиями Battle Brothers. У лучника есть способность быстрый выстрел на 6 клеток. Только эта способность даст нам порядка 168 возможных ходов. Кроме этого лучник может применить эту способность дважды за ход, а может сходить на 1 или 2 клетки и потом один раз выстрелить. То есть уже получается 20 (потенциально можно выстрелить один раз с 19 клеток плюс с исходной клетки можно выстрелить дважды) * 168 = 3360 возможных хода. И это только одна способность одного юнита. А юнитов в игре десятки и у каждого юнита способностей может быть много. А чтобы жизнь медом не казалось. Еще есть прокачка, например, прокаченный лучник стреляет уже не на 6, а на 7 клеток. И есть местность, например, каждая единица разницы в высоте стрелка и цели изменяет дальность выстрела на единицу. Также размер поля там не 8 на 8, а скажем 50 на 50.

Соответственно хоть разработчики Альфа Зеро и декларируют универсальность своего подхода, но как видим при попытке его использовать для более сложных игр объем выходного сигнала растет со страшной скоростью. И реально работать этот подход не будет.

Ну а в чём проблема делать один небольшой ход? Если лучник не потратил свои ходы действий — ход возвращается к нам.

Можно попробовать. Таким способом хотя бы от комбинаторики избавляемся. Но все равно вместо 73 возможных ходов получаются по меньшей мере многие тысячи. Подход Альфа Зеро очень плохо масштабируется.

Именно так - да, будет работать.Здесь есть одно принципиальное НО - если для ВСЕХ единиц была начальная выборка. "Догадаться" применять эту логику для других входов нейронка не сможет. Аналогично - если дать ИНС все возможные ходы ладьёй - она их выучит. а на стоклеточной доске уже не сможет ходить.

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

В чем смысл такого притянутого за уши определения? Во-первых на 100 клеточной сетка сможет ходить, просто наверняка ходы будут не далее + 7 клеток и то не факт. Во-вторых, а кого собственно волнует сетка наученная на 64 клетки и как она будет работать на 100 клетках? Для точных работ делают точные инструменты, которые наилучшим образом делают свою задачу, но глупо требовать от них идеальной работы в других областях. Мелкая пила перепилит любые мелкие сучки и доски без особого труда и ею удобно работать, но пилить ею толстенный дуб - можно, но глупо, нормальные люди берут мощную бензо или какую там подходящую.

Нет. Это я был не прав. На входе у Альфа Зеро просто шахматная позиция. Ходить фигурами она сама учится.

Правильно. На стоклеточной доске Альфа Зеро ходить ладьей не сможет. У нее нет логики.

—- добавлено: 22 дек 2018, опубликовано: 22 дек 2018 —-

На стоклеточной не сможет ходить. Под стоклеточную доску нужно будет размер матриц на входе и выходе менять. И это большая проблема на самом деле. Это означает, что изменение внешних условий требует перестройки нейронной сети и переобучения. А реальный мир в отличие от шахмат изменчив.

Кстати, интересный вопрос насчет шахмат Фишера. Насколько сложно научить Лилу делать рокировку согласно правилам Фишера? Если взять уже обученную версию нейронной сети, то ее достаточно немного дообучить или все сложнее?

Надо просто поправить генератор ходов, чтобы рокировка считалась допустимым ходом и выполнялась по правилам. А играть Lc0 сможет даже со старой сетью. Только слабее потому при обучении многие типы позиций просто не возникали, так что не мешало бы дообучить. Кто-то проводил эксперимент, когда просто в начальной расстановке поменял местами слонов и коней. Сила игры Lc0 упала сразу на 100-150 пунктов.

AlphaZero считает варианты? На сколько ходов?

Мы же только что установили, что в Альфа Зеро нет генератора ходов. Ходы делает самая нейронка. Нынешняя версия в шахматах Фишера вообще рокировать не будет. Что на самом деле логично, мы же ей никак не объяснили, что правила изменились. А интересно насколько полностью обученная сеть воприимчива к дообучению при изменении внешних условий.

Почему нет? На входе позиция, на выходе некоторые коэффициенты по одному на каждый из возможных ходов. А уже генератор ходов берёт только те выходы, которые отвечают легальным ходам.

Что в шахматах, что в реальном мире позиции (внешняя обстановка) меняются, а правила (законы природы) остаются неизменными. Реальный мир только сложнее.

Так с точки зрения нейронки обученной на классических шахматах рокировка по правилам шахмат Фишера это невозможный ход. Соответственно коэффициент там будет около нулевой. Генератор ходов (правильнее назвать его проверяльщик валидности ходов) ничем здесь помочь не может.

Что в мире шахмат,а он тоже относится к реальности,что в мире вообще один единственный закон,-побеждает сильнейший и это неизменно))