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

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.