Geometry-aware MCTS

A search story about legal moves, expensive constraints, and symmetry

← Back to AI 4 Math

Project: Geometry-Aware MCTS for Extremal Problems in Combinatorial Geometry · HTML

With Luoning Zhang, Tianhao Wang, and Nathan Kaplan.

No-Three-in-Line looks almost like a game: place a point on an \(n\times n\) grid, make sure it does not complete a collinear triple, and repeat. The difficulty is that one point changes the status of many empty squares at once. A configuration can be valid now and have very few useful continuations left.

That is an awkward setting for ordinary Monte Carlo Tree Search. A naïve tree treats every empty square as an action. Many rollouts then end as soon as they try a forbidden point. The search spends simulations discovering something the geometry could have told it in advance.

We chose to remove those branches altogether.

For a current point set \(s\), we maintain the actions that preserve the geometric constraint:

\[\mathcal A_{\mathrm{feas}}(s) = \left\{p\in G_n\setminus s:\Phi(s\cup\{p\})=\mathrm{True}\right\}.\]

Feasible-action update

Place one point and watch future actions disappear

Selected
0
Feasible
49
Blocked
0

Choose any hollow grid point. If the new point and an earlier point determine a line, every other empty grid point on that line becomes a forbidden action. Click a blocked × to reveal the pair that blocks it.

  • Selected
  • Feasible action
  • Already blocked
  • Blocked by the last move

All 49 grid points are initially feasible.

In the full search, MCTS chooses which feasible point to try. This figure isolates the deterministic geometric update that happens after that choice; it is not a simulation of the full tree search.

MCTS never sees a point outside \(\mathcal A_{\mathrm{feas}}(s)\). This changes its job. It no longer has to learn which moves are illegal; it only has to compare legal continuations.

Conceptually, that is the cleanest part of the method. Computationally, it creates the next problem. For No-Three-in-Line, scanning every empty square and checking it against the current set costs \(O(n^3)\). Repeating that scan at every node can make a more intelligent search slower than the naïve one.

The geometry gives a way out. Once a new point is placed, a blocked square never becomes legal again. We keep the previous feasible set and remove only the squares newly ruled out by lines through the new point. Incremental ray casting reduces the update to \(O(n^2)\).

The same interface—“give the tree the legal actions”—can be reused. The routine behind that interface still has to be written for each geometric constraint.

The price of enforcing legality

The cumulative ablation at \(n=40\) shows why both sides of this design mattered. Each point is the mean over 20 random seeds, using \(10n^2\) MCTS iterations per decision. The line is the terminal configuration size; the bars are runtime.

{
  "type": "bar",
  "data": {
    "labels": [
      "Baseline",
      "+ Feasible",
      "+ Incremental",
      "+ Canonical",
      "+ C4 batch",
      "+ Anytime",
      "+ Subtree reuse"
    ],
    "datasets": [
      {
        "type": "bar",
        "label": "Runtime (seconds)",
        "data": [106.53, 1533.96, 1134.8, 1184.56, 282.59, 277.33, 250.42],
        "backgroundColor": "rgba(23, 162, 184, 0.4)",
        "borderColor": "rgb(23, 162, 184)",
        "borderWidth": 1,
        "yAxisID": "yTime",
        "order": 2
      },
      {
        "type": "line",
        "label": "Terminal points",
        "data": [47.8, 70.3, 70.0, 70.0, 72.0, 72.6, 72.6],
        "borderColor": "rgb(138, 87, 196)",
        "backgroundColor": "rgb(138, 87, 196)",
        "pointRadius": 4,
        "borderWidth": 3,
        "tension": 0.2,
        "yAxisID": "yPoints",
        "order": 1
      }
    ]
  },
  "options": {
    "responsive": true,
    "aspectRatio": 1.55,
    "interaction": {
      "mode": "index",
      "intersect": false
    },
    "plugins": {
      "title": {
        "display": true,
        "text": "Max No-Three-in-Line ablation at n = 40",
        "color": "#888888"
      },
      "legend": {
        "labels": {
          "color": "#888888"
        }
      }
    },
    "scales": {
      "x": {
        "ticks": {
          "color": "#888888",
          "maxRotation": 45,
          "minRotation": 20
        },
        "grid": {
          "color": "rgba(128, 128, 128, 0.15)"
        }
      },
      "yPoints": {
        "type": "linear",
        "position": "left",
        "beginAtZero": true,
        "title": {
          "display": true,
          "text": "Mean terminal points",
          "color": "#888888"
        },
        "ticks": {
          "color": "#888888"
        },
        "grid": {
          "color": "rgba(128, 128, 128, 0.15)"
        }
      },
      "yTime": {
        "type": "linear",
        "position": "right",
        "beginAtZero": true,
        "title": {
          "display": true,
          "text": "Runtime (seconds)",
          "color": "#888888"
        },
        "ticks": {
          "color": "#888888"
        },
        "grid": {
          "drawOnChartArea": false
        }
      }
    }
  }
}

