A Mathematical Sensation: How AI Disproved the Megaminx Hypothesis
For a long time, classical discrete optimization algorithms such as IDA* with precomputed pattern databases (PDB) were considered the unsurpassed standard for solving mechanical puzzles. However, the open-source project CayleyPy proved otherwise: a neural network model outperformed the record of renowned combinatorial search expert Tomas Rokicki while making a theoretical discovery along the way.
In the Megaminx puzzle (a dodecahedron with a state space of about 1.01×10⁶⁸), the symmetrical Superflip configuration was regarded as a key benchmark. For a long time, it was assumed to be the furthest state from the solved configuration. The previous record for solving it was 55 moves, with a theoretical lower bound of 48 moves for the graph diameter. CayleyPy team member Vladislav Kuznetsov used machine learning to find a solution in just 47 moves in the FTM metric. Since 47 is less than 48, this strictly proved that Superflip is not an antipodal state of the Cayley graph for the Megaminx. Rokicki called this result the first major breakthrough in applying AI to permutation puzzle theory.
The Core of the CayleyPy Approach
In massive state spaces (7.4×10⁴⁵ combinations for the 4×4×4 cube), classical PDB tables require immense memory, while reinforcement learning algorithms struggle with sparse reward signals. The CayleyPy developers introduced an elegant three-step alternative:
- Data generation via random walks: random moves are generated from the solved state, and the model records "state – number of steps from the finish" pairs.
- Heuristic training: the neural network is trained to estimate the distance of an arbitrary configuration to the solved state, creating a continuous gradient instead of a binary "solved/unsolved" signal.
- Beam Search: during the solve phase, the algorithm generates neighboring nodes, evaluates them using the neural network, and keeps only a fixed number of the best candidates, methodically advancing until reaching the target combination.
In practice, expanding the dataset size showed limited benefits, whereas simply widening the beam width in Beam Search consistently shortened the resulting solution path.
Triumph on Large Cubes
The effectiveness of this approach was confirmed by a series of benchmarks:
- On the classic 3×3×3 cube, the pipeline achieved 98.4% optimal solves, outperforming DeepCubeA (60.3%) and EfficientCube (69.6%).
- In the 4×4×4 cube competition on the Kaggle platform, the team took first place, beating Rokicki with an average solution length of 46.51 moves (compared to a hypothesized "God's Number" of around 48).
Currently, the authors of CayleyPy are testing the algorithm on massive 5×5×5, 6×6×6, and 7×7×7 cubes, where the state space reaches up to 1.95×10¹⁶⁰. All project developments are open-source, and any machine learning enthusiast can participate in the open Kaggle competitions.