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 5 Discussion and Conclusions We conclude that our study has weakly solved Othello, although we recognize that our achievement is just above the criteria for weakly solving. For certain borderline positions with 36 empty squares, Edax requires a large amount of computation to determine the game-theoretic value and corresponding move. However, given the continuing advances in personal computers, it is reasonable to conclude that our approach requires only reasonable computational resources. By providing an additional “opening” book for these positions with 35 or fewer empty squares, we could further reduce the computational demand. However, to expedite our announcement, we opted against computing additional books in this study. Nonetheless, there may be interest among Othello enthusiasts for software that can determine the best move using fewer computational resources. As Figure 3 indicates, many of our calculations to weakly solve Othello were devoted to positions where, according to the estimation, there is a clear advantage in terms of winning or losing. This indicates that one cannot claim a pseudo-solution by not proving positions whose estimated game-theoretic value exceeds any threshold. As Figure 3 implies, for positions that were expected to have a significant difference in scores, there were some in which a solving by Edax took a large amount of time. It is possible that the systematic and significant errors in Edax’s function to estimate the game-theoretic value from a position (called the static evaluation function), especially for positions unlikely to appear in actual games, are the reason for this. Regarding this issue, while it can be addressed by preparing an additional opening book, there is also potential for retraining or improving the design of the static evaluation function. We recognize that some readers may be skeptical about the validity of computational proofs. Naturally, computational errors due to CPU or memory faults cannot be entirely ruled out. However, as the vast majority of calculations were executed on a computer cluster with ECC memory, we believe the results to be nearly indisputable. Moreover, even if a computational error were present, the chance of overturning our conclusion of a final draw is extremely low. If any errors are detected, they can be easily recalculated using the publicly released software. To the best of our knowledge, no category in between weakly and strongly solving has been proposed. We considered strongly solving Othello is intractable and aimed for a weak solution. We have created software that will always achieve a draw or win to achieve the criteria for weakly solving. If the opponent makes a blunder, however, we do not guarantee that the software capitalizes on it. Although strongly solving the game may be intractable, developing software that consistently makes the best move represents a challenge that lies between weak and strong solving, and is likely to attract widespread interest. Therefore, we would propose to call this intermediate category "semi-strong solving". This study does not achieve semi-strong solving of Othello; this remains as future work. Considering the game’s popularity and estimated size of the search space, we speculate that chess might be the next weakly solved grand challenge. However, because the search space of chess is very large, not only improvements in computational power but also theoretical breakthroughs might be necessary. We hope that this study will inspire readers and contribute to significant advancements in future computer science. Acknowledgments The author gratefully thanks members of Preferred Networks Inc., including Dr. Kenta Oono, Dr. Kohei Hayashi, Dr. Masanori Koyama, and Dr. Shin-ichi Maeda, for their useful discussions and encouragement. Parts of this study, especially the majority of the calculations, were conducted during the author’s 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. The author gratefully thanks the company for having the rule. 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 5 Discussion and Conclusions We conclude that our study has weakly solved Othello, although we recognize that our achievement is just above the criteria for weakly solving. For certain borderline positions with 36 empty squares, Edax requires a large amount of computation to determine the game-theoretic value and corresponding move. However, given the continuing advances in personal computers, it is reasonable to conclude that our approach requires only reasonable computational resources. By providing an additional “opening” book for these positions with 35 or fewer empty squares, we could further reduce the computational demand. However, to expedite our announcement, we opted against computing additional books in this study. Nonetheless, there may be interest among Othello enthusiasts for software that can determine the best move using fewer computational resources. As Figure 3 indicates, many of our calculations to weakly solve Othello were devoted to positions where, according to the estimation, there is a clear advantage in terms of winning or losing. This indicates that one cannot claim a pseudo-solution by not proving positions whose estimated game-theoretic value exceeds any threshold. As Figure 3 implies, for positions that were expected to have a significant difference in scores, there were some in which a solving by Edax took a large amount of time. It is possible that the systematic and significant errors in Edax’s function to estimate the game-theoretic value from a position (called the static evaluation function), especially for positions unlikely to appear in actual games, are the reason for this. Regarding this issue, while it can be addressed by preparing an additional opening book, there is also potential for retraining or improving the design of the static evaluation function. We recognize that some readers may be skeptical about the validity of computational proofs. Naturally, computational errors due to CPU or memory faults cannot be entirely ruled out. However, as the vast majority of calculations were executed on a computer cluster with ECC memory, we believe the results to be nearly indisputable. Moreover, even if a computational error were present, the chance of overturning our conclusion of a final draw is extremely low. If any errors are detected, they can be easily recalculated using the publicly released software. To the best of our knowledge, no category in between weakly and strongly solving has been proposed. We considered strongly solving Othello is intractable and aimed for a weak solution. We have created software that will always achieve a draw or win to achieve the criteria for weakly solving. If the opponent makes a blunder, however, we do not guarantee that the software capitalizes on it. Although strongly solving the game may be intractable, developing software that consistently makes the best move represents a challenge that lies between weak and strong solving, and is likely to attract widespread interest. Therefore, we would propose to call this intermediate category "semi-strong solving". This study does not achieve semi-strong solving of Othello; this remains as future work. Considering the game’s popularity and estimated size of the search space, we speculate that chess might be the next weakly solved grand challenge. However, because the search space of chess is very large, not only improvements in computational power but also theoretical breakthroughs might be necessary. We hope that this study will inspire readers and contribute to significant advancements in future computer science. Acknowledgments The author gratefully thanks members of Preferred Networks Inc., including Dr. Kenta Oono, Dr. Kohei Hayashi, Dr. Masanori Koyama, and Dr. Shin-ichi Maeda, for their useful discussions and encouragement. Parts of this study, especially the majority of the calculations, were conducted during the author’s 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. The author gratefully thanks the company for having the rule. 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.

We Solved Othello... But What Does This Mean?

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

AI Tries (and Fumbles) at Inflation Forecasting

Othello Is Finally Solved

Solving Othello: Related Works You Should Be Aware Of

The Results of Our Othello Experiment: How We Solved the Game

Othello Is Solved: But If You're Curiousity Is Still Running Rampant, Check Out These References

10 Tips for Using Diagrams to Ace The System Design Interview

AI Tries (and Fumbles) at Inflation Forecasting

Othello Is Finally Solved

Solving Othello: Related Works You Should Be Aware Of

The Results of Our Othello Experiment: How We Solved the Game

Othello Is Solved: But If You're Curiousity Is Still Running Rampant, Check Out These References

10 Tips for Using Diagrams to Ace The System Design Interview

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps