Gomoku AI: splitting threat detection from search

The AI in my gomoku game started out as a plain alpha-beta search running four plies deep, and it played badly: it ignored an open three, and sometimes missed its own winning move. The reason is that at that depth, the evaluation function reads “loses in three moves” as an ordinary position.

The fix was not more depth. It was taking everything that can be decided for certain out of the search.

Three layers, order matters

Every move passes through fixed gates:

Order	Test	Action
1	Can I make five?	Play it, no search
2	Can the opponent make five next?	Block
3	Can I / they make an open four?	Play it / break it
4	None of the above	Hand to alpha-beta

The first three are the threat layer. Their shared property: the answer is determined by the shape on the board alone, independent of what happens later. Sending those to the search wastes nodes re-verifying a certainty — and at shallow depth it fails to verify it, so it gets it wrong.

Search should handle uncertainty. It should not be used to rediscover things the board already states.

Why open four needs its own test

An open four (.XXXX.) wins outright: the opponent has one stone and cannot block both ends.

If layer three merely checks “do I have four in a row”, it also counts a closed four, which one block kills. Playing that hands over a free tempo. So the test is on the shape string: 011110 is open, 011112 and 211110 are closed.

I scan nine-cell windows along all four axes and match the resulting 0/1/2 strings:

const PATTERN = {
  FIVE: 1e7,
  OPEN_FOUR: 3e5,
  FOUR: 2.6e4,
  OPEN_THREE: 2e4,
  THREE: 1100,
  OPEN_TWO: 600,
  TWO: 90,
  ONE: 6,
};

Those numbers are not arbitrary. They must satisfy two rules: five beats everything else combined, and an open four must outweigh two open threes — otherwise the AI trades a forced win for a pair of threats.

The search layer’s three standard parts

• Iterative deepening: search depth 1, 2, 3…, keeping the last completed layer. When time runs out, the previous layer’s answer is intact rather than half-finished.
• Transposition table: positions keyed by a Zobrist hash, storing depth, score, and a bound flag (exact / upper / lower).
• Candidate pruning: only points near existing stones. Of 225 intersections, usually fewer than 20 are worth considering.

One detail that is easy to get wrong: the time budget must be checked inside the search, not by an outer setTimeout. I look at the clock every 1024 nodes, set an abort flag, and unwind layer by layer. Otherwise a layer interrupted halfway yields a score computed from a partial tree.

Difficulty is just the budget

Five levels are one engine with five parameter sets:

Level	Depth	Time	Noise	Width
1 Novice	1	90ms	0.9	8
2 Casual	2	200ms	0.5	10
3 Skilled	4	450ms	0.18	12
4 Hard	6	900ms	0.04	14
5 Master	8	1800ms	0	16

“Noise” picks randomly among the top candidates. Weakening by depth alone does not work, because the threat layer still fires — the novice level would still win on the spot when it can.

Making the AI explain itself

While tuning, the hard question is always “why did it play that”. Recording a trace is easy; the depth, best move and score per layer, plus a few root candidates.

The part that took real work was the scores. alpha-beta mostly returns bounds — “no better than X” — and displaying those makes a row of candidates show identical numbers, which reads as broken. So when the user opens the tool tree, root candidates are re-searched with a full window to get exact values. Slower, but only paid by someone who actually wants to look.

Numbers shown to a user must be real numbers. A “process” assembled from bounds is worse than no process at all.

Takeaway

This AI is roughly at “respects an open three”. A real engine does much more (VCF/VCT searches, learned evaluation). But for a browser game, the threat layer bought far more than going from depth 4 to depth 8 — because the game is usually decided in a short burst.