The baseline averaged 47.8 terminal points in 106.53 seconds. Restricting the tree to feasible moves changed the mean to 70.3 points, but runtime rose to 1,533.96 seconds. The decision that fixed the dead rollouts had become the main computational cost.

Incremental updates preserved essentially the same terminal size and lowered the runtime to 1,134.80 seconds. That did not yet make the search cheap, but it separated the value of enforcing legality from the cost of recomputing it.

Symmetry can remove a move—or redefine one

The square grid has the dihedral symmetry group \(D_4\). We used it in two ways, and the difference between them became important.

Canonical pruning acts during node expansion. For the current state, we compute the symmetries that leave it fixed and keep one action from each orbit. At the empty root the reduction is roughly a factor of eight; deeper in the tree it depends on which symmetries the partial configuration still has.

Symmetric batch transitions change the meaning of one action. After a point is selected, the transition tries to add its full \(C_4\) or \(D_4\) orbit. If the orbit violates the constraint, it falls back to the single selected point. Rather than merely deleting duplicate branches, batching lets the tree move through a structured configuration in fewer steps.

The ablation made the distinction visible. Adding canonical pruning produced no statistically significant gain at \(n=40\). In this cumulative ablation, the large change appeared only after \(C_4\) batch transitions were added: the mean rose from 70.0 to 72.0 points and runtime fell from 1,184.56 to 282.59 seconds.

Anytime tracking and subtree reuse affected different quantities. Anytime tracking raised the mean to 72.6, while subtree reuse reduced runtime to 250.42 seconds without changing the mean.

The same bottleneck on a larger grid

At \(n=70\), the scale made the tradeoff harder to ignore. The baseline averaged 64.8 points in 1,036.85 seconds. Feasible masking raised that to 119.2 points, but required 54,667.12 seconds. With symmetric batching, the mean reached 124.8 points in 7,722.33 seconds; with subtree reuse, the final variant ran in 6,693.15 seconds.

At this size, changing the action representation reduced runtime by nearly a factor of seven relative to feasible masking alone.

One search scaffold, six separate geometries

The tree-search code could be reused, but the feasible-set update could not. Collinearity, domination, concyclicity, and equal-distance constraints each needed their own geometric test. Even the useful symmetry changed: \(C_4\) worked best for Max No-Three-in-Line, while full \(D_4\) worked best for Min Complete.

The outcomes differed across constraints. For No-Three-in-Line, the search found 216 points on a \(119\times119\) grid and improved the known records for \(82\le n\le119\). For Min Complete, it found 92 points at \(n=96\). For No-Four-in-Line, it reached the matching upper bound \(3n\) through \(n=100\).

No-Isosceles was the useful counterexample. The search found 124 points at \(n=90\), but it did not beat the specialized known construction. Sharing a search interface did not make the mathematical structure of the six problems interchangeable.

The large runs used one CPU core and 6 GB of memory, with cutoffs of one or two weeks depending on the problem. The point of the search was not to turn computation into a proof. It was to produce verified configurations in ranges where exhaustive methods were out of reach.

What actually transferred

What transferred was the boundary between MCTS and geometry: the tree asks for valid actions, and a problem-specific routine maintains them. What did not transfer automatically was the mathematics inside that routine or the choice of symmetry.

That is the main lesson I take from the project. MCTS became useful here only after the geometry was allowed to shape the state and the actions. Every reported configuration satisfies its constraint, but it proves optimality only when it meets an independent theoretical bound. In the other cases, the search is best understood as a computational laboratory for finding constructions and deciding where to look next.

← Back to AI 4 Math