Spending Thinking Time Wisely: Accelerating MCTS with Virtual Expansions
This addresses the problem of time-intensive AI search algorithms for applications with limited computational resources, though it is an incremental improvement over existing MCTS methods.
The paper tackles the high computational cost of Monte-Carlo tree search (MCTS) by proposing Virtual MCTS (V-MCTS), which adaptively allocates more search time to harder states and less to simpler ones, achieving comparable performance to original MCTS with less than 50% average search time in 9x9 Go and Atari games.
One of the most important AI research questions is to trade off computation versus performance since ``perfect rationality" exists in theory but is impossible to achieve in practice. Recently, Monte-Carlo tree search (MCTS) has attracted considerable attention due to the significant performance improvement in various challenging domains. However, the expensive time cost during search severely restricts its scope for applications. This paper proposes the Virtual MCTS (V-MCTS), a variant of MCTS that spends more search time on harder states and less search time on simpler states adaptively. We give theoretical bounds of the proposed method and evaluate the performance and computations on $9 \times 9$ Go board games and Atari games. Experiments show that our method can achieve comparable performances to the original search algorithm while requiring less than $50\%$ search time on average. We believe that this approach is a viable alternative for tasks under limited time and resources. The code is available at \url{https://github.com/YeWR/V-MCTS.git}.