Playing multiaction adversarial games: Online evolutionary planning versus tree search

Niels Justesen, Tobias Mahlmann, Sebastian Risi, Julian Togelius

    Research output: Contribution to journalArticlepeer-review

    Abstract

    We address the problem of playing turn-based multiaction 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 multiaction 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.

    Original languageEnglish (US)
    Article number8007320
    Pages (from-to)281-291
    Number of pages11
    JournalIEEE Transactions on Games
    Volume10
    Issue number3
    DOIs
    StatePublished - Sep 2018

    Keywords

    • Computational complexity
    • Evolutionary computation
    • Monte Carlo tree search
    • Tree search

    ASJC Scopus subject areas

    • Artificial Intelligence
    • Software
    • Control and Systems Engineering
    • Electrical and Electronic Engineering

    Fingerprint Dive into the research topics of 'Playing multiaction adversarial games: Online evolutionary planning versus tree search'. Together they form a unique fingerprint.

    Cite this