Memory Bounded Monte Carlo Tree Search
Tools
Tools
Powley, Edward 
ORCID: 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.
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: | Computer Science, Information & General Works Technology > Digital Works > Digital Games |
| Courses by Department: | The Games Academy > Computing for Games |
| Related URLs: | |
| Depositing User: | Edward Powley |
| Date Deposited: | 04 Jan 2018 14:48 |
| Last Modified: | 11 Nov 2022 16:30 |
| URI: | https://repository.falmouth.ac.uk/id/eprint/2782 |
Actions
 |
View Item (login required) |