Learning sketches for programmatic strategies

• Ano de defesa: 2021
• Autor(a) principal: Medeiros, Leandro Couto
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: eng
• Instituição de defesa: Universidade Federal de Viçosa; Ciência da Computação
• Palavras-chave em Português: Inteligência artificial; Aprendizado do computador; Jogos; Ciência da Computação
• Link de acesso: https://locus.ufv.br//handle/123456789/29671; https://doi.org/10.47328/ufvbbt.2022.076

Program synthesis has been a major focus of research in recent years due to its innate capability of generating interpretable programs. By contrast, neural network models are implemented as opaque models and are thus hard to interpret. Neural networks are eas- ier to train because gradient information is available while program synthesis tasks are not differentiable, making the optimization task challenging. In this work we show that behavioral cloning can be used to learn effective sketches of programmatic strategies, fa- cilitating the optimization task. We show that even the sketches learned by cloning the behavior of weak players can help the synthesis of programmatic strategies. This is be- cause even weak players can provide helpful information, e.g., that a player must choose an action in their turn of the game. If behavioral cloning is not employed, the synthesizer needs to learn even the most basic information by playing the game, which can be compu- tationally expensive. We demonstrate empirically the advantages of our sketch-learning approach with synthesizers based on simulated annealing and with synthesizers based on UCT. We evaluate our synthesizers in the games of Can’t Stop and MicroRTS. The sketch-based synthesizers are able to learn stronger programmatic strategies than their original counterparts. Our synthesizers generate strategies of Can’t Stop that defeat a tra- ditional programmatic strategy for the game. They also synthesize strategies that defeat the best performing method from the latest MicroRTS competition. Keywords: Artificial Intelligence. Program Synthesis. Search. Games.