DEV Community

Cover image for Liberties, ko and two passes: how I coded the rules of Go in about 360 lines of JavaScript
My MP Games
My MP Games

Posted on

Liberties, ko and two passes: how I coded the rules of Go in about 360 lines of JavaScript

Go has the shortest rulebook of any board game I've built. Place a stone, capture a group by taking its last liberty, don't repeat a position, and the bigger area wins.

Getting those few rules exactly right still took more care than the postcard version suggests.

Go is one of the 60+ games on mympgames, my free multiplayer browser arcade. It runs on 9×9, 13×13 and 19×19 boards. The whole rules engine is one file, go-rules.js, and that same file runs in two places: on the server, which decides what's legal, and in a Web Worker in the browser, where the computer opponent thinks. This post follows one stone from the moment you click to the moment the game is scored. The code is real, trimmed a little.

The board is a flat array of numbers

No classes, no Stone objects. A position is an array of size * size integers, where 0 is empty, 1 is black and 2 is white. A small neighbors(size, i) helper turns an index into its up, down, left and right neighbours with four bounds checks. Corners get two neighbours and edges get three, which is why corners are easier to live in. The rules never need to know that.

A flat array is also cheap to copy, which matters because the AI copies boards thousands of times per move.

Liberties: one flood fill does everything

Almost every rule in Go is a question about a group: stones of one colour joined up and down or side to side, plus the empty points next to them (their liberties). I answer it with one function:

function groupAndLibs(board, size, start) {
  const color = board[start];
  const group = [], libs = new Set();
  const seen = new Set([start]);
  const stack = [start];
  while (stack.length) {
    const i = stack.pop();
    group.push(i);
    for (const n of neighbors(size, i)) {
      if (board[n] === 0) libs.add(n);
      else if (board[n] === color && !seen.has(n)) {
        seen.add(n);
        stack.push(n);
      }
    }
  }
  return { group, libs };
}
Enter fullscreen mode Exit fullscreen mode

It's an iterative depth-first search with an explicit stack, so a long chain on 19×19 can't blow the call stack. Liberties go in a Set because stones often share an empty neighbour, and counting it twice gives you a group with "two" liberties that is really in atari.

The life of a move

Here's tryPlay, the function that decides whether a click is legal. The order of the steps is the interesting part.

function tryPlay(pos, point) {
  if (pos.board[point] !== EMPTY) return { ok: false, error: 'Occupied' };
  const next = pos.board.slice();
  const color = pos.turn, opp = other(color);
  next[point] = color;

  // 1. Remove opponent groups that just lost their last liberty
  const captured = [], seen = new Set();
  for (const n of neighbors(pos.size, point)) {
    if (next[n] !== opp || seen.has(n)) continue;
    const g = groupAndLibs(next, pos.size, n);
    g.group.forEach((x) => seen.add(x));
    if (g.libs.size === 0) captured.push(...g.group);
  }
  for (const c of captured) next[c] = EMPTY;

  // 2. Only now check whether my own group has room to breathe
  const own = groupAndLibs(next, pos.size, point);
  if (own.libs.size === 0) return { ok: false, error: 'Suicide' };

  // 3. Never recreate an earlier position
  const hash = next.join('');
  if (pos.history.includes(hash)) return { ok: false, error: 'Ko' };

  return { ok: true, board: next, captured, hash };
}
Enter fullscreen mode Exit fullscreen mode

Captures come before the suicide check. Playing into a spot with no liberties is fine if it captures something, because the capture creates the liberties. Check suicide first and you forbid some of the most common captures in the game, including the move that starts every ko fight. It's an easy order to get backwards.

Suicide is illegal. Some rulesets (New Zealand, for example) allow multi-stone suicide. I went with the stricter rule most players expect, and the server simply rejects it.

Ko is handled as positional superko. The classic ko rule says you can't immediately retake a single stone. Instead of special-casing that shape, I store a string of every board position in the game and refuse any move that recreates one. That covers basic ko and the rare long cycles (like triple ko) that the simple rule misses.

