Bi-Directional Monte Carlo Tree Search

Kristian Spoerer
dx.doi.org/10.17576/apjitm-2021-1001-02

Abstract

This paper describes a new algorithm called Bi-Directional Monte Carlo Tree Search. The essential idea of Bi-directional Monte Carlo Tree Search is to run an MCTS forwards from the start state, and simultaneously run an MCTS backwards from the goal state, and stop when the two searches meet. Bi-Directional MCTS is tested on 8-Puzzle and Pancakes Problem, two single-agent search problems, which allow control over the optimal solution length d and average branching factor b respectively. Preliminary results indicate that enhancing Monte Carlo Tree Search by making it Bi-Directional speeds up the search. The speedup of Bi-directional MCTS grows with increasing the problem size, in terms of both optimal solution length d and also branching factor b. Furthermore, Bi-Directional Search has been applied to a Reinforcement Learning algorithm. It is hoped that the speed enhancement of Bi-directional Monte Carlo Tree Search will also apply to other planning problems.

keyword

Single Agent Search, Monte Carlo Tree Search, Bi-Directional Search, 8-Puzzle, Pancakes Problem, Reinforcement Learning.

Area

Data Mining and Optimization