Othello Is Finally Solved

cover
30 May 2024

Author:

(1) Hiroki Takizawa, Preferred Networks, Inc., Chiyoda-ku, Tokyo, Japan (contact@hiroki-takizawa.name).

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

Figure 1: (Left) The initial board position of 8 × 8 Othello. (Right) A diagram of an optimal game record designated by our study. The game record is “F5D6C3D3 C4F4F6F3 E6E7D7C5 B6D8C6C7 D2B5A5A6 A7G5E3B4 C8G6G4C2 E8D1F7E2 G3H4F1E1 F2G1B1F8 G8B3H3B2 H5B7A3A4 A1A2C1H2 H1G2B8A8 G7H8H7H6”. The numbers in the stones indicate the order of moves, and the colors of stones indicate the final result. Our study confirms that if a deviation from this record occurs at any point, our software, playing as the opponent, is guaranteed a draw or win.

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


This paper is available on arxiv under CC 4.0 license.