Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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

Justesen, Niels ; Mahlmann, Tobias LU ; Risi, Sebastian and Togelius, Julian (2018) In IEEE Transactions on Games 10(3). p.281-291
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
; ; and
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Evolutionary computation, Games, Monte Carlo methods, Planning, Real-time systems, Search problems
in
IEEE Transactions on Games
volume
10
issue
3
pages
281 - 291
publisher
IEEE - Institute of Electrical and Electronics Engineers Inc.
external identifiers
  • scopus:85087797993
ISSN
2475-1502
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
2022-04-25 02:53:36
@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         = {{2475-1502}},
  keywords     = {{Evolutionary computation; Games; Monte Carlo methods; Planning; Real-time systems; Search problems}},
  language     = {{eng}},
  number       = {{3}},
  pages        = {{281--291}},
  publisher    = {{IEEE - Institute of Electrical and Electronics Engineers Inc.}},
  series       = {{IEEE Transactions on Games}},
  title        = {{Playing Multi-Action Adversarial Games : Online Evolutionary Planning versus Tree Search}},
  url          = {{http://dx.doi.org/10.1109/TCIAIG.2017.2738156}},
  doi          = {{10.1109/TCIAIG.2017.2738156}},
  volume       = {{10}},
  year         = {{2018}},
}