Go

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 × $10^{170}$ legal positions — vastly more than the number of atoms in the observable universe (about $10^{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.

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">{{hint}}</p>
<div class="ctrl">
  <label>{{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>{{label_depth}} <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>{{stat_branching}}</span><b id="bf">25</b></div>
  <div class="row"><span>{{stat_positions}}</span><b id="nodes">—</b></div>
  <div class="row big" id="verdict">{{press_count}}</div>
</div>
<div class="btns">
  <button id="count" type="button">{{btn_count}}</button>
  <button id="check" type="button" class="ghost">{{btn_check}}</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; }

// Code not found

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.

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 $10^{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.

"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.

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.