← 返回 PaperDaily 大模型与智能体

几何感知MCTS来了：6题5破纪录

这篇论文把“无三点共线”这类老牌几何难题，硬生生改造成了一个能跑 MCTS 的搜索问题。更妙的是，它不是只会搜，还会用几何对称性和增量约束把搜索树修得更瘦，挺有工程味道。

龙哥读论文发布于 2026-08-25 00:20:06 阅读 4 查看原文

#强化学习 #人工智能 #AI科研

🐉 龙哥读论文知识星球来了！
公众号每日8篇拆解不够看？星球无上限更AI领域论文、资讯、招聘、招博、开源代码，一站式干货，每日2分钟刷完即赚！ 👇扫码加入「龙哥读论文」知识星球，前沿干货、实用资源一站式拿捏～ xingqiu_header

龙哥推荐理由：
这篇论文把“无三点共线”这类老牌几何难题，硬生生改造成了一个能跑 MCTS 的搜索问题。更妙的是，它不是只会搜，还会用几何对称性和增量约束把搜索树修得更瘦，挺有工程味道。

原论文信息如下：

论文标题:
Geometry-Aware MCTS for Extremal Problems in Combinatorial Geometry 发表日期:
2026年06月发表单位:
University of California, Irvine 原文链接:
https://arxiv.org/pdf/2606.26399v1.pdf

图1：几何感知MCTS框架总览，展示可行动作空间、对称批量转移、规范剪枝、子树复用与全局最优跟踪如何协同工作

图3：不完整与完整点配置示例

图4：增量射线扫描更新过程，并对比可行动作空间与朴素动作空间

图5：基于状态稳定子的规范剪枝与对称批量转移示意

图6：六类约束下的尺度变化与历史最好结果对比

图8：不同算法变体的消融实验，对比平均终止点数与平均运行时间

图9：119×119网格上发现的216点无三点共线配置

图10：96×96网格上的最小完整集示例，含92个点

组合几何问题解法遭遇瓶颈，MCTS能否破局？

组合几何里有一类问题，表面上看像“摆点游戏”，实际上个个都很刁钻：在一个n×n网格里放点，既要满足全局几何约束，又要尽量多、尽量少，或者尽量“覆盖”整个平面。比如最经典的无三点共线问题，听起来像小学数学，做起来却像在迷宫里找出口——每落一个点，后面一大片位置都可能被连锁封死。

这篇论文盯上的，就是这类“局部一手，全球遭殃”的问题。传统精确求解器当然靠谱，但一碰到大网格就容易算到怀疑人生；强化学习和 transformer 方法也不轻松，前者容易掉进稀疏奖励的“有效性悬崖”，后者则被网格规模和 token 消耗拖住了腿。于是作者换了个思路：既然这是一个逐步构造配置的过程，那干脆把它当成搜索问题，用 蒙特卡洛树搜索（Monte Carlo Tree Search，MCTS）来啃。

图1：几何感知MCTS框架总览，展示可行动作空间、对称批量转移、规范剪枝、子树复用与全局最优跟踪如何协同工作

先说一句大白话版结论：这不是“拿 MCTS 硬搜”，而是“给 MCTS 装上几何雷达”。它不再把网格看成一堆独立格子，而是把约束、对称性、可行动作空间都提前塞进搜索流程里，让树搜索少走弯路。这样一来，搜索树不再像野草一样疯长，反而像被认真修过枝的盆栽，能把算力花在更可能出好结果的分支上。

揭秘：如何让MCTS拥有“几何感知”？

这篇论文最关键的地方，不是把 MCTS 拿来用，而是把它改造成了一个适合几何构造的“专用版”。作者先把问题写成一个确定性的马尔可夫决策过程（MDP，Markov Decision Process，中文可理解为“马尔可夫决策过程”）：状态是当前已经放下的点集，动作是继续往哪个格子里放点，转移就是把这个点加入集合。听起来像游戏，但本质上是在做严格的构造搜索。

为了让读者先抓住“难点在哪”，作者给了一个很直观的基线：朴素动作空间就是“网格里没被占用的格子都可以试”。这当然天真得可爱，但也最容易被现实教育。因为如果不考虑几何约束，MCTS 在每一步都要面对海量候选动作；而一旦随机走错一步，整个配置就可能直接报废。论文里把这一点称为有效性悬崖：奖励信号极其稀疏，模型很难靠“试错”学会规矩。

公式里的 UCB1 是树搜索里最常见的“既要探索，也要利用”的打分方式。前半部分看历史收益，后半部分看访问次数少不少；常数 C 控制探索有多激进。问题在于，几何构造里“试错空间”太大，普通 UCB1 很容易被噪声带偏，所以作者不是简单套公式，而是围绕动作空间、约束维护和对称性做了一整套改造。

这里先补一个基础概念：MCTS 可以理解为“边想边试”的搜索器，通常分成选择、扩展、模拟、回传四步。选择阶段按 UCB1 往下走；扩展阶段把一个新动作挂到树上；模拟阶段随机或半随机往前走；回传阶段把结果往上更新。论文的巧妙之处在于，它把每一步都做了“几何特化”，让搜索不再像瞎摸，而更像带着尺子和圆规在走。

