用解空间拓扑优化蒙特卡洛树搜索，提升谜题求解效率。
Solution Space Topology Guides CMTS Search
- 通过兼容图建模有效颜色分配结构，捕捉解空间拓扑。
- 算法在5类任务中100%准确检测模式规则，且拓扑特征随难度变化。
- 引入代数连通性等特征显著提升搜索性能，适合复杂谜题求解者。
搜索引导型AI的核心问题之一是：蒙特卡洛树搜索（MCTS）应以何种拓扑结构为指导？以往工作尝试使用网格拓扑（基于单元格连接的拉普拉斯谱特性）指导ARC风格任务中的MCTS，但未见成效。我们发现根本原因在于：网格拓扑在所有实例中保持不变。为此，我们提出测量“解空间拓扑”——即由检测到的模式规则约束的有效颜色分配结构。通过构建兼容图（节点为 (单元格, 颜色) 对，边表示满足模式约束的兼容分配）实现该结构。方法包括：(1) 在5种类型任务上以100%准确率自动检测模式规则；(2) 构建编码解空间结构的兼容图；(3) 提取随任务难度变化的拓扑特征（代数连通性、刚性、颜色结构）；(4) 通过兄弟节点归一化得分将这些特征融入MCTS节点选择。论文提供形式化定义、严谨的选择公式及全面消融实验，表明代数连通性是主导信号。研究证明：拓扑确实重要，但必须是正确的拓扑——对于谜题求解，是解空间结构，而非问题空间结构。
原文摘要 · Abstract (English)
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 \emph{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 \emph{right} topology. For puzzle solving, this is solution space structure, not problem space structure.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。