Othello Solved

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

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">{{hint}}</p>
<div id="board" class="board"></div>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="reset" type="button" class="ghost">{{btn_reset}}</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; }

// Code not found

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 $10^{28}$ positions — which is why settling it took a colossal, carefully pruned search.

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

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

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.