How the Go AI Works: Monte Carlo Tree Search

The opponent on LK Forge Go (Weiqi / Baduk) does not think like the chess or Othello engines. Those score a position and search a tree of best replies. Go breaks that approach — so this engine uses a completely different classical method: Monte Carlo Tree Search (MCTS).

Why Go needs a different algorithm

Two things make Go hard for minimax. The branching factor is enormous — a 19×19 board has hundreds of legal moves at every turn — and, worse, there is no simple, reliable way to score a position. In chess you can count material; in Go, "who is ahead" mid-game is famously hard to judge. Without a trustworthy evaluation, a minimax search has nothing solid to compare. MCTS sidesteps both problems at once.

Play it out, don't judge it

Instead of evaluating a position, MCTS plays it to the end — many times. To pick a move the engine repeats a four-step loop thousands of times per move: select a promising line down the tree it has built so far, expand it by one new move, run a fast random playout to the finish, and back up the win or loss through the tree. The move that wins the most playouts is the one it plays. The playouts are eye-aware, so they don't fill in their own eyes and stall — but they are otherwise random, which is exactly what makes them fast enough to run thousands of times a move in a browser.

// one MCTS iteration (repeated thousands of times per move)
function iterate(root, rng) {
  const leaf = select(root);            // walk down by UCT (exploit + explore)
  const node = expand(leaf);            // add one new child move
  const winner = playout(node, rng);   // random game to two passes
  backup(node, winner);                // update win/visit counts up the tree
}

The "select" step balances two urges with the classic UCT rule: exploit moves that have scored well, but explore moves it has barely tried. Over thousands of iterations the tree grows lopsided toward the strongest lines — the engine spends its playouts where the game is actually decided.

Does thinking longer help? More than you'd expect

Because MCTS strength is just "how many playouts can you afford," we measured what each doubling buys. On 9×9, every doubling of the playout budget added about +233 Elo — and, unusually, the gains grew rather than shrank, from +171 Elo at the first doubling to +357 at the last, a cumulative +1,167 Elo from 50 to 1,600 playouts a move, with no flattening in sight.

That is the whole engine: don't judge the position, play it out thousands of times and count wins, guided down the tree by UCT. Curious how classical search compares across our other games? See Six Games, Three Classic Algorithms, or the full scaling study in Does Doubling a Go AI's Search Help?

FAQ

How does the Go AI choose a move?

The Go AI uses Monte Carlo Tree Search (MCTS). To pick a move it plays out thousands of fast random games to the end, keeps a small tree of the most promising lines, and favours the move that won the most of those playouts. It runs entirely in your browser, and it is strongest on the 9x9 board.

Why doesn't the Go AI use minimax like the chess AI?

Because Go has an enormous branching factor and no simple, reliable way to score a position — material counting works in chess, but 'who is ahead' in Go is famously hard to evaluate mid-game. MCTS sidesteps that: instead of judging a position, it plays it out to the end many times and counts wins, which needs no hand-written evaluation. It also uses a UCT rule to balance exploiting moves that have scored well against exploring ones it has barely tried, so the search still concentrates where the game is actually being decided.

Does thinking longer make the Go AI much stronger?

Yes, thinking longer makes the Go AI much stronger, and more than expected. In a seeded self-play study on 9x9, each doubling of the playout budget added about +233 Elo, and the gains grew rather than shrank — from +171 Elo at the first doubling to +357 at the last, a cumulative +1,167 Elo from 50 to 1,600 playouts a move. That is the opposite of the diminishing returns typically seen in game-tree search, and it held with no sign of flattening out even at the largest budget tested.

What board sizes and rules does it support?

9x9, 13x13 and 19x19, with the full rules — captures, the ko rule, illegal suicide, passing and automatic area (Chinese) scoring. It is an enjoyable, honest-amateur opponent, strongest on 9x9 where a fixed number of playouts covers far more of the game. On 13x13 and especially 19x19 the same playout budget is spread across a much bigger board, so the engine plays more loosely there.