Перевод статьи по английскому языку. Playing board games is considered a major challenge for both humans and ai researchers
 Скачать 55.36 Kb.
|
| 2.3 Scalable deep reinforcement learning | Масштабируемое глубокое обучение с подкреплением |
| Recently, several works tackled the problem of scalability in RL in the context of combinatorial optimization using GNNs that are natural models to deal with such challenges. For example, Lederman et al. [2018] utilized the REINFORCE algorithm [Williams, 1992] for clause selection in a QBF solver using a GNN, and successfully solved arbitrary large formulas. Abe et al. [2019] combined Graph Isomorphism Networks [Xu et al., 2018] and the AGZ framework for solving small instances of NP-complete combinatorial problems on graphs. Dai et al. [2017] proposed a framework that combines RL with structure2vec graph embedding [Dai et al., 2016], to construct incremental solutions for Traveling 2 Salesman and other problems. Other RL models that deal with combinatorial optimization problems include Yolcu and Póczos [2019], Xing and Tu [2020]. | Недавно в нескольких работах рассматривалась проблема масштабируемости в RL в контексте комбинаторной оптимизации с использованием GNNs, которые являются естественными моделями для решения таких задач. Например, Ледерман и др. [2018] использовали алгоритм УСИЛЕНИЯ [Williams, 1992] для выбора предложений в решателе QBF с использованием GNN и успешно решали произвольные большие формулы. Эйб и др. [2019] объединили сети изоморфизма графов [Сюй и др., 2018] и фреймворк AGZ для решения небольших экземпляров NP-полных комбинаторных задач на графах. Дай и др. [2017] предложили фреймворк, который сочетает RL с внедрением графа structure2vec [Dai et al., 2016], для построения инкрементных решений для коммивояжера и других проблем. Другие модели RL, которые имеют дело с проблемами комбинаторной оптимизации, включают Yolcu и Póczos [2019], Xing и Tu [2020]. |
| A fundamental difference between trying to scale combinatorial optimization problems and our task is that a reductionist approach is much less intuitive for scaling up board games. For example, when trying to solve a large-scale SAT instance (as in Yolcu and Póczos [2019]), the problem necessarily gets smaller as long as the search advances. More specifically, by setting a literal xi to True or False, all clauses that contain xi or ¬xi can be deleted (either in conjunctive normal form or disjunctive normal form). In contrast, in a board game, the problem size remains the same during the entire search, with much more challenging rare boards that have not yet been encountered. | Фундаментальное различие между попытками масштабирования задач комбинаторной оптимизации и нашей задачей заключается в том, что редукционистский подход гораздо менее интуитивно понятен для масштабирования настольных игр. Например, при попытке решить крупномасштабный экземпляр набора (как в случае с вами и Почосом [2019]), проблема обязательно уменьшается по мере продвижения поиска. Более конкретно, установив для литерала xi значение True или False, все предложения, содержащие xi или ¬xi, могут быть удалены (либо в конъюнктивной нормальной форме, либо в дизъюнктивной нормальной форме). В отличие от этого, в настольной игре размер проблемы остается неизменным на протяжении всего поиска, с гораздо более сложными редкими досками, которые еще не встречались. |
| Among existing work on using learning to scale up board games, the most similar to our approach is that of Schaul and Schmidhuber [2009]. To enable size generalization for Go-inspired board games, they presented MDLSTM, a scalable neural network based on MDRNNs and LSTM cells, computing four shared-weight swiping layers, one for each diagonal direction on the board. For each position on the board, they combine these four values into a single output representing the action probabilities. Their results show that MDLSTM transfers the strategies learned on small boards to large ones, leading to a level of play on a 15 × 15 board that is on par with human beginners. Some other similar approaches include those of Gauci and Stanley [2010], Wu and Baldi [2007]. Gauci and Stanley extrapolated 5 × 5 Go solutions to 7 × 7, thus speeding up the training. Wu and Baldi designed a DAG-RNN for Go and demonstrated that systems trained using a set of 9 × 9 amateur games achieve surprisingly high correlation to the strategies obtained by a 19 × 19 professional players’ test set. | Среди существующих работ по использованию обучения для масштабирования настольных игр наиболее похожим на наш подход является подход Шаула и Шмидхубера [2009]. Чтобы обеспечить обобщение размеров для настольных игр, вдохновленных Go, они представили MDLSTM, масштабируемую нейронную сеть, основанную на ячейках MDRNNs и LSTM, вычисляющую четыре слоя прокрутки с общим весом, по одному для каждого направления диагонали на доске. Для каждой позиции на доске они объединяют эти четыре значения в один выходной сигнал, представляющий вероятности действий. Их результаты показывают, что MDLSTM переносит стратегии, изученные на маленьких досках, на большие, что приводит к уровню игры на доске 15 × 15, который находится на уровне начинающих игроков. Некоторые другие аналогичные подходы включают подходы Гаучи и Стэнли [2010], Ву и Балди [2007]. Гаучи и Стэнли экстраполировали решения 5 × 5 Go на 7 × 7, тем самым ускорив обучение. Ву и Балди разработали DAG-RNN для Go и продемонстрировали, что системы, обученные с использованием набора любительских игр 9 × 9, достигают удивительно высокой корреляции со стратегиями, полученными с помощью набора тестов профессиональных игроков 19 × 19. |
| All the above models, aimed at scaling up board games, do not incorporate an RL framework within their model, neither for training nor playing. In contrast to our model, which starts its training as a tabula rasa (i.e., without using any specific domain knowledge), the training processes of Schaul and Schmidhuber and Gauci and Stanley are based on playing against a fixed heuristic based opponent, while Wu and Baldi trained their model using records of games played by humans. | Все вышеперечисленные модели, направленные на расширение масштабов настольных игр, не включают в свою модель фреймворк RL ни для обучения, ни для игры. В отличие от нашей модели, которая начинает свое обучение как tabula rasa (т.е. без использования каких-либо конкретных знаний предметной области), тренировочные процессы Шаула и Шмидхубера, а также Гаучи и Стэнли основаны на игре против фиксированного эвристического противника, в то время как Ву и Балди обучали свою модель, используя записи игр, сыгранных люди. |
| 3 Scalable AlphaZero for board games | Масштабируемый AlphaZero для настольных игр |
| In this section we describe in detail our RL based model for scalable board games. Our model is based on AZ, equipped with additional components that allow it to train on small board sizes and play on larger ones. The board game environment encodes the rules of the game and maintains the board state. We denote by A the set of possible actions and by S the set of possible board states. | В этом разделе мы подробно опишем нашу модель масштабируемых настольных игр на основе RL. Наша модель основана на AZ, оснащена дополнительными компонентами, которые позволяют ей тренироваться на досках небольшого размера и играть на досках большего размера. Среда настольной игры кодирует правила игры и поддерживает состояние доски. Мы обозначаем через A множество возможных действий, а через S - множество возможных состояний платы. |
| As mentioned in Section 2.1, the AZ player is an RL model consisting of a combined neural network, fθ : S → [0, 1]|A| × {−1, 0, 1}, with parameters θ and an MCTS. The network takes as input the raw board representation of the current state s ∈ S, and outputs fθ(s) = (ps, vs), where the probability vector ps = (p1, p2, ..., p|A|) ∈ [0, 1]|A| represents the probabilities of selecting each action on the board, and the value vs ∈ [−1, 1] estimates the chances of the current player winning the game (i.e., −1 for losing, 0 for a tie and 1 for winning), given its current state. At each state s, an fθ-guided MCTS is activated. The MCTS procedure then outputs the probability π for playing each valid move. For a full description of the MCTS procedure, see Appendix A.1. The pseudocode for our model, including the MCTS procedure, is provided in Appendix C. | Как упоминалось в разделе 2.1, AZ player представляет собой модель RL, состоящую из комбинированной нейронной сети, fθ : S → [0, 1]|A| × {-1, 0, 1}, с параметрами θ и MCTS. Сеть принимает в качестве входных данных необработанное представление платы текущего состояния s ∈ S и выдает fθ(s) = (ps, vs), где вектор вероятности ps = (p1, p2, ..., p|A|) ∈ [0, 1]|A| представляет вероятности выбора каждого действия на доске, а значение vs ∈ [-1, 1] оценивает шансы текущего игрока на победу в игре (т.е. -1 для проигрыша, 0 для ничьей и 1 для победы), учитывая его текущее состояние. В каждом состоянии s активируется MCTS, управляемый fθ. Затем процедура MCTS выводит вероятность π для воспроизведения каждого допустимого хода. Полное описание процедуры MCTS см. в Приложении A.1. Псевдокод для нашей модели, включая процедуру MCTS, приведен в приложении C. |
| To summarize, the main changes we made to the original AZ are • Replacing the CNN by our GNN. • Adding subgraph sampling for guidance of the MCTS search. • Removing rotation and reflection augmentations in the training set. The next sections elaborate on each of these components. | Подводя итог, можно сказать, что основными изменениями, которые мы внесли в оригинальный AZ, являются • Замена CNN на наш GNN. • Добавление выборки подграфов для руководства поиском MCTS. • Удаление дополнений вращения и отражения в обучающем наборе. В следующих разделах подробно рассматривается каждый из этих компонентов. |
| 3.1 Replacing the CNN | Замена CNN |
| The main difference between our scalable RL player and AZ comes from choosing the specific neural network type. AZ uses a CNN as the network fθ. As already mentioned, CNN architectures are limited due to the specific input they require, thus they do not enjoy the potential computational benefits of scalable methods. The message passing technique used in a GNN [Gilmer et al., 2017] (see Section 2.2) allows the network to get a variable sized graph with no limitation on either the number of nodes or the number of edges. In fact, a GNN only requires a fixed size of feature dimension for each node (and each edge, if edge features are used). This last observation makes a GNN a scalable neural network according to the definition above. Consequently, replacing the original CNN in the AZ framework with a GNN is a key step toward our construction of a scalable player mechanism. | Основное различие между нашим масштабируемым RL-плеером и AZ заключается в выборе конкретного типа нейронной сети. AZ использует CNN в качестве сетевого Fθ. Как уже упоминалось, архитектуры CNN ограничены из-за специфических входных данных, которые им требуются, поэтому они не пользуются потенциальными вычислительными преимуществами масштабируемых методов. Метод передачи сообщений, используемый в GNN [Gilmer et al., 2017] (см. Раздел 2.2), позволяет сети получать граф переменного размера без ограничений ни на количество узлов, ни на количество ребер. Фактически, GNN требует только фиксированного размера пространственного измерения для каждого узла (и каждого ребра, если используются граничные объекты). Это последнее наблюдение делает GNN масштабируемой нейронной сетью в соответствии с приведенным выше определением. Следовательно, замена оригинального CNN в рамках AZ на GNN является ключевым шагом на пути к созданию масштабируемого механизма воспроизведения |
| To instantiate fθ as a GNN, we first need to translate the board state into a graph. We define the graph G(s) = (V, E) where nodes in V are the positions on the board (usually, V = {(i, j)|i, j ∈ [n]} for a grid-like square board of size n × n), and the edges in E connect “geographically” adjacent positions on the board (for the grid-like example above we connect only vertical and horizontal neighbors and discard diagonal neighbors). For a node v ∈ V we denote by h 0 v the initial feature representing the current piece placed on v (−1 for a light piece, 1 for a dark piece and 0 for an empty square). Last, we add a dummy node (as demonstrated in Gilmer et al. [2017]) that is connected to all other nodes in V , allowing us to improve the long-distance data flow between nodes. The dummy node has an initial feature h 0 dummy = 0. Figure 1 illustrates the graph generation procedure, which corresponds to the initial board of the Othello game. | Чтобы создать экземпляр fθ как GNN, нам сначала нужно перевести состояние платы в график. Мы определяем граф G (s) = (V, E), где узлы в V - это позиции на доске (обычно V = {(i, j) | i, j ∈ [n]} для квадратной доски, похожей на сетку, размером n × n), и ребра в E соединяют “географически” соседние позиции на доске (для приведенного выше примера, похожего на сетку, мы соединяем только вертикальных и горизонтальных соседей и отбрасываем диагональных соседей). Для узла v ∈ V мы обозначаем через h 0 v начальный объект, представляющий текущую фигуру, размещенную на v (-1 для светлой фигуры, 1 для темной фигуры и 0 для пустого квадрата). Наконец, мы добавляем фиктивный узел (как показано в Gilmer et al. [2017]), который подключен ко всем другим узлам в V, что позволяет нам улучшить передачу данных на большие расстояния между узлами. Фиктивный узел имеет начальный признак h 0 dummy = 0. Рисунок 1 иллюстрирует процедуру генерации графика, которая соответствует начальной доске игры "Отелло". |
| Our GNN receives the generated graph as input and outputs both the probability for playing the specific action corresponding to the node and the value of the current state (i.e., the whole graph). The final GNN architecture, which is based on the GIN model (see the discussion in Section 2.2) with extra skip connections, is illustrated in Figure 2. The architecture was implemented using PyTorch Geometric [Fey and Lenssen, 2019]. It contains the following modules: | Наш GNN получает сгенерированный график в качестве входных данных и выводит как вероятность выполнения определенного действия, соответствующего узлу, так и значение текущего состояния (т.е. всего графика). Окончательная архитектура GNN, основанная на модели GIN (см. обсуждение в разделе 2.2) с дополнительными пропускными соединениями, показана на рисунке 2. Архитектура была реализована с использованием PyTorch Geometric [Fey and Lenssen, 2019]. Он содержит следующие модули: |
| 1. Three GIN layers with layer normalization and a ReLU activation function. 2. Concatenation of all previous intermediate representations. 3. Two fully-connected layers with batch normalization, ReLU activation function and dropout. 4. The computation is separated into two different heads, for computing the policy p and the value v. p is computed using one fully-connected layer, followed by a log-sof tmax operation, yielding the probability vector. v is computed using one fully-connected layer, followed by a global mean pooling layer (i.e., the mean among all nodes) and, finally, a tanh nonlinearity function. | 1. Три слоя GIN с нормализацией слоев и функцией активации ReLU. 2. Объединение всех предыдущих промежуточных представлений. 3. Два полносвязных слоя с батч нормализацией, функцией активации ReLU и отсевом. 4. Вычисление разделяется на две разные главы для вычисления политики p и значения v. p вычисляется с использованием одного полностью связанного слоя, за которым следует операция log-softmax, дающая вектор вероятности. v вычисляется с использованием одного полностью связанного слоя, за которым следует глобальный средний уровень объединения (т.е. среднее значение среди всех узлов) и, наконец, функция нелинейности tanh. |
| 3.2 Guiding MCTS | Направляющие MCTS |
| The second change we made refers to the guidance of the MCTS by the network fθ. According to MCTS, fθ(s 0 ) = (ps 0 , vs 0 ) is computed for each nonterminal leaf node s 0 discovered during the game. These values are used for updating 4 the MCTS variables P(s 0 , ·) = ps 0 , propagating vs 0 along the path seen in the current game simulation, and updating their Q(s, a) values accordingly. | Второе изменение, которое мы внесли, относится к руководству MCTS со стороны сети Fθ. Согласно MCTS, fθ(s 0 ) = (ps 0 , vs 0 ) вычисляется для каждого нетерминального конечного узла s 0, обнаруженного во время игры. Эти значения используются для обновления 4 переменных MCTS P(s 0 , ·) = ps 0 , распространения vs 0 по пути, видимому в текущей игровой симуляции, и обновления их значений Q(s, a) соответственно. |
| Here we can take advantage of the scalability of our network fθ, and enhance the performance of the tree search. Upon arriving at s 0 , we sample a few subgraphs of the graph generated by s 0 and send them to fθ(·). For each subgraph we first sample the subgraph size d ∈ [(m − 1)2 , m2 ] and then sample d nodes present in the subgraph. The subgraph size d should be large enough to form an “interesting” new state and include enough legal actions. The subgraphs’ size range (m) as well as the number of sampled subgraphs are two hyperparameters of our model. Note that sending more than one graph to the network for each newly visited leaf node can be implemented efficiently using batches, which increases the prediction time by only a small factor. Our experiments show that using a small number of subgraphs improves the player’s performance remarkably. |