Information capture and reuse strategies in Monte Carlo Tree Search, with applications to games of hidden information

Powley, Edward ORCID: https://orcid.org/0000-0002-7317-7304, Cowling, Peter I and Whitehouse, Daniel (2014) Information capture and reuse strategies in Monte Carlo Tree Search, with applications to games of hidden information. Artificial Intelligence, 217 (Dec). pp. 92-116. ISSN 0004-3702

Preview

Text info_capture_reuse.pdf Download (715kB) | Preview

Abstract / Summary

Monte Carlo Tree Search (MCTS) has produced many breakthroughs in search-based decision-making in games and other domains. There exist many general-purpose enhancements for MCTS, which improve its efficiency and effectiveness by learning information from one part of the search space and using it to guide the search in other parts. We introduce the Information Capture And ReUse Strategy (ICARUS) framework for describing and combining such enhancements. We demonstrate the ICARUS framework's usefulness as a frame of reference for understanding existing enhancements, combining them, and designing new ones.

We also use ICARUS to adapt some well-known MCTS enhancements (originally designed for games of perfect information) to handle information asymmetry between players and randomness, features which can make decision-making much more difficult. We also introduce a new enhancement designed within the ICARUS framework, EPisodic Information Capture and reuse (EPIC), designed to exploit the episodic nature of many games. Empirically we demonstrate that EPIC is stronger and more robust than existing enhancements in a variety of game domains, thus validating ICARUS as a powerful tool for enhancement design within MCTS.

Item Type:	Article
Identification Number:	10.1016/j.artint.2014.08.002
ISSN:	0004-3702
Subjects:	Computing & Data Science Computing & Data Science > Game Design
Courses by Department:	The Games Academy
Depositing User:	Edward Powley
Date Deposited:	24 Mar 2017 13:49
Last Modified:	18 Nov 2024 14:25
URI:	https://repository.falmouth.ac.uk/id/eprint/2264

View Record (staff only)