Abstract
Turn-based multi-action adversarial games are games in which each player turn consists of a sequence of atomic actions, resulting in an extremely high branching factor. Many strategy board, card, and video games fall into this category, for which the current state of the art is Online Evolutionary Planning (OEP) - an evolutionary algorithm (EA) that treats atomic actions as genes, and complete action sequences as genomes. In this paper, we introduce Evolutionary Monte Carlo Tree Search (EMCTS) to tackle this challenge, combining the tree search of MCTS with the sequence-based optimization of EAs. Experiments on the game Hero Academy show that EMCTS convincingly outperforms several baselines including OEP and an improved variant of OEP introduced in this paper, at different time settings and numbers of atomic actions per turn. EMCTS also scales better than any existing algorithm with the complexity of the problem.
| Original language | English |
|---|---|
| Title of host publication | Proceedings of the 2018 IEEE Conference on Computational Intelligence and Games, CIG 2018 |
| Publisher | IEEE Computer Society |
| Volume | 2018-August |
| ISBN (Electronic) | 9781538643594 |
| DOIs | |
| Publication status | Published - 11 Oct 2018 |
| Event | 14th IEEE Conference on Computational Intelligence and Games, CIG 2018 - Maastricht, Netherlands Duration: 14 Aug 2018 → 17 Aug 2018 |
Conference
| Conference | 14th IEEE Conference on Computational Intelligence and Games, CIG 2018 |
|---|---|
| Country/Territory | Netherlands |
| City | Maastricht |
| Period | 14/08/18 → 17/08/18 |
Keywords
- Game tree search
- Monte Carlo Tree Search
- Strategy games