Introduction

Othello — sold as Reversi long before it had a name — is one of the easiest games in the world to learn. Two players take turns dropping discs on an 8x8 board; each move must trap a line of the opponent's discs between your own, and every trapped disc flips to your color. When the board fills, whoever owns more discs wins.

The rules fit on a napkin, yet the game branches ferociously. From the opening position there are roughly 102810^{28} legal positions — far too many to ever list. For decades nobody knew the one thing every player secretly wonders: if both sides played flawlessly, who would win?

In 2023, the engineer Hiroki Takizawa answered it. After a search that pruned and verified an astronomical tree, he proved that perfect play by both sides ends in a draw — 32 discs each. Othello joined checkers in the small club of classic games that are solved.

Flip the Discs

Here is a tiny Othello endgame. It is Black to move, and only one legal move wins — every other choice throws the game away. Click a highlighted square to drop a black disc and watch the trapped white discs flip.

<p class="hint">A tiny 4x4 Othello endgame — <b>Black to move</b>. Three squares are
legal (yellow rings), but only <b>one</b> wins under perfect play; the other two lose.
Click a ring to drop a black disc and watch the trapped white discs <b>flip</b>. White
then replies with its best move, and the board fills.</p>
<div id="board" class="board"></div>
<div class="status" id="status">Black to move. Only one square wins — choose carefully.</div>
<div class="btns">
  <button id="reset" type="button" class="ghost">Reset position</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; }
