Othello. Solved.

Back in the 1980s, a high school friend and I created Excalibur, a computer othello program that I've posted about before. Even on an OG IBM PC we could play a perfect endgame from 14 moves out. There's been a lot of Moore's law since then and I've wondered if it could be possible to determine for sure the winner of an Othello game with perfect play. And now we know the answer: No, because it is a draw. 

Recently Hiroki Takizawa announced that he had solved Othello, originally known as Reversi. It's a simple game where two players, black and white, alternately play pieces of their color. When the black player moves, all the white pieces between the played piece and other black pieces flip to black. The reverse when white plays. Whomever has the most pieces of their color at the end wins.

Takizawa solved Othello with massive computing power and considerable alpha-beta pruning. The basic idea of alpha-beta pruning is that if you have a move that guarantees a win (or a draw in this case), you don't need to look at other moves. He builds his algorithm on a variation of a program Edax that could do perfect play from 36 moves out. I should acknowledge that this work has not yet been independently verified or refereed.

The resulting perfect play is in the diagram above. Takizawa checked that any deviation from this play would lead to either a draw or loss for the deviating player. Technically this is called "weakly solving" Othello where "strongly solving" means giving an algorithm that plays perfectly from any reachable position. Weakly solving is strong enough for me. 

I'm surprised it is a draw. There are so many possible values for the difference between white and black pieces at the end and Othello is not symmetric--it really matters who plays first. So it seems quite a coincidence that perfect play ends up perfectly even. But now we know.

Thanks to Jon Katz for pointing us to this paper.