A board you can't brute-force

Chess looks small. Sixty-four squares, thirty-two pieces, a handful of rules a child can learn in an afternoon. So why did it take computers half a century to beat the best humans — and why does it still matter to the theory of computation?

The answer is the game tree. From the starting position White has 20 legal moves. Black replies with 20. After just a few turns the number of distinct games explodes. Claude Shannon estimated in 1950 that the number of possible chess games is around 1012010^{120} — the "Shannon number." For comparison, there are only about 108010^{80} atoms in the observable universe. You could not write down all chess games even if every atom were a hard drive.

This is the heart of computational complexity: a problem can be tiny to describe and yet astronomically large to solve. Chess is the friendliest doorway into that idea — and a perfect place to watch a clever algorithm beat brute force.

Play a machine that never loses

You can't brute-force chess, but you can brute-force its little cousin: tic-tac-toe. The same algorithm that powers chess engines — minimax — fits a 3×3 board in a few lines of code, and there it plays perfectly. Try to beat it. You can't: the best you can force is a draw.

<p class="hint">You are <b>X</b>. The machine is <b>O</b> and plays with <b>minimax</b> — it searches the whole game tree and always picks an optimal move. Go ahead, try to win. You can't: the best you can force is a draw.</p>
<div id="board" class="board"></div>
<p id="status" class="status">Your move — you are X.</p>
<div class="stats">
  <span>Positions the machine examined last move: <b id="nodes">0</b></span>
</div>
<button id="reset" class="btn">Reset game</button>

