Aprendendo estratégias programáticas através de características comporta- mentais
Arquivos
Data
2023-02-24
Autores
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Viçosa
Resumo
Nos últimos anos, a pesquisa em síntese de estratégias programáticas tem despertado bastante interesse dos pesquisadores por gerar programas que podem ser interpretados por humanos, sendo até mesmo possível modificá-los manualmente. Entretanto, sinteti- zar estratégias programáticas é uma tarefa desafiadora devido à necessidade de realizar uma busca não diferenciável em um grande espaço de programas. Deste modo, utiliza-se atualmente uma abordagem de self-play para guiar a busca. No entanto, essa abordagem geralmente fornece um fraco sinal para guiar a busca, uma vez que o self-play só é ca- paz de avaliar o desempenho de um programa em relação a outros programas. Assim, enquanto pequenas mudanças em um programa podem não melhorar o seu desempenho, tais mudanças podem representar passos na direção de um programa mais eficiente. Nessa dissertação, apresentaremos duas abordagens que utilizam características comportamen- tais para guiar a busca. A primeira utiliza as características comportamentais provenien- tes de um oráculo através do processo de clonagem comportamental para aprender um sketch de uma estratégia programática. Em nossos experimentos, observamos que até mesmos oráculos fracos podem prover informações úteis, ajudando na síntese. Testamos nossa proposta de aprendizado de sketch juntamente com os algoritmos de busca Simu- lated Annealing e UCT como sintetizadores. Com isso, tentamos sintetizar as melhores respostas aproximadas para uma estratégia tradicional do Can’t Stop e para o vencedor da competição de 2020 do MicroRTS. Nosso método foi capaz de sintetizar estratégias programáticas mais fortes do que os oráculos originais e derrotaram as estratégias alvo. Em nossa segunda abordagem, propomos um algoritmo de busca de dois níveis que busca concorrentemente no espaço de programas e em um espaço de características comporta- mentais. Nossa hipótese é que um algoritmo de self-play em conjunto com uma função baseada em características pode gerar um forte sinal para auxiliar a síntese. Enquanto ambas as funções são usadas para guiar a pesquisa no espaço do programa, a função de self-play é usada para guiar a pesquisa no espaço de características, com o objetivo de permitir a seleção de características com maior probabilidade de levar a programas vitoriosos. Testamos nossa hipótese no MicroRTS, um jogo de estratégia em tempo real. Nossos resultados mostram que a busca de dois níveis sintetiza estratégias mais fortes do que métodos que buscam apenas no espaço do programa. Além disso, as estratégias que nosso método sintetiza obtiveram a maior taxa de vitórias em um torneio simulado com vários agentes, incluindo os melhores agentes das duas últimas competições do MicroRTS. Palavras-chave: Inteligência Artificial. Síntese de Programas. Algoritmo de Busca. Jogos.
In recent years, research on the synthesis of programmatic strategies has aroused a lot of interest among researchers as it generates programs that can be interpreted by humans, and it is even possible to manually modify them. However, synthesizing programmatic strategies is a challenging task due to the need to perform a non-differentiable search on a large programs’ space. Thus, a self-play approach is currently used to guide the search. Nevertheless, this approach generally provides a weak signal to guide the search, since self-play is only able to evaluate the performance of a program in relation to other programs. Thereby, while small changes to a program may not improve its performance, such changes may represent steps towards a more efficient program. In this dissertation, we will present two approaches that use behavioral features to guide the search. The first uses the behavioral features derived from an oracle through the process of behavioral cloning to learn a sketch of a programmatic strategy. In our experiments, we observed that even weak oracles can provide useful information, helping with the synthesis. We tested our sketch learning proposal with Simulated Annealing and UCT search algorithms as synthesizers. With this, we tried to synthesize the best approximate answers for a traditional Can’t Stop strategy and for the winner of the 2020’s MicroRTS competition. Our method was able to synthesize stronger programmatic strategies than the original oracles and to defeate the target strategies. In our second approach, we propose a bilevel search algorithm that searches concurrently in the programs’ space and in a space of behavioral features. Our hypothesis is that a self-play algorithm in conjunction with a feature-based function can generate a strong signal to aid synthesis. While both functions are used to guide the search in the program space, the self-play function is used to guide the search in the features’ space, with the aim of allowing the selection of features that are more likely to lead to winning programs. We tested our hypothesis on MicroRTS, a real-time strategy game. Our results show that the bilevel search synthesizes stronger strategies than methods that search only in the program space. Furthermore, the strategies that our method synthesizes achieved the highest win rate in a simulated tournament with multiple baseline agents,including the best agents from the last two MicroRTS competitions. Keywords: Artificial Intelligence. Program Synthesis. Search Algorithm. Games.
In recent years, research on the synthesis of programmatic strategies has aroused a lot of interest among researchers as it generates programs that can be interpreted by humans, and it is even possible to manually modify them. However, synthesizing programmatic strategies is a challenging task due to the need to perform a non-differentiable search on a large programs’ space. Thus, a self-play approach is currently used to guide the search. Nevertheless, this approach generally provides a weak signal to guide the search, since self-play is only able to evaluate the performance of a program in relation to other programs. Thereby, while small changes to a program may not improve its performance, such changes may represent steps towards a more efficient program. In this dissertation, we will present two approaches that use behavioral features to guide the search. The first uses the behavioral features derived from an oracle through the process of behavioral cloning to learn a sketch of a programmatic strategy. In our experiments, we observed that even weak oracles can provide useful information, helping with the synthesis. We tested our sketch learning proposal with Simulated Annealing and UCT search algorithms as synthesizers. With this, we tried to synthesize the best approximate answers for a traditional Can’t Stop strategy and for the winner of the 2020’s MicroRTS competition. Our method was able to synthesize stronger programmatic strategies than the original oracles and to defeate the target strategies. In our second approach, we propose a bilevel search algorithm that searches concurrently in the programs’ space and in a space of behavioral features. Our hypothesis is that a self-play algorithm in conjunction with a feature-based function can generate a strong signal to aid synthesis. While both functions are used to guide the search in the program space, the self-play function is used to guide the search in the features’ space, with the aim of allowing the selection of features that are more likely to lead to winning programs. We tested our hypothesis on MicroRTS, a real-time strategy game. Our results show that the bilevel search synthesizes stronger strategies than methods that search only in the program space. Furthermore, the strategies that our method synthesizes achieved the highest win rate in a simulated tournament with multiple baseline agents,including the best agents from the last two MicroRTS competitions. Keywords: Artificial Intelligence. Program Synthesis. Search Algorithm. Games.
Descrição
Palavras-chave
Inteligência artificial, Programação de sistemas (Computação), Algoritmo computacionais, Jogos
Citação
ALEIXO, David da Silva. Aprendendo estratégias programáticas através de características comporta- mentais. 2023. 63 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal de Viçosa, Viçosa. 2023.