Monte-Carlo tree search (MCTS) is an effective anytime algorithm with a vast
amount of applications. It strategically allocates computational resources to
focus on promising segments of the search tree, making it a very attractive
search algorithm in large search spaces. However, it often expends its limited
resources on reevaluating previously explored regions when they remain the most
promising path. Our proposed methodology, denoted as AmEx-MCTS, solves this
problem by introducing a novel MCTS formulation. Central to AmEx-MCTS is the
decoupling of value updates, visit count updates, and the selected path during
the tree search, thereby enabling the exclusion of already explored subtrees or
leaves. This segregation preserves the utility of visit counts for both
exploration-exploitation balancing and quality metrics within MCTS. The
resultant augmentation facilitates in a considerably broader search using
identical computational resources, preserving the essential characteristics of
MCTS. The expanded coverage not only yields more precise estimations but also
proves instrumental in larger and more complex problems. Our empirical
evaluation demonstrates the superior performance of AmEx-MCTS, surpassing
classical MCTS and related approaches by a substantial margin.

AmEx-MCTS is a novel formulation of Monte-Carlo tree search that decouples value updates, visit count updates, and the selected path, resulting in a considerably broader search using identical computational resources and surpassing classical MCTS and related approaches.