Geometry-Aware MCTS sets new records on Max-N3IL (n=82-119)

Luoning Zhang, Xu Zhuang, Tianhao Wang and Nathan Kaplan submitted a paper to arXiv on 24 Jun 2026 proposing a Geometry-Aware Monte Carlo Tree Search framework to attack extremal problems in combinatorial geometry. The method enforces geometric constraints incrementally, reduces constraint-checking complexity for collinearity constraints from O(n^3) to O(n^2), and produced new best-known computational results on five out of six problems the authors considered.

What is Geometry-Aware MCTS and how does it work?

Geometry-Aware MCTS is a Monte Carlo Tree Search framework that strictly enforces geometric constraints via incremental updates to the feasible action space, and that exploits geometric symmetries through canonical pruning and symmetric batch transitions. The paper describes enforcing constraints about collections of collinear points, and reports that for those constraints the incremental mechanism lowers constraint checking complexity from O(n^3) to O(n^2). The authors also use canonical pruning during node expansion to reduce branching and symmetric batch transitions to accelerate discovery of promising configurations.

What results did the authors report?

The authors established new best-known computational results on five out of six problems they tested, including substantial empirical gains on classical benchmarks. For the No-Three-in-Line problem (Max-N3IL) they report finding configurations of size roughly 1.8 n for grids of size 82 ≤ n ≤ 119. For the Smallest Complete Set problem they find configurations of size roughly 0.95 n, which the paper describes as providing new upper bounds within the tested grids. The paper contrasts these outcomes with the limitations of other approaches: classical exact solvers face combinatorial explosion, and "standard reinforcement learning and transformer-based models struggle with the sparse reward "validity cliff" and quadratic token-consumption limits."

Why it matters

The work shows that embedding geometric structure directly into a search procedure can both cut algorithmic cost and improve empirical results on hard combinatorial-geometry tasks. Reducing constraint-check complexity from O(n^3) to O(n^2) for collinearity checks directly addresses a key computational bottleneck the authors identify. The reported new best-known results on five of six problems indicate the approach can outperform general-purpose solvers and learning methods on sparse-reward, global-constraint problems.

What to watch

Look for whether the authors publish code and datasets linked from the arXiv entry's "Code, Data and Media Associated with this Article" section, and whether the framework extends Max-N3IL improvements beyond the tested range (n > 119) or closes the gap on the single problem where it did not set a new best-known result.