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

В декабре 2017 года новый шахматный движок Google DeepMind, AlphaZero, убедительно победил Stockfish 8, один из сильнейших компьютерных шахматных движков в мире. Хотя AlphaZero не играл в самой сильной версии Stockfish, и система все еще находится на рассмотрении (эта пьеса от Хосе Камачо Колладоса отлично помогает смягчить некоторые из утверждений), похоже, что AlphaZero скоро станет сильнейшей шахматной системой. существующая игровая сущность, если она еще не существует. Статья DeepMind находится на arXiv здесь.

Популярность AlphaZero особенно примечательна тем, что основная часть программного обеспечения, стоящая за ней, изначально не была создана для игры в шахматы. Вместо этого AlphaZero - это модифицированная версия AlphaGoZero, программы DeepMind, которая недавно использовалась для победы над лучшим игроком в го в мире. Чтобы заполучить нового чемпиона по компьютерным шахматам, исследователи DeepMind по сути взяли AlphaGoZero, удалили все специфические для Go функции из AlphaZero (например, некоторые аспекты AlphaGo зависели от симметрии вращения доски для го), добавили правила игры в шахматы и обучил новую систему на 5000 пользовательских чипах машинного обучения Google в течение 4 часов.

Как компьютеры играют в шахматы

Как DeepMind так быстро удалось конкурировать с лучшими шахматными программами мира? Те же два основных компонента, функция значения и поиск по дереву, обеспечивают работу AlphaZero и Stockfish, а также большинства других шахматных движков. Функция значения принимает состояние игры в качестве входных данных (для шахмат это просто положение каждой фигуры плюс бит, указывающий, сделал ли каждый игрок рокировку) и выводит единственное число, которое определяет, насколько «хорошо» это состояние для игрока. компьютерный плеер. Если функция оценки работает хорошо, она будет высоко оценивать позиции доски, которые являются благоприятными для компьютера, и оценивать низкие позиции доски, которые могут привести к проигрышу компьютера.

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

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

Хотя AlphaZero и Stockfish работают в соответствии с этим общим методом, они используют очень разные функции значений. Функция ценности Stockfish - это формула, основанная на стоимости фигур на доске и ряде правил, таких как следующие:

Piece Placement
1. Encourage knights to occupy the center of the board.
2. Encourage queens and rooks to defend each other and attack.
3. Encourage 7th rank attacks for rooks.

Pawn Structure
1. Penalize doubled, backward and blocked pawns.
2. Encourage pawn advancement where adequately defended.
3. Encourage control of the center of the board.

Etc.

(эти примеры взяты из сообщения в блоге Кэтрин Рэй о том, как Stockfish)

Разработчики Stockfish должны написать каждое из этих правил в дополнение к определению их относительной важности. Хотя все делается вручную, правила далеко не произвольные. Сообщество Stockfish создало процесс для тестирования изменений функции значения и поиска по дереву. Каждое новое потенциальное дополнение к функции оценки Stockfish или поиску по дереву, о котором думает разработчик, проходит через обширный набор тестов, чтобы определить его влияние на производительность программы. Если тесты пройдут успешно, настройка будет добавлена ​​в проект, и Stockfish станет немного лучше. Stockfish - это шахматный движок с открытым исходным кодом, который с годами стал сильнее благодаря итерациям, в которых участвовали десятки людей. Посмотреть последние тесты, которые команда провела онлайн, можно здесь.

Как работает AlphaZero

Разработчик AlphaZero придерживается противоположного подхода. В его функцию ценности нет встроенных эвристик. Вместо этого функция ценности изучается полностью с нуля с помощью модели нейронной сети. Сеть начинается с функции значения, которая просто присваивает случайные значения каждому состоянию. Затем две копии всего движка (функция значения нейронной сети плюс поиск по дереву) играют друг против друга. После игры нейронная сеть обновляется новыми данными. После завершения обучения функция ценности сети учится назначать немного более высокие значения для игровых позиций, которые привели к победе, и немного более низкие значения для игровых позиций, которые привели к поражению. Этот процесс повторяется тысячи раз: две копии AlphaZero воспроизводят друг друга, функция значения обновляется, две новые копии (с немного улучшенными функциями значений) воспроизводятся друг с другом, функция значения обновляется дальше и т. Д. После 300 000 поколений нейронных сетей. улучшения сети и миллиард игр для самостоятельной игры (настоящий AlphaZero играл около 4000 раз между каждым обновлением) AlphaZero был достаточно хорош, чтобы победить Stockfish.

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

Основным вкладом AlphaZero было решение этих проблем. После множества экспериментов DeepMind разработал серию новых уловок и обнаружил функцию ценности и поиск по дереву, которые можно достоверно изучить только через самостоятельную игру. Затем они задействовали свой инженерный талант и ресурсы инфраструктуры, чтобы продемонстрировать, что система может работать в массовом масштабе, необходимом для освоения сложных игр, таких как шахматы и го (версия, в которой использовалась Stockfish, использовала 5000 пользовательских чипов машинного обучения). Интересно, что примерно в то же время исследователи из Университетского колледжа Лондона разработали похожий алгоритм, но им не хватало инженерных ресурсов, чтобы применить его к такой комбинаторно богатой игре, как шахматы. Вместо этого они остановились на Hex, более простой и менее известной игре. В результате их статья привлекла гораздо меньше внимания, чем DeepMind.

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

Чем отличается AlphaZero

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

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

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

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

Поскольку AlphaZero понимает шахматы в основном статистически, для достижения экспертного уровня игры требуется примерно в 10 000 раз больше человеческого опыта. Но, в отличие от написания романа или разговора, отказ от семантики в пользу вычисления чисел оказался выигрышной стратегией для шахмат и го. Фактически, AlphaZero может выявить недостатки в нашей способности играть в эти игры. Например, в одной из публично выпущенных шахматных игр AlphaZero приносит в жертву коня ради небольшого позиционного преимущества, которое в конечном итоге выигрывает игру на много ходов позже (видео игры с анализом есть на YouTube). Наша эвристика (например, идея о том, что конь стоит три очка и неспособность признать ценность небольшого позиционного изменения) и наша неспособность заглянуть в будущее так же далеко, как компьютер, не позволили нам обнаружить эти типы ходов. . (Хотя это не так уж плохо для человеческих знаний; AlphaZero заново открыла и использовала несколько знакомых открытий.) Stockfish, несмотря на свою способность исследовать гораздо больше возможных ходов, чем AlphaZero, по-прежнему ограничен своей ценностной функцией, серией эвристик, написанных людьми и опираясь на наше лучшее понимание игры.

В 1997 году IBM создала Deep Blue, первый шахматный движок, который мог побеждать лучших игроков-людей. Двадцать лет спустя, похоже, DeepMind создал движок, который может победить лучших разработчиков шахматных движков. AlphaZero достигла мирового уровня в шахматах и ​​го, не имея специальных знаний ни в одной из игр. Теперь DeepMind стоит перед еще более серьезным испытанием - смогут ли они перенести свои игровые алгоритмы в реальный мир?

Я работаю над новым постом о сложности применения алгоритма AlphaZero к финансам и другим областям реального мира. Подписывайтесь на меня в Twitter или Medium, чтобы получать последние обновления!