Memory Bounded Monte Carlo Tree Search

Tools

Powley, Edward ORCID logoORCID: https://orcid.org/0000-0002-7317-7304, Cowling, Peter I. and Whitehouse, Daniel (2018) Memory Bounded Monte Carlo Tree Search. In: 13th AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE'17), 5-9 October 2017, Snowbird, Utah, USA.

[thumbnail of MemoryLimiting.pdf]
Preview
 Text
MemoryLimiting.pdf - Accepted Version
Available under License Creative Commons Attribution Non-commercial.
Download (383kB) | Preview

Abstract / Summary

Monte Carlo Tree Search (MCTS) is an effective decision making algorithm that often works well without domain knowledge, finding an increasing application in commercial mobile and video games. A promising application of MCTS is creating AI opponents for board and card games, where Information Set MCTS (ISMCTS) can provide a challenging opponent and reduces the cost of creating game-specific AI opponents. Most research to date has aimed at improving the quality of decision making by (IS)MCTS, with respect to time usage. Memory usage is also an important constraint in commercial applications, particularly on mobile platforms or when there are many AI agents. This paper presents the first systematic study of memory bounding techniques for (IS)MCTS. (IS)MCTS is well known to be an anytime algorithm. We also introduce an anyspace version of (IS)MCTS which can make effective use of any pre-specified amount of memory. This algorithm has been implemented in a commercial version of the card game Spades downloaded more than 6 million times. We find that for games of imperfect information high quality decisions can be made with rather small memory footprints, making (IS)MCTS an even more attractive algorithm for commercial game implementations.

Item Type: Conference or Workshop Item (Paper)
Subjects: Computing & Data Science
Computing & Data Science > Game Design
Courses by Department: The Games Academy
Related URLs:
Depositing User: Edward Powley
Date Deposited: 04 Jan 2018 14:48
Last Modified: 18 Nov 2024 14:24
URI: https://repository.falmouth.ac.uk/id/eprint/2782
View Item View Record (staff only)
Altmetric