The board game Othello, played with Go pieces on an 8×8 uncheckered board, is solved. Perfect play leads to a draw, writes Hiroki Takizawa.
The game of Othello is one of the world’s most complex and popular games that has yet to be computationally solved. Othello has roughly ten octodecillion (10 to the 58th power) possible game records and ten octillion (10 to the 28th power) possible game position. The challenge of solving Othello, determining the outcome of a game with no mistake made by either player, has long been a grand challenge in computer science. This paper announces a significant milestone: Othello is now solved, computationally proved that perfect play by both players lead to a draw. Strong Othello software has long been built using heuristically designed search techniques. Solving a game provides the solution which enables software to play the game perfectly. ….
In this paper, we announce that we have weakly solved Othello (8 × 8 board). The game-theoretic value of the initial
position turned out to be a draw (an optimal game record and the final result are shown in Figure 1). This is not
surprising, because human Othello experts have been predicting it. Another notable point is that the number of positions we needed to explore to get the strict solution was far less than the number of positions predicted in previous research.
Checkers was solved years ago. Go is solved on a 7×7 board, but the standard 19×19 board is 145 orders of magnitude more complex. Takizawa unexpectedly claiming to have clocked Othello suggests things are moving fast.
Solving Chess seems conceivable, but experts can’t even agree on what exponential degree of computing power might be required. If “draw” seems too obvious, the interesting part is which opening leads to the solution, and any tactical snarls to consider along the way. My bet, though, is that it’s going to be tedious positional entropy from outset to finish, proving once again that anything interesting a human might do is, technically, a blunder.
The paper’s release is timed well, as the Othello world championship is underway in Rome.