Online evolution for multi-action adversarial games

Niels Justesen; Tobias Mahlmann; Julian Togelius

doi:10.1007/978-3-319-31204-0_38

Online evolution for multi-action adversarial games

Niels Justesen, Tobias Mahlmann, Julian Togelius

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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.

Original language	English (US)
Title of host publication	Applications of Evolutionary Computation - 19th European Conference, EvoApplications 2016, Proceedings
Editors	Paolo Burelli, Giovanni Squillero
Publisher	Springer Verlag
Pages	590-603
Number of pages	14
ISBN (Print)	9783319312033
DOIs	https://doi.org/10.1007/978-3-319-31204-0_38
State	Published - 2016
Event	19th European Conference on Applications of Evolutionary Computation, EvoApplications 2016 - Porto, Portugal Duration: Mar 30 2016 → Apr 1 2016

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9597
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	19th European Conference on Applications of Evolutionary Computation, EvoApplications 2016
Country/Territory	Portugal
City	Porto
Period	3/30/16 → 4/1/16

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-319-31204-0_38

Cite this

Justesen, N., Mahlmann, T., & Togelius, J. (2016). Online evolution for multi-action adversarial games. In P. Burelli, & G. Squillero (Eds.), Applications of Evolutionary Computation - 19th European Conference, EvoApplications 2016, Proceedings (pp. 590-603). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9597). Springer Verlag. https://doi.org/10.1007/978-3-319-31204-0_38

Online evolution for multi-action adversarial games. / Justesen, Niels; Mahlmann, Tobias; Togelius, Julian.
Applications of Evolutionary Computation - 19th European Conference, EvoApplications 2016, Proceedings. ed. / Paolo Burelli; Giovanni Squillero. Springer Verlag, 2016. p. 590-603 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9597).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Justesen, N, Mahlmann, T & Togelius, J 2016, Online evolution for multi-action adversarial games. in P Burelli & G Squillero (eds), Applications of Evolutionary Computation - 19th European Conference, EvoApplications 2016, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9597, Springer Verlag, pp. 590-603, 19th European Conference on Applications of Evolutionary Computation, EvoApplications 2016, Porto, Portugal, 3/30/16. https://doi.org/10.1007/978-3-319-31204-0_38

Justesen N, Mahlmann T, Togelius J. Online evolution for multi-action adversarial games. In Burelli P, Squillero G, editors, Applications of Evolutionary Computation - 19th European Conference, EvoApplications 2016, Proceedings. Springer Verlag. 2016. p. 590-603. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-31204-0_38

Justesen, Niels ; Mahlmann, Tobias ; Togelius, Julian. / Online evolution for multi-action adversarial games. Applications of Evolutionary Computation - 19th European Conference, EvoApplications 2016, Proceedings. editor / Paolo Burelli ; Giovanni Squillero. Springer Verlag, 2016. pp. 590-603 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{5c6c4c7e9c0241559e729c14a33d5a33,

title = "Online evolution for multi-action adversarial games",

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 = "Niels Justesen and Tobias Mahlmann and Julian Togelius",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2016.; 19th European Conference on Applications of Evolutionary Computation, EvoApplications 2016 ; Conference date: 30-03-2016 Through 01-04-2016",

year = "2016",

doi = "10.1007/978-3-319-31204-0_38",

language = "English (US)",

isbn = "9783319312033",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "590--603",

editor = "Paolo Burelli and Giovanni Squillero",

booktitle = "Applications of Evolutionary Computation - 19th European Conference, EvoApplications 2016, Proceedings",

}

TY - GEN

T1 - Online evolution for multi-action adversarial games

AU - Justesen, Niels

AU - Mahlmann, Tobias

AU - Togelius, Julian

N1 - Publisher Copyright: © Springer International Publishing Switzerland 2016.

PY - 2016

Y1 - 2016

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84961750938&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84961750938&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-31204-0_38

DO - 10.1007/978-3-319-31204-0_38

M3 - Conference contribution

AN - SCOPUS:84961750938

SN - 9783319312033

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 590

EP - 603

BT - Applications of Evolutionary Computation - 19th European Conference, EvoApplications 2016, Proceedings

A2 - Burelli, Paolo

A2 - Squillero, Giovanni

PB - Springer Verlag

T2 - 19th European Conference on Applications of Evolutionary Computation, EvoApplications 2016

Y2 - 30 March 2016 through 1 April 2016

ER -

Online evolution for multi-action adversarial games

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this