Othello Is Finally Solved

Table of Links

Abstract and Intro

Related Works

Methods

Results

Discussion and Conclusions and Acknowledgements

Additional Information and Declarations and References

ABSTRACT

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 positions. 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.

It is 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 a solution that enables the software to play the game perfectly.

Keywords Othello · Reversi · Games · alpha-beta search

1 Introduction

Mastering pure strategy games like chess has been considered a symbol of human intelligence. Since the dawn of computer science, this has been a subject of artificial intelligence (AI) research. For example, there were early consideration by Charles Babbage [1] and Claude Shannon [2]. To date, with the enhancement of machine learning techniques and computing capabilities, superhuman-strength software has been developed for some of the most popular games, including chess [3], Go [4], Shogi (Japanese chess) [5, 6], and Othello [7].

However, these superhuman-strength programs cannot perfectly solve the games.

Perfectly solving these games (called games of perfect information) means to determine the final result, which is the outcome of the game under perfect play by both players; this result is termed the “game-theoretic value”. Solved games are classified into at least three types [8, 9]. The most basic type is called ultra-weakly solved games. In this category, we know the game-theoretic value of the initial board position but not any actual winning strategy.

Next, in the case of weakly solved games, we know not only the game-theoretic value of the initial position but also a strategy for both players to achieve this value from the initial position under reasonable computational resources. For example, checkers was weakly solved in this sense [10]. At more comprehensive level, we have strongly solved games, where the outcomes are calculated for all possible position that might arise during game-play.

Othello (also called Reversi) is a highly popular game due to its deep strategic nature. It was invented in the 19th century in England, and in the 20th century, the current format of Othello became widespread in Japan and is now played all over the world. The annual World Championships have been held since 1977, which demonstrates its widespread appeal across the globe.

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 already predicted it. Another notable point is that the number of positions we needed to explore to get the strict solution was far less that predicted in previous research[8]. We believe this is due to our sophisticated search algorithm configuration.

The Othello result is a monumental achievement for humanity, demonstrating the remarkable advances in computer science and AI technology. Solving Othello has been one of the grand challenges for AI. Over recent decades, AI capabilities have expanded owing to advances in both computing power and algorithms, including enhanced search techniques.

In our study, even with the use of the latest computer cluster, solving Othello remained a significant hurdle. Our breakthrough came by improving search efficiency and modifying the latest Othello software.

This paper describes our method to solve Othello, several findings as results, and implications of this research. The raw data and programs to reproduce the results are available on GitHub, Zenodo, and figshare (see Data Availability section).