* { box-sizing: border-box; }
.hint { font-size: 14px; color: #556; line-height: 1.5; }
.board {
  display: grid; grid-template-columns: repeat(3, 72px);
  grid-template-rows: repeat(3, 72px); gap: 6px; margin: 14px 0; justify-content: center;
}
.cell {
  display: flex; align-items: center; justify-content: center;
  font-size: 40px; font-weight: 700; background: #f3f5f8;
  border: 2px solid #d7dee6; border-radius: 10px; cursor: pointer;
  user-select: none; transition: background .15s;
}
.cell:hover { background: #e7ecf2; }
.cell.x { color: #1f6feb; }
.cell.o { color: #c0392b; }
.cell.taken { cursor: default; }
.status { text-align: center; font-weight: 600; color: #334; min-height: 22px; }
.stats { text-align: center; font-size: 13px; color: #667; margin-bottom: 10px; }
.btn {
  display: block; margin: 0 auto; padding: 8px 18px; font-size: 14px;
  border: none; border-radius: 8px; background: #1f6feb; color: #fff; cursor: pointer;
}
.btn:hover { background: #1a5fd0; }

// Tic-tac-toe with a perfect minimax opponent.
// 'X' = human, 'O' = machine. The machine maximizes its own outcome
// assuming the human plays optimally against it.
const HUMAN = 'X', AI = 'O';
let board = Array(9).fill('');
let over = false;
let nodes = 0;

const LINES = [
  [0,1,2],[3,4,5],[6,7,8], // rows
  [0,3,6],[1,4,7],[2,5,8], // cols
  [0,4,8],[2,4,6]          // diagonals
];

function winner(b) {
  for (const [a,c,d] of LINES) {
    if (b[a] && b[a] === b[c] && b[a] === b[d]) return b[a];
  }
  return b.includes('') ? null : 'draw';
}

// minimax: returns a score from the machine's point of view.
// +10 (minus depth) if AI wins, -10 (plus depth) if human wins, 0 for a draw.
// Subtracting depth makes it prefer faster wins and slower losses.
function minimax(b, isAI, depth) {
  const w = winner(b);
  if (w === AI)    return 10 - depth;
  if (w === HUMAN) return depth - 10;
  if (w === 'draw') return 0;

  let best = isAI ? -Infinity : Infinity;
  for (let i = 0; i < 9; i++) {
    if (b[i] !== '') continue;
    nodes++;                       // count every position we explore
    b[i] = isAI ? AI : HUMAN;
    const score = minimax(b, !isAI, depth + 1);
    b[i] = '';
    best = isAI ? Math.max(best, score) : Math.min(best, score);
  }
  return best;
}

function bestMove() {
  nodes = 0;
  let move = -1, bestScore = -Infinity;
  for (let i = 0; i < 9; i++) {
    if (board[i] !== '') continue;
    board[i] = AI;
    const score = minimax(board, false, 0);
    board[i] = '';
    if (score > bestScore) { bestScore = score; move = i; }
  }
  return move;
}

const boardEl = document.getElementById('board');
const statusEl = document.getElementById('status');
const nodesEl = document.getElementById('nodes');

function render() {
  boardEl.innerHTML = '';
  board.forEach((v, i) => {
    const c = document.createElement('div');
    c.className = 'cell' + (v ? ' taken ' + v.toLowerCase() : '');
    c.textContent = v;
    if (!v && !over) c.onclick = () => play(i);
    boardEl.appendChild(c);
  });
}

function play(i) {
  if (over || board[i]) return;
  board[i] = HUMAN;
  let w = winner(board);
  if (!w) {
    const m = bestMove();
    if (m >= 0) board[m] = AI;
    nodesEl.textContent = nodes;
    w = winner(board);
  }
  render();
  if (w === HUMAN)      { statusEl.textContent = 'You win?! (a bug — report it!)'; over = true; }
  else if (w === AI)    { statusEl.textContent = 'The machine wins.'; over = true; }
  else if (w === 'draw'){ statusEl.textContent = 'Draw — the best you can do.'; over = true; }
  else statusEl.textContent = 'Your move — you are X.';
}

document.getElementById('reset').onclick = () => {
  board = Array(9).fill(''); over = false; nodes = 0;
  nodesEl.textContent = '0';
  statusEl.textContent = 'Your move — you are X.';
  render();
};

render();
Result
Console

Minimax explores the game tree assuming both players play optimally — the machine maximizes its outcome while assuming you will minimize it. Edit the code, watch how it picks each move, and notice the counter: even this trivial game has hundreds of positions. Now multiply that by the chess explosion.

The hard part

The naive game tree for chess is far too big to search. Two ideas tame it:

  • Depth limits + evaluation. Engines don't search to the end of the game. They look a fixed number of moves ahead and score the resulting position with a heuristic (material, king safety, mobility). Good evaluation turns an impossible search into a deep-but-finite one.

  • Alpha-beta pruning. If one reply already refutes a move, you don't need to examine the rest. Pruning can cut the effective branching factor roughly to its square root — turning depth 8 into the cost of depth 4. This single trick is what made 1990s engines like Deep Blue competitive.

But heuristics are a workaround, not a verdict on difficulty. What does theory say about chess itself? Generalized chess — played on an n×n board with proportionally many pieces — is EXPTIME-complete. That is a stronger statement than "NP-hard": EXPTIME-complete problems provably require exponential time; there is no polynomial algorithm, not even in principle (unlike P vs NP, which is still open). Chess isn't hard because we haven't been clever enough. It is hard as a mathematical fact.

The standard 8×8 board is finite, so in a literal sense chess is "solvable" — but the constant is so enormous the distinction is academic. Checkers (8×8) was solved in 2007 after 18 years of computation; chess remains far out of reach.

Where it matters

Game-tree search is not just for games:

  • Adversarial AI. Minimax and its modern successor — Monte Carlo Tree Search, the engine behind AlphaGo and AlphaZero — drive decision-making whenever an opponent reacts to you: negotiation bots, security games, automated trading.

  • Planning under an adversary. Robotics and logistics use the same "assume the worst response" reasoning to stay robust.

  • Benchmarks for machine intelligence. Chess (1997, Deep Blue) and Go (2016, AlphaGo) were milestones precisely because brute force was impossible — they forced the invention of search heuristics and, later, self-learning neural networks.

The arc from Deep Blue (handcrafted evaluation + deep search) to AlphaZero (a network that learned chess from self-play in hours) is the story of how we trade human-written heuristics for learned ones — without ever escaping the exponential tree underneath.

Small rules, infinite depth

Chess is the perfect first lesson in complexity: rules you can state in a paragraph, a search space larger than the universe, and a provable wall — EXPTIME — that no amount of cleverness removes. We didn't beat chess by searching everything. We beat it by searching smartly: depth limits, evaluation functions, pruning, and finally learning.

That pattern — can't compute everything, so approximate well — is the same one behind the traveling salesman, data compression, and nearly every hard problem on kipu. Chess just makes it visible on 64 squares.

Share this article

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

Comments

Loading comments...

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