Title: Learning Empirically Admissible Neural Heuristics for Combinatorial Search

Abstract:

Achieving optimal solution paths for classic combinatorial puzzles, including the Rubik’s Cube, Lights Out, and sliding tile variants, continues to pose a significant challenge within the field of artificial intelligence. While heuristic search algorithms like A* ensure optimality, they rely strictly on admissible heuristics—those that do not overestimate the actual remaining cost to reach the goal. Although deep reinforcement learning approaches, such as DeepCubeA, utilize deep neural networks to estimate these cost-to-go values, standard training via mean-squared error (MSE) frequently results in overestimations. Such violations of admissibility undermine the guarantee of optimal solutions.

To address this, we present a robust framework for learning neural heuristics that are calibrated to be admissible. Our method employs an underestimating Admissible Bellman Operator alongside an Asymmetric Loss function designed specifically to penalize overestimation. Furthermore, to mitigate residual errors inherent in neural function approximation, we introduce a post-hoc calibration safety offset derived from validation scrambles. Evaluation results indicate that our calibrated neural heuristics exhibit no admissibility violations under the testing protocol and successfully maintain path optimality. Compared to standard analytical baselines, this approach reduces search node expansions by up to 83.0% on the 2x2 Rubik's Cube, 19.9% on the 3x3 Lights Out grid, and 1.9% on the 8-Puzzle.

Source: arXiv Generated at: 2026-06-04 00:00:00 UTC