The hash is just board.join(''). It's not clever, and history.includes is a linear scan, but a 9×9 game is maybe 60–100 moves. Zobrist hashing is on my list if 19×19 ever gets slow.

tryPlay never mutates the position. A separate playMove commits the result, so the AI can ask "is this legal?" without changing anything.

Ending the game is the hard part

In chess the game ends on the board. In Go, the players agree that it's over, and then agree on which stones are dead. That's a social protocol, and I coded it as a small state machine with three phases: play, mark and done. Passing bumps a passes counter and hands over the turn. When it reaches 2, the phase flips to mark.

Any real move resets passes to 0, so only two passes in a row end play. In the mark phase, clicking a stone toggles its whole group as dead or alive, and, importantly, resets both players' "accept" flags:

for (const i of g.group) allDead ? pos.dead.delete(i) : pos.dead.add(i);
pos.accept = [false, false];
Enter fullscreen mode Exit fullscreen mode

Without that reset, I could accept the score, wait for you to accept, and quietly mark your group dead in between. Every change forces both players to agree again. When both flags are true, the game is scored and the phase becomes done.

There's also an optional dead-stone estimate, and I made it deliberately timid. It only marks enclosed one-liberty groups, and skips anything sharing short liberties with an enemy group, because that might be seki (mutual life). A wrong "dead" mark is far more annoying than a missing one.

Scoring: area, not territory

I used area scoring (often called Chinese scoring): your stones on the board plus the empty regions only you surround. Komi defaults to 7.5 for white, and the room can switch it to 6.5.

// flood-fill each empty region and record which colours border it
const only = border.size === 1 ? [...border][0] : 0;
for (const x of region) owner[x] = only;
...
const black = b;
const white = w + pos.komi;
Enter fullscreen mode Exit fullscreen mode

An empty region bordered by both colours counts for nobody. Area scoring has one big advantage for software: prisoners don't affect the result (I still count them for the UI), and filling neutral points at the end can't change who won. With territory scoring, that's where disputes come from.

Because komi has a half point, ties can't happen with the default settings. The code still handles a tie, in case someone ever adds whole-number komi.

How it plugs into the server

The server doesn't know anything about Go. Each game in the catalog has an engine and a config, and Go's three sizes are the same engine with { size: 9 }, { size: 13 } or { size: 19 }. A thin wrapper turns room actions (move, pass, toggle-dead, accept, resign) into calls to the rules module, checks that it's your turn, and maps seats to colours, since you can choose to play white. Moves travel as coordinates like D4, using the traditional letters that skip I.

The computer opponent is flat Monte Carlo

The server bot that plays most of the other games skips Go. Instead, the AI runs in a Web Worker in your browser, importing the same go-rules.js file. Search happens off the main thread, so the board stays responsive while it thinks, and the server never burns CPU on it.

It's plain flat Monte Carlo, with no tree search. For each legal move, it plays the game out to the end many times with quick, mostly sensible moves (it likes captures and the third and fourth lines, and avoids the edge), scores each finished board with the same areaScore, and picks the best win rate. If even its best move wins less than 12% of the time, it passes. Difficulty is just a budget: beginner gets 8 playouts in 80 ms and plays a random move 55% of the time, while expert gets 500 playouts in 1.6 seconds.

It won't trouble a club player, but on 9×9 it makes sensible moves, takes captures when they're there, and the beginner level is honestly beatable by someone learning the game. That was the goal.

Tradeoffs I'd make again (and one I wouldn't)

  • One rules file, two runtimes. Server and AI can never disagree about legality.
  • Superko via full-board strings. Dumb, correct and readable. Optimise later if needed.
  • Area scoring. Fewer edge cases, fewer arguments.
  • What I'd change: legalPoints runs tryPlay on every point, and the server sends that list with every state update. On 9×9 that's 81 cheap checks. On 19×19 it's 361 board copies per update. It's fine today, but it's the first thing I'll look at if the big board ever feels slow.

If you want to see these rules in action, you can play Go at mympgames.com/play/go. It's free and runs in the browser, against a friend or the computer. And if Go isn't your game, there are 60+ others at mympgames.com.

Top comments (0)