Single-Agent Optimization Through Policy Iteration Using Monte-Carlo Tree Search
This work addresses single-agent optimization problems, such as puzzle games, by improving search efficiency and performance, though it is incremental as it builds on existing MCTS and reinforcement learning techniques.
The paper tackled the problem of applying Monte-Carlo Tree Search (MCTS) to single-agent optimization by enhancing it with action value normalization, a virtual loss function for parallelization, and a policy network trained via self-play, resulting in outperforming baseline algorithms on SameGame and being competitive with state-of-the-art methods on public benchmarks.
The combination of Monte-Carlo Tree Search (MCTS) and deep reinforcement learning is state-of-the-art in two-player perfect-information games. In this paper, we describe a search algorithm that uses a variant of MCTS which we enhanced by 1) a novel action value normalization mechanism for games with potentially unbounded rewards (which is the case in many optimization problems), 2) defining a virtual loss function that enables effective search parallelization, and 3) a policy network, trained by generations of self-play, to guide the search. We gauge the effectiveness of our method in "SameGame"---a popular single-player test domain. Our experimental results indicate that our method outperforms baseline algorithms on several board sizes. Additionally, it is competitive with state-of-the-art search algorithms on a public set of positions.