图3：不完整与完整点配置示例。论文强调，搜索并不是一直加点就完事，真正的终止状态是“再也加不进去了”，也就是在包含关系下已经最大，但这不代表它一定是全局最优。

效果炸裂：6个问题中5个刷新记录，最大无三点共线规模逼近1.8n

论文的结果部分，属于那种“方法讲完，成绩单也交出来了”的类型。作者在六个组合几何问题上做了实验，结果是五个问题刷新了已知最好记录。这个成绩放在组合几何里不算小打小闹，因为这些问题很多都不是“调参就能赢”的简单活，而是和全局约束、搜索空间爆炸正面硬刚。

图6：六类约束下的尺度变化与历史最好结果对比。这里最吸睛的是无三点共线问题：作者在 82≤n≤119 的网格上找到了规模约为 1.8n 的配置，和经典的 1.5n 构造下界相比，确实往上拱了一截。

图9：119×119网格上发现的216点无三点共线配置。这个结果很有画面感：在一个并不算小的网格里，作者真的“摆”出了 216 个点，而且还保证没有三点共线。对这类问题来说，能把点数往上多塞几个，背后往往是搜索策略和约束维护都得很精细。

图10：96×96网格上的最小完整集示例，含92个点。对于“最小完整集”这类问题，目标不是越多越好，而是越少越好，属于反向操作，但难度一点不比前者低。

更有意思的是，这套框架并不是只会处理一个“无三点共线”问题。它还能迁移到无四点共线、无四点共圆、无等腰三角形、几何支配集等问题上。换句话说，作者不是在做一个单点突破的小技巧，而是在尝试搭一个组合几何通用搜索器。这就很对味了：顶会论文最怕“只会一题”，这篇至少在框架泛化上是有想法的。

图14：39×39 网格上的无四点共圆配置，包含 69 个点。这个问题的几何味道更重，说明框架不只是对“共线”类约束有效，对更一般的几何谓词也能派上用场。

从实验设计上看，这篇论文也比较克制。作者用了单 CPU 核、6GB 内存限制、长时间预算去跑，目的不是炫硬件，而是证明框架本身能在受限条件下扛住大网格。这个思路挺实在：如果一个方法只能靠“开十张卡”才有点意思，那离真正可用通常还差一口气。

核心技术拆解：增量动作空间、对称性剪枝与批量转移

这部分是整篇论文最有“工程脑”的地方。作者没有停留在“把 MCTS 用上了”这种层面，而是把瓶颈拆成三个：动作空间太大、对称分支太多、搜索过程太慢。然后分别给出对应解法，像修机器一样一颗螺丝一颗螺丝拧紧。

朴素动作空间就是“空格子都能试”。问题在于，网格一大，候选动作数量立刻膨胀成平方级；而且很多动作根本不合法，试了也是白试。论文的做法是把动作空间直接收缩成 可行动作空间，也就是只保留不会破坏几何约束的位置。

图4：增量射线扫描更新过程，并对比可行动作空间与朴素动作空间。核心思想很简单：新放一个点，就只更新它会影响到的那部分格子，而不是每一步都把整张网格重新扫一遍。对无三点共线问题来说，这种增量维护把单节点约束检查从 O(n3) 降到了 O(n2)，这可不是抠一点点时间，是直接给搜索树瘦身。

这两条公式合起来，就是“只删不增”的增量维护逻辑：新点一落下，受影响的位置就被从可行空间里划掉。对于共线约束，作者用“射线扫描”来找出新点与已有点连成的所有线段，再把这些线上的格子标为不可行。这个设计的妙处在于，它把几何约束从抽象判定，变成了可缓存、可增量更新的状态信息。

第二个技巧是对称性剪枝。网格本身有 8 种对称变换，也就是二面体群 D4：四种旋转加四种翻转。很多状态其实只是“换了个角度拍照”，本质上是同一个搜索子树。作者于是引入状态稳定子 Stab(s)，只保留每个等价类的代表动作做扩展。翻译成人话就是：长得一样的分支，只搜一个，别浪费命。

更妙的是，作者只在扩展阶段做剪枝，模拟阶段不做。原因也很实诚：模拟本来就快，若每一步都算稳定子和轨道，开销会把省下来的收益吃掉。这种“该省的省、该花的花”的策略，挺像一个会过日子的搜索器。

图5：基于状态稳定子的规范剪枝与对称批量转移示意。这里的第三招叫对称批量转移。如果一个动作在某个对称群下能生成一组互相兼容的点，就一次性全放进去；如果不兼容，就退回只放一个点。这个设计很像“能整组上就别一个个试”，既加快了搜索深度，也更容易把状态推到对称性更强的区域里。

最后还有两个很实用的小动作：子树复用和时间衰减探索。前者避免每下一步就把树清空重来，后者让探索强度随着搜索推进慢慢降下来，别总是“东张西望”不肯收手。再加上“任何时刻都记录当前全局最好解”的追踪机制，MCTS 不只是沿着主路径走，还能把 rollout 里偶然撞到的好配置捞回来。

