Advanced

Playing Multi-Action Adversarial Games : Online Evolutionary Planning versus Tree Search

Justesen, Niels; Mahlmann, Tobias LU ; Risi, Sebastian and Togelius, Julian (2017) In IEEE Transactions on Computational Intelligence and AI in Games
Abstract

We address the problem of playing turn-based multi-action adversarial games, which include many strategy games with extremely high branching factors as players take multiple actions each turn. This leads to the breakdown of standard tree search methods, including Monte Carlo Tree Search (MCTS), as they become unable to reach a sufficient depth in the game tree. In this paper we introduce Online Evolutionary Planning (OEP) to address this challenge, which searches for combinations of actions to perform during a single turn guided by a fitness function that evaluates the quality of a particular state. We compare OEP to different MCTS variations that constrain the exploration to deal with the high branching factor in the turn-based... (More)

We address the problem of playing turn-based multi-action adversarial games, which include many strategy games with extremely high branching factors as players take multiple actions each turn. This leads to the breakdown of standard tree search methods, including Monte Carlo Tree Search (MCTS), as they become unable to reach a sufficient depth in the game tree. In this paper we introduce Online Evolutionary Planning (OEP) to address this challenge, which searches for combinations of actions to perform during a single turn guided by a fitness function that evaluates the quality of a particular state. We compare OEP to different MCTS variations that constrain the exploration to deal with the high branching factor in the turn-based multi-action game Hero Academy. While the constrained MCTS variations outperform the vanilla MCTS implementation by a large margin, OEP is able to search the space of plans more efficiently than any of the tested tree search methods as it has a relative advantage when the number of actions per turn increases.

(Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
epub
subject
keywords
Evolutionary computation, Games, Monte Carlo methods, Planning, Real-time systems, Search problems
in
IEEE Transactions on Computational Intelligence and AI in Games
publisher
Institute of Electrical and Electronics Engineers Inc.
external identifiers
  • scopus:85029148021
ISSN
1943-068X
DOI
10.1109/TCIAIG.2017.2738156
language
English
LU publication?
yes
id
c9df9472-81f7-4873-b5f4-eba203d44526
date added to LUP
2017-10-03 08:54:52
date last changed
2018-01-07 12:20:24
@article{c9df9472-81f7-4873-b5f4-eba203d44526,
  abstract     = {<p>We address the problem of playing turn-based multi-action adversarial games, which include many strategy games with extremely high branching factors as players take multiple actions each turn. This leads to the breakdown of standard tree search methods, including Monte Carlo Tree Search (MCTS), as they become unable to reach a sufficient depth in the game tree. In this paper we introduce Online Evolutionary Planning (OEP) to address this challenge, which searches for combinations of actions to perform during a single turn guided by a fitness function that evaluates the quality of a particular state. We compare OEP to different MCTS variations that constrain the exploration to deal with the high branching factor in the turn-based multi-action game Hero Academy. While the constrained MCTS variations outperform the vanilla MCTS implementation by a large margin, OEP is able to search the space of plans more efficiently than any of the tested tree search methods as it has a relative advantage when the number of actions per turn increases.</p>},
  author       = {Justesen, Niels and Mahlmann, Tobias and Risi, Sebastian and Togelius, Julian},
  issn         = {1943-068X},
  keyword      = {Evolutionary computation,Games,Monte Carlo methods,Planning,Real-time systems,Search problems},
  language     = {eng},
  month        = {08},
  publisher    = {Institute of Electrical and Electronics Engineers Inc.},
  series       = {IEEE Transactions on Computational Intelligence and AI in Games},
  title        = {Playing Multi-Action Adversarial Games : Online Evolutionary Planning versus Tree Search},
  url          = {http://dx.doi.org/10.1109/TCIAIG.2017.2738156},
  year         = {2017},
}