Alphazzle: Jigsaw Puzzle Solver with Deep Monte-Carlo Tree Search
This addresses the challenge of efficiently exploring the exponential solution space in jigsaw puzzle solving for computer vision applications, but it is incremental as it combines existing methods like MCTS and neural networks.
The paper tackled the problem of solving jigsaw puzzles by developing Alphazzle, a reassembly algorithm using deep Monte-Carlo Tree Search (MCTS) with neural networks to estimate rewards, achieving excellent results.
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.