Summary of Approximately Optimal Search on a Higher-dimensional Sliding Puzzle, by Nono Sc Merleau et al.
Approximately Optimal Search on a Higher-dimensional Sliding Puzzle
by Nono SC Merleau, Miguel O’Malley, Érika Roldán, Sayan Mukherjee
First submitted to arxiv on: 2 Dec 2024
Categories
- Main: Artificial Intelligence (cs.AI)
- Secondary: Discrete Mathematics (cs.DM); Machine Learning (cs.LG); Neural and Evolutionary Computing (cs.NE)
GrooveSquid.com Paper Summaries
GrooveSquid.com’s goal is to make artificial intelligence research accessible by summarizing AI papers in simpler terms. Each summary below covers the same AI paper, written at different levels of difficulty. The medium difficulty and low difficulty versions are original summaries written by GrooveSquid.com, while the high difficulty version is the paper’s original abstract. Feel free to learn from the version that suits you best!
| Summary difficulty | Written by | Summary |
|---|---|---|
| High | Paper authors | High Difficulty Summary Read the original abstract here |
| Medium | GrooveSquid.com (original content) | Medium Difficulty Summary A comprehensive study is presented on higher-dimensional sliding puzzles, which are constructed on the vertices of a d-dimensional hypercube. The goal is to move each of the 2^d-l rings to pre-defined target vertices on the cube, subject to a k-rule constraint that allows movement only when a hypercube face of dimension k containing a ring is completely free of other rings. An algorithm called God’s algorithm provides the minimum number of moves needed to match ring colours with vertex colours, but its time complexity is not polynomial. This paper presents a computational study comparing three techniques: exact algorithm A* search and two approximately optimal methods – evolutionary algorithm (EA) and reinforcement learning (RL). Results show that all three methods can solve the puzzle for dimension 3, but as dimension increases, A* search fails while RL and EA provide acceptable solutions. The EA method consistently requires less computational time, although it does not always find the minimum number of moves. |
| Low | GrooveSquid.com (original content) | Low Difficulty Summary A team of researchers studied a special kind of puzzle called a higher-dimensional sliding puzzle. They wanted to figure out how many steps it takes to solve this puzzle in different dimensions. The puzzle is like a 3D version of the game Tetris, where you need to move colored blocks into place. To make things more challenging, they added some rules about what pieces can and can’t touch each other. One way to solve the puzzle is called God’s algorithm, but it doesn’t work very well if you have too many dimensions. The researchers tried three different methods to see how quickly they could solve the puzzle: one that was exact, and two that were almost as good but didn’t use up all their computer power. They found that these methods worked pretty well for a 3D puzzle, but got slower when they went into higher dimensions. |
Keywords
» Artificial intelligence » Reinforcement learning
