# Single-Agent Optimization Through Policy Iteration Using Monte-Carlo Tree Search

arXiv: https://arxiv.org/abs/2005.11335 · HTML: https://mlsanity.com/paper/2005.11335/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 May 2020.

## Built on by (most cited first, 3 of 3)

- [Transformer Based Planning in the Observation Space with Applications to Trick Taking Card Games](https://mlsanity.com/paper/2404.13150/) (2024)
- [Alphazzle: Jigsaw Puzzle Solver with Deep Monte-Carlo Tree Search](https://mlsanity.com/paper/2302.00384/) (2023)
- [Towards Tackling MaxSAT by Combining Nested Monte Carlo with Local Search](https://mlsanity.com/paper/2302.13225/) (2023)

## Abstract (arXiv)

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.