Publications
agents ai data decisions esports gaist games heuristics hyperheuristics optimisation scheduling search
2018 |
Baier, Hendrik; Cowling, Peter I Evolutionary MCTS with Flexible Search Horizon Inproceedings Proceedings of the AAAI Artificial Intelligence and Interactive Digital Entertainment Conference 2018 (AIIDE'18), Canada, AAAI, 2018. Abstract | BibTeX | Tags: agents, ai, decisions, games, heuristics, search | Links: @inproceedings{baier2018evolutionary, title = {Evolutionary MCTS with Flexible Search Horizon}, author = {Hendrik Baier and Peter I. Cowling}, url = {http://www.petercowling.com/wp-content/uploads/2018/09/Evolutionary-MCTS-with-Flexible-Search-Horizon.pdf}, year = {2018}, date = {2018-11-07}, booktitle = {Proceedings of the AAAI Artificial Intelligence and Interactive Digital Entertainment Conference 2018 (AIIDE'18), Canada}, journal = {In Proceedings of Artificial Intelligence and Interactive Digital Entertainment (AIIDE'18), Canada}, publisher = {AAAI}, abstract = {In turn-based multi-action adversarial games each player turn consists of several atomic actions, resulting in an extremely high branching factor. Many strategy board, card, and video games fall into this category, which is currently best played by Evolutionary MCTS (EMCTS) – searching a tree with nodes representing action sequences as genomes, and edges representing mutations of those genomes. However, regular EMCTS is unable to search beyond the current player’s turn, leading to strategic short-sightedness. In this paper, we extend EMCTS to search to any given search depth beyond the current turn, using simple models of its own and the opponent’s behavior. Experiments on the game Hero Academy show that this Flexible-Horizon EMCTS (FH-EMCTS) convincingly out- performs several baselines including regular EMCTS, Online Evolutionary Planning (OEP), and vanilla MCTS, at all tested numbers of atomic actions per turn. Additionally, the separate contributions of the behavior models and the flexible search horizon are analyzed.}, keywords = {agents, ai, decisions, games, heuristics, search}, pubstate = {published}, tppubtype = {inproceedings} } In turn-based multi-action adversarial games each player turn consists of several atomic actions, resulting in an extremely high branching factor. Many strategy board, card, and video games fall into this category, which is currently best played by Evolutionary MCTS (EMCTS) – searching a tree with nodes representing action sequences as genomes, and edges representing mutations of those genomes. However, regular EMCTS is unable to search beyond the current player’s turn, leading to strategic short-sightedness. In this paper, we extend EMCTS to search to any given search depth beyond the current turn, using simple models of its own and the opponent’s behavior. Experiments on the game Hero Academy show that this Flexible-Horizon EMCTS (FH-EMCTS) convincingly out- performs several baselines including regular EMCTS, Online Evolutionary Planning (OEP), and vanilla MCTS, at all tested numbers of atomic actions per turn. Additionally, the separate contributions of the behavior models and the flexible search horizon are analyzed. |
Baier, Hendrik; Cowling, Peter I Evolutionary MCTS for Multi-Action Adversarial Games Inproceedings Proceedings of the IEEE Conference on Computational Intelligence in Games, IEEE, 2018. Abstract | BibTeX | Tags: agents, decisions, heuristics, search | Links: @inproceedings{baier2018evolutionary_cig, title = {Evolutionary MCTS for Multi-Action Adversarial Games}, author = {Hendrik Baier and Peter I. Cowling}, url = {http://www.petercowling.com/wp-content/uploads/2019/02/baier2018evolutionary_cig.pdf}, year = {2018}, date = {2018-09-01}, booktitle = {Proceedings of the IEEE Conference on Computational Intelligence in Games}, publisher = {IEEE}, abstract = {Turn-based multi-action adversarial games are games in which each player turn consists of a sequence of atomic actions, resulting in an extremely high branching factor. Many strategy board, card, and video games fall into this category, for which the current state of the art is Online Evolutionary Planning (OEP) – an evolutionary algorithm (EA) that treats atomic actions as genes, and complete action sequences as genomes. In this paper, we introduce Evolutionary Monte Carlo Tree Search (EMCTS) to tackle this challenge, combining the tree search of MCTS with the sequence-based optimization of EAs. Experiments on the game Hero Academy show that EMCTS convincingly outperforms several baselines including OEP and an improved variant of OEP introduced in this paper, at different time settings and numbers of atomic actions per turn. EMCTS also scales better than any existing algorithm with the complexity of the problem.}, keywords = {agents, decisions, heuristics, search}, pubstate = {published}, tppubtype = {inproceedings} } Turn-based multi-action adversarial games are games in which each player turn consists of a sequence of atomic actions, resulting in an extremely high branching factor. Many strategy board, card, and video games fall into this category, for which the current state of the art is Online Evolutionary Planning (OEP) – an evolutionary algorithm (EA) that treats atomic actions as genes, and complete action sequences as genomes. In this paper, we introduce Evolutionary Monte Carlo Tree Search (EMCTS) to tackle this challenge, combining the tree search of MCTS with the sequence-based optimization of EAs. Experiments on the game Hero Academy show that EMCTS convincingly outperforms several baselines including OEP and an improved variant of OEP introduced in this paper, at different time settings and numbers of atomic actions per turn. EMCTS also scales better than any existing algorithm with the complexity of the problem. |