Multiagent Monte Carlo Tree Search

Monte Carlo Tree Search (MCTS) is a best-first search which is efficient in large search spaces and is effective at balancing exploration versus exploitation. In this work, we introduce a novel extension for MCTS, called Multiagent Monte Carlo Tree Search (MAMCTS), which pairs MCTS with difference evaluations. We demonstrate the performance of MAMCTS in a cooperative, multiagent path-planning domain called Multiagent Gridworld. We show that MAMCTS using difference evaluations outperforms MAMCTS using local rewards by up to 31.4% and MAMCTS using the global reward by up to 88.9% for a system with 1,000 agents.