Перевод статьи по английскому языку. Playing board games is considered a major challenge for both humans and ai researchers
 Скачать 55.36 Kb.
|
| Здесь мы можем воспользоваться преимуществами масштабируемости нашей сети fθ и повысить производительность поиска по дереву. По прибытии в s 0 мы отбираем несколько подграфов графа, сгенерированного s 0, и отправляем их в fθ(·). Для каждого подграфа мы сначала выбираем размер подграфа d ∈ [(m − 1)2 , m2 ], а затем выбираем d узлов, присутствующих в подграфе. Размер подграфа d должен быть достаточно большим, чтобы сформировать “интересное” новое состояние и включить достаточное количество юридических действий. Диапазон размеров подграфов (m)’ а также количество отобранных подграфов являются двумя гиперпараметрами нашей модели. Обратите внимание, что отправка более одного графика в сеть для каждого вновь посещенного конечного узла может быть эффективно реализована с использованием пакетов, что увеличивает время прогнозирования лишь в небольшой раз. Наши эксперименты показывают, что использование небольшого количества подграфов значительно улучшает производительность игрока. | |
| The MCTS variables are updated in our model according to P(s 0 , ·) = (p1+p1◦p2)/2, where p1 is the probability vector ps 0 taken from the evaluation fθ(G(s 0 )), p2 is the scatter mean/max of the probability vectors computed on the subgraphs (i.e., it takes into account how many times a node was sampled), and ◦ stands for element-wise multiplication. Propagating v(s 0 ) remains unchanged. | Переменные MCTS обновляются в нашей модели в соответствии с P(s 0 , ·) = (p1+p1◦p2)/2, где p1 - вектор вероятности ps 0, взятый из оценки fθ(G(s 0 )), p2 - среднее значение разброса / макс векторов вероятности вычисляется на подграфах (т.е. учитывает, сколько раз был выбран узел), а ◦ означает поэлементное умножение. Распространяющийся v(s 0 ) остается неизменным. |
| 3.3 Training pipeline | Конвейер обучения |
| The training pipeline, as in the AZ model, comprises a loop between the selfplay and optimization stages. The game result, z ∈ {−1, 0, 1}, of each selfplay is propagated to all the states visited during the game. The player plays against itself, thus accumulating positive and negative examples. The neural network parameters are optimized at the end of the selfplay stage to match the MCTS probabilities π and the winner z. For more details about the AZ training pipeline, see Appendix A.2. | Конвейер обучения, как и в модели AZ, содержит цикл между этапами самостоятельного воспроизведения и оптимизации. Результат игры, z ∈ {-1, 0, 1}, каждой самостоятельной игры распространяется на все состояния, посещенные во время игры. Игрок играет против самого себя, накапливая таким образом положительные и отрицательные примеры. Параметры нейронной сети оптимизируются в конце этапа самоигры, чтобы соответствовать вероятностям π MCTS и победителю z. Для получения более подробной информации о программе обучения AZ см. Приложение A.2. |
| For each training example produced during selfplay, AGZ generates extra examples by looking at rotations and reflections of the board. In contrast, AZ did not use these extra training examples, demonstrating the strength of their guiding network. By looking at the board as a graph, our GNN takes these invariances into account, thus justifying the removal of extra examples without the need to enhance the performance of the guiding network (e.g., by increasing the number of parameters). Consequently, removing rotation and reflection examples results in a massive reduction in the required training resources and substantially speeds up training time (by 5x). | Для каждого обучающего примера, созданного во время самостоятельной игры, AGZ генерирует дополнительные примеры, просматривая вращения и отражения доски. В отличие от этого, AZ не использовала эти дополнительные обучающие примеры, демонстрируя силу своей руководящей сети. Рассматривая доску в виде графика, наш GNN учитывает эти инвариантности, тем самым оправдывая удаление дополнительных примеров без необходимости повышения производительности направляющей сети (например, за счет увеличения количества параметров). Следовательно, удаление примеров вращения и отражения приводит к значительному сокращению требуемых ресурсов для обучения и существенно ускоряет время обучения (в 5 раз). |
| 4 Evaluation | Оценка |
| We conduct our experiments on three scalable board games: (1) Othello [Landau, 1985]: also known as Reversi. Players alternately place stones on the board trying to “capture” the opponent’s stones. Any straight line sequence of stones belonging to the opponent, lying between the just placed stone and another stone of the current player, are turned over and switch colors. The winner is determined by the majority stones’ color. (2) Gomoku: also known as ‘Five in a row’ or Gobang. Players take turns placing stones on the board. The first player to place k (here 5) stones in a row, a column or a diagonal, wins. (3) Go: the well-known game of Go [Smith, 1908]. Two players alternately place stones on intersections of the board with the goal of surrounding more territory than the opponent. Table 1 analyzes the game complexity of the games used for testing. | Мы проводим наши эксперименты с тремя масштабируемыми настольными играми: (1) Отелло [Ландау, 1985]: также известный как Реверси. Игроки поочередно размещают камни на доске, пытаясь “захватить” камни противника. Любая прямая последовательность камней, принадлежащих противнику, лежащих между только что размещенным камнем и другим камнем текущего игрока, переворачивается и меняет цвет. Победитель определяется по цвету большинства камней. (2) Гомоку: также известный как ‘Пять в ряд’ или Гобанг. Игроки по очереди выкладывают камни на доску. Выигрывает первый игрок, который разместит k (здесь 5) камней в ряд, столбец или по диагонали. (3) Го: хорошо известная игра Го [Смит, 1908]. Два игрока поочередно размещают камни на пересечениях доски с целью окружить больше территории, чем соперник. В таблице 1 анализируется игровая сложность игр, используемых для тестирования. |
| We define two reference opponents for each game: a random player that randomly chooses a legal move, and a greedy player that chooses his action based on a hand-coded tactical heuristic score. The specific heuristics for each game is described in Appendix D. The greedy opponent provides a sufficient challenge to demonstrate the utility of generalization. Note that both reference players can play on every board size without making any changes to the action-choosing mechanism. | Мы определяем двух эталонных противников для каждой игры: случайного игрока, который случайным образом выбирает законный ход, и жадного игрока, который выбирает свое действие на основе закодированного вручную тактического эвристического счета. Конкретные эвристические приемы для каждой игры описаны в приложении D. Жадный оппонент представляет собой достаточный вызов, чтобы продемонстрировать полезность обобщения. Обратите внимание, что оба эталонных игрока могут играть на доске любого размера без внесения каких-либо изменений в механизм выбора действий. |
| As a measure of success we use the average outcome of 100 games against one of the reference opponents, counted as 1 for a win, 0.5 for a tie and 0 for a loss. Each player plays half the time with dark pieces (plays first) and half with light pieces (plays second). We also analyze individually each main change we made. Furthermore, we play against the original AZ player that was trained to play on a large board, which enables us to measure the effect of our improvements on the training speed and realtime playing performance. Full CNN architecture of the AZ player in described in Appendix D. All tables and graphs provided include standard errors (five independent runs). | В качестве показателя успеха мы используем средний результат 100 игр против одного из эталонных соперников, засчитываемый как 1 за победу, 0,5 за ничью и 0 за поражение. Каждый игрок играет половину времени темными фигурами (играет первыми) и половину светлыми фигурами (играет вторыми). Мы также анализируем индивидуально каждое внесенное нами основное изменение. Кроме того, мы играем против оригинального игрока AZ, который был обучен игре на большой доске, что позволяет нам измерить влияние наших улучшений на скорость обучения и производительность игры в реальном времени. Полная архитектура CNN проигрывателя AZ описана в приложении D. Все представленные таблицы и графики содержат стандартные ошибки (пять независимых запусков). |
| 4.1 Experimental setup | Экспериментальная установка |
| Our RL infrastructure runs over a physical computing cluster. To train SAZ, we use one GPU (TITAN X(Pascal)/PCIe/SSE2) and one CPU (Intel Core i7), referred to as one resource unit. For each experiment conducted, we use the same resources to train. Our Othello player model was trained for three days on boards of all sizes, between 5 and 8. Our Gomoku player was trained for 2.5 days on boards of random sizes, between 5 and 9. The hyperparameters are selected via preliminary results on small boards. The training parameters for SAZ and the original AZ are presented in Appendix D. | Наша инфраструктура RL работает на физическом вычислительном кластере. Для обучения SAZ мы используем один графический процессор (TITAN X (Pascal)/PCIe/SSE2) и один процессор (Intel Core i7), называемый единицей ресурсов. Для каждого проведенного эксперимента мы используем одни и те же ресурсы для обучения. Наша модель игрока в Отелло тренировалась в течение трех дней на досках всех размеров, от 5 до 8. Наш игрок в гомоку тренировался в течение 2,5 дней на досках произвольного размера, от 5 до 9. Гиперпараметры выбираются по предварительным результатам на небольших досках. Параметры обучения для SAZ и исходного AZ представлены в приложении D. |
| 4.2 Model analysis | Анализ модели |
| For the model analysis we define some baseline players, each trained for three days (unless otherwise specified), as our model was: | Для анализа модели мы определяем несколько базовых игроков, каждый из которых тренируется в течение трех дней (если не указано иное), поскольку наша модель была: |
| • Model1 refers to training the original AZ (with a CNN replacing the GNN) on the actual board size used for testing. We used a shallower CNN than the one used in the AZ model, due to our limited computational resources (the architecture is described in Appendix D). Note that because we failed to train a competitive AZ player with the shallow CNN, we reused symmetries of the training examples (see Section 3.3) as proposed in AGZ model. • Model2 refers to training SAZ on the actual board size used for testing, rather than smaller boards. • Model3 is the same player as SAZ without the subgraph sampling component, i.e., the action probabilities are taken directly from the output of fθ on the full graph. • Model4 is the same as SAZ except here we discard the output of fθ on the full graph; thus, the action probabilities are calculated only according to the sampled subgraphs’ mean. • Model5 refers to an MCTS guided by a small CNN. The small CNN was trained by the AZ model on a smaller board of size m. The action probabilities are taken as the scatter mean of the network output on all the sub-boards of size m of the state that is evaluated. | • Model1 относится к обучению исходного AZ (с CNN, заменяющим GNN) на фактическом размере платы, используемой для тестирования. Мы использовали более мелкий CNN, чем тот, который использовался в модели AZ, из-за наших ограниченных вычислительных ресурсов (архитектура описана в приложении D). Обратите внимание, что, поскольку нам не удалось обучить конкурентоспособного игрока AZ с помощью мелкого CNN, мы повторно использовали симметрии обучающих примеров (см. Раздел 3.3), как предложено в модели AGZ. • Модель 2 относится к обучению SAZ на фактическом размере платы, используемой для тестирования, а не на платах меньшего размера. • Model3 - это тот же игрок, что и SAZ, без компонента выборки подграфа, т.е. вероятности действий берутся непосредственно из выходных данных fθ на полном графике. • Model4 ’ это то же самое, что и SAZ, за исключением того, что здесь мы отбрасываем вывод fθ на полном графике; таким образом, вероятности действий вычисляются только в соответствии со средним значением выборочных подграфов. • Модель 5 относится к MCTS, управляемому небольшим CNN. Маленький CNN был обучен моделью AZ на доске меньшего размера m. Вероятности действий берутся как среднее значение разброса выходных данных сети на всех подплатах размера m оцениваемого состояния. |
| The merits of our modified components: We start with a small ablation study, where we evaluate the contributions of our main changes. We start with the complete SAZ and leave one component out each time, both for training and realtime playing purposes. Note that in this experiment, we focus on the first two changed components presented in Section 3. Removal of the third component was tested as well, but, as expected, it has no effect on the performance, as the GNN framework has the property of rotation and reflection invariant. It does, however, increase the training time significantly. | Достоинства наших модифицированных компонентов: Мы начинаем с небольшого исследования абляции, где оцениваем вклад наших основных изменений. Мы начинаем с полного секса и каждый раз оставляем один компонент, как для тренировок, так и для игр в реальном времени. Обратите внимание, что в этом эксперименте мы фокусируемся на первых двух измененных компонентах, представленных в разделе 3. Удаление третьего компонента также было протестировано, но, как и ожидалось, это никак не повлияло на производительность, поскольку фреймворк GNN обладает свойством инвариантности вращения и отражения. Однако это значительно увеличивает время обучения. |
| Table 2 shows the average outcome (see definition in Section 4) of each model playing against the greedy opponent on a 16 × 16 board for Othello, and 17 × 17 for Gomoku. Blue and red colors represent whether or not a player wins more than 50% of the games against the greedy opponent. In general, it can be seen that removing each component results in a decrease in performance. Both model1 and model2 produce the poorest results, probably due to insufficient training time on the large board. Model3 is already achieving fair results, while our SAZ slightly improves its performance. We will further discuss the subgraph sampling contribution in the next experiment. | В таблице 2 показан средний результат (см. определение в разделе 4) каждой модели, играющей против жадного противника на доске 16 × 16 для Отелло и 17 × 17 для Гомоку. Синий и красный цвета показывают, выигрывает ли игрок более 50% игр у жадного соперника. В целом, можно видеть, что удаление каждого компонента приводит к снижению производительности. Как model1, так и model2 дают самые плохие результаты, вероятно, из-за недостаточного времени обучения на большой доске. Модель 3 уже достигает неплохих результатов, в то время как наш РАЗМЕР немного улучшает ее производительность. Мы дополнительно обсудим вклад выборки подграфа в следующем эксперименте. |
| Generalization to larger boards: As mentioned, SAZ was designed to allow training and playing on different sizes of input. The generalization study is presented in Figure 3 and shows the average outcome against the reference opponents for Othello and Gomoku, on various board sizes. We also include other baseline players’ performance. All models tested in this experiment were trained for three days on our machine. Overall, SAZ performs significantly better than other methods, consistently winning over 75% of the games against the greedy opponent in all cases. | Обобщение для больших досок: Как уже упоминалось, SAZ был разработан для того, чтобы позволить тренироваться и играть на разных входных данных. Обобщающее исследование представлено на рисунке 3 и показывает средний результат против эталонных соперников для "Отелло" и "Гомоку" на различных размерах доски. Мы также учитываем результаты других базовых игроков. Все модели, протестированные в этом эксперименте, были обучены в течение трех дней на нашей машине. В целом, SAZ работает значительно лучше, чем другие методы, последовательно выигрывая более 75% игр у жадного противника во всех случаях. |
| Among all baseline players, model4 and model5 exhibit the worst performance against both opponents and suffer the greatest performance decrease as the board gets larger. The results of both models suggest that using a small network, applied only on local areas of the full board, does not provide good generalization power, probably because long-term relations are necessary to fully observe the state. Model3 is pretty stable along board sizes, reasonably achieving its best results playing on the board sizes on which it was trained. Observe that our Othello SAZ reaches its peak efficacy on a board size that it had not seen during training. |