Is Othello solved?

The result in one table

abcdefgh

12345678

What "solved" means, exactly

Game theorists use three levels, and mixing them up is where most of the confusion on this topic comes from.

Ultra-weakly solved

You know the result of the game from the start, but you have no way to play it. Some games can be proved a draw by an argument that never names a single move.

Weakly solved

You know the result from the starting position and you have a strategy that guarantees at least that result against any defence. This is where Othello now sits.

Strongly solved

You know the correct result from every legal position, including ones reached after mistakes. Othello is not strongly solved and probably never will be, because there are far too many positions to store.

Weakly solved is the same level checkers reached in 2007, and it is also a draw. Chess and Go are not solved at any level.

How the proof was actually done

The method is not clever mathematics. It is an enormous, carefully split search.

1. Start from a known good engine. Edax is the strongest free Othello program, written by Richard Delorme. Takizawa modified version 4.4.6 rather than writing something new, which means the search was already fast and already well tested.
2. Break the game into pieces. The tree was split into roughly 1.5 billion separate sub-problems, each a position that could be handed to one machine and solved on its own.
3. Solve each piece exactly. Every sub-problem was searched to the end of the game, which is the only kind of search that proves anything. Around 1.5 x 10¹⁸ positions were examined in total.
4. Put the pieces back together. The results combine into a proof that black cannot force a win and white cannot force a win, which leaves a draw.

The whole thing ran on MN-J, a supercomputer at Preferred Networks, the Tokyo company where Takizawa works. The modified engine, the scripts and the result data were all published, on GitHub and on Zenodo, so the claim can be checked rather than taken on trust.

The smaller boards were solved first

Othello on a smaller board is a far easier problem, and both common sizes fell decades earlier. On both of them the second player wins, which is a useful antidote to the idea that moving first must be an advantage.

Feinstein's 6x6 solve took weeks of computer time in 1993 at Paderborn. Thirty years later the full size board needed a supercomputer and a distributed search. The gap between those two numbers is a good measure of how much harder each extra rank and file makes the game. More on the small board variants.

Why Othello fell and chess has not

Three things make Othello a much easier target than chess or Go, and none of them is about the game being simple to play well.

• Games are short and finite. Every move fills a square, so a game lasts at most sixty moves and cannot repeat a position or loop. Chess games can, in principle, run for hundreds of moves, and Go boards can return to earlier shapes.
• The end is cheap to calculate. The last dozen empty squares can be searched to the finish in a fraction of a second, so every line of the proof terminates in a hard answer rather than an estimate. That is why the game shrinks so fast once a position is deep enough.
• A position is tiny. Two 64-bit numbers describe the whole board, so billions of positions can be stored, hashed and compared without difficulty.

Chess has none of those properties, and Go has a board with 361 points instead of 64. Both remain far out of reach, and are likely to stay there.

What the proof does not give you

This is the part that gets overstated most often.

• It is not a lookup table. You cannot download a file that tells you the best move in your position. A weak solution only covers the lines needed to prove the starting result.
• It does not make engines perfect. Edax and every other program still search, still use an evaluation function, and still play the midgame by judgement rather than by proof.
• It does not help you at the board. Perfect play runs for around sixty moves of exact calculation. No human can follow it, and no human opponent will play the drawing line at you.
• It does not mean the first move is worthless in practice. It means it is worth nothing against perfect defence. Against a person, black still gets to choose the shape of the game. Black's four first moves.

How close does the computer on this site get?

Not to a proof of the whole game, but to a proof of the ending. The Hard level here searches the midgame heuristically, then switches to an exact solver once around sixteen to twenty squares are empty. From that point it plays the finish perfectly, and it will tell you the final score before it happens. That is the same kind of search Takizawa ran, on a much smaller slice of the game. How the engine works, or play it.

Sources

• Hiroki Takizawa, "Othello is Solved", arXiv:2310.19387, submitted 30 October 2023, revised January 2024.
• The modified Edax used for the proof, published with the paper.
• Edax, by Richard Delorme, the original engine.
• Joel Feinstein's 6x6 solution, 1993.
• Computer Othello on Wikipedia, for the 4x4 and 6x6 results and the wider program history.
• Solved game, for the ultra-weak, weak and strong definitions.