Coevolutionary genetic algorithm and graph neural networks for a risk-like board game : policy predictions for population initialization

Abstract

Over the last decades, various Artificial Intelligence techniques have been employed in Risk implementations to address the unique challenges posed by this complex strategy board game, such as its high branching factor and the variable topology of different maps. Modern state-of-the-art research has gravitated towards the use of Graph Neural Networks and algorithms that learn the game tabula rasa, aligning with the latest trends in AI for games like chess, shogi, and Go. Results indicate that this methodology has not yet surpassed the performance of incorporating hand-crafted logic into agents, as in other domains. Recently, Genetic Algorithms have been introduced to the cutting-edge performance toolbox as an alternative to tree-based search methods, showing promising improvements. In this approach, player moves are treated as individuals in a population, which is evolved to identify optimal solutions. As originally proposed (BAUER, 2024), populations are initialized by sampling random moves. This research explores and evaluates the effectiveness of incorporating policy prediction to initialize populations, as opposed to random initialization. In our experiments, the GA with policy initialization significantly outperformed the standard GA, achieving a 9.05% higher score and winning 60.6% of head-to-head matchups.

Nas últimas décadas, diferentes técnicas de Inteligência Artificial foram aplicadas em implementações de Risk para lidar com os desafios únicos proporcionados por esse complexo e estratégico jogo de tabuleiro, tais como o alto fator de ramificação do jogo, além das diferentes topologias de cada mapa. A pesquisa moderna que atinge o estado da arte convergiu para a utilização de Redes Neurais de Grafos e algoritmos que aprendem a jogar sem conhecimento prévio (tabula rasa), em conformidade com as últimas tendências em IA aplicada a jogos como xadrez, shogi e Go. Resultados indicam que essa linha metodológica ainda não foi capaz de superar agentes que incorporam lógicas específicas do jogo (feitas à mão), conforme acontece em outros domínios. Recentemente, Algoritmos Genéticos foram adicionados à caixa de ferramentas das técnicas de melhor performance, constituindo uma alternativa aos métodos baseados em busca em árvore, apresentando resultados contundentes. Essa classe de algoritmos trata as ações de um turno de um jogador como indivíduos de uma população, que é evoluída para a identificação das melhores solu- ções. Tipicamente, os indivíduos de uma população serão inicializados randomicamente, isto é, por amostragem de jogadas aleatórias. O presente trabalho visa experimentar o uso de predição de política na inicialização das populações, ao invés de recorrer à inicialização randômica. Nos nossos experimentos, o algoritmo genético com inicialização por predição de política desempenhou significativamente melhor que o algoritmo genético conforme originalmente proposto (BAUER, 2024), obtendo uma pontuação 9.05% maior, e vencendo 60.6% dos confrontos diretos.