面向组合几何极值问题的几何感知MCTS

# 面向组合几何中极值问题的几何感知MCTS 来源：https://arxiv.org/html/2606.26399 徐庄 xzhuang8@uci\.edu  
加州大学尔湾分校数学系  
王天浩 tianhw11@uci\.edu  
加州大学尔湾分校数学系  
Nathan Kaplan nkaplan@math\.uci\.edu  
加州大学尔湾分校数学系  

###### 摘要  

本文研究了组合几何中的若干极值问题，这些问题涉及在 n×n 网格中满足严格全局几何约束的点配置。经典精确求解器因组合爆炸而难以处理这类问题，而标准的强化学习和基于 Transformer 的模型则受困于稀疏奖励的“有效性悬崖”和二次令牌消耗限制。为了克服这些瓶颈，我们提出了一个几何感知的蒙特卡洛树搜索（MCTS）框架。我们的方法通过增量更新可行动作空间来严格强制执行几何约束。对于涉及共线点集合的约束（如经典的“三点不共线”问题 Max-N3IL），该机制将约束检查复杂度从 O(n³) 降低到 O(n²)。为了提高搜索效率，我们以两种方式利用几何对称性：在节点扩展期间进行规范剪枝以减少分支因子，以及采用对称批量转移来加速发现有前景的配置。我们进行了大量实验，并在所考虑的六个问题中的五个上建立了新的最佳已知计算结果。值得注意的是，对于 Max-N3IL，我们在 82 ≤ n ≤ 119 的网格上找到了大小约为 1.8n 的配置。对于最小完全集问题，我们在测试网格内找到了大小约为 0.95n 的配置，提供了新的上界。这项工作确立了几何感知 MCTS 作为一个高度可适应的框架，用于发现组合几何中的新颖配置。

## 1 引言

参见标题  
图 1：几何感知 MCTS 框架概览。搜索过程由问题规范（灰色）引导，包括由特定问题约束定义的可行动作空间，以及从几何先验导出的对称批量转移（例如旋转和反射）。核心 MCTS 引擎（蓝色）利用规范剪枝来减少扩展过程中的分支。生成的策略决定主循环（右侧），该循环采用子树重用以提高效率，并使用任意最优追踪来异步记录所有模拟中全局找到的最佳配置。

参见标题  
(a) 一个没有三点共线的配置示例。  
参见标题  
(b) 一个存在三点共线（对角线上）的配置示例。  
参见标题  
(c) 一个最大尺寸的无三点共线配置。  
图 2：3x3 网格上的三个点配置示例。