这个探索衰减公式的意思是：随着搜索进度变高，探索项逐渐减弱，策略会越来越“认准”已经看起来更靠谱的分支。尤其在子树复用场景下，作者把历史访问量也算进去，避免每一步都把探索强度重置成满格，这点很细，也很关键。

未来可期：一个强大的组合几何通用求解器框架

如果只看结果，很多人会把它理解成“又一个把某个几何题做强了的搜索方法”。但从框架角度看，这篇论文更像是在搭一个通用模板：只要能把问题写成“状态 + 几何谓词 + 可行动作维护”，就有机会用同一套几何感知 MCTS 去试。这个思路对组合几何很重要，因为很多问题的难点并不在于单步判断，而在于全局结构如何被逐步构造出来。

当然，这套方法也不是“银弹”。它对约束的单调性比较依赖，也比较吃几何结构是否能被增量维护；如果问题的约束更复杂、更非局部，或者动作之间的相互作用更诡异，增量可行空间的维护就可能变得麻烦。另外，虽然论文展示了不错的最好结果，但这些结果本质上还是搜索发现的构造，离“理论上证明最优”还有距离。换句话说，它很能打，但还不是数学证明机器。

不过，正因为它不是只会讲道理，才显得有价值。它把几何约束、对称性、搜索策略和工程优化揉到一起，形成了一个比较完整的“可扩展搜索框架”。对后续工作来说，值得继续追的方向至少有两个：一是把更多几何谓词纳入统一建模，二是继续降低搜索成本，让这种方法能在更大规模、更复杂约束下稳定工作。

龙迷三问

下面是龙哥对于大家可能的一些问题的解答：

这篇论文到底解决了什么问题？它研究的是组合几何里的极值构造问题，核心是如何在n×n网格里放点，同时满足“无三点共线”“无四点共线”“无四点共圆”“无等腰三角形”等全局几何约束，并尽量把点数做大或做小。

MCTS 在这里为什么能用？因为这类问题天然适合“逐步构造”：每放一个点，状态就确定地更新一次，且合法性可以被严格检查。MCTS 擅长在大搜索空间里边试边学，再配上可行动作空间、对称性剪枝和子树复用，就比纯随机搜索靠谱得多。

“几何感知”具体指什么？不是给模型戴上一副玄学眼镜，而是把几何结构直接写进搜索过程：哪些点能放、哪些点会破坏约束、哪些状态只是对称变体，这些信息都被显式编码进来了。这样 MCTS 才不是盲搜，而是“懂几何地搜”。

如果你还有哪些想要了解的，欢迎在评论区留言或者讨论~

龙哥点评

论文创新性分数：★★★★☆ 这篇论文的亮点不在“发明了 MCTS”，而在于把几何约束、对称性和增量维护做成了一套可复用框架，思路比较完整。

实验合理度：★★★★☆ 选题和对照都比较对路，尤其是用受限算力去跑大网格，能更真实地反映方法本身的效率。

学术研究价值：★★★★☆ 对组合几何和搜索算法的交叉研究很有启发，尤其适合后续继续扩展到更多几何极值问题。

稳定性：★★★☆☆ 方法依赖约束单调性和较强几何结构，能不能稳稳迁移到更复杂问题，还得继续看。

适应性以及泛化能力：★★★★☆ 已经证明能跨多个几何问题工作，说明框架泛化不是嘴上说说。

硬件需求及成本：★★★☆☆ 单卡单核也能跑，但大规模搜索仍然吃时间，属于“能用但不轻松”。

复现难度：★★★☆☆ 算法细节不少，尤其是增量维护和对称剪枝，复现时需要仔细对齐实现。

产品化成熟度：★★★☆☆ 更像研究型求解器，适合离线探索和发现新构造，离通用产品还差一段工程化距离。

可能的问题：对称性和增量约束很强，但问题一旦更复杂，维护成本会迅速上升；目前更像高质量搜索框架，还不是统一的“几何证明器”。

主要参考文献

Luoning Zhang, Xu Zhuang, Tianhao Wang, Nathan Kaplan. Geometry-Aware MCTS for Extremal Problems in Combinatorial Geometry. arXiv:2606.26399v1, 2026.

Kocsis and Szepesvári. Bandit based Monte-Carlo Planning. 2006.

Coulom. Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search. 2007.

*本文仅代表个人理解及观点，不构成任何论文审核或者项目落地推荐意见，具体以相关组织评审结果为准。欢迎就论文内容交流探讨，理性发言哦～想了解更多原文细节的小伙伴，可以点击"阅读原文"，查看更多原论文细节哦！

欢迎加入龙哥读论文粉丝群，扫描下方二维码或者添加龙哥助手微信号加群：kangjinlonghelper。一定要备注：研究方向+地点+学校/公司+昵称（如图像处理+上海+清华+龙哥），根据格式备注，可更快被通过且邀请进群。
『龙哥读论文』微信群目前包含：图像处理、大模型及智能体、自动驾驶及机器人、AI医疗及AI金融5个群
几何题、树搜索、AI解题，三件套都想聊？来群里一起拆！🐉