Author:
(1) Hiroki Takizawa, Preferred Networks, Inc., Chiyoda-ku, Tokyo, Japan (contact@hiroki-takizawa.name). 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). This paper is available on arxiv under CC 4.0 license. Author: (1) Hiroki Takizawa, Preferred Networks, Inc., Chiyoda-ku, Tokyo, Japan (contact@hiroki-takizawa.name). Author: Author: (1) Hiroki Takizawa, Preferred Networks, Inc., Chiyoda-ku, Tokyo, Japan (contact@hiroki-takizawa.name). Table of Links Abstract and Intro Abstract and Intro Related Works Related Works Methods Methods Results Results Discussion and Conclusions and Acknowledgements Discussion and Conclusions and Acknowledgements Additional Information and Declarations and References 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 Keywords 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. This paper is available on arxiv under CC 4.0 license. available on arxiv

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

Othello Is Finally Solved

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

AI Tries (and Fumbles) at Inflation Forecasting

The Noonification: The FBI, Apple, and the San Bernardino Massacre (10/3/2023)

A Detailed Analysis of Inter-Annotator Agreement

A Detailed Analysis on the Effectiveness of Automatic Filtering

AI-Driven Creativity: QDAIF Shines in Generating Diverse and High-Quality Texts

Breathing Life into Still Photos: Exploring Neural Motion Textures

AI Tries (and Fumbles) at Inflation Forecasting

The Noonification: The FBI, Apple, and the San Bernardino Massacre (10/3/2023)

A Detailed Analysis of Inter-Annotator Agreement

A Detailed Analysis on the Effectiveness of Automatic Filtering

AI-Driven Creativity: QDAIF Shines in Generating Diverse and High-Quality Texts

Breathing Life into Still Photos: Exploring Neural Motion Textures

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps