Dissertação

{en_GB=A Rapidly-exploring Random Trees based approach for General Video Game Playing} {} EVALUATED

{pt=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%., en=General Video Game Playing (GVGP) is a field of Artificial Intelligence (AI) where the goal is to design an agent that can play a variety of video games successfully. This field approximates the important problem of general AI. Rapidly-exploring Random Trees (RRT) is a search algorithm known to perform well in a variety of domains, however it has not been used so far in a GVGP agent. In this thesis, we investigate how RRT can be applied as the exploration algorithm of a GVGP agent. We identify the problems that prevent RRT from being directly applied in a GVGP agent and propose three variants of it, that circumvent those problems. We also investigate two possible enhancements for the algorithms: Species First (SF), a novel technique designed by us to avoid the repeated exploration of identical states and Tree Reuse (TR), a common technique in GVGP agents. The proposed solution is evaluated using the deterministic single-player games of General Video Game AI (GVG-AI), a GVGP competition. Results show that the variants of RRT we propose make for viable GVGP agents, however not competitive with the best vanilla algorithm, Monte Carlo Tree Search (MCTS) – average win ratio of 12.9% on our best variant vs 17.0% for MCTS. The SF enhancement proved beneficial for our agents, being part of our best agent, which has a win ratio of 14.2%.}
{pt=Rapidly-exploring Random Trees, General Video Game Playing, General Video Game AI, Inteligência Artificial para Jogos, video jogos, en=Rapidly-exploring Random Trees, General Video Game Playing, General Video Game AI, Artificial Intelligence for Games, video games}

Novembro 5, 2018, 14:30

Orientação

ORIENTADOR

João Miguel De Sousa de Assis Dias

Departamento de Engenharia Informática (DEI)

Professor Auxiliar