🤖 AI

Geometry-Aware MCTS for Extremal Problems in Combinatorial Geometry

This paper introduces a Geometry-Aware Monte Carlo Tree Search framework that overcomes the limitations of classical solvers and standard AI models in combinatorial geometry by enforcing constraints through incremental action space updates and exploiting geometric symmetries, thereby establishing new best-known results for extremal problems like the No-Three-in-Line and Smallest Complete Set problems.

Original authors: Luoning Zhang, Xu Zhuang, Tianhao Wang, Nathan Kaplan

Published 2026-06-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Luoning Zhang, Xu Zhuang, Tianhao Wang, Nathan Kaplan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a giant checkerboard, say 100 squares by 100 squares. Your goal is to place as many coins as possible on this board, but you have a strict rule: no three coins can ever line up in a straight row, column, or diagonal.

This is a famous math puzzle called the "No-Three-in-Line" problem. It sounds simple, but as the board gets bigger, the number of ways you can arrange the coins explodes into the trillions. Trying to find the best arrangement by checking every possibility is like trying to drink from a firehose; it's impossible.

This paper introduces a new, smarter way to solve these puzzles using a computer algorithm called Geometry-Aware MCTS. Here is how they did it, explained in everyday terms:

The Problem: The "Validity Cliff"

Imagine you are playing a game where you place one coin at a time.

Old AI methods (like Reinforcement Learning): These are like a blindfolded person throwing darts. They might place 99 coins perfectly, but if the 100th coin accidentally lines up with two others, the entire game is ruined. The computer gets no reward for the 99 good coins, only a "game over" signal. This is called the "validity cliff." The AI gets frustrated and stops learning because it rarely gets a "win."
Old Math solvers: These are like a librarian trying to read every single book in a library to find one specific sentence. They are accurate but too slow for big boards.

The Solution: A "Smart Gardener" Approach

The authors built a new system that acts like a smart gardener tending to a garden of possibilities. Instead of guessing and failing, the gardener knows exactly which seeds (coins) can be planted without ruining the garden.

Here are the three main tricks they used:

1. The "Fence" (Incremental Feasible Action Space)

Instead of letting the computer check every empty square on the board to see if a coin fits, the system builds a fence around the valid spots.

How it works: When you place a coin, the system instantly draws invisible lines (rays) through that coin and every other coin already on the board. Any empty square that falls on those lines is immediately marked as "off-limits."
The Analogy: Imagine you are placing furniture in a room. Instead of measuring the whole room every time you move a chair, you just mark the specific spots the chair cannot go. This makes checking for rules incredibly fast, turning a slow, heavy task into a quick one.

2. The "Mirror Trick" (Symmetry and Pruning)

A square board looks the same if you rotate it 90 degrees or flip it like a pancake.

The Problem: If the computer finds a good arrangement, it wastes time checking the exact same arrangement just rotated or flipped.
The Fix: The system acts like a mirror. If it sees a move that is just a rotated version of a move it has already checked, it ignores it. It only explores the "original" version. This cuts the amount of work the computer has to do by a huge margin (about 87.5% less work right at the start!).

3. The "Snowball Effect" (Symmetric Batch Transitions)

Sometimes, the best arrangements are perfectly symmetrical (like a snowflake).

The Trick: Instead of placing one coin and waiting to see what happens, the system tries to place a whole group of coins at once. If you place one coin, the system immediately tries to place its "mirror images" (rotated or flipped copies) at the same time.
The Result: If the whole group fits the rules, the computer jumps forward four steps in one go. If the group breaks the rules, it just places the single coin and tries again. This helps the computer find beautiful, symmetrical patterns much faster.

The Results: Breaking Records

Using this "Smart Gardener" approach, the team solved problems that were previously thought to be too hard for computers.

For the "No-Three-in-Line" problem: They found arrangements for boards as large as 119x119. They managed to place about 1.8 coins for every 1 square of the board's side length. This is a significant improvement over the previous best-known mathematical guesses.
For other puzzles: They also improved the best-known answers for problems involving "smallest sets that cover the board" and "no four points on a circle."

Why This Matters

The paper doesn't claim this will cure diseases or predict the stock market. Instead, it shows that by combining strict geometric rules with smart search strategies, computers can solve complex mathematical puzzles that were previously stuck.

They proved that you don't need a super-computer or a massive AI brain to solve these; you just need a method that respects the geometry of the problem. They did all this using just a single standard computer processor and a modest amount of memory, proving that "smart pruning" is more powerful than raw computing power.

Technical Summary: Geometry-Aware MCTS for Extremal Problems in Combinatorial Geometry

Problem Statement

The paper addresses a class of extremal problems in combinatorial geometry defined on discrete $n \times n$ grids. These problems seek to find point configurations that satisfy strict, global geometric constraints while maximizing or minimizing the number of points. Representative examples include:

Max-No-Three-in-Line (Max-N3IL): Finding the maximum number of points such that no three are collinear.
Min-Complete: Finding the smallest "complete" set (where no additional point can be added without violating the no-three-in-line constraint).
Min-Dominating Set: Finding the smallest set of points such that every grid point lies on a line defined by two points in the set.
Other Variants: Problems involving constraints on four collinear points (Max-N4IL), four concyclic points (Max-No-4-on-Circle), and isosceles triangles (Max-No-Isosceles).

