Approximately Optimal Search on a Higher-dimensional Sliding Puzzle

Nono SC Merleau, Miguel O’Malley, Érika Roldán, Sayan Mukherjee · 2024

Read Approximately Optimal Search on a Higher-dimensional Sliding Puzzle by Nono SC Merleau, Miguel O’Malley, Érika Roldán, Sayan Mukherjee (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-01937.txt.

Description

Four authors take a sliding puzzle off the chessboard and onto a hypercube. Colored rings sit on the corners of a d-dimensional cube, and the task is to slide each ring to its matching corner. A move is legal only when a whole face of a set size is empty, a rule that generalizes how pieces collide. Finding the fewest moves is God's algorithm territory, and even the classic 15-puzzle resists fast exact answers.

The team benchmarked three solvers: exact A-star search, an evolutionary method, and reinforcement learning. All three cracked the three-dimensional puzzle at every setting. As dimensions rose, A-star fell away, while the two learners still found routes with a median under 30 moves. The evolutionary method ran fastest but rarely found the true minimum at the top dimensions.

Catalog record

CREATORNono SC Merleau, Miguel O’Malley, Érika Roldán, Sayan Mukherjee
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE69 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-01937

Browse the full library · About the Tower of Babel