Learning sketches for programmatic strategies

Detalhes bibliográficos
Ano de defesa: 2021
Autor(a) principal: Medeiros, Leandro Couto
Orientador(a): Não Informado pela instituição
Banca de defesa: Não Informado pela instituição
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
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Link de acesso: https://locus.ufv.br//handle/123456789/29671
https://doi.org/10.47328/ufvbbt.2022.076
Resumo: 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.