5x5 Go

5x5 Go With a Two-Move Lookahead

· 5 min read
gamesjavascriptgo

A playable 5x5 Go board against a bot that does 2-ply minimax: for each legal move it evaluates the resulting position assuming Black plays its best reply. The board, rules engine, AI, and rendering live in a single HTML file. No build step.

Play it full page. Source on GitHub.

Why 5x5

Full-board Go is a bad fit for a hobby weekend. 19x19 has too much state for a 1-ply bot and too much theory for an evening. 9x9 is closer but still demands real heuristics for the bot to feel like an opponent. 5x5 is the smallest size that keeps every Go rule alive. Captures happen, ko shows up, life and death matters, and a naive bot is roughly as strong as a beginner who has never read a book.

Black is solved on 5x5. With Chinese rules and 2.5 komi, perfect play is a 25-point win for Black. The bot in this post does not play perfectly.

Board representation

The board is a 5x5 array of 0 (empty), 1 (black), 2 (white). Stones sit on intersections, not squares. Coordinates are [y][x] because that is the order JavaScript array literals read.

const N = 5;
const EMPTY = 0, BLACK = 1, WHITE = 2;
let board = Array.from({ length: N }, () => new Array(N).fill(EMPTY));

That is the whole representation. The board is recomputed fresh on every operation rather than maintained as a side table of group structures with a zobrist hash for repetition detection.

The rules engine

tryMove(board, x, y, colour, ko) is the only function that needs to be right. It returns null for illegal moves, otherwise a new board, the list of captured stones, and the resulting ko point.

The order of operations matters. Place the stone first, then capture opponent groups with no liberties, then check whether the placed group itself has liberties. Doing it in the other order forbids legal capture-suicide moves where you fill your own last liberty but kill an opponent group in the process.

function tryMove(b, x, y, colour, ko) {
  if (b[y][x] !== EMPTY) return null;
  if (ko && ko[0] === x && ko[1] === y && ko[2] === colour) return null;
  const opp = colour === BLACK ? WHITE : BLACK;
  const nb = cloneBoard(b);
  nb[y][x] = colour;

  const captured = [];
  for (const [nx, ny] of neighbors(x, y)) {
    if (nb[ny][nx] !== opp) continue;
    const g = findGroup(nb, nx, ny);
    if (g.liberties.size === 0) {
      for (const [sx, sy] of g.stones) { nb[sy][sx] = EMPTY; captured.push([sx, sy]); }
    }
  }

  const own = findGroup(nb, x, y);
  if (own.liberties.size === 0) return null; // suicide
  // ...ko detection
  return { board: nb, captured, koPoint: nextKo };
}

findGroup is a flood fill over same-colour stones, collecting adjacent empties as liberties. It runs once per neighbour check and once for the placed stone, so worst case four flood fills per move. On a 25-point board that is invisible.

Ko

Positional superko is overkill for 5x5. The simple ko rule is enough: if a move captures exactly one stone, and the placed stone is itself a single stone with one liberty, mark the captured point as forbidden for the opponent on their next move only. That covers the classic 1-stone ko fight and ignores the rare board-repeat cases that 5x5 games seldom reach.

let nextKo = null;
if (captured.length === 1 && own.stones.length === 1 && own.liberties.size === 1) {
  nextKo = [captured[0][0], captured[0][1], opp];
}

Scoring

Area scoring (Chinese rules) is the easier of the two common scoring systems to implement. Every stone counts. Every empty region surrounded by exactly one colour counts for that colour. Regions touching both colours are dame and count for nobody.

Flood fill each empty region. Track which colours border the region. If exactly one colour borders it, the region belongs to that colour.

if (borders.size === 1) {
  if (borders.has(BLACK)) blackArea += region.length;
  else whiteArea += region.length;
}

White gets a 2.5 komi added to its area total. The .5 removes the possibility of a draw.

The AI

The first version of this bot was 1-ply: try every legal move, pick the one with the highest immediate area score. It played terribly. Static evaluation cannot tell the difference between placing a stone in your own territory and placing one that gets captured next turn, because the captured move scores well right after the bot makes it. Black takes the stone on the next move, and the bot does it again.

Going to 2-ply fixes that. For each candidate move, simulate Black’s best reply (the reply that minimises White’s area score), and use that score as the value of White’s move.

function evalAfterBlackReply(b, ko) {
  const moves = legalMoves(b, BLACK, ko);
  let worst = evaluate(b);
  for (const [x, y] of moves) {
    const r = tryMove(b, x, y, BLACK, ko);
    if (!r) continue;
    const v = evaluate(r.board);
    if (v < worst) worst = v;
  }
  return worst;
}

That is one function call per Black candidate, up to 25 of them, evaluated for each of up to 25 White candidates. Worst case 625 board scorings per AI turn. On a 5x5 board this is about 10 ms in Chrome.

Passing falls out of the same machinery. Treat passing as a candidate “move” whose evaluation is evalAfterBlackReply(currentBoard). If no real move beats passing, the bot passes. That covers both the winning case (no profitable move, end the game) and the losing case (every move gets captured, give up).

const passScore = evalAfterBlackReply(board, null);
let best = null, bestScore = -Infinity;
for (const move of legalMoves(board, AI, koPoint)) {
  // ... compute v from evalAfterBlackReply on the move's resulting board
  if (v > bestScore) { bestScore = v; best = move; }
}
if (best === null || bestScore <= passScore) return null; // bot passes

The centre bias breaks ties toward stronger points, so opening moves go to tengen instead of a corner. The random jitter avoids deterministic loops where the bot oscillates between two equally-rated moves.

Where the bot is weak

Two plies is enough to stop the bot from feeding stones into capture, but not enough to read sequences. Ladders, multi-move kills, and the difference between a real eye and a one-move-from-fatal eye shape are all invisible to a 2-ply search. The bot only sees that the eye-filling move scores well and Black’s reply does not capture, so it plays the move and dies on the turn after. Real bots do tree search to depths of 30+ moves with policy networks doing the pruning. A 2-ply player on 5x5 still beats most people who have never played Go before, which was the bar for this post.

File and deployment

index.html is the whole project. SVG renders the board and stones; click handlers attach to invisible rect elements over each intersection. CSS variables for the wood, line, and stone colours. The Dockerfile is FROM nginx:alpine plus one COPY. Dokploy serves it at go-5x5.danieljohnmorris.com on every push to main.

Related:

All articles