Файл: Playing board games is considered a major challenge for both humans and ai researchers.docx
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 03.05.2024
Просмотров: 5
Скачиваний: 0
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
26079
| ABSTRACT | |
| Playing board games is considered a major challenge for both humans and AI researchers. Because some complicated board games are quite hard to learn, humans usually begin with playing on smaller boards and incrementally advance to master larger board strategies. Most neural network frameworks that are currently tasked with playing board games neither perform such incremental learning nor possess capabilities to automatically scale up. In this work, we look at the board as a graph and combine a graph neural network architecture inside the AlphaZero framework, along with some other innovative improvements. Our ScalableAlphaZero is capable of learning to play incrementally on small boards, and advancing to play on large ones. Our model can be trained quickly to play different challenging board games on multiple board sizes, without using any domain knowledge. We demonstrate the effectiveness of ScalableAlphaZero and show, for example, that by training it for only three days on small Othello boards, it can defeat the AlphaZero model on a large board, which was trained to play the large board for 30 days. | Игра в настольные игры считается серьезной проблемой как для людей, так и для исследователей искусственного интеллекта. Поскольку некоторые сложные настольные игры довольно трудно освоить, люди обычно начинают с игры на досках меньшего размера и постепенно осваивают стратегии на больших досках. Большинство фреймворков нейронных сетей, которым в настоящее время поручено играть в настольные игры, не выполняют такого постепенного обучения и не обладают возможностями автоматического масштабирования. В этой работе мы рассматриваем доску как график и объединяем архитектуру графовой нейронной сети внутри фреймворка AlphaZero, наряду с некоторыми другими инновационными улучшениями. Наш ScalableAlphaZero способен постепенно учиться играть на маленьких досках и продвигаться вперед, чтобы играть на больших. Нашу модель можно быстро обучить играть в различные сложные настольные игры на досках разных размеров, не используя никаких знаний предметной области. Мы демонстрируем эффективность ScalableAlphaZero и показываем, например, что, тренируя его всего три дня на маленьких досках Отелло, он может победить модель AlphaZero на большой доске, которая была обучена играть на большой доске в течение 30 дней. |
| 1 Introduction | |
| Learning a simple instance of a problem with the goal of solving a more complicated one is a common approach within various fields. Both humans and AI programs use such incremental learning, particularly when the large-scale problem instance is too hard to learn from scratch or too expensive. This paper is concerned with applying incremental learning to the challenge of mastering board games. When playing board games, humans have the advantage of being able to learn the game on a small board, recognize the main patterns, and then implement the strategies they have acquired, possibly with some adjustments, on a larger board. In contrast, machine learning algorithms usually cannot generalize well between board sizes. While simple heuristics, such as zero padding of the board or analyzing local neighborhoods, can alleviate this generalization problem, they do not scale well for enlarged boards | Изучение простого примера проблемы с целью решения более сложной - это распространенный подход в различных областях. Как люди, так и программы искусственного интеллекта используют такое постепенное обучение, особенно когда крупномасштабный экземпляр проблемы слишком сложен для изучения с нуля или слишком дорог. Эта статья посвящена применению поэтапного обучения к задаче освоения настольных игр. Играя в настольные игры, люди имеют то преимущество, что могут научиться игре на маленькой доске, распознать основные закономерности, а затем реализовать приобретенные стратегии, возможно, с некоторыми корректировками, на доске большего размера. В отличие от этого, алгоритмы машинного обучения обычно не могут хорошо обобщать между размерами платы. В то время как простые эвристики, такие как нулевое заполнение доски или анализ локальных окрестностей, могут облегчить эту проблему обобщения, они плохо масштабируются для увеличенных досок |
| In this paper we propose ScalableAlphaZero (SAZ), a deep reinforcement learning (RL) based model that can generalize to multiple board sizes of a specific game. SAZ is trained on small boards and is expected to scale successfully to larger ones. Our technique should be usable for scalable board games, whose rules for one board size apply to all feasible board sizes (typically, infinitely many). For instance, Go is scalable but standard chess is not. A strong motivation for finding such a model is a potential substantial reduction in training time. As we demonstrate in this paper, training a model on small boards takes an order of magnitude less time than on large ones. The reason is that the dimension of states is significantly smaller, and gameplay requires fewer turns to complete. | В этой статье мы предлагаем ScalableAlphaZero (SAZ), основанную на глубоком обучении с подкреплением (RL), которая может быть обобщена на несколько размеров доски в конкретной игре. SAZ обучается на небольших досках и, как ожидается, успешно перейдет на более крупные. Наша методика должна быть применима для масштабируемых настольных игр, правила которых для одного размера доски применяются ко всем возможным размерам доски (как правило, бесконечно многим). Например, Go масштабируема, но стандартные шахматы - нет. Сильной мотивацией для поиска такой модели является потенциальное существенное сокращение времени обучения. Как мы демонстрируем в этой статье, обучение модели на маленьких досках занимает на порядок меньше времени, чем на больших. Причина в том, что размер состояний значительно меньше, а игровой процесс требует меньше ходов для завершения. |
| The proposed model is based on two modifications of the well-known AlphaZero (AZ) algorithm. To the best of our knowledge, presently AZ is the strongest superhuman RL based system for two-player zero-sum games. The main drawback of AZ is that it limits the user to training and playing only on a specific board size. This is the result of using a convolutional neural network (CNN) for predictive pruning of the AZ tree. To overcome this obstacle, in SAZ we replace the CNN by a graph neural network (GNN) The GNN is a scalable neural network, i.e., it is an architecture that is not tied to a fixed input dimension. GNN’s scalability enables us to train and play on different board sizes and allows us to scale up to arbitrarily large boards with a constant number of parameters. To further improve the AZ tree search pruning, we propose an ensemble-like node prediction using subgraph sampling; namely, we utilize the same GNN for evaluating a few subgraphs of the full board and then combine their scores to reduce the overall prediction uncertainty. | Предлагаемая модель основана на двух модификациях хорошо известного алгоритма AlphaZero (AZ). Насколько нам известно, в настоящее время AZ является сильнейшей системой, основанной на сверхчеловеческих RL, для игр с нулевой суммой для двух игроков. Главный недостаток AZ заключается в том, что он ограничивает пользователя тренировками и игрой только на доске определенного размера. Это результат использования сверточной нейронной сети (CNN) для прогнозирующей обрезки дерева AZ. Чтобы преодолеть это препятствие, в SAZ мы заменяем CNN графовой нейронной сетью (GNN) GNN - это масштабируемая нейронная сеть, т.е. это архитектура, которая не привязана к фиксированному входному измерению. Масштабируемость GNN позволяет нам тренироваться и играть на досках разного размера, а также позволяет масштабировать до сколь угодно больших досок с постоянным количеством параметров. Чтобы еще больше улучшить обрезку поиска по дереву AZ, мы предлагаем предсказание узлов, подобное ансамблю, с использованием выборки подграфа; а именно, мы используем один и тот же GNN для оценки нескольких подграфов полной платы, а затем объединяем их оценки, чтобы уменьшить общую неопределенность прогнозирования. |
| We conduct experiments on three scalable board games and measure the quality of SAZ by comparing it to various opponents on different board sizes. Our results indicate that SAZ, trained on a maximal board size of 9 × 9, can generalize well to larger boards (e.g., 20×20). Furthermore, we evaluate it by competing against the original AZ player, trained on a large board. Our model, with around ten times less training (computation) time on the same hardware, and without training at all on the actual board size that was used for playing, performs surprisingly well and achieves comparable results. | Мы проводим эксперименты с тремя масштабируемыми настольными играми и измеряем качество SAZ, сравнивая его с различными противниками на разных размерах доски. Наши результаты показывают, что SAZ, обученный на доске максимального размера 9 × 9, может хорошо обобщаться на доски большего размера (например, 20 × 20). Кроме того, мы оцениваем его, соревнуясь с оригинальной AZ, обученной игре на большой доске. Наша модель, затрачивающая примерно в десять раз меньше времени на обучение (вычисления) на том же оборудовании и вообще не требующая обучения реальному размеру доски, которая использовалась для игры, работает на удивление хорошо и достигает сопоставимых результатов. |
| The main contributions of this work are: (1) a model that is capable of successfully scaling up board game strategies. As far as we know this is the first work that combines RL with GNNs for this task; (2) a subgraph sampling technique that effectively decreases prediction uncertainty of GNNs in our context and is of potential independent interest; (3) the presentation of extensive experiments, demonstrated on three different board games, showing that our model requires an order of magnitude less training time than the original AZ but, still, can defeat AZ on large boards. | Основными результатами этой работы являются: (1) модель, способная успешно масштабировать стратегии настольных игр. Насколько нам известно, это первая работа, в которой RL сочетается с GNNs для этой задачи; (2) метод выборки подграфов, который эффективно уменьшает неопределенность прогнозирования GNNs в нашем контексте и представляет потенциальный независимый интерес; (3) презентация обширных экспериментов, продемонстрированных на трех разных настольных играх, показывающая что наша модель требует на порядок меньше времени на обучение, чем оригинальная AZ, но, тем не менее, может победить AZ на больших досках. |
| 2 Related work | Сопутствующая работа |
| The solution proposed in this paper instantiates a GNN model inside the AlphaZero model for the task of scalable board game playing. In this section, we briefly review early work in AI and board games, focusing on the AlphaZero [Silver et al., 2017a] algorithm. We further describe the GNN design and review various works that use GNN to guide an RL model. Finally, we summarize existing methods that aim to deal with scalable board games and accelerate the generalization between sizes. | Решение, предложенное в этой статье, создает экземпляр модели GNN внутри модели AlphaZero для задачи масштабируемой настольной игры. В этом разделе мы кратко рассмотрим ранние работы в области искусственного интеллекта и настольных игр, сосредоточив внимание на алгоритме AlphaZero [Silver et al., 2017a]. Далее мы опишем конструкцию GNN и рассмотрим различные работы, в которых GUN используется для управления моделью RL. Наконец, мы обобщаем существующие методы, направленные на работу с масштабируемыми настольными играми и ускорение обобщения между размерами. |
| 2.1 AlphaZero for board games | AlphaZero для настольных игр |
| Given an optimization problem, deep RL aims at learning a strategy for maximizing the problem’s objective function. The majority of RL programs do not use any expert knowledge about the environment, and learn the optimal strategy by exploring the state and action spaces with the goal of maximizing their cumulative reward. | Учитывая задачу оптимизации, глубокий RL нацелен на изучение стратегии максимизации целевой функции задачи. Большинство программ RL не используют никаких экспертных знаний об окружающей среде и изучают оптимальную стратегию, исследуя состояние и пространство действий с целью максимизации их совокупного вознаграждения. |
| AlphaGo (AG) [Silver et al., 2016] is an RL framework that employs a policy network trained with examples taken from human games, a value network trained by selfplay, and Monte Carlo tree search (MCTS) [Coulom, 2006], which defeated a professional Go player in 2016. About a year later, AlphaGo Zero (AGZ) [Silver et al., 2017b] was released, improving AlphaGo’s performance with no handcrafted game specific heuristics; however, it was still tested only on the game of Go. AlphaZero [Silver et al., 2017a] validated the general framework of AGZ by adapting the same mechanism to the games of Chess and Shogi. AG and AGZ have a three-stage training pipeline: selfplay, optimization and evaluation, whereas AZ skips the evaluation step. AGZ and AZ do not use their neural network to make move decisions directly. Instead, they use it to identify the most promising actions for the search to explore, as well as to estimate the values of nonterminal states. | AlphaGo (AG) [Silver et al., 2016] - это платформа RL, в которой используется сеть политик, обученная примерам, взятым из человеческих игр, сеть ценностей, обученная игрой с самой собой, и поиск по дереву Монте-Карло (MCTS) [Coulom, 2006], которая победила профессионального игрока в Го в 2016 году. Примерно год спустя была выпущена AlphaGo Zero (AGZ) [Silver et al., 2017b], улучшившая производительность AlphaGo без использования эвристики, специфичной для конкретной игры; однако она по-прежнему тестировалась только в игре Go. AlphaZero [Silver et al., 2017a] подтвердил общую структуру AGZ, адаптировав тот же механизм к играм в шахматы и сёги. AG и AGZ имеют трехэтапный конвейер обучения: самостоятельная игра, оптимизация и оценка, в то время как AZ пропускает этап оценки. AGZ и AZ не используют свою нейронную сеть для непосредственного принятия решений о перемещении. Вместо этого они используют его для определения наиболее перспективных действий для поиска, а также для оценки значений нетерминальных состояний. |
| 2.2 Graph neural networks | Графовые нейронные сети |
| GNNs, introduced in Scarselli et al. [2008], are a promising family of neural networks for graph structured data. GNNs have shown encouraging results in various fields including natural language processing, computer vision, logical reasoning and combinatorial optimization. Over the last few years, several variants of GNNs have been developed (e.g., Hamilton et al. [2017], Gilmer et al. [2017], Li et al. [2015], Velickovi ˇ c et al. [2017], Defferrard et al. [2016]), while the ´ selection of the actual variant that suits the specific problem depends on the particularities of the task. | GNNs, представленные в Scarselli et al. [2008], представляют собой многообещающее семейство нейронных сетей для графически структурированных данных. GNNs показали обнадеживающие результаты в различных областях, включая обработку естественного языка, компьютерное зрение, логическое мышление и комбинаторную оптимизацию. За последние несколько лет было разработано несколько вариантов GNNS (например, Hamilton et al. [2017], Gilmer et al. [2017], Li et al. [2015], Velickovic et al. [2017], Defferrard et al. [2016]), в то время как отбор выбор фактического варианта, подходящего для конкретной задачи, зависит от особенностей задачи. |
| In their basic form, GNNs update the features associated with some elements of an input graph denoted by G = (V, E), based on the connections between these elements in the graph. A message passing algorithm iteratively propagates information between nodes, updates their state accordingly, and uses the final state of a node, also called “node embedding”, to compute the desired output. Appendix B.1 provides more details about the message passing procedure. In this paper we use graph isomorphism networks (GINs) [Xu et al., 2018], which are a powerful well-known variant of GNNs. For further details about GINs, see Appendix B.2. | В своей базовой форме GNNs обновляют функции, связанные с некоторыми элементами входного графа, обозначаемыми G = (V, E), на основе связей между этими элементами в графе. Алгоритм передачи сообщений итеративно распространяет информацию между узлами, соответствующим образом обновляет их состояние и использует конечное состояние узла, также называемое “встраиванием узла”, для вычисления желаемого результата. В приложении B.1 содержится более подробная информация о процедуре передачи сообщений. В этой статье мы используем сети изоморфизма графов (GINs) [Xu et al., 2018], которые являются мощным хорошо известным вариантом GNNs. Более подробную информацию о GNNs см. в приложении B.2. |
| Среди всех базовых игроков модели 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, которые, возможно, позволят обнаружить долгосрочные зависимости на плате. |