Automatic Goal Discovery in Subgoal Monte Carlo Tree Search
| Autor: | Dominik Jeurissen, Mark H.M. Winands, Chiara F. Sironi, Diego Perez-Liebana |
|---|---|
| Přispěvatelé: | Dept. of Advanced Computing Sciences, RS: FSE DACS |
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Zdroj: | 2021 IEEE Conference on Games (CoG), 990-993 STARTPAGE=990;ENDPAGE=993;TITLE=2021 IEEE Conference on Games (CoG) |
| Popis: | Monte Carlo Tree Search (MCTS) is a heuristic search algorithm that can play a wide range of games without requiring any domain-specific knowledge. However, MCTS tends to struggle in very complicated games due to an exponentially increasing branching factor. A promising solution for this problem is to focus the search only on a small fraction of states. Subgoal Monte Carlo Tree Search (S-MCTS) achieves this by using a predefined subgoal-predicate that detects promising states called subgoals. However, not only does this make S-MCTS domaindependent, but also it is often difficult to define a good predicate. In this paper, we propose using quality diversity (QD) algorithms to detect subgoals in real-time. Furthermore, we show how integrating QD-algorithms into S-MCTS significantly improves its performance in the Physical Travelling Salesmen Problem without requiring any domain-specific knowledge. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|