Winning at Gomoku: checking the last stone is enough

After finishing the board for Gomoku, the first idea for win detection was a full scan: for every cell, check four directions for five in a row. It works, but running it after every move puts an O(board) cost on the hottest path in the game.

Only the newest stone can create a line

Before the move, the board contained no five in a row, or the game would already be over. So any new line must include the stone just placed. Only its four lines need checking:

const DIRECTIONS = [[0, 1], [1, 0], [1, 1], [1, -1]];

function checkWin(board, row, col, size) {
  const who = at(board, row, col, size);
  if (!who) return null;
  for (const [dr, dc] of DIRECTIONS) {
    const cells = [index(row, col, size)];
    for (const sign of [1, -1]) {
      let r = row + dr * sign;
      let c = col + dc * sign;
      while (inBounds(r, c, size) && at(board, r, c, size) === who) {
        cells.push(index(r, c, size));
        r += dr * sign;
        c += dc * sign;
      }
    }
    if (cells.length >= 5) return { who, cells };
  }
  return null;
}

cells collects the coordinates of the line as a side effect, so highlighting the winning stones in the UI needs no second search.

The cost does not depend on board size

Four directions, and each stops within about four steps because the fifth stone settles it. That is constant work. A 15x15 board and a 19x19 board run almost the same number of loop iterations.

Approach	Cost per move
Full scan	O(size squared), 225 cells to start on 15x15
Check the placed stone	O(1) per direction, independent of size

Two decisions about edges and rules

• Treat out of bounds as not the same colour. Do not write a separate guard: put inBounds and the colour test in one condition, and the edge terminates the walk naturally.
• Decide whether an overline wins. Rules differ, and some forbidden-move variants treat six in a row as a loss. This site treats five or more as a win, expressed in cells.length >= 5. The rule is one expression, so changing it changes one place.

The bitboard version

Pack a 15x15 board into 64-bit integers, a few bits per row, and win detection becomes shifts and ANDs: shift the board along a direction, AND with the original, repeat four times, and the surviving bits are a four in a row. That is the same family of idea as the popcount article. This site did not take that route: 225 cells need four 64-bit words, and diagonals cross word boundaries, so the complexity buys little at this size.

Incremental detection is a general principle: before recomputing everything, ask what this change could possibly affect.