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

А как 0 elo по random play соотносятся с обычным рейтингом? +4000 elo относительно random play это сколько?

 

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

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

Даёшь нейросеть в каждый дом)

 

1) У них был старый Stockfish 8;
2) Это не ошибки, а свойство алгоритма. Отсечения у SF очень качественное, но побочные эффекты имеют место быть, к сожалению.

 

https://www.dropbox.com/s/c70yzp7173bchmq/Leela.jpg
Вроде все-таки 4000

 

Самый слабый ход в партии 33... Bxd4.

 

таблицы, если есть, отключить

 

Слабый относительно чего?
У белых "с раздачи" (по лавинообразной нарастающей для человеческого понимания) инициатива, возможность жертвенной атаки, грандиозная компенсация, необъятный запас прочности (ничья в кармане), всю дорогу прекрасная оценка цепочек-связок фигур и их взаимодействия, удобные тропинки к выигранному эндшпилю, если не поддаться искушению ничьей...
А у черных? "Врожденная" неизлечимая болезнь — "думая" за противника, не видеть дальше собственного носа, спотыкаясь о вечный шах или вечное преследование (у соперника ничья в кармане, дальше и думать не надо, — он щедрый, поделится), смело, веря в непогрешимость своей оценки идти на убой мчаться за горизонт из проигранного дебюта в проигранный эндшпиль?
Шаг в направлении пропасти ищите раньше.

 

https://docs.google.com/spreadsheets/d/1QhYWYQvXBhI5eHJm45fvf97CaV2rRmgrATwVgBFGKoU/htmlview#
random play: -3451 elo, соотвественно сейчас Leela Zero играет примерно в силу 500 пунктов Эло.
Это по шкале, которую Гугл использовал в AlphaGo

 

Минимум в два. В шахматах основная масса рейтингов лежит в диапазоне 1300 - 2800, читай 1500 пунктов. В го один кю/дан это 100 пунков, есть 20 кю (при этом иногда вводят 30 кю, потому что недостаточно 20), есть девять данов и есть про-даны... Так что минимум 3000 пунктов, максимум 5000.

 

Почитав NS и других форумчан, пройдясь по ссылкам на А0, описания Альфа Го для чайников, а также посмотрев описание Монте-Карло (МК) для поиска по дереву,
прокрутив всё через белковую нейронную сеть (НС), пришёл к заключению
(конечно, здесь немало людей более сведующих в предмете, которые, надеюсь, делакатно макнут фейсом в анализы, если что не так):

1. А0 базируется на МК (что, конечно, не изобретение Гугла (Г)). Г сделал существенную техническую модификацию МК, переложив некоторую работу на НС.
Идея заслуживает внимания, но если оценить её научную ценность, я бы назвал как хороший диплом с рекомендацией в аспирантуру, для кандидатской маловато.
Детали будут ниже.

2. НС исследовались ещё когда родители основателей Г под стол пешком ходили, тут новизны нет. НС суть страшной силы арифмометр,
реализующий длинную арифметическую формулу, в которой исследуемая позиция выступает параметром, а коэффициенты получены при обучении сети.
Волшебным образом на выходе получается осмысленная цифирь, достаточно адекватно характеризующую позицию.

3. НС обучалось на играх, не использующих шахматных знаний, только по правилам игры. Это, конечно, круто, но идея, наверняка, не нова и, скорее всего, обкатывалась
на менее сложных играх. Заслуга Г в том. что они вложились в большую НС, мощностей которой хватило на такой эксперимент (конечно, контекст "опыта" даёт моральное
право усомниться, что обучение действительно проходило честно, с нуля, но, всё-таки, будем верить в лучшее).

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

Много это или мало? Каждый решает сам. На выходе, Г, заручишись форой (книга, старая версия, железо, контроль), обыграл самого Вяленого.

Теперь чуть подробнее о предметной части.

А. МК против альфа-беты (АБ). Альфа-бета, на мой непросвещённый взгляд, это алгоритм перебора, стартовавший с идеи "все ходы равны", и в процессе
своей эволюции пытался подстроиться под жизнь, перераспределяя ресурсы в пользу более важных продолжений.
МК изначально стоит на идее неравенства продолжений, и стремится направить поиск в русло наиболее важных продолжений. Почему АБ доминировал,
были ли на это объективные причины или просто все исторически стали топать, не оглядываясь. по дороге АБ, судить не берусь.

