2025/11/03 by Mirco A. Mannucci, Mannucci, Mirco A.
Computer Science · #Artificial Intelligence (cs.AI) #Artificial Intelligence in Games #Computational Engineering #Data Visualization and Analytics #FOS: Computer and information sciences #Finance #Machine Learning (cs.LG) #Topological and Geometric Data Analysis #and Science (cs.CE)
paper · pdf · doi:10.48550/arxiv.2511.01701
openalex publication_date 2025/11/03 · openalex created_date 2025/11/06 · openalex updated_date 2026/07/28
A fundamental question in search-guided AI: what topology should guide Monte Carlo Tree Search (MCTS) in puzzle solving? Prior work applied topological features to guide MCTS in ARC-style tasks using grid topology -- the Laplacian spectral properties of cell connectivity -- and found no benefit. We identify the root cause: grid topology is constant across all instances. We propose measuring solution space topology instead: the structure of valid color assignments constrained by detected pattern rules. We build this via compatibility graphs where nodes are (cell, color) pairs and edges represent compatible assignments under pattern constraints. Our method: (1) detect pattern rules automatically with 100% accuracy on 5 types, (2) construct compatibility graphs encoding solution space structure, (3) extract topological features (algebraic connectivity, rigidity, color structure) that vary with task difficulty, (4) integrate these features into MCTS node selection via sibling-normalized scores. We provide formal definitions, a rigorous selection formula, and comprehensive ablations showing that algebraic connectivity is the dominant signal. The work demonstrates that topology matters for search -- but only the right topology. For puzzle solving, this is solution space structure, not problem space structure.