Geometry-Aware MCTS for Extremal Problems in Combinatorial Geometry

Computer Science > Artificial Intelligence [Submitted on 24 Jun 2026] Geometry-Aware MCTS for Extremal Problems in Combinatorial Geometry Luoning Zhang, Xu Zhuang, Tianhao Wang, Nathan Kaplan We study certain extremal problems in combinatorial geometry that ask about configurations of points in an n \times n grid that satisfy strict, global geometric constraints. Classical exact solvers suffer from combinatorial explosion for these types of problems, and standard reinforcement learning and transformer-based models struggle with the sparse reward "validity cliff" and quadratic token-consumption limits. To overcome these bottlenecks, we propose a Geometry-Aware Monte Carlo Tree Search (MCTS) framework. Our approach strictly enforces geometric constraints through incremental updates to the feasible action space. For constraints about collections of collinear points, like those that occur in the classic No-Three-in-Line problem (Max-N3IL), this mechanism reduces the constraint checking complexity from O(n^3) to O(n^2). To improve search efficiency, we exploit geometric symmetries in two ways: canonical pruning during node expansion to reduce the branching factor, and symmetric batch transitions to accelerate the discovery of promising configurations. We perform extensive experiments and establish new best-known computational results on five out of six of the problems that we considered. Notably, for Max-N3IL we find configurations of size roughly 1.8 n for grids of size 82 \le n \le 119. For the Smallest Complete Set problem, we find configurations of size roughly 0.95 n, providing new upper bounds within the tested grids. This work establishes Geometry-Aware MCTS as a highly adaptable framework for discovering novel configurations in combinatorial geometry. Subjects: Artificial Intelligence (cs.AI); Computational Geometry (cs.CG); Machine Learning (cs.LG); Combinatorics (math.CO) Cite as: arXiv:2606.26399 [cs.AI]   (or arXiv:2606.26399v1 [cs.AI] for this version)   https://doi.org/10.48550/arXiv.2606.26399 Focus to learn more Submission history From: Nathan Kaplan [view email] [v1] Wed, 24 Jun 2026 21:34:08 UTC (7,020 KB) Access Paper: HTML (experimental) view license Current browse context: cs.AI < prev   |   next > new | recent | 2026-06 Change to browse by: cs cs.CG cs.LG math math.CO References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)