Meta busca de Monte Carlo em árvores usando caça níquel multialavanca combinatorial com contexto

Abstract

A técnica de Busca de Monte Carlo em Árvores (MCTS - Monte Carlo Tree Search) tem se popularizado nos últimos anos devido aos recentes resultados positivos, incluindo o desempenho sobrehumano em Go. Embora o algoritmo base de Monte Carlo tenha se mostrado efetivo em diferentes contextos, os melhores resultados são atingidos quando técnicas compatíveis com a espécie de problema são aplicados. A literatura existente apresenta uma série de estratégias que melhoram o desempenho do algoritmo quando aplicado domínios específicos, mas a determinação de qual variação é efetiva em cada domínio é atualmente feita pelo projetista, e a pesquisa se beneficiaria de uma ferramenta capaz de automatizar o processo de escolha da melhor variante do algoritmo. Este trabalho apresenta o Meta MCTS, uma solução para o problema de seleção das melhorias do MCTS para cada problema usando Caça Níqueis Multialavanca com Contexto (CCMAB - Contextual Combinatorial Multi-Armed Bandits). Em CCMABs, cada contexto é um caça níquel e o objetivo é maximizar a recompensa, dada pela combinação das alavancas ativadas no caça-níquel. Em nossa modelagem, cada domínio de aplicação do MCTS é um contexto e cada possível melhoria do MCTS é uma alavanca do caça-níquel correspondente. Para contornar o problema da explosão combinatorial que ocorre com o número de melhorias, usamos a técnica de Naïve Sampling para definir quais melhorias selecionar em cada contexto. Para testar o algoritmo em diferentes contextos, usamos a plataforma GVGAI (General Video Game Artificial Intelligence), onde um agente deve jogar múltiplos jogos digitais. Os resultados experimentais mostram que o Meta MCTS consegue determinar as melhorias mais promissoras para cada contexto em apenas 500 iterações de treinamento, atingindo um desempenho superior à linha de base, onde as melhorias são ligadas independentemente do contexto. Considerando-se o desempenho médio dos algoritmos para os jogos analisados, nosso método obteve resultados aproximados ao estado-da-arte.

The Monte Carlo Tree Search (MCTS) technique has become popular in the last years due to the recent positive results, including the superhuman performance in the game of Go. Even though the vanilla version of the algorithm has been successful in different contexts, the best results are achieved when strategies tuned to the specific problem are used. Existing studies showcase multiple strategies that improve the algorithm performance when used in specific domains, but the selection of the variants that are suited to a given context is currently executed by the researcher, and future projects would benefit from a tool that automates this choice of the best variant. This work presents Meta MCTS, a solution for the selection of enhancements for each domain using Contextual Combinatorial Multi Armed Bandits (CCMABs). In CCMABs, each context is represented by a bandit and the objective is to maximize the rewards that are granted given the combination of arms activated in the bandit. In our model, each application domain is a context and each MCTS enhancement is an arm in the corresponding bandit. To deal with the combinatorial explosion that arises from the large number of enhancements, we use the Naïve Sampling technique to determine which modifications should be selected in a given context. To test the algorithm in different scenarios we used the GVGAI (General Video Game Artificial Intelligence) framework where the agent must play multiple computer games. Our experimental results show that Meta MCTS is able to determine the most promising enhancements for each domain in only 500 training iterations, outperforming the baseline, where the modifications are used without considering the current context.