Б. Кратко описание МК.
У нас есть дерево перебора. Это дерево могло быть унаследовано от прошлого хода, если достигнутая (после ответа соперника) вершина уже исследовалась на предыдущем
ходу, или мы должны стартовать с нуля, если позиция вообще начальная, или мы ход соперника оценивали как слабый и не считали нужным копать в этом направлении.
"С нуля" - это просто просто дерево перебора на один полуход (в описаниях встречал 2, но логики необходимости 2 не почуял. Очередь хода? Не выглядит важным).

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

Процедура продолжается до тех пор, пока мы не достигли листа - конечной вершины дерева перебора.
Теперь стоит задача оценить этот лист.
В классическом МК для листа начинается случайная игра до конца партии, и, на основе этого движения лист оценивается.
Если выиграли, значит, дерево удлинняется в этом направлении, а оценки вышестоящих узлов корректируются (увеличиваются).
Если проиграли, дерево в этом направлении не расширяется, оценки вышестоящих уменьшаются.
В обоих случая, по пути обратно в начальную точку перебора обновляется и статистика посещений узлов.

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

В. Где порылась собака?

Гугл, вместо запуска случайной игры до конца в МК, просто использует в листе оценку, выдаваемую НС. Не бог весть как оригинально.
Эту идею можно реализовать и без НС.
Интереснее вопрос, насколько хороша ОФ, выдаваемая НС. Это предмет отдельного исследования.

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

Как-то так.

 

Я подозреваю, что практически любую задачу, решаемую с помощью НС, можно реализовать и без НС. Преимущество нейросетей - в универсальности. Они достаточно хорошо справляются с совершенно разными задачами.
Гугл всё же не шахматы пытается решить, и не Го, а создаёт ИИ. Думаю, с этой точки зрения универсальный алгоритм, способный самостоятельно освоить и очень хорошо играть в такие разные игры, как шахматы, го и сёги, это очень большой успех.

 

В программах на MCTS поиск не является изначально случайным. Это не модификация. Так-же как и в Альфе не рандомная PUCT, а небольшая рандомность внесена искусственно при выборе хода уже после построения дерева, так и в других программах на MCTS/UCT - нет рандомности.

 

MS,
Гугл, конечно быстрее всех подсуетился, это да. Но с другой стороны они выполнили объём работы лет на пять вперёд "за нас". Читая мнение специалистов, у меня сложилось впечатление, что основная новинка для них, это новый подход к использованию reinforcement learning. По крайней мере разница между его реализациями в АльфаГоФан и АльфаГоЗеро заметна. Передача способа выбора хода от специальных правил к нейросети, по моему мнению, тоже очень важная и достаточно не очевидная вещь. Особенно для го. Когда можно за долю секунды "интуитивно" выделить три-четыре перспективных варианта из 200 возможных, это имеет огромное значение.

В пользу Гугла ещё можно сказать, что за настольные игры можно было взяться ещё в 2012 году, но желающих было мало, пока Гугл наглядно не продемонстрировал открывающиеся возможности. Среди методов, которые использовал Зеро, большинство сейчас действительно уже общее место, но не стоит забывать, что ещё три года назад не были известны ни residual-блоки, ни батч-нормализация, ни инициализация Ксавье для полулинейной функции активации. Существовала только L2 регуляризация.

 

Ха-ха, вы не поверите, но самая первая работа в этом направлении как раз была дипломной :
Christopher Clark. Deep Go, 2014

 

https://habrahabr.ru/company/wunderfund/blog/315476/
https://habrahabr.ru/post/303196/
https://habrahabr.ru/company/mailru/blog/311706/
https://logic.pdmi.ras.ru/~sergey/teaching/dl2017/

 

Покадрово несколько закадровых красот, проявившихся в анализе:




Есть желающие защищать Stockfish'ем такие позиции?

 

https://docs.google.com/spreadsheets/d/1QhYWYQvXBhI5eHJm45fvf97CaV2rRmgrATwVgBFGKoU/htmlview#
Нормальный, "человеческий" рейтинг программ в ГО

Code:

AlphaGo Zero  5185
Ke Jie        3640
AlphaGo Fan   3144
Zen-15.5-2c1g 2856
Zen 5 6d      1888
Pachi 2d      1298
GnuGo 5k       431

