Online Evolution for Multi-Action Adversarial Games

Research output: Chapter in Book/Report/Conference proceedingPaper in conference proceeding

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.

Details

Authors
  • Niels Justesen
  • Tobias Mahlmann
  • Julian Togelius
Organisations
Research areas and keywords

Subject classification (UKÄ) – MANDATORY

  • Computer Science

Keywords

  • evolutionary computation, monte carlo tree search, games, online evolution
Original languageEnglish
Title of host publicationApplications of Evolutionary Computation 2016
EditorsPaolo Burelli, Giovanni Squillero
PublisherSpringer
Pages590-603
Number of pages13
Volume9597
ISBN (Electronic)978-3-319-31204-0
ISBN (Print)978-3-319-31203-3
Publication statusPublished - 2016
Publication categoryResearch
Peer-reviewedYes
EventEvostar 2016 -
Duration: 2016 Mar 30 → …

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume9597
ISSN (Print)0302-9743

Conference

ConferenceEvostar 2016
Period2016/03/30 → …

Total downloads

No data available