The board game Othello, also known as Reversi as it played by reversing the colors of black and white disks, has been solved using alpha-beta pruning. Given "perfect play", that is a situation in which neither player makes a mistake, the outcome will always be a draw.

Solving board games has a long tradition in computer science and many students are familiar with learning about alpha beta pruning by solving, i.e. determining the outcome of, tic-tac-toe and discovering that it is a game in which the player who goes first always wins.

With only a 3x3 grid, tic-tac-toe is a trivial game to solve, but others have required more effort. For example, the game of Connect 4 on a 6x7 grid has 4,531,985,219,092 possible positions. It was solved in 1988, revealing again that the player who goes first has the advantage and can always force a win. 

Checkers, with 500 billion billion positions, was solved in 2007 when computer scientists showed that, if both sides play perfectly, the game is always drawn.

Othello uses 64 disks and using figures given the arXiv paper by Hiroki Takizawa titled "Othello is Solved" it has roughly ten octodecillion (10 to the 58th power) possible game records and ten octillion (10 to the 28th power) possible game positions, making it the largest game to be solved to date. Like Checkers, if both sides play perfectly, the game is always drawn.

To come to this conclusion Takizawa built his algorithm on a variation of an open source Othello-playing program called Edax that can do perfect play from 36 moves out together with considerable alpha-beta pruning.

This is the optimal game and the study confirms that if a deviation occurs at any point, the software, playing as the opponent, is guaranteed a draw or a win:

Takizawa needed massive computing power and in the arXiv paper explains that the majority of the calculations were conducted during his work time at Preferred Networks Inc. This was made possible by the company’s 20-percent rule, which allows employees to dedicate 20 percent of their work time to pursue their own ideas and projects. In addition Preferred Networks let him run his program on its supercomputing cluster called MN-J. This cluster includes MN-3, which in 2020 was ranked the most powerful supercomputer in the world in terms of energy efficiency, and is currently ranked 11th.  

It probably isn't surprising that this result comes from Japan where the modern version of the game was patented in 1971 and a national Othello championship was established in 1973. In 2019 an online version of the game called "the weakest AI Othello" became an instant hit . Programmed by Takuma Yoshida to avoid strong tiles and see human victory as its own success it ensures that the human opponent always wins.

More Information

Othello is Solved by Hiroki Takizawa

Related Articles

Number Of Legal Go Positions Finally Worked Out

Rubik's cube - the order of God's Number

No 16-Clue Sudoku!

The Chaos Within Sudoku - A Richter Scale

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info