Challenges:
Classical exact solvers (e.g., Integer Linear Programming) suffer from combinatorial explosion and scalability walls (often failing at $n \approx 19$ ) due to the $O(n^3)$ constraint density. Standard Reinforcement Learning (RL) and Transformer-based models struggle with:

The "Validity Cliff": A single invalid move (e.g., creating three collinear points) renders the entire configuration invalid, creating a sparse reward signal that hinders gradient-based optimization.
Token/Computational Overhead: Representing grids requires $O(n^2)$ tokens, leading to poor scaling for attention mechanisms, while autoregressive generation often hallucinates invalid placements.
Generalization: Existing AI methods often fail to scale beyond small grids ( $n < 15$ ) or rely on training data that cannot generalize to the irregular, non-algebraic structures of large optimal configurations.

Methodology: Geometry-Aware MCTS

The authors propose a Geometry-Aware Monte Carlo Tree Search (MCTS) framework that formulates these problems as deterministic Markov Decision Processes (MDPs). The framework introduces specific algorithmic innovations to handle the strict constraints and large search spaces:

1. Incremental Feasible Action Space ( $A_{feas}$ )

Instead of treating the entire grid as the action space, the framework strictly maintains a set of feasible actions where placing a point does not violate the geometric invariant $\Phi$ .

Mechanism: For problems like Max-N3IL, the system uses Ray Casting. When a new point is placed, it "casts rays" to all existing points, marking all grid cells on those lines as invalid.
Complexity Improvement: This incremental update reduces the complexity of checking constraints from $O(n^3)$ (re-scanning the whole grid) to $O(n^2)$ per node. This ensures the search never enters invalid states, bypassing the sparse-reward cliff.

2. Exploiting Grid Symmetry ( $D_4$ )

The framework leverages the dihedral group $D_4$ (rotations and reflections) to reduce the search space and accelerate discovery.

Canonical Pruning: During the tree expansion phase, the algorithm computes the stabilizer subgroup $Stab(s)$ of the current state. It prunes the action space to include only one representative (canonical) action per orbit of equivalent moves, significantly reducing the branching factor.
Symmetric Batch Transitions: The MDP transition function is modified to attempt placing an entire orbit of points simultaneously. If the batch placement is valid, the agent commits the whole symmetric set in one step; otherwise, it falls back to placing a single point. This accelerates the discovery of symmetric configurations and keeps the search tree deeper within symmetric subspaces.

3. Enhanced Search Strategy

To maximize efficiency under a finite computational budget, the framework employs:

Subtree Reuse: Since transitions are deterministic, the search tree is not discarded after each step. The child node becomes the new root for the next phase, preserving accumulated visit counts and allowing for "warm starts."
Time-Dependent Exploration Decay: The exploration constant in the UCB1 formula is decayed over time, but crucially, the decay calculation accounts for visit counts inherited from previous tree phases to maintain continuous confidence.
Anytime Optimal Tracking: During simulations, any terminal state found is evaluated against the global best. This ensures that "outlier" solutions discovered deep in random rollouts are permanently recorded, even if the final MCTS policy converges to a different path.

Key Contributions

Algorithmic Innovation: The introduction of an incremental feasible action space maintenance mechanism that reduces constraint checking complexity from $O(n^3)$ to $O(n^2)$ for collinear constraints.
Symmetry Exploitation: The development of Canonical Pruning (via state stabilizers) and Symmetric Batch Transitions, which effectively reduce branching factors and accelerate search depth in symmetric subspaces.
New Computational Bounds: The framework establishes new best-known computational results for five out of the six problems studied.
- Max-N3IL: Found configurations of size $\approx 1.8n$ for grids $82 \le n \le 119$ , significantly improving upon the asymptotic lower bound of $\approx 1.5n$ .
- Min-Complete & Min-Dom: Found configurations of size $\approx 0.95n$ for $37 \le n \le 96$ , providing new upper bounds.
- Other Problems: Improved lower bounds for Max-N4IL (finding $3n$ points), Max-No-Isosceles ( $\approx 1.4n$ ), and Max-No-4-on-Circle ( $\approx 1.8n$ ).

Results and Significance

The paper demonstrates that Geometry-Aware MCTS can effectively navigate the "validity cliff" and combinatorial explosion that plague other methods.

Scalability: The framework successfully explored grid sizes up to $n=119$ for Max-N3IL using only a single CPU core and a strict 6GB memory limit, a feat previously unattainable for these specific problem scales.
Efficiency: Ablation studies confirm that the combination of incremental updates, canonical pruning, and batch transitions is essential. While canonical pruning alone offered marginal gains, its synergy with batch transitions unlocked significant performance improvements.
Significance: The work establishes Geometry-Aware MCTS as a highly adaptable framework for discovering novel configurations in combinatorial geometry. It provides empirical constructions that bridge the gap between theoretical lower bounds and trivial upper bounds, offering valuable data points for future theoretical work. The authors note that while their method does not provide closed-form proofs, it offers a scalable, search-based paradigm capable of handling hard global constraints where algebraic or probabilistic methods struggle.

The paper concludes that this approach serves as a versatile tool for discrete geometry constructions, with future potential for integration with neural networks for value/policy guidance and further scaling via parallelization.