# Geometry-Aware MCTS for Extremal Problems in Combinatorial Geometry

arXiv: https://arxiv.org/abs/2606.26399 · HTML: https://mlsanity.com/paper/2606.26399/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 35 references that are in the map.
- First posted on arXiv 24 Jun 2026.

## Builds on (most cited first, 10 of 10)

- [Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design](https://mlsanity.com/paper/2501.08603/) (2025)
- [Constructions in combinatorics via neural networks](https://mlsanity.com/paper/2104.14516/) (2021)
- [PatternBoost: Constructions in Mathematics with a Little Help from AI](https://mlsanity.com/paper/2411.00566/) (2024)
- [MCTS-Judge: Test-Time Scaling in LLM-as-a-Judge for Code Correctness Evaluation](https://mlsanity.com/paper/2502.12468/) (2025)
- [Is Programming by Example solved by LLMs?](https://mlsanity.com/paper/2406.08316/) (2024)
- [Exploring search space trees using an adapted version of Monte Carlo tree search for combinatorial optimization problems](https://mlsanity.com/paper/2010.11523/) (2020)
- [Combining Simulated Annealing and Monte Carlo Tree Search for Expression Simplification](https://mlsanity.com/paper/1312.0841/) (2013)
- [Enhancements for Real-Time Monte-Carlo Tree Search in General Video Game Playing](https://mlsanity.com/paper/2407.03049/) (2024)
- [Three methods, one problem: Classical and AI approaches to no-three-in-line](https://mlsanity.com/paper/2512.11469/) (2025)
- [On the Out-of-Distribution Generalization of Reasoning in Multimodal LLMs for Simple Visual Planning Tasks](https://mlsanity.com/paper/2602.15460/) (2026)

## Abstract (arXiv)

We study certain extremal problems in combinatorial geometry that ask about configurations of points in an n × 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(n3) to O(n2). 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 ≤ n ≤ 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.