Aprendendo estratégias programáticas através de características comporta- mentais

• Ano de defesa: 2023
• Autor(a) principal: Aleixo, David da Silva
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Viçosa; Ciência da Computação
• Palavras-chave em Português: Inteligência artificial; Programação de sistemas (Computação); Algoritmo computacionais; Jogos; Ciência da Computação
• Link de acesso: https://locus.ufv.br//handle/123456789/31747; https://doi.org/10.47328/ufvbbt.2023.552

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.