我们研究 n×n 网格上的某些极值问题。这些问题询问网格中满足特定几何约束的点的最大或最小数量。代表性的例子包括找出无等腰三角形的最大点集、无四点共圆的最大点集，或最小的独立几何支配集。三点不共线问题（Max-N3IL）作为理论问题和算法问题都吸引了大量关注。该问题的历史至少可以追溯到 Dudeney (1917 (https://arxiv.org/html/2606.26399#bib.bib1))。它询问在 n×n 网格中最多可以放置多少个点，使得没有三个点共线。我们将这个问题的答案记作 M(n)。3×3 网格中的一些配置如图 ̃2 (https://arxiv.org/html/2606.26399#S1.F2) 所示。尽管其表述初等，但对于较大的 n，确定 M(n) 仍然是一个公开挑战。由于 n 条平行线覆盖了 n×n 网格，并且每条线上不能有两个以上的点，因此 M(n) ≤ 2n。Flammenkamp (1992 (https://arxiv.org/html/2606.26399#bib.bib5); 1998 (https://arxiv.org/html/2606.26399#bib.bib6)) 已经证明对于所有 n ≤ 46 以及 n ∈ {48, 50, 52}，M(n)=2n。Prellberg (2026 (https://arxiv.org/html/2606.26399#bib.bib36)) 最近使用约束满足编程的高级工具将这些结果扩展到 M(n)=2n 对于所有 n ≤ 64 以及 n ∈ {66, 68}。Heule 使用最近开发的 SAT 求解器找到了解，表明对于 n ∈ {65, 67, 69, 70}，M(n)=2n。这些结果在 Flammenkamp (https://arxiv.org/html/2606.26399#bib.bib13) 的在线数据库 (2026 (https://arxiv.org/html/2606.26399#bib.bib13)) 中被积极跟踪。对于任何 n ≥ 71，我们不知道 M(n) 的确切值。最佳已知渐近下界归功于 Hall 等人 (1975 (https://arxiv.org/html/2606.26399#bib.bib3))，他们使用来自有限域的结构表明，对于任何 ε > 0 和所有足够大的 n，M(n) > (1.5 - ε)n。这在构造性的 (1.5 - ε)n 下界和简单的 2n 上界之间留下了显著的差距。Guy 和 Kelly (1968 (https://arxiv.org/html/2606.26399#bib.bib4)) 使用概率论论证表明，随着 n 趋向无穷，M(n) ≈ π/√3 n ≈ 1.814n。为了更好地理解 M(n) 的增长，我们希望探测由于搜索空间的组合爆炸而在历史上无法通过计算访问的网格尺寸。这些有限网格上的极值问题的复杂性源于几何约束的全局性。单个点的放置会以复杂的方式影响剩余点的集合，使得局部约束满足变得不足。虽然代数构造提供了严格的保证，但我们完全不清楚是否应该期望极值配置具有代数结构。这促使我们需要计算方法来更好地理解以前无法访问的网格。

近年来，人工智能在组合数学方面取得了显著突破，从发现图论反例 (Wagner, 2021 (https://arxiv.org/html/2606.26399#bib.bib9)) 到预测模曲线不变量 (Zhuang 等人, 2025 (https://arxiv.org/html/2606.26399#bib.bib12))。将这些方法应用于像 Max-N3IL 这样的问题尚未成功。Ramanathan 等人 (2025 (https://arxiv.org/html/2606.26399#bib.bib7)) 最近的一项系统评估强调了三种不同计算范式（精确求解器、强化学习和基于 Transformer 的模型）的严重可扩展性限制。传统的精确求解器，如整数线性规划（ILP），保证最优解，但由于 O(n³) 的约束密度和指数级的搜索空间，在 n=19 处遇到可扩展性瓶颈。相反，标准的无模型强化学习（例如 PPO）失败得更早，仅在 10×10 网格上找到最优配置，然后在 n=11 时系统性失败 (Ramanathan 等人, 2025 (https://arxiv.org/html/2606.26399#bib.bib7))。通用的强化学习智能体难以仅从标量奖励信号中维持全局几何约束意识；单个共线放置就会使整个配置失效，造成稀疏奖励的“有效性悬崖”，阻碍基于梯度的优化。虽然 Prellberg (2026 (https://arxiv.org/html/2606.26399#bib.bib36)) 使用约束满足编程来搜索大小恰好为 2n 的配置，但这产生了令人望而却步的计算成本，对于 n ≤ 60 需要 10 个 CPU 天，并且需要大量的 GPU 并行化才能勉强达到 n=66 (Flammenkamp, 2026 (https://arxiv.org/html/2606.26399#bib.bib13))。最近的先进 AI 范式，如大语言模型（FunSearch, Romera-Paredes 等人, 2024 (https://arxiv.org/html/2606.26399#bib.bib10)；AlphaEvolve, Novikov 等人, 2025 (https://arxiv.org/html/2606.26399#bib.bib20)；以及 MCTS-AHD, Zheng 等人, 2025 (https://arxiv.org/html/2606.26399#bib.bib25)）和基于 Transformer 的搜索（PatternBoost, Charton 等人, 2024 (https://arxiv.org/html/2606.26399#bib.bib21)），已经在类似的极值问题上发现了令人印象深刻的新构造，例如关于 (Z/3Z)^n 中点的著名 Cap Set 问题。这些模型在应用于我们这里考虑的问题时尚未成功。当 PatternBoost 应用于研究 Max-N3IL 时，它在小网格上匹配了最优性能，但无法扩展到 n=15 以上 (Ramanathan 等人, 2025 (https://arxiv.org/html/2606.26399#bib.bib7))。这个特定的可扩展性瓶颈是因为 Transformer 的模式泛化严重受限于用于生成其训练数据的贪婪算法中固有的质量-速度权衡。除了这个数据生成瓶颈之外，基于 Transformer 的模型本质上是高度消耗令牌且计算昂贵的。表示一个 n×n 网格需要 O(n²) 个令牌，导致注意力机制在大网格上扩展性很差。此外，自回归生成通常难以严格遵守硬性的全局约束，容易产生无效放置。像 FunSearch 这样的 LLM 驱动方法擅长发现简洁的启发式规则，但可能的情况是，大网格上的最优配置高度不规则且难以用简单规则表达。此外，可能受限于其训练分布，这些 LLM 在发现该领域未解决问题真正新颖逻辑所需的分布外（OOD）算法泛化方面可能表现出局限性 (Li 和 Ellis, 2024 (https://arxiv.org/html/2606.26399#bib.bib37)；Neuhaus 等人, 2026 (https://arxiv.org/html/2606.26399#bib.bib38))。这些局限性需要一种不同的算法范式，将严格的几何约束满足与可扩展的搜索结合起来。

##### 为什么选择 MCTS：一种几何感知方法

为了克服经典求解器和最近基于学习的方法（如用于 Max-N3IL 的方法）的局限性，我们提出了一个几何感知的 MCTS 框架 (Coulom, 2007 (https://arxiv.org/html/2606.26399#bib.bib15)；Kocsis 和 Szepesvári, 2006 (https://arxiv.org/html/2606.26399#bib.bib14))。蒙特卡洛树搜索（MCTS）通过使用模拟轨迹提供密集的、建设性的奖励信号，避免了标准 RL 的稀疏奖励“有效性悬崖”。此外，它通过屏蔽无效放置轻松地强制执行硬性几何约束，绕过了序列模型的幻觉风险和 O(n²) 令牌开销。虽然 MCTS 的非对称树增长自然地平衡了非结构化空间中的探索与利用，但将其扩展到大型网格（例如 n > 50）需要特定的适应性。我们的框架通过以下方式使其变得可行：(1) 增量维护一个严格的可行动作空间（A_feas）以最小化每个节点的开销，(2) 在扩展和模拟过程中利用 D_4 网格对称性来减少分支，以及 (3) 使用信息持久化、自适应探索和全局最优跟踪来增强搜索策略，以在有限的计算预算下最大化产出。

##### 主要贡献

我们的工作通过展示基于搜索范式的有效性，推动了组合几何与强化学习的交叉领域的发展。通过将极值构造制定为几何马尔可夫决策过程（MDP），我们引入了具体的算法创新，使得 MCTS 在广阔且约束繁重的空间中变得可行。具体贡献如下：

- •我们提出了一种增量式可行动作空间（A_feas）维护机制。对于基于共线点集约束的问题，如 Max-N3IL，这种射线投射方法将每个节点上约束检查的复杂度从 O(n³) 降低到 O(n²)。这有效绕过了通常使标准 RL 智能体瘫痪的稀疏奖励“有效性悬崖”。
- •我们通过动态计算的状态稳定化子 Stab(s) ≤ D_4 引入规范动作剪枝，将树扩展限制在轨道代表元上，同时故意在 rollout 期间禁用剪枝，以最小化计算开销而不牺牲分支缩减。
- •我们提出了对称批量转移，这是一种新颖的 MDP 转移机制，它在所选对称性集合下同时放置一个轨道。这显著加速了有前景的对称配置的发现，并允许规范剪枝在搜索树更深层仍保持有效。
- •我们改进了所考虑的六个问题中五个的最佳已知计算界限。值得注意的是，我们显著扩展了在 Max-N3IL 中获得优于约 1.5n 的渐近下界的下界的范围。我们还发现了比已知构造更小的最小完全集问题的上界配置。

## 2 问题建模

我们在离散网格 G_n = [n] × [n] 上，在硬性几何约束下研究极值子集构造。与概率生成任务不同，构造根据二元谓词 Φ（例如，“没有三点共线”）要么有效要么无效。因此，我们将该过程建模为一个顺序决策问题，从而启用搜索和规划方法 (Vodopivec 等人, 2017 (https://arxiv.org/html/2606.26399#bib.bib40))。

### 2.1 一个通用的几何 MDP 框架

我们将几何构造顺序地制定为一个确定性 MDP，由元组 (S, A, T, R) 定义。尽管目标配置是排列不变的，但这种顺序制定在计算上是有利的，因为它在每一步都强制执行硬性约束，立即修剪无效分支。状态空间 S = {s | s ⊆ G_n} 是网格的幂集，其中状态 s ∈ S 表示一个点配置，初始化为空集 s = ∅。为了维持结构有效性，我们定义一个布尔几何不变量 Φ: S → {True, False}（例如，对于 Max-N3IL，Φ(s) 成立当且仅当没有三点共线）。因此，动作空间严格限制在可行放置上，定义为 A_feas(s) = {p ∈ G_n \ s | Φ(s ∪ {p}) = True}。这确保了采取的任何动作都保持 Φ（A_feas 的高效增量维护在 3.2 节 (https://arxiv.org/html/2606.26399#S3.SS2) 中详细说明）。转移是确定性和加性的，由 s′ = s ∪ {a} 给出，其中 a ∈ A_feas(s)。当且仅当 A_feas(s) = ∅ 时，状态 s 是终止状态（记为 s_T），意味着该配置在包含关系下是极大的。注意，一个配置是极大的并不意味着它具有最优基数。最后，奖励函数 R(s_T, n) 在终止时进行评估。