Краткое введение: от Minimax до AlphaZero, путь полной информационной игры (1)

Последняя редакция: 12-15 14:35, исправлены некоторые опечатки и неправильные предложения, исправлено сравнение шахматной мощности между Мастером и Зеро, а также дополнена таблица Эло и диаграмма энергопотребления каждой версии AlphaGo.

Эта статья начинается с алгоритма Минимакс и продолжается до последних версий AlphaGo Zero и AlphaZero, и ее целью является представить алгоритмы, которые люди придумали для полных информационных игр, и идеи, лежащие в их основе. В этом посте также будут освещены мысли и детали серии DeepMind Alpha, а также предложены личные размышления по определенным вопросам.

Говорят, что DeepMind недавно сделал большие новости.Они использовали ту же структуру алгоритма, полностью аналогичную AlphaGo Zero, для решения многих сложных шахматных задач, включая шахматы, без человеческих шахматных данных. сильнейший фрейм (шахматы не проигрывают даже 100 партий подряд, и это ясно отражает огромный разрыв, вызванный предыдущими ходами).

Они назвали фреймворк AlphaZero, что просто на один Go меньше, чем AlphaGo Zero. AlphaZero подтвердила, что подход ResNet + MCTS применим не только к Go, но и к большинству игр, в которых люди могут управлять игрой.

На данный момент мы можем считать, что простая проблема игры с полной информацией в основном решена AlphaZero (ввиду массивности игры, решить ее полностью почти невозможно, но возможно решить в той мере, в какой это возможно). что люди "не могут понять, что они делают". , решение выше этого уровня на самом деле не имеет особого практического значения, поэтому не будет преувеличением сказать "базовое решение").

Точнее, AlphaZero решает проблему «игры двух игроков с полной информацией и нулевой суммой в конечном состоянии».

Примечание. Стандартный термин — «ограниченная стратегия», но лично я считаю, что для большинства современных шахматных игр более подходящим может быть «конечное состояние», поскольку «конечное состояние» включает в себя ограниченные стратегии, и, исходя из этого, большинство шахматных игр Дополнительные правила можно использовать для ограничения количества ходов (например, в го используются различные правила ко для предотвращения повторения состояний, в то время как в шахматах есть аналогичные правила для предотвращения повторения или определения ничьих).

Здесь мы разбираем некоторые версии программного обеспечения, которые будут упомянуты позже:

Вяленая рыба, сильнейшая на сегодняшний деньоткрытый источникшахматная программа,Чемпион чемпионата TCEC по компьютерным шахматам 2016 г.. Лучшие игроки-люди обычно могут играть только против его ослабленной версии.
Элмо,Чемпион мира Shogi Computer Shogi Association (CSA).
AlphaGo-Hui, первая статья DeepMind о природеMastering the game of Go with deep neural networks and tree searchПрограммное обеспечение для го, упомянутое в , много раз побеждало чемпиона Европы по го Фань Хуэя, а его самая сильная сила может достигать 5 данов.Первое программное обеспечение, которое обыграло профессионального игрока в го. Ему нужно изучить человеческую игру в го, которая требует тысяч процессоров и сотен графических процессоров для работы с максимальной производительностью.
AlphaGo-Lee на International Open спобедил Ли Седоля 4-1версии, которая произвела фурор в мире. В основном то же, что и AlphaGo-Hui, может использовать более мощную вычислительную мощность (48 TPU использовались в качестве базового уровня в более поздних статьях). Его ранг составляет около 9,5.
АльфаГо-Мастер,Лучшие профессиональные игроки в го в мире, одержавшие 60 побед подряд на платформе для игры в го Yehu., произвел фурор в шахматном мире и обыграл Кэ Цзе со счетом 3:0 в партии Учжэнь. Игра в шахматы, которую он изучает, исходит от AlphaGo-Lee, и ей нужно только 4 TPU и 2 CPU во время выполнения (достаточно одного вычислительного узла, то есть только небольшого шасси, а пиковое энергопотребление ожидается на уровне 500 Вт). Говорят, что сила шахмат составляет AlphaGo-Lee 3 фигуры (в шутку называемые профессиональными 20 данами).
AlphaGo-Zero, вторая статья DeepMind о природеMastering the game of Go without human knowledgeглавный герой,Не используйте какие-либо руководства по игре, прямо или косвенно полученные от людей, и не используйте никаких знаний о Го, кроме правил игры., потребовалось всего 3 дня, чтобы превзойти AlphaGo-Lee (Хуан Шицзе назвал это «Человеческое го за тысячу лет, а ноль прошел через три дня»), и впоследствии победил версию Ли Шиши с рекордом 100-0. Его аппаратная конфигурация такая же, как у Master. Сильнейшая версия AlphaGo-Zero против AlphaGo-Master 89% побед в 100 играх
AlphaZero, недавняя работа DeepMind, аппаратная конфигурация и алгоритм в основном такие же, как у AlphaGo-Zero, но тот же набор алгоритмов.Уметь решать задачи в шахматы и сёги в дополнение к го, и победил Stockfish (Stockfish использовала версию 8, 64 потока процессора и настроила хэш-таблицу на максимум). И он превзошел AlphaGo-Lee всего за 8 часов.

