Geometry-Aware MCTS for Extremal Problems in Combinatorial Geometry

# Geometry-Aware MCTS for Extremal Problems in Combinatorial Geometry
Source: [https://arxiv.org/html/2606.26399](https://arxiv.org/html/2606.26399)
Xu Zhuangxzhuang8@uci\.eduDepartment of Mathematics, University of California, IrvineTianhao Wangtianhw11@uci\.eduDepartment of Mathematics, University of California, IrvineNathan Kaplannckaplan@math\.uci\.eduDepartment of Mathematics, University of California, Irvine

###### Abstract

We study certain extremal problems in combinatorial geometry that ask about configurations of points in ann×nn\\times ngrid 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 fromO​\(n3\)O\(n^\{3\}\)toO​\(n2\)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 roughly1\.8​n1\.8nfor grids of size82≤n≤11982\\leq n\\leq 119\. For the Smallest Complete Set problem, we find configurations of size roughly0\.95​n0\.95n, 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\.

## 1Introduction

![Refer to caption](https://arxiv.org/html/2606.26399v1/x1.png)Figure 1:Overview of the Geometry\-Aware MCTS framework\.The search process is guided by problem specification \(grey\) including a Feasible Action Space defined by the specific problem constraint and Symmetric Batch Transitions \(e\.g\., rotations and reflections\) derived from a geometric prior\. The core MCTS engine \(blue\) utilizes Canonical Pruning to reduce branching during expansion\. The resulting policy dictates the main loop \(right\), which employs Subtree Reuse for efficiency and Anytime Optimal Tracking to asynchronously record the global best\-found configuration across all simulations\.![Refer to caption](https://arxiv.org/html/2606.26399v1/n3il-3x3-4.png)\(a\)An example configuration with no three collinear points\.
![Refer to caption](https://arxiv.org/html/2606.26399v1/n3il-3x3-5.png)\(b\)An example configuration with three collinear points \(diagonal line\)\.
![Refer to caption](https://arxiv.org/html/2606.26399v1/n3il-3x3-6.png)\(c\)A configuration with no three collinear points of maximum size\.

Figure 2:Three examples of point configurations on a 3x3 grid\.We study certain extremal problems onn×nn\\times ngrids\. These problems ask about the maximum or minimum number of points in the grid that satisfy certain geometric constraints\. Representative examples include finding the largest point sets with no isosceles triangles, the largest point sets with no four points on a circle, or the smallest independent geometric dominating set\. The No\-Three\-in\-Line Problem \(Max\-N3IL\) has attracted considerable attention, both as a theoretical problem and as an algorithmic one\. This problem has a history going back at least toDudeney \([1917](https://arxiv.org/html/2606.26399#bib.bib1)\)\. It asks for the maximum number of points in ann×nn\\times ngrid such that no33points are collinear\. We denote the answer to this problem byM​\(n\)M\(n\)\. Some configurations in a3×33\\times 3grid are given in[fig\.˜2](https://arxiv.org/html/2606.26399#S1.F2)\.

Despite its elementary formulation, determiningM​\(n\)M\(n\)remains an open challenge for largenn\. Sincennparallel lines cover then×nn\\times ngrid and we cannot have more than two points on any of these lines, we see thatM​\(n\)≤2​nM\(n\)\\leq 2n\.Flammenkamp \([1992](https://arxiv.org/html/2606.26399#bib.bib5);[1998](https://arxiv.org/html/2606.26399#bib.bib6)\)has shown thatM​\(n\)=2​nM\(n\)=2nfor alln≤46n\\leq 46and forn∈\{48,50,52\}n\\in\\\{48,50,52\\\}\.Prellberg \([2026](https://arxiv.org/html/2606.26399#bib.bib36)\)has very recently used advanced tools from constraint satisfaction programming to extend these results to show thatM​\(n\)=2​nM\(n\)=2nfor alln≤64n\\leq 64and forn∈\{66,68\}n\\in\\\{66,68\\\}\. Heule used a recently developed SAT solver to find solutions showing thatM​\(n\)=2​nM\(n\)=2nforn∈\{65,67,69,70\}n\\in\\\{65,67,69,70\\\}\. These results are actively tracked in[Flammenkamp](https://arxiv.org/html/2606.26399#bib.bib13)’s online database\([2026](https://arxiv.org/html/2606.26399#bib.bib13)\)\. We do not know the exact value ofM​\(n\)M\(n\)for anyn≥71n\\geq 71\. The best\-known asymptotic lower bound is due toHallet al\.\([1975](https://arxiv.org/html/2606.26399#bib.bib3)\), who use a construction coming from finite fields to show that for anyϵ\>0\\epsilon\>0and for all sufficiently largenn,M​\(n\)\>\(1\.5−ϵ\)​nM\(n\)\>\(1\.5\-\\epsilon\)n\. This leaves a significant gap between the constructive\(1\.5−ϵ\)​n\(1\.5\-\\epsilon\)nlower bound and the trivial2​n2nupper bound\.Guy and Kelly \([1968](https://arxiv.org/html/2606.26399#bib.bib4)\)used probabilistic arguments to suggest that asnngoes to infinity,M​\(n\)≈π3​n≈1\.814​nM\(n\)\\approx\\frac\{\\pi\}\{\\sqrt\{3\}\}n\\approx 1\.814n\. In order to better understand the growth ofM​\(n\)M\(n\), we would like to probe grid sizes that have historically been inaccessible to computation because of the combinatorial explosion in the search space\.

The complexity of these extremal problems on finite grids arises from the global nature of the geometric constraints\. A single point placement affects the set of remaining points in complex ways, making local constraint satisfaction insufficient\. While algebraic constructions provide rigorous guarantees, it is not at all clear whether we should expect extremal configurations to have algebraic structure\. This motivates a need for computational methods to better understand grids that have previously been inaccessible\.

In recent years, AI has achieved remarkable breakthroughs in combinatorial mathematics, from discovering graph theory counterexamples\(Wagner,[2021](https://arxiv.org/html/2606.26399#bib.bib9)\)to predicting modular curve invariants\(Zhuanget al\.,[2025](https://arxiv.org/html/2606.26399#bib.bib12)\)\. Applying these methods has not yet been successful on problems like Max\-N3IL\. A recent systematic evaluation byRamanathanet al\.\([2025](https://arxiv.org/html/2606.26399#bib.bib7)\)highlighted severe scalability limits across three distinct computational paradigms: exact solvers, reinforcement learning, and transformer\-based models\. Traditional exact solvers, such as Integer Linear Programming \(ILP\), guarantee optimal solutions but hit a scalability wall atn=19n=19due to theO​\(n3\)O\(n^\{3\}\)constraint density and exponential search space\. Conversely, standard model\-free Reinforcement Learning \(e\.g\., PPO\) fails even earlier, finding optimal configurations only up to10×1010\\times 10grids before systematically failing atn=11n=11\(Ramanathanet al\.,[2025](https://arxiv.org/html/2606.26399#bib.bib7)\)\. Generic RL agents struggle to maintain global geometric constraint awareness solely from scalar reward signals; a single collinear placement renders the entire configuration invalid, creating a sparse\-reward “validity cliff” that frustrates gradient\-based optimization\. WhilePrellberg \([2026](https://arxiv.org/html/2606.26399#bib.bib36)\)employs constraint satisfaction programming to search for configurations of size exactly2​n2n, this incurs prohibitive computational costs, demanding 10 CPU days forn≤60n\\leq 60and extensive GPU parallelization to merely reachn=66n=66\(Flammenkamp,[2026](https://arxiv.org/html/2606.26399#bib.bib13)\)\.

More recently, advanced AI paradigms like Large Language Models \(FunSearch,Romera\-Paredeset al\.,[2024](https://arxiv.org/html/2606.26399#bib.bib10); AlphaEvolve,Novikovet al\.,[2025](https://arxiv.org/html/2606.26399#bib.bib20); and MCTS\-AHD,Zhenget al\.,[2025](https://arxiv.org/html/2606.26399#bib.bib25)\) and Transformer\-based search \(PatternBoost,Chartonet al\.,[2024](https://arxiv.org/html/2606.26399#bib.bib21)\) have discovered impressive new constructions for similar extremal problems, for example the famous Cap Set Problem about points in\(ℤ/3​ℤ\)n\(\\mathbb\{Z\}/3\\mathbb\{Z\}\)^\{n\}\. These models have not yet been successful when applied to the problems we consider here\. When PatternBoost is applied to study Max\-N3IL, it matches optimal performance on small grids but fails to scale beyondn=15n=15\(Ramanathanet al\.,[2025](https://arxiv.org/html/2606.26399#bib.bib7)\)\. This specific scalability wall arises because the transformer’s pattern generalization is severely bottlenecked by the quality\-speed trade\-off inherent in the greedy algorithms used to generate its training data\. Beyond this data generation bottleneck, transformer\-based models are intrinsically highlytoken\-consumingand computationally expensive\. Representing ann×nn\\times ngrid requiresO​\(n2\)O\(n^\{2\}\)tokens, leading to attention mechanisms that scale poorly for larger grids\. Furthermore, autoregressive generation often struggles to strictly adhere tohardglobal constraints without hallucinating invalid placements\. LLM\-driven methods likeFunSearchexcel at finding concise heuristics, but it may be the case that optimal configurations on large grids are highly irregular and difficult to express using simple rules\. Furthermore, potentially constrained by their training distributions, these LLMs may exhibit limitations in the out\-of\-distribution \(OOD\) algorithmic generalization required to discover genuinely novel logic for unsolved problems in this area\(Li and Ellis,[2024](https://arxiv.org/html/2606.26399#bib.bib37); Neuhauset al\.,[2026](https://arxiv.org/html/2606.26399#bib.bib38)\)\. These limitations necessitate a different algorithmic paradigm that combines strict geometric constraint satisfaction with scalable search\.

##### Why MCTS: A Geometry\-Aware Approach

To overcome the limitations of classical solvers and recent learning\-based methods for problems like Max\-N3IL, we propose aGeometry\-Aware MCTSframework\(Coulom,[2007](https://arxiv.org/html/2606.26399#bib.bib15); Kocsis and Szepesvári,[2006](https://arxiv.org/html/2606.26399#bib.bib14)\)\. Monte Carlo Tree Search \(MCTS\) avoids the sparse\-reward “validity cliff” of standard RL by using simulated trajectories to provide dense, constructive reward signals\. Furthermore, it effortlessly enforces hard geometric constraints by masking invalid placements, bypassing both the hallucination risks andO​\(n2\)O\(n^\{2\}\)token overhead of sequence models\. While the asymmetric tree growth of MCTS naturally balances exploration and exploitation in unstructured spaces, scaling it to large grids \(e\.g\.,n\>50n\>50\) requires specific adaptations\. Our framework makes this tractable by \(1\) incrementally maintaining a strict feasible action space \(𝒜feas\\mathcal\{A\}\_\{\\text\{feas\}\}\) to minimize per\-node overhead, \(2\) exploitingD4D\_\{4\}grid symmetry during expansion and simulation to reduce branching, and \(3\) augmenting the search strategy with information persistence, adaptive exploration, and global optimum tracking to maximize yield under a finite computational budget\.

##### Main Contributions

Our work advances the intersection of combinatorial geometry and reinforcement learning by demonstrating the efficacy of search\-based paradigms\. By formulating extremal construction as a geometric Markov Decision Process \(MDP\), we introduce specific algorithmic innovations to make MCTS tractable in vast, constraint\-heavy spaces\. The specific contributions are as follows:

- •We propose anIncremental Feasible Action Space\(𝒜feas\\mathcal\{A\}\_\{\\text\{feas\}\}\) maintenance mechanism\. For problems based on constraints about collinear sets of points, such as Max\-N3IL, this ray\-casting approach reduces the per\-node complexity for checking constraints fromO​\(n3\)O\(n^\{3\}\)toO​\(n2\)O\(n^\{2\}\)\. This effectively bypasses the sparse\-reward “validity cliff” that typically paralyzes standard RL agents\.
- •We introduceCanonical Action Pruningvia dynamically computed state stabilizersStab​\(s\)≤D4\\text\{Stab\}\(s\)\\leq D\_\{4\}, restricting tree expansion to orbit representatives while deliberately disabling pruning during rollouts to minimize computational overhead without sacrificing branching reduction\.
- •We proposeSymmetric Batch Transitions, a novel MDP transition mechanism that executes the simultaneous placement of an orbit under a chosen collection of symmetries\. This significantly accelerates the discovery of promising symmetric configurations and allows canonical pruning to remain effective deeper into the search tree\.
- •We improve the best\-known computational bounds for five out of the six problems that we considered\. Notably, we significantly extend the range in which we have lower bounds for Max\-N3IL that are better than the asymptotic lower bound of size approximately1\.5​n1\.5n\. We also find configurations giving upper bounds for the Smallest Complete Set problem that are smaller than the best\-known construction\.

## 2Problem Formulation

We study extremal subset construction on the discrete grid𝒢n=\[n\]×\[n\]\\mathcal\{G\}\_\{n\}=\[n\]\\times\[n\]under hard geometric constraints\. Unlike in probabilistic generation tasks, a construction is either valid or invalid according to a binary predicateΦ\\Phi\(e\.g\., “no three points are collinear”\)\. We therefore cast the process as a sequential decision problem, enabling search and planning methodsVodopivecet al\.\([2017](https://arxiv.org/html/2606.26399#bib.bib40)\)\.

### 2\.1A General Geometric MDP Framework

We formulate geometric construction sequentially as a deterministic MDP defined by the tuple\(𝒮,𝒜,𝒯,ℛ\)\(\\mathcal\{S\},\\mathcal\{A\},\\mathcal\{T\},\\mathcal\{R\}\)\. Although the target configuration is permutation\-invariant, this sequential formulation is computationally advantageous because it enforces hard constraints at every step, immediately pruning invalid branches\. The state space𝒮=\{s∣s⊆𝒢n\}\\mathcal\{S\}=\\\{s\\mid s\\subseteq\\mathcal\{G\}\_\{n\}\\\}is the power set of the grid, where a states∈𝒮s\\in\\mathcal\{S\}represents a configuration of points, initialized at the empty sets=∅s=\\emptyset\. To maintain structural validity, we define a Boolean geometric invariantΦ:𝒮→\{True,False\}\\Phi:\\mathcal\{S\}\\to\\\{\\text\{True\},\\text\{False\}\\\}\(e\.g\., for Max\-N3IL,Φ​\(s\)\\Phi\(s\)holds iff no three points are collinear\)\. Consequently, the action space is strictly confined to feasible placements, defined as𝒜feas​\(s\)=\{p∈𝒢n∖s∣Φ​\(s∪\{p\}\)=True\}\\mathcal\{A\}\_\{\\text\{feas\}\}\(s\)=\\\{p\\in\\mathcal\{G\}\_\{n\}\\setminus s\\mid\\Phi\(s\\cup\\\{p\\\}\)=\\text\{True\}\\\}\. This ensures that any action taken preservesΦ\\Phi\(efficient incremental maintenance of𝒜feas\\mathcal\{A\}\_\{\\text\{feas\}\}is detailed in Section[3\.2](https://arxiv.org/html/2606.26399#S3.SS2)\)\. Transitions are deterministic and additive, given bys′=s∪\{a\}s^\{\\prime\}=s\\cup\\\{a\\\}fora∈𝒜feas​\(s\)a\\in\\mathcal\{A\}\_\{\\text\{feas\}\}\(s\)\. A statessis terminal \(denoted assTs\_\{T\}\) if and only if𝒜feas​\(s\)=∅\\mathcal\{A\}\_\{\\text\{feas\}\}\(s\)=\\emptyset, meaning the configuration is maximal under inclusion\. Note that just because a configuration is maximal does not mean that it has optimal cardinality\. Finally, the reward functionR​\(sT,n\)R\(s\_\{T\},n\)is evaluated at terminal states\. For maximization variants \(e\.g\., Max\-N3IL\),RRincreases with\|sT\|\|s\_\{T\}\|; for minimization variants \(e\.g\., Min\-Complete\), it decreases with\|sT\|\|s\_\{T\}\|\. Detailed formulations are given in Appendix[C\.1](https://arxiv.org/html/2606.26399#A3.SS1)\.

### 2\.2Problem Variants

We apply the proposed MDP framework to six extremal combinatorial geometry problems\. For each problem, the geometric constraints are strictly governed by the state validity predicateΦ​\(s\)\\Phi\(s\), and the objective is to either maximize or minimize the terminal set cardinality\|sT\|\|s\_\{T\}\|\. LetP⊆sP\\subseteq sdenote an arbitrary subset of the current state\.

##### Collinear Constraints: Max\-N3IL and Min\-Complete\.

Both problems share the same predicate enforcing general position:Φ\(s\)=\{∀P⊆swith\|P\|=3,¬Coll\(P\)\}\\Phi\(s\)=\\left\\\{\\forall P\\subseteq s\\text\{ with \}\|P\|=3,\\neg\\text\{Coll\}\(P\)\\right\\\}, whereColl​\(P\)\\text\{Coll\}\(P\)is true if the points inPPare collinear\. Because our MDP naturally terminates only at inclusion\-wise maximal states \(𝒜feas=∅\\mathcal\{A\}\_\{\\text\{feas\}\}=\\emptyset\), any terminal configuration is inherently a “complete” set\. As illustrated in[fig\.˜3](https://arxiv.org/html/2606.26399#S2.F3), the search stops exactly when all remaining empty cells lie on a line connecting two points already included in the set \([figs\.˜3\(b\)](https://arxiv.org/html/2606.26399#S2.F3.sf2)and[3\(c\)](https://arxiv.org/html/2606.26399#S2.F3.sf3)\)\. Max\-N3IL seeks to maximize\|sT\|\|s\_\{T\}\|\(Dudeney,[1917](https://arxiv.org/html/2606.26399#bib.bib1)\), whereas Min\-Complete \(a\.k\.a\. Smallest Independent Geometric Dominating Set\) seeks to minimize\|sT\|\|s\_\{T\}\|\(Aichholzeret al\.,[2023](https://arxiv.org/html/2606.26399#bib.bib27)\)\.

##### Smallest Geometric Dominating Set \(Min\-Dom\)\.

This problem is like Min\-Complete, except that we drop the requirement that no three points of the configuration are collinear\. LetCover​\(X\)\\text\{Cover\}\(X\)be true if the lines spanned by all pairs of distinct points inXXcollectively cover every point in the grid𝒢n\\mathcal\{G\}\_\{n\}\(i\.e\., every grid point is either inXXor collinear with at least two distinct points inXX\)\. The predicate is defined asΦ​\(s\)=\{∀s′⊊s,¬Cover​\(s′\)\}\\Phi\(s\)=\\left\\\{\\forall s^\{\\prime\}\\subsetneq s,\\neg\\text\{Cover\}\(s^\{\\prime\}\)\\right\\\}\. Ifssis not a dominating set, then no subset ofssis a dominating set\. Ifssis a dominating set, then any superset ofssis also a dominating set\. In this way, we see that the search terminates exactly when a minimal dominating set is found\. The objective is to minimize\|sT\|\|s\_\{T\}\|\(Aichholzeret al\.,[2023](https://arxiv.org/html/2606.26399#bib.bib27)\)\.

##### Additional Problems\.

To demonstrate the flexibility of our framework, we explore three additional problems\. In each one, we aim to maximize\|sT\|\|s\_\{T\}\|\.

1. 1\.Max\-N4IL:Φ\(s\)=\{∀P⊆swith\|P\|=4,¬Coll\(P\)\}\\Phi\(s\)=\\left\\\{\\forall P\\subseteq s\\text\{ with \}\|P\|=4,\\neg\\text\{Coll\}\(P\)\\right\\\}, a natural relaxation of N3IL\.
2. 2\.Max\-No\-4\-on\-Circle:Φ\(s\)=\{∀P⊆swith\|P\|=4,¬Circ\(P\)\}\\Phi\(s\)=\\left\\\{\\forall P\\subseteq s\\text\{ with \}\|P\|=4,\\neg\\text\{Circ\}\(P\)\\right\\\}, whereCirc​\(P\)\\text\{Circ\}\(P\)indicates the points are concyclic on a circle of finite radius\(Dong and Xu,[2025](https://arxiv.org/html/2606.26399#bib.bib29)\)\.
3. 3\.Max\-No\-Isosceles:Φ\(s\)=\{∀P⊆swith\|P\|=3,¬Isos\(P\)\}\\Phi\(s\)=\\left\\\{\\forall P\\subseteq s\\text\{ with \}\|P\|=3,\\neg\\text\{Isos\}\(P\)\\right\\\}, whereIsos​\(P\)\\text\{Isos\}\(P\)is true if at least two Euclidean distances between points inPPare equal, including degenerate cases \(i\.e\., collinear triples where one point is the midpoint of the segment\)\.

![Refer to caption](https://arxiv.org/html/2606.26399v1/complete_incomplete_ex.png)\(a\)This set is not complete\. Either of the two white squares could be added without creating a collinear triple\.
![Refer to caption](https://arxiv.org/html/2606.26399v1/complete_ex.png)\(b\)A complete set on a3×33\\times 3grid\.
![Refer to caption](https://arxiv.org/html/2606.26399v1/complete_optimal.png)\(c\)A complete set on a3×33\\times 3grid of minimum size\.

Figure 3:Examples of incomplete and complete point configurations\.

## 3Method: Geometry\-Aware MCTS

Monte Carlo Tree Search \(MCTS\) has demonstrated remarkable versatility and success across diverse domains, ranging from significantly improving real\-time decision\-making in heuristic\-free general video game playing\(Soemerset al\.,[2016](https://arxiv.org/html/2606.26399#bib.bib33)\), to enabling effective test\-time scaling for Large Language Models\(Wanget al\.,[2025](https://arxiv.org/html/2606.26399#bib.bib34)\)\. However, it is challenging to apply off\-the\-shelf MCTS to extremal problems in combinatorial geometry because of the strictness of the constraints and theO​\(n2\)O\(n^\{2\}\)increase in the size of the action space\. In this section, we first define the standard baseline and analyze its limitations, then introduce our Geometry\-Aware framework\.

### 3\.1Baseline MCTS and the Naive Action Space

We adopt the UCT \(Upper Confidence bounds applied to Trees\) algorithm\(Kocsis and Szepesvári,[2006](https://arxiv.org/html/2606.26399#bib.bib14)\)as our baseline\. During the selection phase, the agent traverses the tree by selecting actions that maximize the UCB1 \(Upper Confidence Bound 1\) criterion:

UCB1​\(s,a\)=Q​\(s,a\)N​\(s,a\)\+C​ln⁡N​\(s\)N​\(s,a\),\\text\{UCB1\}\(s,a\)=\\frac\{Q\(s,a\)\}\{N\(s,a\)\}\+C\\sqrt\{\\frac\{\\ln N\(s\)\}\{N\(s,a\)\}\},\(1\)whereQ​\(s,a\)Q\(s,a\)is the accumulated reward,N​\(s,a\)N\(s,a\)is the visit count, andCCgoverns exploration\. Since our MDP transitions are deterministic,Q​\(s,a\)Q\(s,a\)simplifies to the value of the unique successor state,V​\(s′\|s,a\)V\(s^\{\\prime\}\|s,a\), andN​\(s,a\)N\(s,a\)precisely equals the visit count of that child node\. After executing the standard MCTS phases \(selection, expansion, simulation, and backpropagation\) for a computational budgetHH, the search policy selects the most visited action:a=argmaxa∈𝒜​\(s\)N​\(s,a\)a=\\operatorname\*\{argmax\}\_\{a\\in\\mathcal\{A\}\(s\)\}N\(s,a\)\.

##### Naive Action Space and Dual Bottlenecks\.

Lacking domain\-specific geometric constraints, the baseline agent considers any unoccupied grid cell as a potential move\. This defines theNaive Action Space:

𝒜naive​\(s\)=𝒢n∖s\.\\mathcal\{A\}\_\{\\text\{naive\}\}\(s\)=\\mathcal\{G\}\_\{n\}\\setminus s\.\(2\)Operating on𝒜naive\\mathcal\{A\}\_\{\\text\{naive\}\}introduces two fundamental scalability bottlenecks\. First, thecombinatorial branching factor\(\|𝒜naive\|≈n2\|\\mathcal\{A\}\_\{\\text\{naive\}\}\|\\approx n^\{2\}\) severely dilutes visit counts at the root \(e\.g\., nearly 5,000 actions forn=70n=70\), rendering UCB1 estimates high\-variance\. Second, thevalidity bottleneckarises because the density of valid moves decays rapidly\. A rollout policy selecting uniformly from𝒜naive\\mathcal\{A\}\_\{\\text\{naive\}\}almost certainly violates the invariantΦ\\Phi, triggering immediate termination with sub\-optimal reward\. Consequently, discovering deep, valid configurations by chance becomes mathematically intractable for largenn\.

### 3\.2Feasible Action Space via Incremental Maintenance

To resolve the validity bottleneck described in Section[3\.1](https://arxiv.org/html/2606.26399#S3.SS1), our framework restricts the search strictly to theFeasible Action Space\(𝒜feas\\mathcal\{A\}\_\{\\text\{feas\}\}\) that is described in Section[2\.1](https://arxiv.org/html/2606.26399#S2.SS1)\. This ensures that any action does not violateΦ\\Phi\. Although𝒜feas​\(s\)\\mathcal\{A\}\_\{\\text\{feas\}\}\(s\)was defined conceptually in Section[2](https://arxiv.org/html/2606.26399#S2), computing it from scratch at every search node is computationally expensive\. For the Max\-N3IL problem, verifying a single candidate pointppagainst the current statesscan be done inO​\(\|s\|\)=O​\(n\)O\(\|s\|\)=O\(n\)time using slope hashing: one computes the normalized direction fromppto eachpi∈sp\_\{i\}\\in sand checks for collisions in a hash table, where any collision witnesses a collinear triple\. Aggregated over allO​\(n2\)O\(n^\{2\}\)grid locations, a full validity scan from scratch therefore costsO​\(n3\)O\(n^\{3\}\), which still becomes prohibitive when repeated at every node of a deep search tree\.

##### Monotonicity and Incremental Updates\.

We leverage the property ofconstraint monotonicity\. In our target problems, placing a point never “frees up” a previously blocked location—it only imposes new constraints\. Thus,𝒜feas​\(s′\)⊂𝒜feas​\(s\)\\mathcal\{A\}\_\{\\text\{feas\}\}\(s^\{\\prime\}\)\\subset\\mathcal\{A\}\_\{\\text\{feas\}\}\(s\)for any successor states′s^\{\\prime\}\. Instead of recomputing constraints from scratch, upon transitionings→s∪\{pn​e​w\}s\\to s\\cup\\\{p\_\{new\}\\\}, we update𝒜feas\\mathcal\{A\}\_\{\\text\{feas\}\}by solely identifying cells invalidated by the new point:

𝒜feas​\(s∪\{pn​e​w\}\)=𝒜feas​\(s\)∖\(\{pn​e​w\}∪NewConstraints​\(pn​e​w,s\)\)\.\\mathcal\{A\}\_\{\\text\{feas\}\}\(s\\cup\\\{p\_\{new\}\\\}\)=\\mathcal\{A\}\_\{\\text\{feas\}\}\(s\)\\setminus\\left\(\\\{p\_\{new\}\\\}\\cup\\text\{NewConstraints\}\(p\_\{new\},s\)\\right\)\.\(3\)

##### Example: Ray Casting for Max\-N3IL\.

For the Max\-N3IL problem, this update takes the form ofRay Casting\. As illustrated in Figure[4](https://arxiv.org/html/2606.26399#S3.F4), placing a new pointpn​e​wp\_\{new\}creates lines with each existing pointpi∈sp\_\{i\}\\in s\. We writeRay​\(u,v\)\\text\{Ray\}\(u,v\)for the set of points in the grid on the line connectinguuandvv\. The update rule becomes:

NewConstraints​\(pn​e​w,s\)=⋃pi∈sRay​\(pn​e​w,pi\)\.\\text\{NewConstraints\}\(p\_\{new\},s\)=\\bigcup\_\{p\_\{i\}\\in s\}\\text\{Ray\}\(p\_\{new\},p\_\{i\}\)\.\(4\)Computing a discrete line \(e\.g\., via GCD of coordinates\) and marking its cells takesO​\(n\)O\(n\)operations, and there are\|s\|≤2​n\|s\|\\leq 2nexisting points\. Therefore, the total update complexity isO​\(n2\)O\(n^\{2\}\)\. This represents a significant improvement over theO​\(n3\)O\(n^\{3\}\)baseline, enabling deeper search within the same time budget\.

Furthermore, the strict enforcement of geometric constraints naturally prunes the search tree\. As illustrated by comparing Figure[4\(b\)](https://arxiv.org/html/2606.26399#S3.F4.sf2)and Figure[4\(c\)](https://arxiv.org/html/2606.26399#S3.F4.sf3), the size of the feasible action space\|𝒜feas\|\|\\mathcal\{A\}\_\{\\text\{feas\}\}\|shrinks drastically as more points are placed, whereas\|𝒜naive\|\|\\mathcal\{A\}\_\{\\text\{naive\}\}\|only decreases by one per step\. This effectively mitigates thecombinatorial branching factorbottleneck identified in Section[3\.1](https://arxiv.org/html/2606.26399#S3.SS1), allowing the UCB estimates to converge significantly faster on the remaining highly\-promising branches\.

![Refer to caption](https://arxiv.org/html/2606.26399v1/5by5_A_feas_pts3.png)\(a\)Statesswith 3 points\. Red cells indicate unoccupied points that are not in𝒜feas\\mathcal\{A\}\_\{\\text\{feas\}\}\.
![Refer to caption](https://arxiv.org/html/2606.26399v1/5by5_A_feas_pts4.png)\(b\)States′s^\{\\prime\}\(4 points\)\. Ray casting incrementally updates𝒜feas\\mathcal\{A\}\_\{\\text\{feas\}\}\.
![Refer to caption](https://arxiv.org/html/2606.26399v1/5by5_A_naive_pts4.png)\(c\)The naive action space𝒜naive\\mathcal\{A\}\_\{\\text\{naive\}\}for the same 4 points \(only occupied cells are illegal\)\.

Figure 4:Visualizing the Incremental Ray Casting update and comparing𝒜feas\\mathcal\{A\}\_\{\\text\{feas\}\}with𝒜naive\\mathcal\{A\}\_\{\\text\{naive\}\}on a5×55\\times 5grid\.

### 3\.3Exploiting Grid Symmetry

Then×nn\\times ngrid inherently possesses geometric symmetries described by the dihedral groupD4D\_\{4\}, which consists of eight isometric transformations \(four rotations and four reflections\)\. Because the validity predicateΦ\\Phiis invariant under these transformations, the MDP induces highly redundant symmetric branches during tree search\. We exploit this symmetry through two complementary mechanisms: reducing the search width via state\-dependent canonical pruning, and accelerating the search depth via global symmetric batch transitions\.

#### 3\.3\.1Canonical Pruning via State Stabilizers

To mitigate the combinatorial branching factor during the*Expansion*phase of MCTS, we dynamically prune geometrically equivalent actions based on the symmetry of the current state\. LetStab​\(s\)≤D4\\text\{Stab\}\(s\)\\leq D\_\{4\}denote the stabilizer subgroup of a valid statess, defined as the set of transformations that leave the state configuration unchanged:

Stab​\(s\)=\{g∈D4∣g⋅s=s\}\.\\text\{Stab\}\(s\)=\\\{g\\in D\_\{4\}\\mid g\\cdot s=s\\\}\.\(5\)The group action ofStab​\(s\)\\text\{Stab\}\(s\)partitions the feasible action space𝒜feas​\(s\)\\mathcal\{A\}\_\{\\text\{feas\}\}\(s\)into equivalence classes, or*orbits*\. For any candidate actiona∈𝒜feas​\(s\)a\\in\\mathcal\{A\}\_\{\\text\{feas\}\}\(s\), its orbit under the stabilizer is denoted by𝒪Stab​\(s\)​\(a\)=\{g⋅a∣g∈Stab​\(s\)\}\\mathcal\{O\}\_\{\\text\{Stab\}\(s\)\}\(a\)=\\\{g\\cdot a\\mid g\\in\\text\{Stab\}\(s\)\\\}\. Because transitioning to any action within the same orbit leads to isomorphic subtrees, we define a canonical pruning mechanism that restricts the expansion to exactly one representative action per orbit:

𝒜pruned​\(s\)=\{rep​\(𝒪Stab​\(s\)​\(a\)\)∣a∈𝒜feas​\(s\)\},\\mathcal\{A\}\_\{\\text\{pruned\}\}\(s\)=\\\{\\text\{rep\}\(\\mathcal\{O\}\_\{\\text\{Stab\}\(s\)\}\(a\)\)\\mid a\\in\\mathcal\{A\}\_\{\\text\{feas\}\}\(s\)\\\},\(6\)whererep​\(⋅\)\\text\{rep\}\(\\cdot\)is a deterministic tie\-breaking function, such as selecting the action with the lexicographically smallest coordinate index\.

Crucially, this canonical pruning is applied*exclusively*during node expansion\. We intentionally disable it during the*Simulation*\(rollout\) phase\. Since a simulation merely generates a single random trajectory to estimate the value function, computing stabilizers and orbits at each simulation step incurs severe computational overhead without the benefit of permanent branching factor reduction\. The impact of this pruning is most impactful at the beginning of the search; for instance, at the empty root node where\|Stab​\(∅\)\|=8\|\\text\{Stab\}\(\\emptyset\)\|=8, the initial branching factor is immediately reduced by nearly7/87/8\(as visualized in[fig\.˜5\(a\)](https://arxiv.org/html/2606.26399#S3.F5.sf1)\)\.

#### 3\.3\.2Symmetric Batch Transitions

While canonical pruning optimizes the tree width, empirical observations on the problems we tested suggest that optimal configurations frequently possess symmetries\(Flammenkamp,[1992](https://arxiv.org/html/2606.26399#bib.bib5);[1998](https://arxiv.org/html/2606.26399#bib.bib6);[2026](https://arxiv.org/html/2606.26399#bib.bib13); Prellberg,[2026](https://arxiv.org/html/2606.26399#bib.bib36); Aichholzeret al\.,[2023](https://arxiv.org/html/2606.26399#bib.bib27)\)\. To incorporate this structural prior, we introduce*Symmetric Batch Transitions*, which fundamentally redefines the MDP transition function to accelerate search depth and guide the agent toward highly symmetric subspaces\.

Before the search begins, we pre\-select a group of symmetriesG≤D4G\\leq D\_\{4\}\(e\.g\., the rotational groupC4C\_\{4\}\)\. When an actiona∈𝒜feasa\\in\\mathcal\{A\}\_\{\\text\{feas\}\}is selected by the agent \(either in the tree or during rollout\), we compute its orbit under the action ofGG, denoted as𝒪G​\(a\)=\{g⋅a∣g∈G\}\\mathcal\{O\}\_\{G\}\(a\)=\\\{g\\cdot a\\mid g\\in G\\\}\. We then evaluate whether these points can be placed simultaneously without violating the geometric invariant\. The modified transition function𝒯batch\\mathcal\{T\_\{\\text\{batch\}\}\}follows an “all\-or\-nothing” rule:

𝒯batch​\(s\)=\{s∪𝒪G​\(a\)if​Φ​\(s∪𝒪G​\(a\)\)=True,s∪\{a\}otherwise\.\\mathcal\{T\}\_\{\\text\{batch\}\}\(s\)=\\begin\{cases\}s\\cup\\mathcal\{O\}\_\{G\}\(a\)&\\text\{if \}\\Phi\(s\\cup\\mathcal\{O\}\_\{G\}\(a\)\)=\\text\{True\},\\\\ s\\cup\\\{a\\\}&\\text\{otherwise\}\.\\end\{cases\}\(7\)The batch transition is executed internally as a sequence of incremental additions, ensuring that each point is validated against the updated feasible action space𝒜feas\\mathcal\{A\}\_\{\\text\{feas\}\}\. As a result, the agent commits the entire orbit𝒪G​\(a\)\\mathcal\{O\}\_\{G\}\(a\)in a single MDP transition if mutually compatible \([figs\.˜5\(b\)](https://arxiv.org/html/2606.26399#S3.F5.sf2)and[5\(c\)](https://arxiv.org/html/2606.26399#S3.F5.sf3)\); otherwise, it gracefully falls back to placing only the single actionaa\([figs\.˜5\(d\)](https://arxiv.org/html/2606.26399#S3.F5.sf4),[5\(e\)](https://arxiv.org/html/2606.26399#S3.F5.sf5)and[5\(f\)](https://arxiv.org/html/2606.26399#S3.F5.sf6)\)\.

This batching mechanism operates throughout the entire MCTS pipeline, drastically accelerating terminal state evaluations during simulations\. Furthermore, it creates a powerful synergy with the canonical pruning described in Section[3\.3\.1](https://arxiv.org/html/2606.26399#S3.SS3.SSS1)\. Batch transitions are designed to generate states that preserve the global symmetryGGdeeper within the search tree, provided the fallback is not triggered\. Consequently, canonical pruning remains highly effective at reducing\|𝒜feas\|\|\\mathcal\{A\}\_\{\\text\{feas\}\}\|at deeper search depths\.

![Refer to caption](https://arxiv.org/html/2606.26399v1/sym_prun_empty_n3il-5x5-day.png)\(a\)Pruned𝒜feas\\mathcal\{A\}\_\{\\text\{feas\}\}on an empty grid\.
![Refer to caption](https://arxiv.org/html/2606.26399v1/batch_act_1_n3il-5x5-day.png)\(b\)Place a point and attempt batch actions underC4C\_\{4\}\.
![Refer to caption](https://arxiv.org/html/2606.26399v1/sym_prun_4pts_n3il-5x5-day.png)\(c\)Batch transition successful\.
![Refer to caption](https://arxiv.org/html/2606.26399v1/sym_prun_5pts_fallback_n3il-5x5-day.png)\(d\)Place another point and try batch action underC4C\_\{4\}\.
![Refer to caption](https://arxiv.org/html/2606.26399v1/n3il-5x5-batch_fail.png)\(e\)Constraint violated \(red points created collinear triples\)\.
![Refer to caption](https://arxiv.org/html/2606.26399v1/n3il-5x5-batch_fallback.png)\(f\)Fallback to single action\.

Figure 5:Visualization of Canonical Pruning via State Stabilizers \(green\-shaded spaces are pruned𝒜feas\\mathcal\{A\}\_\{\\text\{feas\}\}\) and Symmetric Batch Transitions \(succeeded from action[5\(b\)](https://arxiv.org/html/2606.26399#S3.F5.sf2)to state[5\(c\)](https://arxiv.org/html/2606.26399#S3.F5.sf3)but failed from action[5\(d\)](https://arxiv.org/html/2606.26399#S3.F5.sf4)to state[5\(e\)](https://arxiv.org/html/2606.26399#S3.F5.sf5)\)\. Note that canonical pruning is effective on states[5\(a\)](https://arxiv.org/html/2606.26399#S3.F5.sf1)and[5\(c\)](https://arxiv.org/html/2606.26399#S3.F5.sf3)\.

### 3\.4Enhanced Search Strategy

To further maximize the performance of Geometry\-Aware MCTS under a finite computational budget, we adopt and adapt three targeted optimization strategies\. These enhancements focus on*information persistence*,*dynamic exploration adjustment*, and*global result harvesting*, transforming the standard MCTS into a more efficient solver for deterministic combinatorial tasks\.

#### 3\.4\.1Subtree Reuse \(Information Persistence\)

In standard MCTS implementations, the search tree is typically discarded after each decision step, resetting the agent’s knowledge to zero\. Given that our MDP transitions are deterministic, discarding the tree wastes significant computational effort\. We therefore adopt aSubtree Reusestrategy\(Silveret al\.,[2016](https://arxiv.org/html/2606.26399#bib.bib16)\)\. Upon executing an actionaaand transitioning from the current rootssto a child states′s^\{\\prime\}, we do not re\-initialize the tree\. Instead, we promote the child node corresponding tos′s^\{\\prime\}to become the new root for the subsequent search phase\. To maintain memory efficiency, the previous root and its unselected branches are detached and garbage\-collected\. This strategy ensures that the new search phase begins with a “warm start,” whereNexisting​\(s′\)\>0N\_\{\\text\{existing\}\}\(s^\{\\prime\}\)\>0, allowing the agent to immediately focus on deeper lookaheads rather than re\-exploring the immediate action space\.

#### 3\.4\.2Time\-Dependent Exploration Decay

A critical challenge in the extremal problems we study is the*small suboptimality gap*: the value difference between optimal and near\-optimal actions is often extremely small\. Even with exponential reward shaping, the exploration termC​ln⁡N​\(s\)/N​\(s,a\)C\\sqrt\{\\ln N\(s\)/N\(s,a\)\}in the UCB1 formula \([1](https://arxiv.org/html/2606.26399#S3.E1)\) can dominate the exploitation termQ​\(s,a\)/N​\(s,a\)Q\(s,a\)/N\(s,a\), hindering convergence\. To address this, we implement a time\-dependent exploration decay mechanism\(Ruijlet al\.,[2013](https://arxiv.org/html/2606.26399#bib.bib35)\), modulating the exploration constant via a decay functionλ​\(r\)\\lambda\(r\):C​\(t\)=Cbase⋅λ​\(r\),where​λ​\(r\)=1−0\.85​r\.C\(t\)=C\_\{\\text\{base\}\}\\cdot\\lambda\(r\),\\text\{ where \}\\lambda\(r\)=1\-0\.85\\sqrt\{r\}\.Here,r=i/Ntotal∈\[0,1\]r=i/N\_\{\\text\{total\}\}\\in\[0,1\]represents the progress ratio of the search, whereiiis the current iteration index andNtotalN\_\{\\text\{total\}\}is the allocated search budget\. A critical design choice is formulatingrrunder the Subtree Reuse paradigm\. Ifrris computed relative only to the newly allocated budget for the current step,C​\(t\)C\(t\)resets to its maximum at every transition, destroying accumulated confidence\. Instead, we incorporate the inherited visit countNexisting​\(s′\)N\_\{\\text\{existing\}\}\(s^\{\\prime\}\)from the previous tree as valid prior exploration:

r=Nexisting​\(s′\)\+iNtotal\.r=\\frac\{N\_\{\\text\{existing\}\}\(s^\{\\prime\}\)\+i\}\{N\_\{\\text\{total\}\}\}\.\(8\)This formulation ensures the exploration factorC​\(t\)C\(t\)remains continuous and monotonically decreasing across sequential decisions\. As the effective visit count approachesNtotalN\_\{\\text\{total\}\}, the decay aggressively reduces exploration noise, committing the policy to the empirically superior branch\.

#### 3\.4\.3Anytime Optimal State Tracking

The standard output of MCTS is a policy derived from the visit counts of the root node, intended to maximize the expected future reward\. However, in extremal problems, our objective is to identify the*global maximum*configuration \(e\.g\., the largest possible set\), regardless of whether it lies on the most probable path\. To address this, we augment MCTS with anAnytime Optimal State Trackingmechanism\. During the simulation phase, whenever the rollout policy reaches a terminal statesTs\_\{T\}, we evaluate its rewardR​\(sT,n\)R\(s\_\{T\},n\)\. IfR​\(sT,n\)R\(s\_\{T\},n\)exceeds the best reward found so far globally, we record the statesTs\_\{T\}, independent of the tree search statistics\. This decoupling ensures that valid “outlier” solutions found via serendipity in deep rollouts are never lost, effectively treating the simulation phase as a global random sampler running in parallel with the policy optimization\.

## 4Experiments and Results

### 4\.1Experimental Setup

We conducted all experiments on a High Performance Computing Cluster using a single CPU core and a strict 6GB memory limit per trial\. We chose this limit to show the memory efficiency of our framework\. Time limits are set to 14 days for Max\-N3IL and 7 days for the other problems we tested\. Comprehensive hardware details, hyperparameter configurations, and ablation constraints are provided in Appendix[C](https://arxiv.org/html/2606.26399#A3)and[D](https://arxiv.org/html/2606.26399#A4)\.

Our baseline strategy was a single search trial per configuration to maximize the exploration of large grid sizes under our strict compute budget\. However, due to opportunistic job scheduling on the shared cluster, a subset of configurations received multiple evaluations\. Because our objective is to establish theoretical existence bounds rather than expected average returns, we report the absolute best \(global maximum or minimum\) valid configuration discovered across all available trials for any givennn\.

### 4\.2Main Results

Table 1:Comparison of our MCTS results against best\-known theoretical and computational bounds\. See Appendix[A](https://arxiv.org/html/2606.26399#A1)and[E](https://arxiv.org/html/2606.26399#A5)for detailed previous best known results\.Note:“Ours” reports the empirical performance trend observed or specific improvements found within the tested range\. All baseline comparisons are based on the records available as of June 23, 2026\.The proposed framework establishes new best\-known computational bounds for five out of the six problems we evaluated \([table˜1](https://arxiv.org/html/2606.26399#S4.T1)\)\.[Figure˜6](https://arxiv.org/html/2606.26399#S4.F6)illustrates the detailed scaling behaviors \(optimality ratio\|sT\|/n\|s\_\{T\}\|/n\)\. While minor local variance exists due to MCTS stochasticity and opportunistic multi\-trial sampling, the macroscopic trends robustly support our empirical bounds\. The framework demonstrates exceptional search efficiency and generalizability across diverse constraints:

Collinearity Constraints \([figs\.˜6\(a\)](https://arxiv.org/html/2606.26399#S4.F6.sf1)and[6\(d\)](https://arxiv.org/html/2606.26399#S4.F6.sf4)\):Our MCTS framework finds sets of points of size roughly1\.8​n1\.8nfor eachnnsatisfying82≤n≤11982\\leq n\\leq 119\. This sits squarely between the algebraic lower bound of size approximately1\.5​n1\.5nand the upper bound of size2​n2n\. This demonstrates the success of this method on grids that were previously inaccessible\.

For the Max\-N4IL problem, for eachnnsatisfying3≤n≤1003\\leq n\\leq 100we were able to find optimal configurations with3​n3npoints with no44collinear points, outperforming the previous1\.973​n1\.973nlower bound\. It would be interesting to see if we can produce these kinds of configurations for even larger grids\.

Coverage Objectives \([figs\.˜6\(b\)](https://arxiv.org/html/2606.26399#S4.F6.sf2)and[6\(c\)](https://arxiv.org/html/2606.26399#S4.F6.sf3)\):For minimization tasks, our MCTS framework was most successful in finding configurations with fullD4D\_\{4\}\-symmetry\. We find complete sets of size approximately0\.95​n0\.95nfor eachnnin the range37≤n≤9637\\leq n\\leq 96\. Since𝒟n≤ℐn\\mathscr\{D\}\_\{n\}\\leq\\mathscr\{I\}\_\{n\}for eachnn, this provides a new upper bound for both Min\-Complete and Min\-Dom in this range\. For somenn\(e\.g\.,n=83n=83\), we find a geometric dominating set of size smaller than the smallest complete set that we found\.

Non\-linear & Distance Constraints \([figs\.˜6\(e\)](https://arxiv.org/html/2606.26399#S4.F6.sf5)and[6\(f\)](https://arxiv.org/html/2606.26399#S4.F6.sf6)\):We find configurations of approximately1\.8​n1\.8npoints with no44points on a circle of finite radius for eachn≤39n\\leq 39\. For Max\-No\-Isosceles, the framework finds configurations of size approximately1\.4​n1\.4n\. Highly specialized constructions using recent AI tools find larger sets for specific grid sizes \(e\.g\.,n∈\{64,100\}n\\in\\\{64,100\\\}\)\(Georgievet al\.,[2025](https://arxiv.org/html/2606.26399#bib.bib31)\), and could likely be applied to a whole range of values ofnn\. We still include the performance of our MCTS framework to demonstrate that it remains competitive with these more specialized approaches without requiring domain\-specific heuristic redesign\. This establishes a boundary of our current search capabilities\.

![Refer to caption](https://arxiv.org/html/2606.26399v1/x2.png)\(a\)Max\-N3IL
![Refer to caption](https://arxiv.org/html/2606.26399v1/x3.png)\(b\)Min\-Complete
![Refer to caption](https://arxiv.org/html/2606.26399v1/x4.png)\(c\)Min\-Dom
![Refer to caption](https://arxiv.org/html/2606.26399v1/x5.png)\(d\)Max\-N4IL
![Refer to caption](https://arxiv.org/html/2606.26399v1/x6.png)\(e\)Max\-No\-Isosceles
![Refer to caption](https://arxiv.org/html/2606.26399v1/x7.png)\(f\)Max\-No\-4\-on\-Circle

Figure 6:Scaling behaviors \(optimality ratio\|sT\|/n\|s\_\{T\}\|/n\) across six constraints\. Our results \(red\) are compared against previous best\-known bounds\. The framework successfully pushes empirical lower bounds upwards \([6\(a\)](https://arxiv.org/html/2606.26399#S4.F6.sf1),[6\(d\)](https://arxiv.org/html/2606.26399#S4.F6.sf4),[6\(f\)](https://arxiv.org/html/2606.26399#S4.F6.sf6)\) and tightens upper bounds downwards \([6\(b\)](https://arxiv.org/html/2606.26399#S4.F6.sf2),[6\(c\)](https://arxiv.org/html/2606.26399#S4.F6.sf3)\), demonstrating strong generalization across these kinds of geometric problems\.
### 4\.3Effectiveness of Strategies

The effectiveness of symmetric batch transitions heavily depends on aligning the chosen subgroupGGwith the geometric constraints of the problem\. These geometric priors can be acquired through empirical exploration or existing mathematical literature\.

Symmetric Batch Transitions\.For the Max\-N3IL problem, empirical exploration \([fig\.˜7\(a\)](https://arxiv.org/html/2606.26399#S4.F7.sf1)\) shows that the rotational subgroupC4C\_\{4\}yields the highest optimality ratios overall\. Conversely, axis reflections \(V4V\_\{4\}\) perform poorly, likely because they tend to rapidly remove whole rows and columns from𝒜feas\\mathcal\{A\}\_\{\\text\{feas\}\}\. However, this exact rapid\-elimination mechanism becomes a powerful advantage for minimization tasks\. For the Min\-Complete problem \([fig\.˜7\(b\)](https://arxiv.org/html/2606.26399#S4.F7.sf2)\), the full symmetry groupD4D\_\{4\}leverages these reflections to rapidly cover the grid, successfully driving the search toward sparser dominating sets\. Furthermore, the literature confirms that known optimal N3IL configurations often exhibitC4C\_\{4\}or diagonal symmetries\(Flammenkamp,[1992](https://arxiv.org/html/2606.26399#bib.bib5);[1998](https://arxiv.org/html/2606.26399#bib.bib6);[2026](https://arxiv.org/html/2606.26399#bib.bib13)\), motivating our specific subgroup selections for large grids \(n≥96n\\geq 96\)\. If symmetric placements prove detrimental to a specific problem, the framework adapts to a single\-action search\.

Anytime Optimal Tracking\.[Figure˜7\(c\)](https://arxiv.org/html/2606.26399#S4.F7.sf3)demonstrates the value of asynchronously recording the global best state during random simulations\. This tracking permanently harvests valid “outlier” solutions that might otherwise be discarded when trees are reset or pruned, ensuring the final output is strictly no worse than terminal node evaluations\.

We analyze the incremental contribution of each algorithmic component in our ablation study \(Section[4\.4](https://arxiv.org/html/2606.26399#S4.SS4)\)\.

![Refer to caption](https://arxiv.org/html/2606.26399v1/x8.png)\(a\)Max\-N3IL Batch Transitions
![Refer to caption](https://arxiv.org/html/2606.26399v1/x9.png)\(b\)Min\-Complete Batch Transitions
![Refer to caption](https://arxiv.org/html/2606.26399v1/x10.png)\(c\)Anytime Optimal Tracking

Figure 7:Effectiveness of algorithmic strategies\. The optimal symmetric subgroup is heavily problem\-dependent:C4C\_\{4\}excels for Max\-N3IL \([7\(a\)](https://arxiv.org/html/2606.26399#S4.F7.sf1)\) whileD4D\_\{4\}excels for Min\-Complete by rapidly covering the grid \([7\(b\)](https://arxiv.org/html/2606.26399#S4.F7.sf2)\)\. Asynchronous tracking \([7\(c\)](https://arxiv.org/html/2606.26399#S4.F7.sf3)\) effectively captures outlier configurations discovered deep in rollouts\.
### 4\.4Ablation Study

![Refer to caption](https://arxiv.org/html/2606.26399v1/x11.png)Figure 8:Ablation Study: Comparison of average terminal points \(left\) and average runtime \(right\) across different algorithm variants and grid sizes\. Bar heights represent the mean value overN=20N=20independent random seeds, and error bars indicate the standard deviation \(±1\\pm 1std\)\. Statistical significance is evaluated incrementally against the immediately preceding variant using a one\-sided Welch’s t\-test \(\*p<0\.05p<0\.05, \*\*p<0\.01p<0\.01, \*\*\*p<0\.001p<0\.001\)\. Specifically, the alternative hypothesis for terminal points is that the current variant yields a strictly greater mean \(μcurr\>μprev\\mu\_\{\\text\{curr\}\}\>\\mu\_\{\\text\{prev\}\}\), whereas for runtime, the alternative hypothesis is a strictly lower mean \(μcurr<μprev\\mu\_\{\\text\{curr\}\}<\\mu\_\{\\text\{prev\}\}\)\. Note that runtime is plotted on a logarithmic scale\. See[table˜7](https://arxiv.org/html/2606.26399#A6.T7)for detailed numerical results\.The different components of our framework exhibit hierarchical dependencies; for instance,Canonical Pruningrelies on the structure of theFeasible Action Space\(𝒜feas\\mathcal\{A\}\_\{\\text\{feas\}\}\), andSymmetric Batch Transitionsbuild directly upon this pruning mechanism\. Therefore, we start with the baseline MCTS and cumulatively add components to evaluate the marginal performance gain of each layer\.

As shown in[fig\.˜8](https://arxiv.org/html/2606.26399#S4.F8)and[table˜7](https://arxiv.org/html/2606.26399#A6.T7), our final variant achieves superior performance in producing successful configurations and also demonstrates highly optimized computational efficiency\. While minor runtime fluctuations exist—likely attributable to the stochastic nature of the shared cluster environment—the overall improvements remain robust across all tested grid sizes\.

The first major performance leap occurs with the strict enforcement of the feasible action space \(M1\)\. Compared to the baseline \(M0\), which operates on the naive action space𝒜naive\\mathcal\{A\}\_\{\\text\{naive\}\}and frequently terminates early due to invalid random selections, M1 exhibits a significant improvement in average terminal number of points \(p<0\.001p<0\.001across all grid sizes\) by ensuring the deep exploration of valid configurations\. However, computing𝒜feas\\mathcal\{A\}\_\{\\text\{feas\}\}from scratch at each node severely degrades runtime\. This bottleneck is resolved by the incremental update mechanism \(M2\), which dramatically improves runtime compared to M1 \(p<0\.001p<0\.001\) while incurring no statistically significant performance loss \(p≥0\.05p\\geq 0\.05\)\. This efficiency gain scales exceptionally well for larger grids, such asn∈\{50,70\}n\\in\\\{50,70\\\}, empirically validating the theoreticalO​\(n2\)O\(n^\{2\}\)update complexity\.

The subsequent integration of canonical pruning \(M3\) yields no statistically significant improvement in either performance or efficiency on its own\. Without forced symmetric transitions, symmetric states become increasingly sparse at deeper search levels\. Consequently, the computational overhead of computing the stabilizer at each step outweighs the minimal branching reduction achieved\. This limitation is directly overcome by the introduction ofC4C\_\{4\}symmetric batch transitions \(M4\), which creates a breakthrough in both metrics\. By actively maintaining structural symmetry deeper within the search tree, the batch mechanism unlocks the potential of canonical pruning\. As a result, M4 establishes new empirical peaks for terminal points \(p<0\.001p<0\.001\) and drastically reduces runtime compared to the M1–M3 variants\.

Finally, we evaluate the utility\-focused enhancements\. Although the anytime optimal tracking \(M5\) shows no statistically significant shift in average performance within this specific randomized ablation study, it serves as a critical, zero\-cost fail\-safe\. It ensures that the globally best configuration discovered during any rollout is permanently recorded, independent of the final MCTS policy convergence\. The framework is finalized with the subtree reuse strategy \(Ours\), which significantly improves overall efficiency on larger grids \(p<0\.001p<0\.001forn∈\{50,70\}n\\in\\\{50,70\\\}\) with no statistically significant loss in terminal points\. This confirms that persisting tree statistics across deterministic transitions effectively reduces redundant explorations, demonstrating the scalability of the framework for a wide array of extremal problems in combinatorial geometry\.

## 5Conclusions and Limitations

In this work, we presented a Geometry\-Aware Monte Carlo Tree Search framework tailored for extremal problems with hard geometric constraints\. By integratingIncremental Feasible Action Spacemaintenance and leveraging symmetries throughCanonical PruningandSymmetric Batch Transitions, we help to address the “validity cliff” and combinatorial explosion that hinder generic solvers\.

Our empirical results demonstrate the effectiveness of this approach\. The MCTS framework we propose achieves a significant improvement in performance over baseline implementations\. Our ablation study shows how the various aspects of this approach lead to improved efficiency\. We establish new best\-known bounds for five of the six problems within the grid sizes we evaluated\. This demonstrates the capability of our method to generalize and scale, suggesting that it can serve as a versatile tool for constructions in discrete geometry\.

Despite the combinatorial explosion inherent to these problems, our framework demonstrates remarkable scalability\. All reported main results, including the exploration of grids up ton=119n=119for Max\-N3IL, were achieved using only asingle CPU core with a strict 6GB memory limitwithin a two\-week cutoff\. This confirms that our geometry\-aware pruning effectively mitigates the curse of dimensionality for a significant range ofnn\.

Our method provides empirical constructions rather than closed\-form bounds\. The configurations that we produce are not necessarily optimal, but still provide valuable information for grids of larger sizes that could be used to guide future theoretical work\. Future work will leverage parallelization and GPU acceleration\(Klęsk,[2025](https://arxiv.org/html/2606.26399#bib.bib32)\)to explore even larger spaces\. Integrating neural networks for value/policy guidance for this geometry\-aware search is a promising direction for future research\.

#### Acknowledgments

We acknowledge support from NSF Grant DMS 2154223\. L\. Zhang was supported by a UCI Undergraduate Research Opportunities Program \(UROP\) Summer Fellowship\.

We thank Jeremy Jiang, Desmond West\-Hedlund, Miguel Angel Estrella\-Ibarra, and Erin Hanrahan, for stimulating discussions\. We also thank Hengrui Cai, David Eppstein, and Wenbo Zhang for valuable feedback and suggestions\. Computational resources \(mentioned in Section[4\.1](https://arxiv.org/html/2606.26399#S4.SS1)\) were provided by the High Performance Community Computing Cluster \(HPC3\) at UCI111[https://rcic\.uci\.edu/hpc3/hpc3\.html](https://rcic.uci.edu/hpc3/hpc3.html)\. We thank Ge Gao and the HPC3 Support Team for technical support\.

## References

- O\. Aichholzer, D\. Eppstein, and E\. Hainzl \(2023\)Geometric dominating sets \- a minimum version of the No\-Three\-In\-Line Problem\.Computational Geometry108,pp\. 101913\.External Links:ISSN 0925\-7721,[Document](https://dx.doi.org/10.1016/j.comgeo.2022.101913)Cited by:[§A\.1\.2](https://arxiv.org/html/2606.26399#A1.SS1.SSS2.p1.14),[§A\.1\.2](https://arxiv.org/html/2606.26399#A1.SS1.SSS2.p3.6),[Appendix E](https://arxiv.org/html/2606.26399#A5.SS0.SSS0.Px2.p1.2),[§2\.2](https://arxiv.org/html/2606.26399#S2.SS2.SSS0.Px1.p1.6),[§2\.2](https://arxiv.org/html/2606.26399#S2.SS2.SSS0.Px2.p1.11),[§3\.3\.2](https://arxiv.org/html/2606.26399#S3.SS3.SSS2.p1.1),[Table 1](https://arxiv.org/html/2606.26399#S4.T1.7.7.7.1)\.
- T\. F\. Bloom and O\. Sisask \(2023\)An improvement to the Kelley\-Meka bounds on three\-term arithmetic progressions\.External Links:2309\.02353,[Link](https://arxiv.org/abs/2309.02353)Cited by:[§A\.1\.5](https://arxiv.org/html/2606.26399#A1.SS1.SSS5.p2.5)\.
- C\. B\. Browne, E\. Powley, D\. Whitehouse, S\. M\. Lucas, P\. I\. Cowling, P\. Rohlfshagen, S\. Tavener, D\. Perez, S\. Samothrakis, and S\. Colton \(2012\)A survey of Monte Carlo tree search methods\.IEEE Transactions on Computational Intelligence and AI in Games4\(1\),pp\. 1–43\.External Links:[Document](https://dx.doi.org/10.1109/TCIAIG.2012.2186810)Cited by:[§A\.2](https://arxiv.org/html/2606.26399#A1.SS2.p1.1)\.
- T\. Cazenave \(2025\)Monte Carlo permutation search\.External Links:2510\.06381,[Link](https://arxiv.org/abs/2510.06381)Cited by:[§A\.2](https://arxiv.org/html/2606.26399#A1.SS2.p3.1)\.
- F\. Charton, J\. S\. Ellenberg, A\. Z\. Wagner, and G\. Williamson \(2024\)PatternBoost: Constructions in mathematics with a little help from AI\.External Links:2411\.00566,[Link](https://arxiv.org/abs/2411.00566)Cited by:[§A\.1\.5](https://arxiv.org/html/2606.26399#A1.SS1.SSS5.p1.3),[§1](https://arxiv.org/html/2606.26399#S1.p5.4),[Table 1](https://arxiv.org/html/2606.26399#S4.T1.16.16.16.1)\.
- R\. Coulom \(2007\)Efficient selectivity and backup operators in Monte\-Carlo tree search\.InComputers and Games,H\. J\. van den Herik, P\. Ciancarini, and H\. H\. L\. M\. \(\. Donkers \(Eds\.\),Berlin, Heidelberg,pp\. 72–83\.External Links:ISBN 978\-3\-540\-75538\-8Cited by:[§A\.2](https://arxiv.org/html/2606.26399#A1.SS2.p1.1),[§1](https://arxiv.org/html/2606.26399#S1.SS0.SSS0.Px1.p1.4)\.
- Z\. Dong and Z\. Xu \(2025\)Large grid subsets without many cospherical points\.External Links:2506\.18113,[Link](https://arxiv.org/abs/2506.18113)Cited by:[§A\.1\.4](https://arxiv.org/html/2606.26399#A1.SS1.SSS4.p1.2),[item 2](https://arxiv.org/html/2606.26399#S2.I1.i2.p1.2),[Table 1](https://arxiv.org/html/2606.26399#S4.T1.22.22.22.1)\.
- H\. E\. Dudeney \(1917\)Amusements in mathematics\.Nelson,Edinburgh\.Cited by:[§1](https://arxiv.org/html/2606.26399#S1.p1.5),[§2\.2](https://arxiv.org/html/2606.26399#S2.SS2.SSS0.Px1.p1.6)\.
- A\. Flammenkamp \(1992\)Progress in the no\-three\-in\-line\-problem\.Journal of Combinatorial Theory, Series A60\(2\),pp\. 305–311\.External Links:ISSN 0097\-3165,[Document](https://dx.doi.org/10.1016/0097-3165%2892%2990012-J)Cited by:[§1](https://arxiv.org/html/2606.26399#S1.p2.23),[§3\.3\.2](https://arxiv.org/html/2606.26399#S3.SS3.SSS2.p1.1),[§4\.3](https://arxiv.org/html/2606.26399#S4.SS3.p2.6)\.
- A\. Flammenkamp \(1998\)Progress in the No\-Three\-in\-Line problem, II\.Journal of Combinatorial Theory, Series A81\(1\),pp\. 108–113\.External Links:ISSN 0097\-3165,[Document](https://dx.doi.org/10.1006/jcta.1997.2829)Cited by:[§1](https://arxiv.org/html/2606.26399#S1.p2.23),[§3\.3\.2](https://arxiv.org/html/2606.26399#S3.SS3.SSS2.p1.1),[§4\.3](https://arxiv.org/html/2606.26399#S4.SS3.p2.6)\.
- A\. Flammenkamp \(2026\)The No\-Three\-in\-Line problem\.Note:Accessed: 2026\-04\-08External Links:[Link](https://wwwhomes.uni-bielefeld.de/achim/no3in/readme.html)Cited by:[Appendix E](https://arxiv.org/html/2606.26399#A5.SS0.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2606.26399#S1.p2.23),[§1](https://arxiv.org/html/2606.26399#S1.p4.7),[§3\.3\.2](https://arxiv.org/html/2606.26399#S3.SS3.SSS2.p1.1),[§4\.3](https://arxiv.org/html/2606.26399#S4.SS3.p2.6)\.
- B\. Georgiev, J\. Gómez\-Serrano, T\. Tao, and A\. Z\. Wagner \(2025\)Mathematical exploration and discovery at scale\.External Links:2511\.02864,[Link](https://arxiv.org/abs/2511.02864)Cited by:[§4\.2](https://arxiv.org/html/2606.26399#S4.SS2.p5.6),[Table 1](https://arxiv.org/html/2606.26399#S4.T1.21.21.21.4)\.
- R\. K\. Guy and P\. A\. Kelly \(1968\)The No\-Three\-In\-Line problem\.Canadian Mathematical Bulletin11\(4\),pp\. 527–531\.External Links:[Document](https://dx.doi.org/10.4153/CMB-1968-062-3)Cited by:[Appendix B](https://arxiv.org/html/2606.26399#A2.SS0.SSS0.Px4.p1.5),[§1](https://arxiv.org/html/2606.26399#S1.p2.23)\.
- R\. R\. Hall, T\. H\. Jackson, A\. Sudbery, and K\. Wild \(1975\)Some advances in the no\-three\-in\-line problem\.Journal of Combinatorial Theory, Series A18\(3\),pp\. 336–341\.External Links:ISSN 0097\-3165,[Document](https://dx.doi.org/10.1016/0097-3165%2875%2990043-6)Cited by:[§A\.1\.1](https://arxiv.org/html/2606.26399#A1.SS1.SSS1.p1.7),[§1](https://arxiv.org/html/2606.26399#S1.p2.23),[Table 1](https://arxiv.org/html/2606.26399#S4.T1.2.2.2.1)\.
- J\. Jooken, P\. Leyman, T\. Wauters, and P\. De Causmaecker \(2023\)Exploring search space trees using an adapted version of Monte Carlo tree search for combinatorial optimization problems\.Computers & Operations Research150,pp\. 106070\.External Links:ISSN 0305\-0548,[Document](https://dx.doi.org/10.1016/j.cor.2022.106070)Cited by:[§A\.2](https://arxiv.org/html/2606.26399#A1.SS2.p2.3)\.
- P\. Klęsk \(2025\)MCTS\-NC: A thorough GPU parallelization of Monte Carlo tree search implemented in Python via numba\.cuda\.SoftwareX30,pp\. 102139\.External Links:ISSN 2352\-7110,[Document](https://dx.doi.org/10.1016/j.softx.2025.102139)Cited by:[§5](https://arxiv.org/html/2606.26399#S5.p4.1)\.
- L\. Kocsis and C\. Szepesvári \(2006\)Bandit based Monte\-Carlo planning\.InMachine Learning: ECML 2006,J\. Fürnkranz, T\. Scheffer, and M\. Spiliopoulou \(Eds\.\),Berlin, Heidelberg,pp\. 282–293\.External Links:ISBN 978\-3\-540\-46056\-5Cited by:[§A\.2](https://arxiv.org/html/2606.26399#A1.SS2.p1.1),[§1](https://arxiv.org/html/2606.26399#S1.SS0.SSS0.Px1.p1.4),[§3\.1](https://arxiv.org/html/2606.26399#S3.SS1.p1.9)\.
- B\. Kovács, Z\. L\. Nagy, and D\. R\. Szabó \(2025\)Randomised algebraic constructions for the no\-\(k\+1\)\(k\+1\)\-in\-line problem\.External Links:2508\.07632,[Link](https://arxiv.org/abs/2508.07632)Cited by:[§A\.1\.3](https://arxiv.org/html/2606.26399#A1.SS1.SSS3.p1.2),[Table 1](https://arxiv.org/html/2606.26399#S4.T1.13.13.13.2)\.
- W\. Li and K\. Ellis \(2024\)Is programming by example solved by LLMs?\.InAdvances in Neural Information Processing Systems,A\. Globerson, L\. Mackey, D\. Belgrave, A\. Fan, U\. Paquet, J\. Tomczak, and C\. Zhang \(Eds\.\),Vol\.37,pp\. 44761–44790\.External Links:[Document](https://dx.doi.org/10.52202/079017-1422)Cited by:[§1](https://arxiv.org/html/2606.26399#S1.p5.4)\.
- Y\. Neuhaus, N\. Flammarion, M\. Hein, and F\. Croce \(2026\)On the out\-of\-distribution generalization of reasoning in multimodal LLMs for simple visual planning tasks\.External Links:2602\.15460,[Link](https://arxiv.org/abs/2602.15460)Cited by:[§1](https://arxiv.org/html/2606.26399#S1.p5.4)\.
- A\. Novikov, N\. Vũ, M\. Eisenberger, E\. Dupont, P\. Huang, A\. Z\. Wagner, S\. Shirobokov, B\. Kozlovskii, F\. J\. R\. Ruiz, A\. Mehrabian, M\. P\. Kumar, A\. See, S\. Chaudhuri, G\. Holland, A\. Davies, S\. Nowozin, P\. Kohli, and M\. Balog \(2025\)AlphaEvolve: A coding agent for scientific and algorithmic discovery\.External Links:2506\.13131,[Link](https://arxiv.org/abs/2506.13131)Cited by:[§1](https://arxiv.org/html/2606.26399#S1.p5.4)\.
- T\. Prellberg \(2026\)Constraint satisfaction programming for the No\-three\-in\-line Problem\.External Links:2602\.07751,[Link](https://arxiv.org/abs/2602.07751)Cited by:[Appendix E](https://arxiv.org/html/2606.26399#A5.SS0.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2606.26399#S1.p2.23),[§1](https://arxiv.org/html/2606.26399#S1.p4.7),[§3\.3\.2](https://arxiv.org/html/2606.26399#S3.SS3.SSS2.p1.1)\.
- R\. Raghavan \(2026\)Improved bounds for 3\-progressions\.External Links:2603\.27045,[Link](https://arxiv.org/abs/2603.27045)Cited by:[§A\.1\.5](https://arxiv.org/html/2606.26399#A1.SS1.SSS5.p2.6)\.
- P\. Ramanathan, T\. Prellberg, M\. Lewis, P\. D\. Joshi, R\. A\. Dandekar, R\. Dandekar, and S\. Panat \(2025\)Three methods, one problem: classical and AI approaches to no\-three\-in\-line\.External Links:2512\.11469,[Link](https://arxiv.org/abs/2512.11469)Cited by:[§1](https://arxiv.org/html/2606.26399#S1.p4.7),[§1](https://arxiv.org/html/2606.26399#S1.p5.4)\.
- B\. Romera\-Paredes, M\. Barekatain, A\. Novikov, M\. Balog, M\. P\. Kumar, E\. Dupont, F\. J\. R\. Ruiz, J\. S\. Ellenberg, P\. Wang, O\. Fawzi, P\. Kohli, and A\. Fawzi \(2024\)Mathematical discoveries from program search with large language models\.Nature625\(7995\),pp\. 468–475\.External Links:[Document](https://dx.doi.org/10.1038/s41586-023-06924-6),ISBN 1476\-4687Cited by:[§1](https://arxiv.org/html/2606.26399#S1.p5.4)\.
- B\. Ruijl, J\. Vermaseren, A\. Plaat, and J\. van den Herik \(2013\)Combining simulated annealing and Monte Carlo tree search for expression simplification\.External Links:1312\.0841,[Link](https://arxiv.org/abs/1312.0841)Cited by:[§A\.2](https://arxiv.org/html/2606.26399#A1.SS2.p4.2),[§3\.4\.2](https://arxiv.org/html/2606.26399#S3.SS4.SSS2.p1.11)\.
- S\. Schiffel \(2010\)Symmetry detection in general game playing\.Proceedings of the AAAI Conference on Artificial Intelligence24\(1\),pp\. 980–985\.External Links:[Document](https://dx.doi.org/10.1609/aaai.v24i1.7649)Cited by:[§A\.2](https://arxiv.org/html/2606.26399#A1.SS2.p3.1)\.
- D\. Silver, A\. Huang, C\. J\. Maddison, A\. Guez, L\. Sifre, G\. van den Driessche, J\. Schrittwieser, I\. Antonoglou, V\. Panneershelvam, M\. Lanctot, S\. Dieleman, D\. Grewe, J\. Nham, N\. Kalchbrenner, I\. Sutskever, T\. Lillicrap, M\. Leach, K\. Kavukcuoglu, T\. Graepel, and D\. Hassabis \(2016\)Mastering the game of Go with deep neural networks and tree search\.Nature529\(7587\),pp\. 484–489\.External Links:[Document](https://dx.doi.org/10.1038/nature16961),ISBN 1476\-4687Cited by:[§A\.2](https://arxiv.org/html/2606.26399#A1.SS2.p1.1),[§3\.4\.1](https://arxiv.org/html/2606.26399#S3.SS4.SSS1.p1.5)\.
- D\. Silver, T\. Hubert, J\. Schrittwieser, I\. Antonoglou, M\. Lai, A\. Guez, M\. Lanctot, L\. Sifre, D\. Kumaran, T\. Graepel, T\. Lillicrap, K\. Simonyan, and D\. Hassabis \(2018\)A general reinforcement learning algorithm that masters chess, shogi, and Go through self\-play\.Science362\(6419\),pp\. 1140–1144\.External Links:[Document](https://dx.doi.org/10.1126/science.aar6404)Cited by:[§A\.2](https://arxiv.org/html/2606.26399#A1.SS2.p1.1)\.
- D\. J\. N\. J\. Soemers, C\. F\. Sironi, T\. Schuster, and M\. H\. M\. Winands \(2016\)Enhancements for real\-time Monte\-Carlo tree search in general video game playing\.In2016 IEEE Conference on Computational Intelligence and Games \(CIG\),pp\. 1–8\.External Links:[Document](https://dx.doi.org/10.1109/CIG.2016.7860448)Cited by:[§3](https://arxiv.org/html/2606.26399#S3.p1.1)\.
- T\. Vodopivec, S\. Samothrakis, and B\. Šter \(2017\)On Monte Carlo tree search and reinforcement learning\.Journal of Artificial Intelligence Research60,pp\. 881–936\.External Links:[Document](https://dx.doi.org/10.1613/jair.5507)Cited by:[§2](https://arxiv.org/html/2606.26399#S2.p1.2)\.
- A\. Z\. Wagner \(2021\)Constructions in combinatorics via neural networks\.External Links:2104\.14516,[Link](https://arxiv.org/abs/2104.14516)Cited by:[§1](https://arxiv.org/html/2606.26399#S1.p4.7)\.
- Y\. Wang, P\. Ji, C\. Yang, K\. Li, M\. Hu, J\. Li, and G\. Sartoretti \(2025\)MCTS\-Judge: Test\-time scaling in LLM\-as\-a\-judge for code correctness evaluation\.External Links:2502\.12468,[Link](https://arxiv.org/abs/2502.12468)Cited by:[§3](https://arxiv.org/html/2606.26399#S3.p1.1)\.
- Z\. Zheng, Z\. Xie, Z\. Wang, and B\. Hooi \(2025\)Monte Carlo tree search for comprehensive exploration in LLM\-based automatic heuristic design\.External Links:2501\.08603,[Link](https://arxiv.org/abs/2501.08603)Cited by:[§1](https://arxiv.org/html/2606.26399#S1.p5.4)\.
- X\. Zhuang, Y\. Yao, P\. Hsu, X\. Wang, and P\. Qi \(2025\)Machine learning and LLM\-boost symbolic regression for predictingℚ\\mathbb\{Q\}\-gonality of modular curves\.In2nd AI for Math Workshop @ ICML 2025,External Links:[Link](https://openreview.net/forum?id=LDcFa3E5vJ)Cited by:[§1](https://arxiv.org/html/2606.26399#S1.p4.7)\.

## Appendix ARelated Works

We categorize existing approaches to the extremal problems into two distinct streams: theoretical mathematical constructions and constrained tree search\.

### A\.1Mathematical Bounds and Constructions

#### A\.1\.1No\-3\-in\-Line

Early work focused on number\-theoretic constructions to establish foundational lower bounds\.Hallet al\.\[[1975](https://arxiv.org/html/2606.26399#bib.bib3)\]utilized points on modular hyperbolas \(x​y≡k\(modp\)xy\\equiv k\\pmod\{p\}\) to achieve the current best asymptotic lower bound of roughly1\.5​n1\.5n\. However, a significant gap remains between this constructive lower bound and the trivial upper bound of2​n2n\. This substantial margin suggests that for finite grid sizes \(e\.g\.,n∈\[50,100\]n\\in\[50,100\]\),M​\(n\)M\(n\)—the maximum number of points in ann×nn\\times ngrid such that no33points are collinear—may be significantly higher than what algebraic constructions can guarantee\. Motivated by this gap, our work employs computational search to explore the solution space within this interval, aiming to empirically push the lower bound upward and reveal larger configurations than the ones that we can produce with algebraic constructions\.

#### A\.1\.2Geometric Dominating Sets and Independent Geometric Dominating Sets

FollowingAichholzeret al\.\[[2023](https://arxiv.org/html/2606.26399#bib.bib27)\], a setS⊆𝒢nS\\subseteq\\mathcal\{G\}\_\{n\}is a*geometric dominating set*if every grid pointppis either inSSor lies on a line determined by two points ofSS; equivalently, everyppis collinear with two \(distinct\) points ofSS\. The minimum size of such a set is the*geometric domination number*𝒟n\\mathscr\{D\}\_\{n\}\. If additionally no three points ofSSare collinear, thenSSis an*independent geometric dominating set*\. Letℐn\\mathscr\{I\}\_\{n\}denote the minimum size of a independent geometric dominating set in ann×nn\\times ngrid\. The authors also establish the first general asymptotic bounds for𝒟n\\mathscr\{D\}\_\{n\}: they prove a lower bound𝒟n=Ω​\(n2/3\)\\mathscr\{D\}\_\{n\}=\\Omega\(n^\{2/3\}\)and give an explicit construction of a geometric dominating set of size2​⌈n/2⌉2\\lceil n/2\\rceil\. These results leave a substantial gap between the best known lower and upper bounds in the grid, motivating both improved constructions and stronger counting/packing arguments\.

We understand much less about the minimum size of an independent geometric dominating set\. It is clear thatℐn≤2​n\\mathscr\{I\}\_\{n\}\\leq 2n, but we do not even know that there exist infinitely manynnfor whichℐn<2​n\\mathscr\{I\}\_\{n\}<2n\.

On the computational side,Aichholzeret al\.\[[2023](https://arxiv.org/html/2606.26399#bib.bib27)\]compute the value ofℐn\\mathscr\{I\}\_\{n\}forn≤12n\\leq 12and give upper bounds fornnsatisfying13≤n≤3013\\leq n\\leq 30andn=36n=36, providing evidence and test cases for conjectures about the true growth ofℐn\\mathscr\{I\}\_\{n\}\.

#### A\.1\.3No\-4\-in\-Line

Letf4​\-coll​\(n\)f\_\{4\\text\{\-coll\}\}\(n\)denote the maximum cardinality of a subset of𝒢n\\mathcal\{G\}\_\{n\}containing no four collinear points\. The best asymptotic bounds currently known, established byKovácset al\.\[[2025](https://arxiv.org/html/2606.26399#bib.bib30)\], are:

1\.973​n≤f4​\-coll​\(n\)≤3​n1\.973\\,n\\leq f\_\{4\\text\{\-coll\}\}\(n\)\\leq 3nfor all sufficiently largenn\. Consequently, while the maximum size is known to scale linearly withnn, we do not even have a conjecture for howf4​\-coll​\(n\)f\_\{4\\text\{\-coll\}\}\(n\)grows withnn\.

#### A\.1\.4No\-4\-on\-a\-Circle

Letfcirc​\(n\)f\_\{\\mathrm\{circ\}\}\(n\)denote the maximum cardinality of a subset of\[n\]2\[n\]^\{2\}containing no four concyclic points\. The tightest asymptotic bounds currently known, established byDong and Xu \[[2025](https://arxiv.org/html/2606.26399#bib.bib29)\], are:

n−o​\(n\)≤fcirc​\(n\)≤52​n−32\.n\-o\(n\)\\leq f\_\{\\mathrm\{circ\}\}\(n\)\\leq\\frac\{5\}\{2\}n\-\\frac\{3\}\{2\}\.Consequently, while the maximum size is guaranteed to grow linearly withnn, we do not even have a conjecture for howfcirc​\(n\)f\_\{\\mathrm\{circ\}\}\(n\)grows withnn\.

#### A\.1\.5No\-Isosceles\-Triangle

Letfiso​\(n\)f\_\{\\mathrm\{iso\}\}\(n\)denote the maximum size of a subset of\[n\]2\[n\]^\{2\}containing no three points that form an isosceles triangle, including degenerate collinear configurations\. The best known lower bound is:

fiso​\(n\)≥c​nlog⁡nf\_\{\\mathrm\{iso\}\}\(n\)\\geq c\\,\\frac\{n\}\{\\sqrt\{\\log n\}\}for some absolute constantc\>0c\>0\[Chartonet al\.,[2024](https://arxiv.org/html/2606.26399#bib.bib21)\]\.

The best known upper bounds for this problem come from bounding the number of points on each horizontal line of the grid: three points at positions\(a,y\)\(a,y\),\(a\+d,y\)\(a\+d,y\),\(a\+2​d,y\)\(a\+2d,y\)on the same horizontal line form a \(degenerate\) isosceles triangle, so the restriction of any isosceles\-free set to a single horizontal line must avoid three\-term arithmetic progressions\. Applying the best known bounds for subsets of\{1,2,…,n\}\\\{1,2,\\ldots,n\\\}containing no three\-term arithmetic progression to each of thennhorizontal lines,Bloom and Sisask \[[2023](https://arxiv.org/html/2606.26399#bib.bib39)\]established

fiso​\(n\)≤exp​\(−O​\(\(log⁡n\)1/9\)\)​n2\.f\_\{\\mathrm\{iso\}\}\(n\)\\leq\\mathrm\{exp\}\(\-O\(\(\\log n\)^\{1/9\}\)\)\\,n^\{2\}\.This was further improved byRaghavan \[[2026](https://arxiv.org/html/2606.26399#bib.bib41)\], giving

fiso​\(n\)≤exp​\(−O​\(\(log⁡n\)1/6​\(log⁡log⁡n\)−1\)\)​n2\.f\_\{\\mathrm\{iso\}\}\(n\)\\leq\\mathrm\{exp\}\(\{\-O\(\(\\log n\)^\{1/6\}\(\\log\\log n\)^\{\-1\}\}\)\)\\,n^\{2\}\.
Like in the problems about sizes of dominating sets, the upper and lower bounds here have different orders of magnitude\.

### A\.2Monte Carlo Tree Search

Monte Carlo Tree Search \(MCTS\) was introduced byCoulom \[[2007](https://arxiv.org/html/2606.26399#bib.bib15)\]as a framework combining selective tree search with random rollout evaluations\. The UCT algorithm ofKocsis and Szepesvári \[[2006](https://arxiv.org/html/2606.26399#bib.bib14)\]provided a principled exploration\-exploitation strategy by treating node selection as a multi\-armed bandit problem, and remains the backbone of most modern MCTS implementations\[Browneet al\.,[2012](https://arxiv.org/html/2606.26399#bib.bib18)\]\. MCTS gained widespread attention through AlphaGo and AlphaZero\[Silveret al\.,[2016](https://arxiv.org/html/2606.26399#bib.bib16),[2018](https://arxiv.org/html/2606.26399#bib.bib17)\], which demonstrated superhuman performance on Go, Chess, and Shogi by coupling MCTS with deep neural networks\. These works also established engineering practices—most notably subtree reuse across decision steps—that we adopt in our framework\. However, neural networks are not included in our current implementation, and we leave the integration of learned value and policy functions to future work\.

Beyond game playing, MCTS has been applied to combinatorial optimization problems such as scheduling and vehicle routing\[Jookenet al\.,[2023](https://arxiv.org/html/2606.26399#bib.bib24)\]\. However, these settings typically feature smooth objective functions and separable constraints, where random rollouts naturally produce valid solutions\. The geometric constraints in this work \(e\.g\., collinearity, concyclicity\) areglobal: a single point placement invalidates anO​\(n\)O\(n\)set of grid cells, and uniform random rollouts over the unrestricted action space collapse with high probability\. This incompatibility motivates our Incremental𝒜feas\\mathcal\{A\}\_\{\\text\{feas\}\}mechanism, which maintains geometric validity throughout the search atO​\(n2\)O\(n^\{2\}\)cost per step\.

Two prior lines of work address symmetry within MCTS\.Schiffel \[[2010](https://arxiv.org/html/2606.26399#bib.bib22)\]exploited symmetry in general game playing \(GGP\) by detecting automorphisms at thegame rule leveland merging statistics of globally equivalent states via a transposition table\.Cazenave \[[2025](https://arxiv.org/html/2606.26399#bib.bib23)\]proposed Monte Carlo Permutation Search, which fuses visit statistics of permutation\-equivalent actions to reduce effective branching\. Our approach differs from both in two respects\. First, rather than detecting global game symmetry or fusing statistics, we dynamically compute thestate\-level stabilizer subgroupStab​\(s\)≤D4\\text\{Stab\}\(s\)\\leq D\_\{4\}at each node and restrict expansion to canonical orbit representatives—a finer\-grained, state\-dependent pruning\. Second, our Symmetric Batch Transitions redefine the MDP transition itself by attempting simultaneous orbit\-wide point placements, a mechanism with no direct counterpart in prior MCTS literature\.

The challenge of tuning the exploration–exploitation balance over a long horizon has been addressed by SA\-UCT\[Ruijlet al\.,[2013](https://arxiv.org/html/2606.26399#bib.bib35)\], which anneals the UCB exploration constant over iterations\. We adopt a similar decay schedule but introduce a refinement for the subtree reuse setting: our progress ratiorrincorporates inherited visit countsNexistingN\_\{\\text\{existing\}\}, ensuring that the exploration schedule remains continuous and monotonically decreasing across decision steps rather than resetting at the start of each move\.

## Appendix BComputational Complexity Analysis

We analyze the time complexity of our Geometry\-Aware MCTS framework, using the Max\-N3IL problem on then×nn\\times ngrid as a representative case\. We first derive the per\-iteration cost, then aggregate over the full search to establish the total complexity, and finally contrast this polynomial bound with the intractability of exact methods\.

##### Per\-Iteration Cost Breakdown\.

Each MCTS iteration consists of four phases\. We analyze their worst\-case costs in terms ofnn:

Selection\.The agent traverses the tree from root to leaf\. Since each level corresponds to a point placement and the trajectory length is bounded by2​n2n, the tree depth isO​\(n\)O\(n\)\. At each internal node, the UCB1 score is evaluated over all expanded children, costingO​\(\|𝒜feas\|\)O\(\|\\mathcal\{A\}\_\{\\text\{feas\}\}\|\)where\|𝒜feas\|\|\\mathcal\{A\}\_\{\\text\{feas\}\}\|is equal to the local branching factor\. In the worst case\|𝒜feas\|=O​\(n2\)\|\\mathcal\{A\}\_\{\\text\{feas\}\}\|=O\(n^\{2\}\), but in practice the feasible action space shrinks rapidly with depth \(cf\. Section[3\.2](https://arxiv.org/html/2606.26399#S3.SS2)\)\. The total selection cost isO​\(n\)⋅O​\(\|𝒜feas\|\)O\(n\)\\cdot O\(\|\\mathcal\{A\}\_\{\\text\{feas\}\}\|\)\.

Expansion\.A single child node is created\. The dominant cost is the incremental update of the feasible action space via ray casting \(Section[3\.2](https://arxiv.org/html/2606.26399#S3.SS2)\): the new point forms lines with each of the\|s\|≤2​n\|s\|\\leq 2nexisting points, and each line is traced acrossO​\(n\)O\(n\)grid cells\. This yields an expansion cost ofO​\(n2\)O\(n^\{2\}\)per node\.

Simulation \(Rollout\)\.Starting from the expanded node, the agent performs a random rollout until the terminal condition𝒜feas=∅\\mathcal\{A\}\_\{\\text\{feas\}\}=\\emptysetis reached\. Each rollout step selects a random feasible action and incrementally updates𝒜feas\\mathcal\{A\}\_\{\\text\{feas\}\}at a cost ofO​\(n2\)O\(n^\{2\}\)\. Since at most2​n2npoints can be placed in total, the rollout traverses at mostO​\(n\)O\(n\)steps\. The simulation cost is thereforeO​\(n\)⋅O​\(n2\)=O​\(n3\)O\(n\)\\cdot O\(n^\{2\}\)=O\(n^\{3\}\)\.

Backpropagation\.The reward is propagated from the leaf back to the root\. Each update isO​\(1\)O\(1\), and the path length isO​\(n\)O\(n\), giving a total cost ofO​\(n\)O\(n\)\.

The simulation phase dominates, yielding aper\-iteration cost ofO​\(n3\)O\(n^\{3\}\)\.

##### Total Complexity\.

The full algorithm proceeds through two nested loops\. Theouter loopexecutes the sequential MDP: at each decision step, MCTS selects and commits to an action, advancing the trajectory by one point\. Since the trajectory length is at most2​n2n, the outer loop runs forO​\(n\)O\(n\)steps\. Theinner loopperforms MCTS search at each decision step, executingNiter=O​\(n2\)N\_\{\\text\{iter\}\}=O\(n^\{2\}\)iterations \(we setNiter=O​\(n2\)N\_\{\\text\{iter\}\}=O\(n^\{2\}\)in all experiments\)\. Combining with the per\-iteration cost:

Ttotal=O​\(n\)⏟trajectory×O​\(n2\)⏟iterations per step×O​\(n3\)⏟cost per iteration=O​\(n6\)\.T\_\{\\text\{total\}\}=\\underbrace\{O\(n\)\}\_\{\\text\{trajectory\}\}\\times\\underbrace\{O\(n^\{2\}\)\}\_\{\\text\{iterations per step\}\}\\times\\underbrace\{O\(n^\{3\}\)\}\_\{\\text\{cost per iteration\}\}=O\(n^\{6\}\)\.\(9\)
The total time complexity of our framework is thereforepolynomialin the grid sizenn\.

##### Contrast with Exact Methods\.

The polynomial complexity of our approach stands in sharp contrast to the cost of exact enumeration\. An exhaustive search must, in principle, examine all candidate subsets of then2n^\{2\}grid points up to the trivial upper bound of2​n2n\. The size of this search space is

∑k=12​n\(n2k\),\\sum\_\{k=1\}^\{2n\}\\binom\{n^\{2\}\}\{k\},\(10\)which grows super\-exponentially innn\. Therefore, exact methods are severely limited for large grid sizes\.

##### The Tractability–Optimality Trade\-off\.

Our framework does not guarantee global optimality; it is a heuristic search that trades optimality guarantees for polynomial\-time tractability\. However, this trade\-off is precisely what enables the exploration of grid sizes\(n\>68\)\(n\>68\)that up to this point have been too large for exact computation\. As demonstrated in Section[3](https://arxiv.org/html/2606.26399#S3), the components of our geometry\-aware framework—incremental𝒜feas\\mathcal\{A\}\_\{\\text\{feas\}\}maintenance, canonical pruning, and symmetric batch transitions—ensure that this polynomial budget is spent efficiently, concentrating search effort on the most promising regions of the combinatorial landscape\. The empirical results \(Section[4](https://arxiv.org/html/2606.26399#S4)\) confirm that this approach yields configurations that significantly exceed the best\-known constructive lower bound of≈1\.5​n\\approx 1\.5nand closely approach the conjectured density of≈1\.814​n\\approx 1\.814n\[Guy and Kelly,[1968](https://arxiv.org/html/2606.26399#bib.bib4)\], suggesting thatO​\(n6\)O\(n^\{6\}\)may be capable of identifying structures that approach the current conjectured bounds\.

##### Generality Across Problem Variants\.

TheO​\(n3\)O\(n^\{3\}\)per\-iteration bottleneck arises from the incremental maintenance of𝒜feas\\mathcal\{A\}\_\{\\text\{feas\}\}during simulation, which is specific to the geometric invariantΦ\\Phi\. For other problem variants \(e\.g\., No\-Four\-in\-Line, No\-Four\-on\-a\-Circle\), the per\-step update cost may differ depending on the constraint structure, but the overall algorithmic skeleton—and its polynomial\-time guarantee—remains unchanged\.

## Appendix CDetailed Experimental Configurations

We list the detailed hyperparameters used in our experiments to ensure reproducibility\. Table[2](https://arxiv.org/html/2606.26399#A3.T2)summarizes the configurations for the MCTS algorithm\. The UCT algorithm specified in Section[3\.4\.2](https://arxiv.org/html/2606.26399#S3.SS4.SSS2)was utilized for all experiments\.

### C\.1Reward Functions

For every extremal problem with the goal of maximizing\|sT\|\|s\_\{T\}\|and minimizing\|sT\|\|s\_\{T\}\|, we use these two reward functions respectively:

R​\(sT,n\)=exp⁡\(2​\|sT\|−nn\)andR​\(sT,n\)=exp⁡\(−2​\|sT\|−nn\)\.R\(s\_\{T\},n\)=\\exp\{\\left\(\{2\\frac\{\|\{s\_\{T\}\}\|\-n\}\{n\}\}\\right\)\}\\quad\\text\{and\}\\quad R\(s\_\{T\},n\)=\\exp\{\\left\(\{\-2\\frac\{\|\{s\_\{T\}\}\|\-n\}\{n\}\}\\right\)\}\.\(11\)The design of the reward function is an empirical choice aimed at amplifying signal when the optimality gap is small\. Optimizing the reward shaping is orthogonal to the main contribution of this work\.

### C\.2Hyperparameter Settings for Main Experiments

We set these hyperparameters and configurations based on complexity, best\-known geometric prior, and heuristics for each problem \(see[Table˜2](https://arxiv.org/html/2606.26399#A3.T2)\)\.

Table 2:Detailed hyperparameter settings and algorithmic configurations across problems\.HyperparametersMax IterationsBatch TransitionMax Depth forExplorationSymbolNiterN\_\{\\text\{iter\}\}GGCanonical PruningConstantCCMax\-N3IL\(3≤n≤953\\leq n\\leq 95\)100​n2100n^\{2\}1 trial of each symmetry2​n2n1\.411\.41Max\-N3IL\(96≤n≤11996\\leq n\\leq 119\)25​n225n^\{2\}1 trial each inC4C\_\{4\}andV4V\_\{4\}\(a\)Min\-Complete100​n2100n^\{2\}1 trial of each symmetryMin\-Dom100​n2100n^\{2\}1 trial of each symmetryMax\-N4IL10​n210n^\{2\}&25​n225n^\{2\}\(b\)C4C\_\{4\}3​n3nMax\-No\-Isosceles100​n2100n^\{2\}None22Max\-No\-4\-on\-Circle25​n225n^\{2\}None\(a\)V4V\_\{4\}here specifically denotes diagonal and anti\-diagonal reflections\.\(b\)We ran 1 trial for each value of max iteration\.[Figure˜6\(d\)](https://arxiv.org/html/2606.26399#S4.F6.sf4)shows the max number of points found for eachnn\.
### C\.3Ablation Study Configurations

The ablation study was conducted on the Max\-N3IL problem\. Table[3](https://arxiv.org/html/2606.26399#A3.T3)details the algorithmic configurations for each variant evaluated in the incremental ablation study\.

Table 3:Algorithmic configurations for each variant in the incremental ablation study\. “Max Depth” indicates the maximum search depth up to which canonical pruning is applied\.2​n2nrepresents full\-depth pruning, as the maximum possible number of points is bounded by2​n2nfor Max\-N3IL\. “Opt\. Tracking” represents anytime optimal tracking\.##### Other Settings for Ablation Study:

The computational budget and evaluation metrics were strictly controlled across all variants\. The experiments were conducted on grid sizesn∈\{30,40,50,70\}n\\in\\\{30,40,50,70\\\}\. For each algorithmic variant and grid size, we evaluated the performance over 20 independent trials, initialized with random seeds0through1919\. The search budget \(Ni​t​e​rN\_\{iter\}\) was uniformly set to10​n210n^\{2\}iterations per decision step\.

## Appendix DTechnical Details

Memory Efficiency and State Space Complexity:As stated in the main text, a strict 6GB memory limit was intentionally imposed across all trials to rigorously test the memory efficiency of our framework\. The underlying state space complexity\|𝒮\|=2n2\|\\mathcal\{S\}\|=2^\{n^\{2\}\}grows explosively; for instance, a mere20×2020\\times 20grid already contains\|𝒮\|=2400≈2\.58×10120\|\\mathcal\{S\}\|=2^\{400\}\\approx 2\.58\\times 10^\{120\}states\. By achieving superior results on significantly larger grids \(e\.g\., up ton=119n=119\) within this modest memory budget, we empirically highlight the effectiveness of our geometry\-aware pruning and incremental update mechanisms in mitigating the curse of dimensionality\.

Hardware Heterogeneity and Control:The HPC cluster is a heterogeneous environment comprising various CPU architectures \(e\.g\., Intel Skylake, Cascade Lake, and Ice Lake\)\. To ensure the scientific rigor of ourablation studies, we enforced strict hardware consistency by using Slurm constraints to the best of our ability\. Specifically, all ablation trials were restricted to nodes supporting the following features:intel, avx512, mlx5\_ib, nvme, fastscratch\. This ensures that performance variations are attributable to algorithmic changes rather than underlying hardware differences\.

Resource Optimization for Main Experiments:For non\-ablation experiments \(e\.g\., searching for maximumnnsets\), where the primary goal is sheer computational throughput rather than controlled timing comparisons, we did not impose these hardware constraints\. This allowed the scheduler to utilize any available CPU\-only nodes, thereby maximizing resource utilization and reducing queue wait times under the 7\-day or 14\-day time limits\.

## Appendix EDetailed Previous Best\-Known Results of Max\-N3IL and Min\-Complete Sets

##### Previous Best\-Known Results of Largest No\-Three\-in\-Line Sets:

[Table˜4](https://arxiv.org/html/2606.26399#A5.T4)shows the best detailed results known results according toFlammenkamp \[[2026](https://arxiv.org/html/2606.26399#bib.bib13)\], Prellberg \[[2026](https://arxiv.org/html/2606.26399#bib.bib36)\]\.

Table 4:Previous best known values for the sizes of the N3IL sets \(n≤80n\\leq 80\)\. Bold values indicate that the value is optimal \(i\.e\., reaches the theoretical upper bound2​n2n\)\.
##### Previous Best\-known Results of Smallest Complete Sets:

[Table˜5](https://arxiv.org/html/2606.26399#A5.T5)shows the sizes of the smallest complete sets for2≤n≤122\\leq n\\leq 12\. These results are obtained by exhaustive enumeration, so they are optimal\[Aichholzeret al\.,[2023](https://arxiv.org/html/2606.26399#bib.bib27)\]\.[Table˜6](https://arxiv.org/html/2606.26399#A5.T6)shows the best\-known sizes of smallest complete sets forn\>12\.n\>12\.Note that the definition of “independent dominating set” in their work is equivalent to “complete set” in our context\.

Table 5:Known optimal values for sizes of the smallest complete sets \(n≤12n\\leq 12\)\.Table 6:Current best upper bounds for sizes of smallest complete sets \(n\>12n\>12\)\.

## Appendix FDetailed Experiment Results

### F\.1Ablation Study

Table 7:Incremental ablation study onn×nn\\times ngrids \(Average terminal number of points and average runtime in seconds, with std in parentheses\)\. Statistical significance vs\. the preceding variant is denoted byp∗<0\.05,∗∗p<0\.01,∗⁣∗∗p<0\.001\{\}^\{\*\}p<0\.05,^\{\*\*\}p<0\.01,^\{\*\*\*\}p<0\.001\. Search budget is10​n210n^\{2\}iterations\.

## Appendix GExamples

To best demonstrate the scalability of our framework, we show examples of configurations discovered on larger grids for every problem evaluated in this study\.

### G\.1Max No\-Three\-in\-Line

![Refer to caption](https://arxiv.org/html/2606.26399v1/x12.png)Figure 9:A discovered configuration with216216points on a119×119119\\times 119grid, satisfying the No\-Three\-in\-Line constraint\.
### G\.2Smallest Complete Set

![Refer to caption](https://arxiv.org/html/2606.26399v1/x13.png)\(a\)A complete set with9292points\.
![Refer to caption](https://arxiv.org/html/2606.26399v1/x14.png)\(b\)Raycast visualization demonstrating full grid coverage without violating collinearity constraints\.

Figure 10:A valid smallest complete set \(independent geometric dominating set\) discovered by our framework, consisting of9292points on96×9696\\times 96grid\. The bottom panel visually confirms the validity of the complete set, illustrating how the rays generated by the points cover the entire grid while satisfying the No\-Three\-in\-Line constraint\.
### G\.3Smallest Geometric Dominating Set

![Refer to caption](https://arxiv.org/html/2606.26399v1/x15.png)\(a\)A geometric dominating set with7272points\.
![Refer to caption](https://arxiv.org/html/2606.26399v1/x16.png)\(b\)Raycast visualization demonstrating full grid coverage\.

Figure 11:An example of a geometric dominating set on an83×8383\\times 83grid with7272points\. The bottom panel visually confirms the validity of the dominating set, illustrating how the lines generated by the7272points completely cover the entire grid\.
### G\.4Max No\-Four\-in\-Line

![Refer to caption](https://arxiv.org/html/2606.26399v1/x17.png)Figure 12:An optimal configuration with300300points on a100×100100\\times 100grid, satisfying the No\-Four\-in\-Line constraint\.
### G\.5Max No\-Isosceles Triangle

![Refer to caption](https://arxiv.org/html/2606.26399v1/x18.png)Figure 13:A configuration with124124points on a90×9090\\times 90grid, where no three points form an isosceles triangle\.
### G\.6Max No\-Four\-on\-a\-Circle

![Refer to caption](https://arxiv.org/html/2606.26399v1/x19.png)Figure 14:A configuration with6969points on a39×3939\\times 39grid, satisfying the No\-Four\-on\-a\-Circle constraint\.