Advanced

Online Evolution for Multi-Action Adversarial Games

Justesen, Niels; Mahlmann, Tobias LU and Togelius, Julian (2016) Evostar 2016 In Applications of Evolutionary Computation 2016 9597. p.590-603
Abstract
We present Online Evolution, a novel method for playing turn-based multi-action adversarial games. Such games, which include most strategy games, have extremely high branching factors due to each turn having multiple actions. In Online Evolution, an evolutionary algorithm is used to evolve the combination of atomic actions that make up a single move, with a state evaluation function used for fitness. We implement Online Evolution for the turn-based multi-action game Hero Academy and compare it with a standard Monte Carlo Tree Search implementation as well as two types of greedy algorithms. Online Evolution is shown to outperform these methods by a large margin. This shows that evolutionary planning on the level of a single move can be very... (More)
We present Online Evolution, a novel method for playing turn-based multi-action adversarial games. Such games, which include most strategy games, have extremely high branching factors due to each turn having multiple actions. In Online Evolution, an evolutionary algorithm is used to evolve the combination of atomic actions that make up a single move, with a state evaluation function used for fitness. We implement Online Evolution for the turn-based multi-action game Hero Academy and compare it with a standard Monte Carlo Tree Search implementation as well as two types of greedy algorithms. Online Evolution is shown to outperform these methods by a large margin. This shows that evolutionary planning on the level of a single move can be very effective for this sort of problems. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
evolutionary computation, monte carlo tree search, games, online evolution
in
Applications of Evolutionary Computation 2016
editor
Burelli, Paolo and Squillero, Giovanni
volume
9597
pages
13 pages
publisher
Springer
conference name
Evostar 2016
external identifiers
  • Scopus:84961750938
ISSN
0302-9743
ISBN
978-3-319-31203-3
DOI
10.1007/978-3-319-31204-0_38
language
English
LU publication?
yes
id
6e11bd69-842b-4d23-a9d1-92d3af7dd18a (old id 8569733)
date added to LUP
2016-01-28 10:02:15
date last changed
2017-01-01 07:59:32
@inproceedings{6e11bd69-842b-4d23-a9d1-92d3af7dd18a,
  abstract     = {We present Online Evolution, a novel method for playing turn-based multi-action adversarial games. Such games, which include most strategy games, have extremely high branching factors due to each turn having multiple actions. In Online Evolution, an evolutionary algorithm is used to evolve the combination of atomic actions that make up a single move, with a state evaluation function used for fitness. We implement Online Evolution for the turn-based multi-action game Hero Academy and compare it with a standard Monte Carlo Tree Search implementation as well as two types of greedy algorithms. Online Evolution is shown to outperform these methods by a large margin. This shows that evolutionary planning on the level of a single move can be very effective for this sort of problems.},
  author       = {Justesen, Niels and Mahlmann, Tobias and Togelius, Julian},
  booktitle    = {Applications of Evolutionary Computation 2016},
  editor       = {Burelli, Paolo and Squillero, Giovanni},
  isbn         = {978-3-319-31203-3},
  issn         = {0302-9743},
  keyword      = {evolutionary computation,monte carlo tree search,games,online evolution},
  language     = {eng},
  pages        = {590--603},
  publisher    = {Springer},
  title        = {Online Evolution for Multi-Action Adversarial Games},
  url          = {http://dx.doi.org/10.1007/978-3-319-31204-0_38},
  volume       = {9597},
  year         = {2016},
}