# Alphazzle: Jigsaw Puzzle Solver with Deep Monte-Carlo Tree Search

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 42 references that are in the map.
- First posted on arXiv 1 Feb 2023.

## Builds on (most cited first, 16 of 16)

- [Wide Residual Networks](https://mlsanity.com/paper/1605.07146/) (2016)
- [Unsupervised Learning of Visual Representations by Solving Jigsaw Puzzles](https://mlsanity.com/paper/1603.09246/) (2016)
- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Unsupervised Visual Representation Learning by Context Prediction](https://mlsanity.com/paper/1505.05192/) (2015)
- [Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm](https://mlsanity.com/paper/1712.01815/) (2017)
- [Domain Generalization by Solving Jigsaw Puzzles](https://mlsanity.com/paper/1903.06864/) (2019)
- [Thinking Fast and Slow with Deep Learning and Tree Search](https://mlsanity.com/paper/1705.08439/) (2017)
- [Boosting Self-Supervised Learning via Knowledge Transfer](https://mlsanity.com/paper/1805.00385/) (2018)
- [Learning Image Representations by Completing Damaged Jigsaw Puzzles](https://mlsanity.com/paper/1802.01880/) (2018)
- [Iterative Reorganization with Weak Spatial Constraints: Solving Arbitrary Jigsaw Puzzles for Unsupervised Representation Learning](https://mlsanity.com/paper/1812.00329/) (2018)
- [Ranked Reward: Enabling Self-Play Reinforcement Learning for Combinatorial Optimization](https://mlsanity.com/paper/1807.01672/) (2018)
- [Single-Agent Policy Tree Search With Guarantees](https://mlsanity.com/paper/1811.10928/) (2018)
- [Deepzzle: Solving Visual Jigsaw Puzzles with Deep Learning andShortest Path Optimization](https://mlsanity.com/paper/2005.12548/) (2020)
- [Solving Jigsaw Puzzles with Eroded Boundaries](https://mlsanity.com/paper/1912.00755/) (2019)
- [Image Reassembly Combining Deep Learning and Shortest Path Problem](https://mlsanity.com/paper/1809.00898/) (2018)
- [Single-Agent Optimization Through Policy Iteration Using Monte-Carlo Tree Search](https://mlsanity.com/paper/2005.11335/) (2020)

## Abstract (arXiv)

Solving jigsaw puzzles requires to grasp the visual features of a sequence of patches and to explore efficiently a solution space that grows exponentially with the sequence length. Therefore, visual deep reinforcement learning (DRL) should answer this problem more efficiently than optimization solvers coupled with neural networks. Based on this assumption, we introduce Alphazzle, a reassembly algorithm based on single-player Monte Carlo Tree Search (MCTS). A major difference with DRL algorithms lies in the unavailability of game reward for MCTS, and we show how to estimate it from the visual input with neural networks. This constraint is induced by the puzzle-solving task and dramatically adds to the task complexity (and interest!). We perform an in-deep ablation study that shows the importance of MCTS and the neural networks working together. We achieve excellent results and get exciting insights into the combination of DRL and visual feature learning.