Memory Bounded Monte Carlo Tree Search

Abstract

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.