Конкретные баллы Эло (из статьи AlphaGo-Zero):

AlphaGo-Zero: 5185
AlphaGo-Zero (только сеть, без поиска): 3055
AlphaGo-Master: 4858
AlphaGo-Lee: 3739
AlphaGo-Fan: 3144

Разрыв Эло в 200 баллов соответствует 75% винрейта.

И их сравнение энергопотребления (согласно аппаратному измерителю энергопотребления TDP, такие виды энергопотребления обычно не достигаются):

Энергопотребление разных версий AlphaGo во время игры, (Источник изображения: официальный сайт DeepMind)

Среди них энергопотребление AlphaGo Lee значительно снижено благодаря аппаратному обеспечению (TPU заменяет GPU), в то время как Master и Zero выигрывают от алгоритма (Rollout удален).

Игра с конечной суммой и нулевой суммой для двух игроков с полной информацией

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

Ниже для простоты будем считать, что ничья невозможна,

Знание полного состояния игры + конечное состояние означает, что игрок может пройтиперебор грубой силы, чтобы вычислить все возможные ходы для формирования дерева поиска (раньше называлось ""Game tree»).

Дерево игры идет сверху вниз, и k-й уровень (самый верхний корень дерева считается уровнем 0) представляет игровую ситуацию (то есть состояние) после k шагов. Ребра представляют разные ходы, ребра на одном слое — это ходы одного и того же игрока, и два игрока играют в шахматы попеременно между разными слоями.

У новичков здесь могут возникнуть вопросы: а что, если бы игра позволяла игроку делать больше одного шага за раз? Это не проблема, нас просто волнует влияние хода игрока на состояние. Если игрок делает много шагов, мы называем это «сложным большим шагом».

Дерево поиска крестиков-ноликов, показывающее только первые два хода, игнорируя идеально симметричные случаи (источник: википедия)

А нулевая сумма означает, что при подсчёте всех возможных ходов в определённом состоянии, для определённой партии всегда имеется ряд последующих стратегий для достижения окончательной победы (или хотя бы ничьей), т. так называемая «стратегия победителя».

Поначалу это может показаться немного нелогичным: бывают ли определенные ситуации, когда мы не можем быть уверены, что у нас есть выигрышная стратегия?

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

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

Ниже мы увидим, насколько безжалостным может быть противник, перебравший все возможные ходы.

Мрачный «Бог» и Минимакс

Предположим, у вас есть очень сильный противник, который может перечислить все возможные ходы, тогда он может нарисоватьGame tree, он может выставить все итоговые оценки (например, чем выше оценка, тем успешнее, чем ниже оценка, тем больше неудач).

Для простоты предположим, что игра может закончиться после 4 ходов, и можно получить число, представляющее результат.

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

Минимаксный алгоритм (источник: wikipedia)

Результатом является слой 4.

Затем мы используем идею возврата, обратного вывода. Если он дойдет до третьего этажа, это ход противника, что будет делать противник? Противник должен сделать ход, который минимизирует конечный результат, верно? Итак, в третьем слое мы можем заполнить минимальное значение (так называемый MIN) подключенных узлов в следующем слое; аналогично, во втором слое мы выберем наибольшее значение, потому что мы всегда надеемся быть лучше (так называемый МАКС). Таким образом, две стороны неоднократно формировали MIN-MAX «противостояние» до корневого узла дерева. В этот момент вы обнаружите, что результат равен -7, а это означает, что если ваш оппонент будет рассуждать так же, вы проиграете, и лучший результат, которого вы можете достичь, это сделать результат равным -7.

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

Благодаря своим характеристикам MIN-MAX соответствующий алгоритм также называется Minimax (Min-i-max). На практике алгоритм работает по принципу «сначала в глубину» для эффективности, как показано на рисунке ниже (очень медленный GIF).

Работа алгоритма Минимакс на практике (с порядком обхода), источник: Википедия.

