предисловие
Ссылка на проект:GitHub.com/HiHealthzzz/alp…
Алгоритм AlphaZero выпускается уже больше года, и на GitHub есть различные реализации, начиная от однопоточной низкопроизводительной версии из тысячи строк кода Python и заканчивая распределенной версией из десятков тысяч строк кода C++. Однако ни одна из этих реализаций не может удовлетворить потребности энтузиастов общих алгоритмов, то есть простой и автономный работоспособный высокопроизводительный алгоритм AlphaZero.
Расшифровка AlphaZero в одном изображении
Для начала разберемся с принципом работы алгоритма AlphaZero через картинку
Видно, что поток алгоритма AlaphaGo Zero делится на:
- Самостоятельная игра (с использованием поиска по дереву Монте-Карло) для создания шахматных записей для N игр.
- Обучите сеть с помощью сгенерированного шахматного листа
- Оцените недавно обученную сеть
анализировать
Для алгоритма AlphaZero версии Python он обычно ограничен GIL, а самый трудоемкий этап самостоятельной игры (см. рисунок ниже) не может быть распараллелен, поэтому самый прямой метод оптимизации — использование высокопроизводительного языке, таком как C++, для реализации деталей базовой операции.
Решение
Пул потоков
Чтобы распараллелить процесс самовоспроизведения, сначала нам нужно реализовать пул потоков C++. Существует много информации о пуле потоков в Интернете для справки, поэтому я не буду описывать ее здесь.
Root Parallelization
Как видно из блок-схемы алгоритма, процесс самовоспроизведения реализуется с использованием поиска по дереву Монте-Карло, поэтому существует два измерения для распараллеливания самовоспроизведения: корневое распараллеливание и распараллеливание дерева. Среди них Root Parallelization относится к открытию N игр одновременно, и каждый поток отвечает за одну игру. Распараллеливание дерева относится к распараллеливанию поиска по дереву Монте-Карло (MCTS) в одной игре. Таким образом, легко реализовать распараллеливание корней с потоками N. Давайте обсудим распараллеливание дерева ниже.
Tree Parallelization
Сначала проанализируйте запущенный процесс поиска по дереву Монте-Карло (MCTS):
Каждый раз, когда выполняется фигура, MCTS должен выполнить M симуляций хода, и каждая симуляция представляет собой рекурсивный процесс, как показано ниже:
-
Выберите, если текущий узел не является листовым узлом, вероятность выбора рассчитывается с помощью определенного алгоритма UCT (алгоритм исследования-использования, коэффициент выигрыша (значение q), предсказанный нейронной сетью, и априорная вероятность, чем выше коэффициент выигрыша /предыдущая вероятность, тем выше вероятность выбора), чтобы найти оптимальную позицию следующего перемещения, и выполнять поиск на следующем уровне, пока текущий узел не станет конечным узлом.
-
Разверните и оцените, если текущий узел является конечным узлом, есть два случая:
- Игра текущего узла завершена, и одна сторона побеждает, затем выполняется резервное копирование, чтобы обновить значение коэффициента выигрыша родительского узла.
- Если игра еще не окончена, используйте нейронную сеть, чтобы предсказать коэффициент выигрыша текущего узла и априорную вероятность следующего слоя, расширьте узел с этой априорной вероятностью, а затем выполните резервное копирование, чтобы обновить коэффициент выигрыша родительского узла (q значение) резервное копирование.
-
Резервное копирование, каждый узел сохраняет значение коэффициента выигрыша (значение q), значение q равно количеству побед/количеству посещений, а резервное копирование обновляет это значение и количество посещений от конечного состояния вверх.
-
Играйте, в реальной игре вы можете выбрать дочерний узел с наибольшим количеством посещений под корневым узлом (поскольку узел с большим значением q имеет большую вероятность выбора и больше посещений).
Таким образом, мы можем одновременно выполнять M' (меньше, чем M) симуляций, поэтому некоторые ключевые данные должны быть заблокированы, например, отношения между родительскими и дочерними узлами дерева Монте-Карло, количество посещений, значение q и т. д. . Некоторые люди также разработали несколько алгоритмов без блокировки [5], но из-за взаимосвязи предварительного выделения узлов дерева использование памяти очень велико, и обычные машины не могут работать, поэтому используется заблокированная версия параллельной карты Монте. здесь Поиск в Лос-Анджелесе.
Virtual Loss
Для распараллеливания дерева, если мы просто распараллелим поиск методом Монте-Карло (MCTS), мы столкнемся с проблемой: потоки M' часто ищут один и тот же узел, поэтому наше распараллеливание бессмысленно, потому что поиск такой же, как узел A, означает повторяющуюся работу. Так что в алгоритме UCT при посещении узла потоком мы добавляем штраф Virtual Loss, чтобы другие потоки вряд ли выбрали этот узел для поиска.
LibTorch
Поскольку нейронную сеть необходимо использовать для прогнозирования коэффициента выигрыша и априорной вероятности в процессе MCTS, C++ необходимо вызвать метод прогнозирования нейронной сети, реализованный в Python, но это вернет исходное состояние. То есть ограничение GIL для Pyhton приведет к принудительному последовательному выполнению параллельного самостоятельного воспроизведения. Итак, мы используем внешний интерфейс PyTorch C++ LibTorch для реализации нейронной сети.
CUDA Stream
После работы для нейросети, работающей на GPU, наша программа все еще толком не распараллелена. Это связано с тем, что выполнение прогноза LibTorch ограничено CUDA Steam по умолчанию, который по умолчанию является последовательным, что приводит к блокировке многопоточных вызовов для прогнозирования. Есть два способа избежать этой проблемы: 1. Использовать несколько потоков CUDA 2. Объединить запросы прогнозирования. Метод, который мы используем здесь, заключается в объединении нескольких прогнозов с буферной очередью и одновременной отправке их в графический процессор, что предотвращает блокировку потока из-за конкуренции в рабочем процессе графического процессора.
SWIG
Наконец, мы инкапсулируем приведенный выше код C++ в интерфейс Python с SWIG для вызова основной программы. Хотя это приведет к некоторым потерям производительности, это значительно повысит эффективность разработки.
контрольная работа
После тестирования эффективность обучения после распараллеливания повышается не менее чем в 10 раз. Простой расчет, предполагающий, что каждый MCTS использует 4 потока для одновременной игры в 4 игры, то есть 4x4=16 раз, учитывая накладные расходы на блокировки, буферные очереди и интерфейсы Python, увеличение на порядок является разумным. Кроме того, пока GPU достаточно мощный, увеличение количества потоков может продолжать повышать производительность. В итоге я целый день тренировал стандартный алгоритм игры в нарды 15х15 на GTX1070, который уже может побеждать обычных игроков.
использованная литература
- Mastering the Game of Go without Human Knowledge
- Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm
- Parallel Monte-Carlo Tree Search
- An Analysis of Virtual Loss in Parallel MCTS
- A Lock-free Multithreaded Monte-Carlo Tree Search Algorithm