Introduction

Go is about 2,500 years old and has almost no rules. Two players take turns placing black and white stones on the intersections of a grid; surround your opponent's stones and you capture them; surround more territory than they do and you win. A child can learn it in minutes.

And yet, on the standard 19×19 board there are roughly 2.1 × 1017010^{170} legal positions — vastly more than the number of atoms in the observable universe (about 108010^{80}). Each turn a player has around 250 reasonable moves, against roughly 35 in chess. That gap is everything.

For decades, the brute-force search that conquered chess simply drowned in Go. The game became the great unsolved benchmark of artificial intelligence — until 2016, when something new finally cracked it.

Feel the Explosion

Pick a small board size and a search depth, then watch the game tree grow. Each empty point is a possible move, so the number of positions to examine multiplies at every ply.

<p class="hint">A Go search must consider every empty point as a possible move, then every reply, and so on. <b>Checking</b> one move is instant; <b>planning ahead</b> multiplies the work by the branching factor at every step. Pick a board and a depth and watch the game tree explode.</p>
<div class="ctrl">
  <label>Board:
    <select id="size">
      <option value="3">3 × 3</option>
      <option value="5" selected>5 × 5</option>
      <option value="7">7 × 7</option>
      <option value="9">9 × 9</option>
    </select>
  </label>
  <label>Look ahead (plies): <b id="dlabel">3</b>
    <input id="depth" type="range" min="1" max="8" value="3">
  </label>
</div>
<div id="board" class="board"></div>
<div class="out">
  <div class="row"><span>Empty points (branching factor b):</span><b id="bf">25</b></div>
  <div class="row"><span>Positions a depth-d search examines (≈ bᵈ):</span><b id="nodes">—</b></div>
  <div class="row big" id="verdict">Press "Count the tree".</div>
</div>
<div class="btns">
  <button id="count" type="button">Count the tree</button>
  <button id="check" type="button" class="ghost">Check one move</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.ctrl { display: flex; flex-wrap: wrap; gap: 1rem 1.5rem; align-items: center; font-size: .9rem; margin-bottom: .7rem; }