Конечно, в реальности есть еще один жестокий «Бог», то есть закон Мерфи (Murphy's law). Если вы считаете закон Мерфи своим противником (конечно, это поведение крайних консерваторов), то лучший образ действий — это выбрать наиболее безопасное поведение — выбрать лучший из худших вариантов, и любая удача приведет к большим потерям. .

Анализ сложности Minimax: невозможное совершенство

Ключом к Minimax является возможность расчета всего дерева игры, а стоимость расчета дерева игры пропорциональна размеру дерева игры.

Размер дерева игры в основном определяется двумя числами:

Глубина функции, что представляет собой типичное количество ходов для игры
коэффициент ветвления, который представляет типичную проходимость игры для каждого хода

Легко сделать вывод, что размер игрового дерева примерно b^d

Пока это игра, которая не слишком игрушечная, b^d Это все астрономические числа. Например, для Go это число превышает количество атомов в наблюдаемой Вселенной*.

Дерево игры слишком велико, поэтому нам сложно перечислить все узлы в дереве, и, следовательно, трудно достичь «идеального» состояния.

Но удовольствие от игры заключается в сложности достижения совершенства.

*Примечание: необходимо подчеркнуть «наблюдаемую вселенную». «Превышает количество атомов во Вселенной» — очень строгое утверждение, потому что размер наблюдаемой Вселенной ограничен, а крупномасштабная структура в целом ясна, и мы можем более точно оценить количество атомов на основе наблюдаемых часть. А «вселенная» очень широка, и мы все еще недостаточно знаем о ней сегодня.

Усовершенствования Minimax: ширина и глубина

Благодаря совершенным теоретическим характеристикам Minimax последующие усовершенствования почти все основаны на фреймворке Minimax.

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

Уменьшить глубину признаковЕсть три основных способа:

аппроксимация функции. Мы строим так называемыйфункция оценки, его цель состоит в том, чтобы оценить минимаксный счет для позиции, чтобы нам не приходилось искать результат до конца игры. В общем, оценки тем точнее, чем ближе вы подходите к финалу (поскольку игры, как правило, становятся проще по мере приближения к финалу), поэтому функция оценки не является полной заменой поиска. Это путь AlphaGo-Zero и AlphaZero.
Оценка моделирования. Мы можем начать с определенной позиции, использовать относительно простую систему игры (в ней не было бы смысла, если бы она была такой же сложной, как основная программа), быстро перейти к финальной игре и использовать результат как приближение к минимаксному оценка за эту позицию. Очевидно, что этот метод имеет тенденцию быть более точным, чем больше он доходит до конца. Этот метод также называется rollout.
Смесь двух вышеуказанных методов, например, средневзвешенное значение результатов двух. Вот как используют AlphaGo-Hui и AlphaGo-Lee.

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

при снижении коэффициента ветвленияЕсть два основных способа:

обрезка. Обрезка — это действие, устраняющее некоторые очевидные недостатки. самый известныйАльфа-бета обрезка, который в полной мере использует возможности алгоритма Минимакс и по-прежнему дает те же результаты, что и Минимакс (то есть не приближение), является предпочтительной оптимизацией. В качестве альтернативы, функцию оценки можно использовать для вычитания ветвей некоторых очень плохих ходов.
Выборочная оценка. Идея заключается в моделировании методом Монте-Карло (monte-carlo). Мы можем сначала оценить априорное распределение вероятностей P, а затем выбрать частичные пути на основе P для оценки. Этот метод более агрессивен для уменьшения коэффициента ветвления и чаще используется в шахматных играх с большими факторами ветвления, таких как го. Серия Alpha использует этот подход.

Ниже мы будем ссылаться на эти приемы.

В следующих подразделах описаны некоторые хорошо известные механизмы, направленные на уменьшение факторов ветвления.

Альфа-бета обрезка

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

Основная идея альфа-бета состоит в том, чтобы обрезать некоторые заведомо неоптимальные ветки.Его принцип основан на характеристиках алгоритма Минимакс, который по сути использует «монотонность» минимума и максимума.

Как показано на рисунке выше, если значение 5 находится в узле MAX нижнего уровня, это означает, что значение узла MIN верхнего уровня не должно быть больше 5. И если значение МАКС узла этого слоя уже не меньше 8 (например, потому что МИН узла нижнего слоя равно 8), то правую ветвь можно отрезать (т.е. правая ветвь не нужна продолжить изучение).

Можно видеть, что если нам повезет (фактически полагаемся на функцию оценки, чтобы угадать несколько заранее) и напрямую искать лучший случай, альфа-бета может отрезать большую часть ветвей. В этом случае сложность может быть снижена до $\sqrt{b^d}$ , это, $b^{d\over 2}$ (доказательство опущено). Вот что интересно: в то время как сокращение альфа-бета оптимизирует коэффициент ветвления, но в реальной работе алгоритма эффект аналогичен оптимизации глубины. Хорошая обрезка альфа-бета может удвоить глубину поиска при той же вычислительной мощности, а противник, который может видеть в два раза дальше, очень страшен.

Поиск по дереву Монте-Карло (MCTS)

Идея Монте-Карло очень проста: использовать случайную выборку для оценки определенных значений. Наиболее классическим является следующий оценочный пи $\pi$ пример:

Метод Монте-Карло для оценки числа пи (Источник изображения: Википедия)

В этом примере мы случайным образом равномерно распределяем точки по квадрату, а затем вычисляем, сколько точек находится в 1/4 окружности (это легко, например, оценить евклидово расстояние точки от начала координат), а затем мы можем подсчитайте, сколько точек находится в 1/4 круга. Долю от общего количества точек, занимаемую точками внутри, а затем поднесите ее к формуле площади круга для оценки $\pi$ .

Но как использовать метод Монте-Карло для Game Tree? Давайте сначала рассмотрим простую ситуацию (проблема многорычажной рокерной машины):

Автоматы-рокеры в казино Лас-Вегаса (источник: Википедия)

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

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

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

Но у этого вопроса есть некоторые проблемы:

Если мы ставим слишком много вариантов на вариант, который в первую очередь приносит много, из-за ограниченного количества попыток у нас есть хорошие шансы подвергнуться статистическим колебаниям, упустив вариант, который мы случайно не выбрали, или имеют низкую ценность в первых нескольких раундах, но ожидаемый вариант с большой ценностью. ЭтоExploitation & Exploration(Е и Е) Вопросы, то есть нам нужно найти баланс между разведкой и эксплуатацией. Этот баланс требует от насИзучение множества вариантов правильной девальвации, но это обесценивание не может уменьшить его «истинную ценность», потому что после многократного исследования выбора его среднее значение близко к его истинному значению.
Если мы просто сэмплируем все узлы равномерно в начале, как Монте-Карло, эффективность будет слишком низкой, что невыносимо для сложных задач, таких как Go (аналогично полному отсечению). Если мы априори чувствуем, что определенный выбор лучше (например, из-за нашего имеющегося опыта, рекомендации друга и т. д.), мы можем обеспечить большую априорную вероятность.Используется для направления выборки.

Ниже мы представляем стратегию, используемую AlphaGo Zero, которая является улучшением и упрощением стратегии в традиционном PUCT:

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

ТакО чем это должно быть? Во-первых, большая априорная вероятность, что соответствует большему; а если количество подвиговслишком много, тогдадолжны быть «амортизированы». Итак, предварительная идея:

$U\propto {P\over{1+N}}$

Но одна проблема с поиском по дереву заключается в том, что он разветвлен. Это означает, что между отраслями все еще существует конкуренция. Следовательно, нам также необходимо учитывать «преимущество ветки», то есть соседи ветки (то есть множество вариантов выбора в той же ситуации) также должны даватьВнесите свой вклад, чтобы отразить «преимущество соседа». В конце концов, мы получаем отличный выбор в ситуации, и нам больше интересно попробовать, какие есть другие варианты выбора в этой ситуации. Вклад соседа, очевидно, меньше, чем его собственный, поэтому мы могли бы также добавить корневой знак (почему добавление корневого знака выводится в таких местах, как PUCT):

$U\propto P{{\sqrt{\sum{N'}}}\over{1+N}}$ , (выше никого не добавлено, к вам следует относиться с особым вниманием при первом посещении этой ветки).

Так какой же должна быть константа полной формулы? Это гиперпараметр, обозначаемый как $c_{puct}$ , поэтому полная формула:

$U=c_{puct}P{{\sqrt{\sum{N'}}}\over{1+N}}$

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

Итак, последний вопрос: Q — это среднее значение, откуда берутся эти «значения»? —— Это очень просто, напрямую используйте функцию оценки, чтобы получить значение, когда поиск достигает определенной глубины.просто, затем используйтеОбновить все узлы вышезначение, в то время какУвеличить на 1.

Давайте разберем наши идеи, и у нас есть весь алгоритм:

выберитеСамый большой ход, продолжай идти вниз, пока не нажмешь, расчета нетиузел значения. (называется Выбор)
Встреча еще не рассчитанаиузел значения, набориравно 0, и вычислить априорную вероятность под диском этого узла,такесть ценность. (называется Развернуть )
до ограниченной глубины, используйте функцию оценки/развертывание, чтобы напрямую получить минимаксное значение узла, который является конечным узлом в этом поиске по дереву. (называется Оценить)
Путем возврата обновите все узлы на пути от конечного узла к корневому узлу.(все плюс 1) и(обновлено среднее). (называется Резервное копирование)

Алгоритм MCTS в AlphaGo (источник: документ DeepMind)

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

«Лучше, чем небо»

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

Сначала люди думали, что разрыв между AlphaGo и людьми невелик, или что чиновники AlphaGo очень бедны, поэтому они часто выигрывали в полглаза. Но после версии Master из различных сражений можно обнаружить, что даже после великой трансформации жизненных превратностей AlphaGo по-прежнему выигрывает большинство шахматных партий, будь то против других или против себя. Учитывая, что AlphaGo Master никогда не проигрывал напрямую людям, особенно иногда он может продолжать выигрывать от середины игры до Guanzi, это в основном опровергает предыдущую точку зрения.

На самом деле, причина «Шэнтянь Баньму» очень проста.Особой корреляции между выигрышем в шахматы и количеством набранных очков нет, даже если количество выигрышей меньше, выигрывать в шахматы выгоднее(Очевидно, что от вас требуется выиграть как минимум половину глаза, а от вас требуется выиграть как минимум 7, первое намного проще).

Например. Представим, что в дереве поиска есть 2 альтернативные ветви A и B, а их последующие ветви имеют следующее количество выигрышей и проигрышей:

Если следующие 4 ветки имеют одинаковую вероятность достижения, то, очевидно, математическое ожидание выигрышного числа ветки A больше, что равно 1,75, соответствующее математическое ожидание справа равно 0,5. То есть, если вы хотите выиграть больше номеров, вам следует выбрать ветку А.

Согласно коэффициенту выигрыша, ветка A имеет коэффициент выигрыша 50%, а ветвь B имеет коэффициент выигрыша 100%, хотя все они полуглазы.

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

Альфа-бета-обрезка и поиск по дереву Монте-Карло (MCTS)

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

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

MCTS, очевидно, намного сложнее, и его «обрезка» гораздо сильнее (ограничена гиперпараметром числа итерационных поисков, который не имеет ничего общего с шахматами), что делает его более подходящим для таких факторов ветвления, как Go.Особо крупная шахматная партия; но это также делает ее гарантию производительности не абсолютной (ведь бесплатного обеда не бывает); в то же время она имеет множество гиперпараметров, таких как явные $c_{puct}$ И количество повторных поисков, неявная форма - это релевантная формула (например, квадратный корень или логарифм выше, добавить ли единицу где-то в формулу и где ее следует добавить, короче, вариантов много); в Кроме того, MCTS может быть очень удобным.Возможно «повторное использование» дерева поиска, потому что, хотя значение, полученное оценочной функцией в нижней части дерева поиска, изменяется, когда делается следующий ход, мы можем исправить это изменение путем итерации , чтобы можно было повторно использовать предыдущие результаты.

Далее мы можем сравнить количество узлов, обыскиваемых алгоритмом MCTS и алгоритмом Alpha-beta в шахматах:

AlphaZero обыскала 80 000 узлов за шаг, используя MCTS, описанный выше.
Stockfish (в настоящее время самое мощное шахматное программное обеспечение с открытым исходным кодом) ищет 700 000 000 узлов за ход, используя улучшенную альфа-бета.

Последний в 875 раз больше первого. Это означает, что MCTS в AlphaZero должен давать лучшие результаты только с одной тысячной долей значения. Можно видеть, что эффективность MCTS сильно зависит от его функций генерации и оценки вероятностного распределения.

Другие стратегии обрезки

Эти стратегии исходят от Stockfish, самого мощного программного обеспечения для шахмат с открытым исходным кодом, доступного на сегодняшний день.

Поиск бездействия («Статический поиск»): он больше подходит для шахматных игр, где начальное количество фигур относительно фиксировано и есть подвох (например, в шахматах). После поиска на определенную глубину выбирает только те ветки, которые приводят в результате к поеданию ребенка или генерала. Это связано с тем, что после поимки кубика или генерала доска становится проще и явно приближается к концу (уменьшится и коэффициент ветвления, и глубина поиска), и во многих случаях будет появляться кубик, что сильно ограничивает выбор. В каком-то смысле поиск покоя — это то, что мы часто называем «краткой игрой» в теории шахмат.
Сокращение нулевого хода: во многих типах шахмат есть опция «без хода». Это сокращение предполагает, что «без хода» в целом является плохой стратегией. Если в обнаружении нет «вынужденного хода», он будет сокращен». Нет филиал "шахматы".
Сокращение бесполезности: когда мы знаем максимально возможный диапазон изменений в оценке, мы можем удалить некоторые недопустимые ветви (например, те, которые находятся за пределами диапазона изменения). Думайте об этом как о какой-то усовершенствованной обрезке альфа-бета.
Окна стремления: он пытается повторно использовать результаты обрезки альфа-бета, чтобы избежать повторного поиска каждый раз, когда достигается следующий ход.
Поиск основных вариантов: его можно рассматривать как эвристическое улучшение альфа-бета. Поиск основного варианта может быть значительно быстрее, если мы можем часто угадывать лучший выбор; в противном случае он обходится дорого.
Некоторая другая связанная с полем обрезка: например, обрезка выполняется в соответствии с важностью захваченных фигур, что часто встречается в таких играх, как шахматы, где ценность каждой фигуры сильно различается.

Следующие подразделы посвящены упомянутым выше механизмам уменьшения глубины поиска.

Rollout

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

Очевидно, что развертывание требует много вычислительных ресурсов. Версия AlphaGo-Hui с использованием Rollout использовала 40 поисковых потоков, 1202 процессора и 176 графических процессоров для достижения Elo 3140 (профессиональный уровень 3-5); более поздние версии AlphaGo-Master и AlphaGo-Zero использовали только функцию оценки Используя 1 вычислительный узел (4 TPUv1 + 2 CPU*) напрямую против профессионального 9-го этапа никогда не проигрывал.

Видно, что функция оценки намного эффективнее, чем Rollout. Одна из причин, по которой AlphaGo-Hui и AlphaGo-Hui используют развертывание, заключается в том, что развертывание более распространено в MCTS, а другая причина заключается в том, что функция оценки в то время очень слабая, поэтому они усредняют результаты развертывания и функции оценки для улучшения. Эффект. После AlphaGo-Master DeepMind получил более сильную функцию оценки, поэтому отказался от Rollout*.

*Примечание. Конкретная информация о ЦП не разглашается, но, как правило, высокопроизводительный вычислительный узел в основном двухпроцессорный, редко более чем четырехпроцессорный.
DeepMind также не раскрыла алгоритм версии Master, но сообщила, что «алгоритм версии Master был значительно улучшен, а эффективность значительно повышена. Во время боя 4 TPU могут использоваться на одном узле для запуска без необходимости распространяемой версии», это точно такая же конфигурация, как AlphaGo Zero, видимо, с удаленным Rollout и улучшенной функцией оценки.

Функция оценки и ее конструкция

Одним из прорывных моментов серии AlphaGo является использование нейронных сетей в качестве оценочных функций.Хотя GNU-Go и другие игры в Го применяли нейронные сети для Го ранее, серия AlphaGo использует более глубокие и сложные сети и использует достаточную вычислительную мощность. для подтверждения Большое преимущество нейронной сети как функции оценки.

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

Во-первых, некоторые функции выбираются вручную, такие как количество оставшихся подвижных фигур, застрявших фигур, атакующая ситуация самой продвинутой фигуры, потенциальная угроза короля, взаимодействие двух слонов и различные таблицы, полученные искусственным образом. опыт, такой как эндшпиль, таблица статуса, таблица оценки миттельшпиля, таблица движения пешек и т. д. (Описание, приведенное в документе AlphaZero: значения материальных очков для мидшпиля/эндшпиля, таблицы материального дисбаланса, таблицы фигур-квадратов, подвижность и захваченные фигуры, пешка структура, безопасность короля, аванпосты, пара слонов и другие различные модели оценки)
Каждая функция оценивается (искусственно разработанные правила оценки), взвешивается и суммируется (веса являются регулируемыми и изученными параметрами). Полученный результат используется как результат оценки.
Введите Quiescence Search (упомянутый выше), и попробуйте продолжить поиск ветки едока или генерала внизу исходного дерева поиска, но в это время будут использоваться некоторые искусственно разработанные тактики и другие корректировки, а первоначальный результат оценки будет обновлен, если такой ситуации нет, используется первоначальный результат оценки.

Но эти методы оценки в принципе неэффективны для Go. В Го есть два типа фигур, черные и белые, поэтому нет возможности разработать специальный метод оценки характеристик определенной фигуры; в миттельшпиле и в эндшпиле (закрытие) есть много состояний, это трудно составить таблицу, и людям даже трудно ее оценить Непредсказуемые развороты в миттельшпиле очень распространены в го, в го трудно судить о «застрявших фишках», что соответствует проблеме жизни и смерти в го , что всегда было проблемой даже для профессиональных игроков; Камни явно не предназначены для того, чтобы принести огромные преимущества или облегчить ситуацию, и даже грабеж, вызванный захватом камней, усложнит ситуацию; конец цель го также очень сложна, а не «мат» в шахматах». Это очень простое и прямое условие, и для новичков непростая задача определить, когда можно определить победителя. Компьютеры обычно используют только Метод подсчета очков Тромпа-Тейлора используется для оценки эндшпиля, и для этого требуется, чтобы он был более точным, чтобы пройти весь путь до конца.

Можно сказать, что ключ к шахматамЭти сложные, локальные и глобальные связи между общими структурами, а не сами куски. Из-за этого людям долгое время было трудно разработать отличную функцию оценки, и предполагается, что программное обеспечение Go не будет противником профессиональных игроков через 20 лет.

но"Эти сложные, локальные и глобальные связи между общими структурами"Кажется, соответствует структуре задачи другого рода? - Да, образы.

Наименьшая единица Го — это шахматная фигура, соответствующая пикселям изображения, а мелкие части Го (наклоняться, тянуть, ломаться, летать, прыгать, висеть) соответствуют простым структурам изображения (ребрам, углам и т. , линии); Большая часть соответствует сложной структуре изображения (окна, двери); и эти сложные структуры действуют сложным образом, образуя целое.

Перейти от локального к глобальному в изображениях

Более крупные элементы органично сочетаются с более мелкими частями, и эти сложные комбинации образуют большую игру Го или основную часть изображения.

С точки зрения распознавания и анализа изображений, с 2012 года CNN (Сверточная нейронная сеть) прославилась на таких соревнованиях, как ImageNet, и стала одним из основных методов. Так что это также естественная идея применить CNN к Go.

Сверточные нейронные сети как функции оценки

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

Если текущее состояние доски записано как, нейронная сеть обозначается как $F_\theta$ ( $\theta$ — его параметр), текущее состояние используется как узел дерева игры, а его минимаксное значение равно $V^*_{s}$ , что нам нужно сделать, это найти этот конкретный $\theta^*$ , так что

$F_{\theta^*}(s)\approx V^*_s$ , и чем приблизительнее, тем лучше. На практике мы используем среднеквадратичную ошибку для описания аппроксимации, то есть для решения следующей задачи оптимизации:

$\min_{\theta}\mathbb{E}_s\|F_\theta(s)-V^*_s\|^2$

По сути, это очень сложная проблема подгонки. $F_{\theta^*}$ примерно V^* , после достаточного приближения нейронная сеть может достаточно хорошо оценить минимаксное значение текущей ситуации, что является хорошей функцией оценки (Эта сеть также известна как «сеть ценности».).

Однако в целом сверточная нейронная сеть делится на две части: первая «основная часть» — это сверточный слой (так называемая сверточная нейронная сеть), который может извлекать «хорошее представление входных данных», а вторая — «основная часть». head" этого представления выполняет простое преобразование, чтобы получить окончательный ввод. Вообще говоря, чем глубже «основная часть», тем сильнее репрезентативная способность нейронной сети (это тоже одно из значений «глубокого обучения»), а значит, тем ближе она к наилучшему решению как оценочная функция. Одним из основных отличий AlphaGo-Lee от более поздних версий является углубление сети:

Глубина основной части сети разных версий AlphaGo (с точки зрения слоев CNN) представляет собой масштабированную схематическую диаграмму, в которой предполагается, что версия Master может использовать сеть AlphaGo-Zero (Block20)

AlphaGo-Lee использовала более мелкую сеть для оценки, и, по-видимому, была проблема, похожая на «недообучение», которая требовала Rollout для помощи в оценке; а затем Master и Zero напрямую выбросили Rollout, потому что самой глубокой сети было достаточно для оценки.

Помимо основного тела сети, мы сказали, что для преобразования промежуточных признаков в значения нужна «голова», которая для оценки выглядит так (на примере AlphaGo-Zero):

Он «сглаживает» выходные данные сверточного слоя выше, а затем преобразует их через два полносвязных слоя, чтобы получить значение от -1 до 1 через Tanh, что является окончательной оценкой.

Сверточные нейронные сети как функции политики

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

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

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

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

И AlphaGo-Hui, и Lee используют две сети (сеть стоимости + сеть политик).

Но согласно идее «обучения представлениям», можно повторно использовать «высокоуровневое представление» позиции Go, которое можно использовать для оценки ценности, а также можно использовать в качестве стратегии, так почему бы и нет. мы разделяем тему?

Итак, мы даем сети политик отдельный заголовок (в AlphaGo-Zero):

Этот заголовок сначала подавляет предыдущие «расширенные функции», а затем напрямую получает распределение вероятностей через полностью подключенный слой (обратите внимание, что прямым выходом является логит-распределение, и необходимо добавить слой Softmax, чтобы он стал общим распределением вероятностей. распределение В основном для облегчения оптимизации нейронной сети, улучшения численной стабильности и уменьшения объема вычислений)

Вся структура сети выглядит так:

Верхняя часть основная, а нижняя с двумя головками

Кроме того, следует отметить, что "основная часть" состоит из некоторых частей, называемых Residual Block (остаточные блоки). Это связано со сложностью оптимизации особо глубоких нейронных сетей. Одним из решений является введение "остатков" для формирования Остаточная структура. Остаток — это почти одна из стандартных структур глубокой CNN. Структура остаточного блока, используемого в AlphaGo, следующая:

Глубину сети можно изменить, контролируя количество остаточных блоков.

Функция оценки/стратегическая функция: нейронные сети против дизайна человека

В разделе «Функция оценки и ее дизайн» мы упоминали о сложном дизайне функции оценки в Stockfish. Эти конструкции основаны на человеческом опыте и более эффективны для шахмат и т. д., но они очень неудобны для го.

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

Именно это заставило DeepMind понять, что этот набор методов применим не только к го, но и к большинству шахматных игр, таких как шахматы и сёги. Поэтому они немного изменили AlphaGo-Zero и получили универсальную версию AlphaZero, которая решает подобные проблемы.

Изначально люди думали, что шахматы и сёги не особо подходят для AlphaGo, потому что их фигуры очень разные, а правила намного сложнее, чем в Го. Но AlphaZero по-прежнему легко превосходит Stockfish и Elmo и использует в поиске только одну тысячную их оценок, что показывает, чтоПока достаточно данных (независимо от того, предоставлены ли они людьми или сгенерированы ими самими) и вычислительной мощности, нейронная сеть может обучиться достаточно хорошей функции оценки, выходящей далеко за пределы способности людей к проектированию..

Я думаю, что замена ручного проектирования данными и вычислительной мощностью будет продолжаться.

Оценка, поиск и обучение: в чем суть?

Снова оглядываясь на самый ранний алгоритм Minimax, мы можем обнаружить огромную проблему:

Для получения точной оценки необходимо b^d Время поиска порядка величины (поскольку для точной оценки минимаксного значения требуется все Дерево игры); но для игры в шахматы требуется тольковторичное решение.

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

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

сокращение альфа-бета: используйте избыточность, вызванную монотонностью функций MIN и MAX в Minimax, для выполнения сокращения
MCTS: ожидается, что статистический вывод конечного числа случайных поисков почти всегда согласуется с истинным минимаксным значением (это также означает, что обход всего дерева игры является излишним), тем самым уменьшая количество обходов.
Функция оценки: процесс выполнения алгоритма Minimax полон избыточности и может быть аппроксимирован функцией или опытом с ограниченными параметрами и шагами.
Сокращение нулевого перемещения: операции «без перемещения» часто являются излишними.
Окна стремления: окна, образованные значениями альфа-бета, полученными с помощью сокращения альфа-бета на предыдущем шаге, часто можно использовать повторно, поэтому при повторном выполнении альфа-бета возникает избыточность.
Поиск покоя: (в шахматах) Краткие ситуации, которые устраняют фигуры соперника и представляют угрозу, часто достаточно благоприятны, чтобы их можно было исследовать в первую очередь; они могут быть излишними по сравнению с ситуациями, когда многие ходы вообще не захвачены.

В качестве мощной функции оценки нейронную сеть можно рассматривать какСжатое представление минимаксных значений по всему игровому дереву. Это как понять?

Давайте посмотрим на минимаксное значение каждого узла дерева игры с другой точки зрения:

Мы можем выразить минимаксное значение на дереве игры в виде таблицы

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

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

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

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

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

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

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

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

В то же время нейросети требуется постоянное время для получения оценки любой позиции, что сильно отличается от дерева поиска. Это напоминает мне о любимом протеже Ли Фейфея, нынешнем специалисте по планированию искусственного интеллекта Tesla Андрее Карпати изMediumВ блоге "Программное обеспечение 2.0" размещено .

Блог рассматривает такие технологии, как нейронные сети, как «программное обеспечение второго поколения» и другие вопросы. Наиболее интересным моментом этих алгоритмов нейронных сетей является то, что их временная сложность часто приближается к константе (потому что это просто оценка функции), что ближе к человеческому поведению: люди независимы от ввода во многих когнитивных задачах, время Почти фиксированная обработка, а не значительная характеристика временной сложности, как у большинства современных алгоритмов, разработанных вручную; человеческая интуиция больше похожа на справочную таблицу функций, чем на работающий алгоритм.

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

Содержание следующего

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

Как перебирать данные и нейронные сети? Что такое обучение с подкреплением? Почему позже DeepMind изменил Градиент Политики на Итерацию Политики?
В игре против Ли Седола и AlphaGo, и Ли Седол играли в «Руку Бога», а Ли Седол победил AlphaGo своей «Рукой Бога» в четвертой игре. Так в чем же причина этих «рук богов»? В чем ошибка AlphaGo? Почему я не вижу подобных ошибок в версии Master позже? В этом году я купил и посмотрел отмеченный множеством наград и номинаций документальный фильм Грега Коса AlphaGo, и мы можем вывести из него много важных деталей.
Почему в версии AlphaZero вообще отсутствует стратегия выбора версии игрой? Почему нейронные сети явно не сталкиваются с «локальными оптимумами» (недообучением) и «переоснащением» во время самопротиворечивого обучения? Какие важные детали мы можем извлечь из недавно выпущенного AlphaGo Teach?
Почему стоит выбрать MCTS+CNN вместо обрезки альфа-бета+CNN? Действительно ли MCTS имеет преимущество перед обрезкой альфа-бета?
Алгоритмы и предварительные знания: битва за конференцию NIPS в этом году. На конференции NIPS DeepMind анонсировала AlphaZero, последнюю версию своей программы Go. Но Маркус яростно выступал против «философии нулевого знания», лежащей в основе AlphaZero. Как оценить две стороны?
Является ли матч между AlphaZero и Stockfish «честным»? Как понять возможные изменения, вызванные разрывом вычислительных мощностей?
Что касается аппаратного обеспечения: какой TPU использует DeepMind? В чем разница между TPUv1 и v2?