Learning sketches for programmatic strategies

Abstract

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.

Síntese de programas tem sido um grande foco de pesquisa nos últimos anos devido à sua inata capacidade de gerar programas interpretáveis. Em contraste com modelos de redes neurais, que são implementados como modelos opacos e portanto são difíceis de interpretar. Redes neurais são mais fáceis de treinar devido à informação do gradiente estar disponível, enquanto que tarefas de síntese de programas não são diferenciáveis, tornando a tarefa de otimização desafiante. Nesta dissertação é mostrado que a clonagem comportamental pode ser usada para aprender rascunhos de estratégias programáticas, facilitando a tarefa de otimização. Foi observado que até rascunhos aprendidos ao clonar o comportamento de jogadores fracos podem ajudar na síntese de estratégias programáticas. Isto ocorre porque até mesmo jogadores fracos conseguem prover informações úteis, e.g., que um jogador deve escolher uma ação em sua rodada do jogo. Caso clonagem compor- tamental não seja usada, o sintetizador precisa aprender até mesmo as informações mais básicas jogando o jogo, o que pode ser computacionalmente custoso. É empiricamente de- monstrado as vantagens da abordagem de aprendizado por rascunhos com sintetizadores baseados na têmpera simulada e com sintetizadores baseados no algoritmo UCT. Os sin- tetizadores foram avaliados nos jogos Can’t Stop e MicroRTS. Os sintetizadores baseados em rascunhos são capazes de aprender estratégias programáticas mais fortes do que as abordagens originais. Os sintetizadores geraram estratégias de Can’t Stop que derrotaram uma estratégia programática tradicional do jogo. Também foram sintetizadas estratégias que derrotaram o método com a melhor performance da última competição de MicroRTS. Palavras-chave: Inteligência Artificial. Síntese de Programas. Busca. Jogos.