# Tackling Morpion Solitaire with AlphaZero-likeRanked Reward Reinforcement Learning

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

## Key facts

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

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

- [Self-play Learning Strategies for Resource Assignment in Open-RAN Networks](https://mlsanity.com/paper/2103.02649/) (2021)
- [Adaptive Warm-Start MCTS in AlphaZero-like Deep Reinforcement Learning](https://mlsanity.com/paper/2105.06136/) (2021)
- [Policy-Based Self-Competition for Planning Problems](https://mlsanity.com/paper/2306.04403/) (2023)
- [Split Moves for Monte-Carlo Tree Search](https://mlsanity.com/paper/2112.07761/) (2021)
- [Towards Tackling MaxSAT by Combining Nested Monte Carlo with Local Search](https://mlsanity.com/paper/2302.13225/) (2023)
- [TSS GAZ PTP: Towards Improving Gumbel AlphaZero with Two-stage Self-play for Multi-constrained Electric Vehicle Routing Problems](https://mlsanity.com/paper/2502.15777/) (2025)

## Abstract (arXiv)

Morpion Solitaire is a popular single player game, performed with paper and pencil. Due to its large state space (on the order of the game of Go) traditional search algorithms, such as MCTS, have not been able to find good solutions. A later algorithm, Nested Rollout Policy Adaptation, was able to find a new record of 82 steps, albeit with large computational resources. After achieving this record, to the best of our knowledge, there has been no further progress reported, for about a decade. In this paper we take the recent impressive performance of deep self-learning reinforcement learning approaches from AlphaGo/AlphaZero as inspiration to design a searcher for Morpion Solitaire. A challenge of Morpion Solitaire is that the state space is sparse, there are few win/loss signals. Instead, we use an approach known as ranked reward to create a reinforcement learning self-play framework for Morpion Solitaire. This enables us to find medium-quality solutions with reasonable computational effort. Our record is a 67 steps solution, which is very close to the human best (68) without any other adaptation to the problem than using ranked reward. We list many further avenues for potential improvement.