Среди всех базовых игроков модели 4 и 5 демонстрируют наихудшую производительность против обоих противников и страдают от наибольшего снижения производительности по мере увеличения доски. Результаты обеих моделей предполагают, что использование небольшой сети, применяемой только к локальным областям полной платы, не обеспечивает хорошей мощности обобщения, вероятно, потому, что для полного наблюдения за состоянием необходимы долгосрочные отношения. Модель 3 довольно стабильна по размерам доски, разумно добиваясь наилучших результатов, играя на тех размерах доски, на которых она была обучена. Обратите внимание, что наш Отелло SAZ достигает своей максимальной эффективности на доске такого размера, которого он не видел во время тренировки.
|
We further examine the generalization power geometrically by considering the GNN actions’ latent space. We constructed synthetic Othello boards of specific form, shown in Figure 4a, in different sizes from 6 × 6 to 350 × 350. We apply Principal Component Analysis (PCA) [Wold et al., 1987] on the embedding provided by the GNN for two specific actions – one that we consider a “good action” (top-left corner, capturing all opponent pieces in the first column) and a second that we deem a “bad action” (bottom-right corner, which does not capture pieces at all). Figure 4b shows the first two components of the PCA analysis of both actions (on the X,Y plane) as a function of the board size (Z axis). Clearly, except for a few outliers, most of the good actions (blue) are separated easily from the bad ones (red), showing that the latent space successfully encodes the underlying structure of the actions on the board, even for massive board sizes
|
Далее мы исследуем силу обобщения геометрически, рассматривая скрытое пространство действий GNN. Мы сконструировали синтетические доски Отелло определенной формы, показанные на рис. 4а, разных размеров от 6 × 6 до 350 × 350. Мы применяем анализ главных компонентов (PCA) [Wold et al., 1987] для встраивания, предоставляемого GNN, для двух конкретных действий – одного, которое мы считаем “хорошим действием” (верхний левый угол, захват всех фигур противника в первом столбце), а второе, которое мы считаем “хорошим действием".плохое действие” (нижний правый угол, который вообще не захватывает фрагменты). На рис. 4b показаны первые два компонента анализа PCA для обоих действий (в плоскости X,Y) в зависимости от размера платы (ось Z). Очевидно, что, за исключением нескольких выбросов, большинство хороших действий (синие) легко отделяются от плохих (красные), показывая, что скрытое пространство успешно кодирует основную структуру действий на доске, даже для массивных размеров доски
|
Training time analysis: Figure 5 shows the progression of our GNN during training. We measure the GNN skill by evaluating the average outcome of model3 (i.e., an MCTS guided by the GNN), at each training stage, against the greedy opponent on a 16 × 16 Othello board and a 17 × 17 Gomoku board. Since we test the GNN on a larger board than the ones used for training, it can be seen as another measure of the generalization power. As a comparison we train model1 (i.e., original CNN) on the larger boards for 30 days and evaluate it along the training time as well.
|
Анализ времени тренировки: На рисунке 5 показано прогрессирование нашего GNN во время тренировки. Мы измеряем навык GNN, оценивая средний результат model3 (т.е. MCTS, управляемый GNN) на каждом этапе обучения против жадного противника на доске 16 × 16 Отелло и 17 × 17 Гомоку. Поскольку мы тестируем GNN на доске большего размера, чем те, что используются для обучения, это можно рассматривать как еще одну меру способности к обобщению. Для сравнения мы тренируем модель 1 (т.е. оригинальный CNN) на больших досках в течение 30 дней и оцениваем ее также во время обучения.
|
We observe that as training advances, model3 gets stronger, achieving around an 80% win rate at the end of training, and reaching parity with the greedy player after a few hours of training. In contrast, to achieve parity, model1 needed between four to five days of training, and achieving model3’s final win rate against the greedy player only after 28 days (Othello) and 23 days (Gomoku).
|
Мы наблюдаем, что по мере продвижения обучения model3 становится сильнее, достигая около 80% выигрыша в конце тренировки и достигая паритета с жадным игроком после нескольких часов тренировок. Напротив, для достижения паритета model1 требовалось от четырех до пяти дней тренировок, а достижение окончательного коэффициента выигрыша model3 против жадного игрока только через 28 дней (Отелло) и 23 дня (Гомоку).
|
Comparison to AZ: Table 3 shows the average outcome of various scalable players (rows) against the original AZ guided by a CNN (columns). Entries in the table represent the average outcome of the game with respect to the row player. Blue and red colors represent whether or not a specific (row) player wins more than 50% of the games against AZ. The scalable players include our model as well as other baseline players, all trained for three days on small boards (up to 9 × 9). AZ players were trained for ×10 days on the large board of the size that was used for testing (16 × 16 or 17 × 17).
|
Сравнение с AZ: В таблице 3 показан средний результат различных масштабируемых игроков (строки) против исходного AZ, управляемого CNN (столбцы). Записи в таблице представляют собой средний результат игры по отношению к игроку ряда. Синий и красный цвета указывают на то, выигрывает ли конкретный игрок (подряд) более 50% игр против AZ. Масштабируемые игроки включают в себя нашу модель, а также других базовых игроков, которые тренировались в течение трех дней на небольших досках (до 9 × 9). Игроки AZ тренировались в течение × 10 дней на большой доске того размера, который использовался для тестирования (16 × 16 или 17 × 17).
|
The results show that SAZ wins all competitions, with a more than 50% win rate on Othello and 100% on Gomoku. Model3, which does not use the subgraph sampling technique, also competes fairly well with AZ, but still reduces the performance by 24% on Othello. Both model4 and model5 Othello players are not competitive compared to AZ, showing again that global dependencies on the board are critical for gameplay. Nevertheless, both models produce a positive win rate against AZ on Gomoku, showing that local structures are more helpful for mastering this game. To further illustrate the capabilities of SAZ compared to AZ, we conduct the same experiment with 20 × 20 Othello and 19 × 19 Gomoku boards. The effect is much stronger, as SAZ wins 84% of Othello games against AZ. The AZ 19 × 19 Gomoku player performs poorly in all cases, suggesting that enlarging the board should be accompanied either with a more powerful CNN architecture or with more training.
|
Результаты показывают, что SAZ выигрывает все соревнования, с более чем 50% коэффициентом выигрыша в Отелло и 100% в Гомоку. Модель 3, которая не использует метод выборки подграфов, также довольно хорошо конкурирует с AZ, но все же снижает производительность на 24% в Отелло. Как игроки модели 4, так и модели 5 "Отелло" неконкурентоспособны по сравнению с AZ, что еще раз показывает, что глобальные зависимости от игрового поля имеют решающее значение для игрового процесса. Тем не менее, обе модели дают положительный коэффициент выигрыша против AZ на Гомоку, показывая, что локальные структуры более полезны для освоения этой игры. Чтобы дополнительно проиллюстрировать возможности SAS по сравнению с AZ, мы проводим тот же эксперимент с 20 = 20 досками Отелло и 19 = 19 Гомоку. Эффект гораздо сильнее, так как САЗ выигрывает 84% игр Отелло против АЗ. Игрок AZ 19 × 19 в Гомоку во всех случаях работает плохо, что говорит о том, что расширение доски должно сопровождаться либо более мощной архитектурой CNN, либо дополнительной подготовкой.
|
Go evaluation: Training AZ to the game of Go with full boards is computationally challenging with our available resources. Recall that Deepmind used ∼ 5000 TPUs for 13 days to train AZ 19 × 19 Go player. We therefore trained our SAZ for three days on Go boards of maximal size 9 × 9. To test our model we trained two AZ players on boards of sizes 9 × 9 and 15 × 15 for 20 and 10 days, respectively. Our analysis suggests that SAZ wins around 68% (on a 9 × 9 board) and 77.5% (on a 15 × 15 board) of the games against AZ. These results as well as the extensive experiments on Othello and Gomoku, which have some similarity to the properties of Go, indicate that our method can lead to solutions that master the game of Go with much less computational overhead.
|
Оценка игры в Го: Обучение AZ игре в Go с полными досками является сложной вычислительной задачей с нашими доступными ресурсами. Напомним, что Deepmind использовала 5000 ТПУ в течение 13 дней для обучения AZ 19 × 19 Go. Поэтому мы тренировали наших игроков SAZ в течение трех дней на досках Go максимального размера 9 × 9. Чтобы протестировать нашу модель, мы тренировали двух игроков AZ на досках размером 9 × 9 и 15 × 15 в течение 20 и 10 дней соответственно. Наш анализ показывает, что SAZ побеждает около 68% (на доске 9 = 9) и 77,5% (на доске 15 = 15) игр против AZ. Эти результаты, а также обширные эксперименты с Отелло и Гомоку, которые имеют некоторое сходство со свойствами Go, указывают на то, что наш метод может привести к решениям, которые позволяют освоить игру Go с гораздо меньшими вычислительными затратами.
|
5 Conclusion and future work
|
Заключение и будущая работа
|
In this paper we presented an end-to-end RL model for training on and playing scalable board games. Central to our approach is the combination of a scalable neural network (GNN), and the AZ algorithm. The use of GNNs facilitated the enhancement of the model by the subgraph sampling technique, and enabled scaling from small boards to large ones. Through extensive experimental evaluation, we demonstrated the effectiveness of our method in learning game strategies, which we validated using different games and various board sizes. The generalization analysis suggests that learning on small boards is faster and more practical than learning solely on large boards. The experiments shown in this paper suggest that SAZ offers a promising new technique for learning to play on large boards, requiring an order of magnitude less training, while keeping the performance level intact.
|
В этой статье мы представили сквозную модель RL для обучения масштабируемым настольным играм и игры в них. Центральное место в нашем подходе занимает комбинация масштабируемой нейронной сети (GNN) и алгоритма AZ. Использование пушек способствовало улучшению модели с помощью метода выборки подграфов и позволило масштабировать от маленьких досок до больших. Благодаря обширной экспериментальной оценке мы продемонстрировали эффективность нашего метода в изучении игровых стратегий, которые мы проверили, используя разные игры и доски разного размера. Обобщающий анализ показывает, что обучение на небольших досках происходит быстрее и практичнее, чем обучение исключительно на больших досках. Эксперименты, показанные в этой статье, показывают, что SAZ предлагает многообещающую новую технику для обучения игре на больших досках, требующую на порядок меньше тренировок при сохранении неизменного уровня производительности.
|
We have left a number of potential improvements to future work. First, to date we have focused on board games whose actions refer to the nodes on the graph. This focus was natural because GNNs output the feature vector for each node. Nevertheless, we can use the same approach for another family of board games by using GNNs that estimate edge features (e.g., the game of Chess can be formulated as a graph problem where edges correspond to the actions on the board). A promising approach to achieve this could be to use the method of Berg et al. [2017] who employ the incident node features to derive edge representations. Furthermore, our subgraph sampling technique, which effectively improved our model performance in our context by reducing the GNN’s uncertainty, is of potential independent interest. It would be interesting to validate this approach in different domains. Another promising idea would be to use a model pretrained with our approach and then finetune it to a larger board. The finetuned model would possibly enhance the performance on that size. Finally, it would be important to consider deeper GNN architectures, which will possibly enable discovering longer term dependencies on the board.
|
Мы оставили ряд потенциальных улучшений для будущей работы. Во-первых, на сегодняшний день мы сосредоточились на настольных играх, действия которых относятся к узлам на графике. Этот фокус был естественным, потому что GNNs выводят вектор признаков для каждого узла. Тем не менее, мы можем использовать тот же подход для другого семейства настольных игр, используя GNNs, которые оценивают характеристики ребер (например, игра в шахматы может быть сформулирована как задача о графе, где ребра соответствуют действиям на доске). Многообещающим подходом для достижения этой цели могло бы стать использование метода Berg et al. [2017], которые используют функции узла инцидента для получения представлений ребер. Кроме того, наш метод выборки подграфов, который эффективно улучшил производительность нашей модели в нашем контексте за счет уменьшения неопределенности GNN, представляет потенциальный независимый интерес. Было бы интересно проверить этот подход в разных областях. Другой многообещающей идеей было бы использовать модель, предварительно обученную нашему подходу, а затем доработать ее для платы большего размера. Тонко настроенная модель, возможно, повысила бы производительность при таком размере. Наконец, было бы важно рассмотреть более глубокие архитектуры GNN, которые, возможно, позволят обнаружить долгосрочные зависимости на плате.
| |
Скачать 55.36 Kb.