  Monte Carlo Tree Search (MCTS) algorithms such as AlphaGo and MuZero have
achieved superhuman performance in many challenging tasks. However, the
computational complexity of MCTS-based algorithms is influenced by the size of
the search space. To address this issue, we propose a novel probability tree
state abstraction (PTSA) algorithm to improve the search efficiency of MCTS. A
general tree state abstraction with path transitivity is defined. In addition,
the probability tree state abstraction is proposed for fewer mistakes during
the aggregation step. Furthermore, the theoretical guarantees of the
transitivity and aggregation error bound are justified. To evaluate the
effectiveness of the PTSA algorithm, we integrate it with state-of-the-art
MCTS-based algorithms, such as Sampled MuZero and Gumbel MuZero. Experimental
results on different tasks demonstrate that our method can accelerate the
training process of state-of-the-art algorithms with 10%-45% search space
reduction.