.board { display: grid; grid-template-columns: repeat(4, 56px); gap: 3px;
         background: #1b6b3a; padding: 6px; border-radius: 10px; width: max-content; }
.sq { width: 56px; height: 56px; display: flex; align-items: center; justify-content: center;
      background: #2f9d5b; border-radius: 6px; }
.sq.play { cursor: pointer; box-shadow: inset 0 0 0 2px #ffd84d; }
.sq.play:hover { background: #37b369; }
.disc { width: 42px; height: 42px; border-radius: 50%; transition: transform .15s; }
.disc.b { background: radial-gradient(circle at 35% 30%, #555, #111); }
.disc.w { background: radial-gradient(circle at 35% 30%, #fff, #cfd6dd); border: 1px solid #b6bfc8; }
.disc.flip { animation: pop .25s ease; }
@keyframes pop { 0% { transform: scale(.4); } 100% { transform: scale(1); } }
.dot { width: 14px; height: 14px; border-radius: 50%; background: rgba(255,216,77,.85); }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.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 fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// A miniature Othello (Reversi) endgame on a 4x4 board, Black to move.
// Othello rule: a move is legal only if it traps one or more contiguous opponent
// discs in a straight line (8 directions) between the new disc and another disc of
// your color; all trapped discs flip. After Black moves, White answers with its
// best move (minimax over the tiny remaining tree), then the board is full.
// Exactly ONE of Black's three legal moves wins under perfect play — the same
// question ("is there a move that forces a win against every reply?") that solving the full 8x8 game answered in 2023.
const N = 4, E = 0, B = 1, W = 2;
const DIRS = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]];
// Crafted endgame. Only (0,0) wins (Black 8 - White 7); (0,1) and (0,2) lose 7-9.
const START = [
  [E, E, E, B],
  [W, W, W, B],
  [B, B, W, W],
  [W, W, W, W],
];
let grid = START.map(r => r.slice());
let locked = false; // freeze input while showing a result

const inB = (r,c) => r>=0 && r<N && c>=0 && c<N;
function flips(g, r, c, p){
  if (g[r][c] !== E) return [];
  const opp = p===B ? W : B, out = [];
  for (const [dr,dc] of DIRS){
    const line = []; let nr=r+dr, nc=c+dc;
    while (inB(nr,nc) && g[nr][nc]===opp){ line.push([nr,nc]); nr+=dr; nc+=dc; }
    if (line.length && inB(nr,nc) && g[nr][nc]===p) out.push(...line);
  }
  return out;
}
function legal(g, p){
  const m = [];
  for (let r=0;r<N;r++) for (let c=0;c<N;c++) if (flips(g,r,c,p).length) m.push([r,c]);
  return m;
}
function count(g, p){ let n=0; for (let r=0;r<N;r++) for (let c=0;c<N;c++) if (g[r][c]===p) n++; return n; }
function apply(g, r, c, p){
  const gg = g.map(x=>x.slice()); const f = flips(gg,r,c,p);
  gg[r][c] = p; for (const [fr,fc] of f) gg[fr][fc] = p; return gg;
}
// Perfect-play final disc difference (Black - White); Black maximizes, White minimizes.
function solve(g, p, passed){
  const m = legal(g, p);
  if (!m.length){ if (passed) return count(g,B)-count(g,W); return solve(g, p===B?W:B, true); }
  let best = p===B ? -99 : 99;
  for (const [r,c] of m){ const v = solve(apply(g,r,c,p), p===B?W:B, false);
    best = p===B ? Math.max(best,v) : Math.min(best,v); }
  return best;
}
function bestMove(g, p){
  const m = legal(g, p); let bm = null, bv = p===B ? -99 : 99;
  for (const [r,c] of m){ const v = solve(apply(g,r,c,p), p===B?W:B, false);
    if (p===B ? v>bv : v<bv){ bv = v; bm = [r,c]; } }
  return bm;
}

function setStatus(t, cls){ const s = document.getElementById('status'); s.textContent = t; s.className = 'status '+(cls||''); }

function render(showMoves){
  const playSet = new Set();
  if (showMoves) legal(grid, B).forEach(([r,c]) => playSet.add(r+','+c));
  const b = document.getElementById('board'); b.innerHTML = '';
  for (let r=0;r<N;r++) for (let c=0;c<N;c++){
    const sq = document.createElement('div');
    const isPlay = grid[r][c]===E && playSet.has(r+','+c);
    sq.className = 'sq'+(isPlay?' play':'');
    if (grid[r][c]===B){ const d=document.createElement('div'); d.className='disc b'; sq.appendChild(d); }
    else if (grid[r][c]===W){ const d=document.createElement('div'); d.className='disc w'; sq.appendChild(d); }
    else if (isPlay){ const dot=document.createElement('div'); dot.className='dot'; sq.appendChild(dot); }
    if (isPlay) sq.addEventListener('click', () => play(r,c));
    b.appendChild(sq);
  }
}

function finish(){
  const bc = count(grid,B), wc = count(grid,W);
  if (bc > wc) setStatus(fmt('Perfect! Black wins %bc%–%wc%. That was the only winning move.', { bc: bc, wc: wc }),'ok');
  else if (bc < wc) setStatus(fmt('Black loses %bc%–%wc%. Reset and try another square.', { bc: bc, wc: wc }),'bad');
  else setStatus(fmt('A draw, %bc%–%wc%. Reset and find the win.', { bc: bc, wc: wc }),'bad');
}

function play(r, c){
  if (locked) return;
  if (!flips(grid, r, c, B).length) return;
  grid = apply(grid, r, c, B);
  locked = true;
  render(false);
  setStatus('Black played. White is thinking…','');
  // White replies with its best move, alternating until neither side can move.
  setTimeout(() => {
    let turn = W, passed = false;
    while (true){
      const m = legal(grid, turn);
      if (!m.length){ if (passed) break; passed = true; turn = turn===B?W:B; continue; }
      passed = false;
      const mv = bestMove(grid, turn);
      grid = apply(grid, mv[0], mv[1], turn);
      turn = turn===B?W:B;
    }
    render(false);
    finish();
  }, 450);
}

document.getElementById('reset').addEventListener('click', () => {
  grid = START.map(r => r.slice()); locked = false;
  render(true); setStatus('Black to move. Only one square wins — choose carefully.','');
});
render(true);
Result
Console

This is the whole idea behind solving the game, in miniature. A computer asks, at every position, "is there a move that forces a win (or at least a draw) no matter what the opponent replies?" Here the tree is tiny and you can see the answer instantly. In the full game the same question hangs over 102810^{28} positions — which is why settling it took a colossal, carefully pruned search.

The Real Complexity

"Solved" has a precise meaning, and Othello sits at a specific rung.

  • Weakly solved (2023). Hiroki Takizawa proved the outcome of 8x8 Othello under perfect play: a draw. "Weakly" means we know the result from the standard start and a strategy to achieve it — not the perfect move in every one of the ~102810^{28} positions (that would be strongly solved, like checkers' endgame databases).
  • Why it was hard. The game tree is astronomically large. The proof leaned on minimax with alpha-beta pruning, strong heuristics, and verified search to discard the vast majority of branches without ever visiting them.
  • The general game is intractable. Othello played on an n×n board is PSPACE-complete (Iwata & Kasai, 1994). So while the fixed 8x8 board was finally crackable with enough engineering, there is no expected shortcut for the family in general — the difficulty is genuine, not an accident of size.

That gap is the lesson: a single finite instance can be conquered by sheer searching power, while the general problem behind it stays as hard as anything in PSPACE. Solving one board does not hand you an easy algorithm for all of them.

Where It Matters

"Find a strategy that wins against every reply" is a shape that shows up far beyond board games, and Othello is its clearest playground:

  • Game AI. Minimax, alpha-beta pruning and learned evaluation functions — the exact tools that solved Othello — drive engines for chess, Go and beyond.
  • Planning under an adversary. Robotics, logistics and security all ask "what is my best move if the world (or an opponent) responds in the worst way?" — a game tree in disguise.
  • Formal verification. Checking that a system can never reach a bad state, no matter what inputs arrive, is a two-player game between the verifier and the environment.
  • Knowing the limits. Othello shows the value and the boundary of brute force: one fixed board fell, but the PSPACE-complete general game warns when to stop hoping for a clean algorithm.

Understand how Othello was solved and you have met adversarial search — the engine behind chess engines and the strategy questions lurking in P vs NP.

Conclusion

For half a century the perfect outcome of Othello was an open question hiding behind trivial rules. In 2023 the answer arrived: with flawless play on both sides, the game is a draw. It took a search across an unimaginable tree, guided by clever pruning, to nail down something a child could ask.

And yet the victory is bounded. The standard 8x8 board is now settled, but Othello on an arbitrary board stays PSPACE-complete — proof that conquering one instance is not the same as taming the whole problem. The next time you flip a line of discs, remember: behind that simple click sits a tree so vast that pinning down its perfect ending was a landmark, not a footnote. See also chess and P vs NP.

Share this article

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

Comments

Loading comments...

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