Research map / Reinforcement learning / Visual and representation RL
ERL-MPP: Evolutionary Reinforcement Learning with Multi-head Puzzle Perception for Solving Large-scale Jigsaw Puzzles of Eroded Gaps
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes ERL-MPP, combining a multi-head puzzle perception network (shared encoder with discriminator and puzzlet heads) with an evolutionary actor-critic-evaluator RL agent to solve large-scale jigsaw puzzles with eroded gaps.
Problem
Reassembling large-scale jigsaw puzzles where fragments are separated by large gaps (eroded boundaries), so boundary cues are unreliable and the permutation search space is huge.
Approach
A shared-encoder multi-head perception network (GAN-style discriminator for global status plus puzzlet heads for local pairwise and 2x2 relations) feeds an actor-critic agent whose evaluator is soft-updated from the critic and uses evolutionary crossover/mutation over Swap-2, Swap-3, and Swap-puzzlet actions.
Key results
- On JPLEG-5 (5x5, 12-pixel gaps), ERL-MPP reaches 18.6% Perfect vs 6.1% for PDN-GA, the previous best.
- On MIT 7x10 puzzles with 2-pixel gaps, ERL-MPP achieves 50.0% Perfect vs 11.7% for SD2RL.
- Ablation on JPLEG-5 shows MPPN+EvoRL improves Perfect from 5.1% (SDN+DQN) to 18.6%.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace PDN-GA with ERL-MPP | JPLEG-5 puzzle solving · JPLEG-5 test | Perfect: 6.1 -> 18.6 | Helped |
| use ERL-MPP instead of SD²RL | MIT puzzle solving · MIT 7×10, 2-pixel gap | Perfect: 11.7 -> 50.0 | Helped |
| use ERL-MPP instead of SD²RL | MIT puzzle solving · MIT 7×10, 4-pixel gap | Perfect: 5.0 -> 13.3 | Helped |
| use ERL-MPP instead of SD²RL | MIT puzzle solving · MIT 10×15, 2-pixel gap | Perfect: 3.3 -> 8.3 | Helped |
| use ERL-MPP instead of SD²RL | MIT puzzle solving · MIT 10×15, 4-pixel gap | Perfect: 0.0 -> 0.0 | No clear effect |
| replace SDN with MPPN while using DQN (ablation) | JPLEG-5 puzzle-solving agent · JPLEG-5 test | Perfect: 5.1 -> 9.8; +5.1% | Helped |
| replace SDN with MPPN while using EvoRL (ablation) | JPLEG-5 puzzle-solving agent · JPLEG-5 test | Perfect: 13.5 -> 18.6; 5.1% | Helped |
| replace DQN with EvoRL while using SDN (ablation) | JPLEG-5 puzzle-solving agent · JPLEG-5 test | Perfect: 5.1 -> 13.5 | Helped |
| replace DQN with EvoRL while using MPPN (ablation) | JPLEG-5 puzzle-solving agent · JPLEG-5 test | Perfect: 9.8 -> 18.6; 8.8% | Helped |
Surprising findings
- No method, including ERL-MPP, perfectly assembles any 10x15 puzzle with 4-pixel gaps on the MIT dataset.
- Painting puzzles remain much harder than engravings and artifacts, with ERL-MPP Perfect rate of only 3.3%.
Limitations
- Performance drops sharply for large piece counts with large gaps (0% Perfect on 10x15 with 4-pixel gap).
- Perfect rate remains low on JPLEG-5 (18.6%), with painting puzzles especially hard.
Experimental setup
Datasets: JPLEG-5 MIT jigsaw dataset DIV2K
Benchmarks: JPLEG-5 MIT jigsaw dataset
Metrics: Perfect Absolute Horizontal Vertical Neighbor
Baselines: Deepzzle Greedy Search Tabu Search Genetic Algorithm Inpaint-GAN PDN-GA SD2RL
Builds on: SD2RL PDN-GA EfficientNet Swin Transformer
Closest papers by meaning
- PUZZLES: A Benchmark for Neural Algorithmic Reasoning (NeurIPS 2024 · similarity 0.86)
- Sliding Puzzles Gym: A Scalable Benchmark for State Representation in Visual Reinforcement Learning (ICML 2025 · similarity 0.85)
- Agentic Jigsaw Interaction Learning for Enhancing Visual Perception and Reasoning in Vision-Language Models (ICLR 2026 · similarity 0.85)
- Do multimodal models imagine electric sheep? (NeurIPS 2026 · similarity 0.84)
- PuzzleWorld: A Benchmark for Multimodal, Open-Ended Reasoning in Puzzlehunts (ICLR 2026 · similarity 0.84)
- Evolutionary Reinforcement Learning with Parameterized Action Primitives for Diverse Manipulation Tasks (AAAI 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.