Monte Carlo Tree Search With Reversibility Compression

Monte Carlo Tree Search (MCTS) has been shown to be an effective algorithm for solving search problems in the absence of heuristics. MCTS performs best in spaces where every action has a significant impact on the outcome of the search. In many domains, however, particularly single-player games, many actions have little impact on the outcome, which makes MCTS perform poorly without heuristic support. To address this deficiency in such sparse-impact search problems, we introduce MCTS with Reversibility Compression, or MCTS-R, which uses the notion of action reversibility to compress MCTS trees as they are constructed, without loss of information. This not only reduces the memory footprint of the search tree, but also accelerates search by preventing the duplication of already-explored states, and increasing the attention paid to significant actions. We show that our approach outperforms several comparable algorithms for solving sparse-impact search problems.