 |
| The perfect game |
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.
Update (11/12/23): I uploaded a video playing out the game.
(Bill) I am also surprised that Othello is a draw. But is it a draw for other sized boards? What is known about n=1,2,3,4,5,6,7?
ReplyDeleteLance- is it plausbile that you would have gone into AI-game playing rather than theory (I would think yes- what fields we go into can be artibrary) That you would have gotten the Othello result (i would think no- thats to particular).
The game starts with a central cross cut of 2 black and 2 white stones. This allows the first move to flip some stones, as is required for every move. This requires boards of even size at least 4, So you could ask what is known about n=4 and n=6.
Deleten=2 is presumably a draw. If n is odd, then the rules would need some changing. The n=1 case especially...
ReplyDelete"n=2 is presumably a draw."
DeleteThis is one of the most exquisite examples of deadpan humor that I've ever seen. Flipping brilliant.
Played this for hours on my Atari. Expert level still beat me sometimes...
ReplyDeleteThe line above is only one possible out of millions. The optimal lines form a draw tree. For example, both the diagonal and the perpendicular openings lead to draws in optimal play.
ReplyDelete