A Rapidly-exploring Random Trees based approach for General Video Game Playing EVALUATED

Detalhes: General Video Game Playing (GVGP) é uma área da Inteligência Artificial (IA) cujo objetivo é criar agentes que sejam capazes de jogar uma variedade de jogos com sucesso. Esta área é uma aproximação do importante problema de IA geral. Rapidly-exploring Random Trees (RRT) é um algoritmo de procura com sucesso numa variedade de domínios. Contudo, nunca foi usado em um agente de GVGP. Nesta tese, é investigado como o RRT pode ser aplicado como algoritmo de exploração de um agente de GVGP. Nós identificamos os problemas que impedem o RRT de ser diretamente aplicado em um agente de GVGP e propomos três variantes dele que contornam esses problemas. Também investigamos duas possíveis melhorias para os algoritmos: Species First (SF), uma técnica nova que concebida por nós para evitar a exploração repetida de estados idênticos e Tree Reuse (TR), uma técnica comum em agentes de GVGP. A solução proposta é avaliada usando os jogos singleplayer determinísticos da General Video Game AI (GVG-AI), uma competição de GVGP. Os resultados mostram que as variantes de RRT que propomos fazem agentes viáveis de GVGP, contudo não competitivos com o melhor algoritmo de base, o Monte Carlo Tree Search (MCTS) – média do rácio de vitória de 12.9% na nossa melhor variante e de 17.0% no MCTS. A técnica SF mostrou-se benéfica para os nossos agentes, fazendo parte do nosso melhor agente, que tem uma média de rácio de vitória de 14.2%.

Discussão: novembro 5, 2018, 14:30

Publicação

Obra sujeita a Direitos de Autor

Orientação

AUTOR

Rui Miguel Alves Malaquias da Silva (ist177213)

ORIENTADOR

João Miguel De Sousa de Assis Dias

Departamento de Engenharia Informática (DEI)

Professor Auxiliar