.ctrl label { display: flex; gap: .4rem; align-items: center; }
.ctrl input[type=range] { vertical-align: middle; }
select { font: inherit; padding: .2rem .3rem; }
.board { display: inline-grid; gap: 0; background: #d9b771; padding: 10px; border-radius: 6px; margin: .3rem 0 .8rem; }
.pt { width: 26px; height: 26px; position: relative; cursor: pointer; }
.pt::before, .pt::after { content: ""; position: absolute; background: #6b5328; }
.pt::before { left: 50%; top: 0; bottom: 0; width: 1px; transform: translateX(-.5px); }
.pt::after { top: 50%; left: 0; right: 0; height: 1px; transform: translateY(-.5px); }
.pt .stone { position: absolute; inset: 3px; border-radius: 50%; z-index: 2; }
.pt.black .stone { background: radial-gradient(circle at 35% 30%, #555, #000); }
.pt.white .stone { background: radial-gradient(circle at 35% 30%, #fff, #cfcfcf); border: 1px solid #aaa; }
.pt.flash { outline: 2px solid #c92f3c; outline-offset: -2px; }
.out { font-size: .92rem; margin: .3rem 0 .7rem; }
.row { display: flex; justify-content: space-between; gap: 1rem; padding: .15rem 0; border-bottom: 1px dashed #ddd; }
.row b { font-variant-numeric: tabular-nums; }
.row.big { font-size: 1rem; font-weight: 700; border: none; padding-top: .5rem; display: block; }
.row.big.ok { color: #0a7d33; }
.row.big.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// The "easy to check / hard to solve" tension of Go.
//  - CHECK: verifying a single move is legal = instant, local work.
//  - SOLVE: a depth-d minimax search must examine ~ b^d positions, where b is the branching factor (here, the number of empty points). On the real 19x19 board b ~ 250 and games run hundreds of plies, giving ~10^360 nodes — far past any machine. Generalized Go is EXPTIME-complete (Robson, 1983).
let N = 5;
const stones = {}; // key "r,c" -> 'black' | 'white', a few decorative stones

function key(r,c){ return r + ',' + c; }
function emptyCount(){ return N*N - Object.keys(stones).length; }

// human-readable big number
function fmt(x){
  if (x < 1e6) return x.toLocaleString('en-US');
  const e = Math.floor(Math.log10(x));
  const m = (x / Math.pow(10, e));
  return m.toFixed(2) + ' × 10^' + e;
}
// exact count of positions in a uniform game tree of branching b, depth d: b + b^2 + ... + b^d  (nodes examined). Returned as a float for display.
function treeNodes(b, d){
  let total = 0, term = 1;
  for (let i = 0; i < d; i++){ term *= b; total += term; }
  return total;
}

function render(){
  const b = document.getElementById('board');
  b.style.gridTemplateColumns = 'repeat(' + N + ', 26px)';
  b.innerHTML = '';
  for (let r = 0; r < N; r++) for (let c = 0; c < N; c++){
    const d = document.createElement('div');
    const s = stones[key(r,c)];
    d.className = 'pt' + (s ? ' ' + s : '');
    if (s) { const st = document.createElement('div'); st.className = 'stone'; d.appendChild(st); }
    d.addEventListener('click', () => onCheck(r, c, d));
    b.appendChild(d);
  }
  document.getElementById('bf').textContent = emptyCount();
}

// CHECK one move: is this empty point playable? (instant, local check)
function onCheck(r, c, el){
  const v = document.getElementById('verdict');
  if (stones[key(r,c)]){
    v.textContent = 'That point is occupied — not a legal move.';
    v.className = 'row big bad';
  } else {
    el.classList.add('flash');
    setTimeout(() => el.classList.remove('flash'), 600);
    v.textContent = '✓ Checked instantly: that move is legal. One check is trivial.';
    v.className = 'row big ok';
  }
}

// SOLVE: count the whole search tree for the chosen depth.
function onCount(){
  const b = emptyCount();
  const d = +document.getElementById('depth').value;
  const nodes = treeNodes(b, d);
  document.getElementById('nodes').textContent = fmt(nodes);
  const v = document.getElementById('verdict');
  // ~1e9 positions/sec is a generous machine; how long to enumerate?
  const secs = nodes / 1e9;
  let msg;
  if (secs < 1) msg = 'Searchable in under a second — on this toy board.';
  else if (secs < 3600) msg = i18nFmt('About %round% s of brute force at a billion positions/sec.', { round: Math.round(secs) });
  else if (secs < 3.15e7) msg = i18nFmt('About %v% hours of brute force.', { v: (secs/3600).toFixed(1) });
  else if (secs < 3.15e10) msg = i18nFmt('About %v% years of brute force.', { v: (secs/3.15e7).toFixed(1) });
  else msg = i18nFmt('More than %fmt% years — longer than the age of the universe.', { fmt: fmt(secs/3.15e7) });
  v.textContent = i18nFmt('✗ %fmt% positions to examine. %msg% And real Go is 19×19, depth ~300.', { fmt: fmt(nodes), msg: msg });
  v.className = 'row big ' + (secs < 1 ? 'ok' : 'bad');
}

function syncSize(){
  N = +document.getElementById('size').value;
  // sprinkle a couple of stones so the board looks alive (kept < N*N-1 empties)
  for (const k in stones) delete stones[k];
  if (N >= 5){ stones[key(1,1)] = 'black'; stones[key(N-2,N-2)] = 'white'; }
  render();
  document.getElementById('nodes').textContent = '—';
  const v = document.getElementById('verdict');
  v.textContent = 'Press "Count the tree".'; v.className = 'row big';
}

document.getElementById('depth').addEventListener('input', e => {
  document.getElementById('dlabel').textContent = e.target.value;
});
document.getElementById('size').addEventListener('change', syncSize);
document.getElementById('count').addEventListener('click', onCount);
document.getElementById('check').addEventListener('click', () => {
  const v = document.getElementById('verdict');
  v.textContent = 'Click any empty intersection on the board to check that move.';
  v.className = 'row big';
});
syncSize();
Result
Console

Notice the asymmetry. Checking whether a single move is legal is instant — just look at the local stones. But planning ahead, examining every reply to every reply, multiplies the count by the branching factor at each step. Push the depth slider a few notches and the total rockets past anything a computer could ever enumerate — and that is on a toy board, not the real 19×19.

The Real Complexity

How hard is Go, really? Not casual play — perfect play.

  • Checking a single position is easy: verifying a move's legality and counting territory is quick local work.
  • Searching the game tree is the trap: with a branching factor near 250 and games well over a hundred moves long, the game-tree complexity is on the order of 1036010^{360} — utterly beyond brute force.
  • It's EXPTIME-complete. In 1983, John M. Robson proved that generalized Go on an n×n board (with the Japanese ko rule) is EXPTIME-complete. EXPTIME is the class of problems solvable in exponential time — and being complete for it means Go is among the hardest problems in that class. Unlike with P vs NP, this is not an open question: EXPTIME provably contains problems that need exponential time, so no polynomial algorithm for perfect Go can exist.
  • This puts Go beyond NP. EXPTIME strictly contains P, and Go is harder in the worst case than any NP-complete problem like SAT. It shares this league with generalized chess (also EXPTIME-complete).

So the breakthrough of 2016 was not a faster exact solver — that's impossible. AlphaGo combined deep neural networks (to evaluate positions and suggest moves) with Monte-Carlo tree search, learning to prune the astronomical tree down to the handful of lines that matter. It beat top human professionals by being a brilliant approximator, not by solving the unsolvable.

Where It Matters

"Search a space far too big to enumerate, guided by learned intuition" is a pattern that reaches well past the goban:

  • Reinforcement learning: AlphaGo's self-play recipe became AlphaZero, which mastered chess and shogi from scratch, and inspired controllers for robotics and data-center cooling.
  • Monte-Carlo tree search: sampling promising lines instead of exhausting them is now standard in planning, scheduling and automated reasoning.
  • Scientific discovery: the same lab's AlphaFold applied learned search to protein structure, transforming biology.
  • A model for hard search: Go is the canonical lesson that when a problem is provably intractable, the answer is smart approximation — the same mindset that tames routes and other NP-hard problems.

Understand why Go is hard and you understand why modern AI leans on learning to navigate spaces no algorithm can ever fully explore.

Conclusion

Go is a paradox carved in stones: rules a child can learn, a game tree no computer can ever fully search. Its generalized form is EXPTIME-complete — provably exponential, with no shortcut hiding anywhere. That is not a conjecture like P vs NP; it is a theorem.

When AlphaGo finally won in 2016, it did not solve Go. It learned to play it well enough — a profound reminder that the future of computing on impossibly hard problems is not perfect answers, but intelligent guesses. The universe of Go positions stays unsearchable; we just learned to find our way through it.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/go/Content licensed under CC BY-NC 4.0.