текущий рейтинг Leela Zero
808ac5f3       358

 

Сказочный сон золотой вяленой рыбки:

23... Kg7!? 24. hxg5 Nd7!? 25. Qh4?! fxg5! 26. Bxg5 Bxg5
27. Qxg5+ Kh8 28. Rxd7 Bxd7 29. Re7 Qxc3 30. Rxd7 Qa1+ 31. Kh2 Rxf2

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

Так-то уж "большая дорога" куда приятнее для черных!

 

AlphaZero — Stockfish 8
(позиция из анализа)

Интересно, что бы тут могли наковырять белые для притяжения к их игре широких масс?
Ну или вот в такой:

 

Тут у программ рейтинг честный, привязан к реальному рейтингу Ke Jie - 3640
А кю/дан - с KGS. Завышенный.

 

Думаю, никто отрицает, что результат есть. Вопрос в том, чтобы правильно его оценить.

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

 

Я думаю, адвансер может усилить игру Стокфиша в новоиндийской партии с жертвой фигуры. Причина поражения Стокфиша: его ладья a8 и конь b8 были вне игры. Оценки Стокфиша для таких позиций ненадёжны, т.к. это обстоятельство сказывается нескоро, где-то за горизонтом расчёта. Усилить игру Стокфиша = развить коня b8 так, чтобы оценка не испортилась. После этого оценкам проги можно верить, т.к. долгосрочный, непонятный ей момент исчезает. Если она при развитом коне поставит оценку 0.00, то это действительно 0.00.

Первый напрашивающийся момент, когда можно было развить коня:

Предлагаю 23... Nd7(!) вместо исполненного в партии 23... b5(?). Глубоко не анализировал, но сомневаюсь, что за белых тут что-то найдётся. У них будет несколько пешек за фигуру, но у чёрных всё развито, такие позиции топ-движки оценивают трезво. Кто-то может найти тут перевес за белых против Стокфиша на своём компе, которому даётся, скажем, полчаса на партию?

Может быть, коня можно было развить позже, хотя я навскидку не вижу где. Тогда, наверное, ошибка с 23-го хода перекочёвывает туда.

Смущает 24. Be4 - выйдет ли там конь? Или получится как в партии, когда Стокфиш ставит нолики, но через десяток ходов обнаруживает, что ему "почему-то" плохеет? Хотя, возможно, и обойдётся - глубоко не копал. Тогда это ещё один способ удержать партию.

 

Очень интересно было бы посмотреть на ничейные партии. Во всех ли партиях SF отбивался или все-таки А0 приходилось кое-где спасаться?

 

Забавно было бы, если везде))

 

Стокфиш так сильно отбивался, что Альфа не во всех партиях спаслась...

 

Есть достаточно стандартная UCT формула. в которой вес каждого хода равен
Eval(move)+c*UCT_Value(move)
Это не значит что всегда будет делаться ход с большим Eval(move) - оценкой после хода, это значит что при прочих равных он будет сделан когда в узле появились в первый раз, и будет делаться чаще остальных при одинаковой статистике.
Естественно для получения "хорошего" Eval , и можно использовать, и давно уже используют нейросети. И в этом решении нейросеть напрямую участвует в выборе хода.

В Альфе, грубо говоря - другая формула. PUCT
Eval(move)+c*P(move)*UCT_Value(move)
где P - вероятность того что ход в этой позиции сильнейший. И в этом решении нейросеть напрямую участвует в выборе хода. И в этом решении не всегда в позиции будет выполняться ход с большим Eval(move) и/или P(move).

То есть нейросеть и раньше, до Альфы, участвовала в выборе хода.
Eval(move) - уже давно считают с использованием нейросетей. Использование нейросетей для получения P(move) - возможно впервые появилось в Альфе.

 

Спасибо за постик!
Как приятно осознавать, что не одинок во Вселенной!..
Я, конечно, не о глубине борозды и не о возрасте коней!
Рекомендую пройтись по моим выкладкам здесь на Форуме, многие заданные Вами вопросы прояснятся-отпадут.
Полный анализ партии публиковать не буду, если только совсем уж меня не перемкнет после очередной (шквала, правда, почему-то не наблюдалось) текстовой и/или ютубовской халтуры какого-нибудь очередного (имя им легион) мэтра.
Лень стало представителям нашего рода своими мозгами думать!