Solving Othello: Related Works You Should Be Aware Of
:::info
Author:
(1) Hiroki Takizawa, Preferred Networks, Inc., Chiyoda-ku, Tokyo, Japan ([email protected]).
:::
Table of Links
Abstract and Intro
Related Works
Methods
Results
Discussion and Conclusions and Acknowledgements
Additional Information and Declarations and References
2 Related Works
2.1 Solved Games
To the best of our knowledge, the latest game solved prior to this study as a grand challenge is checkers [10]. However, many nontrivial games have been solved, including Connect Four [8], Qubic [8], Go-Moku [8], Nine Men’s Morris [11], and Awari [12]. The difficulty of solving these games largely depends on the number of positions or situations in the game. Solving a game not only reveals its outcome but can also be useful in creating puzzles based on that game [9].
2.2 Solving Technique
The algorithms used to solve games have been extensively studied, and they are chosen based on the purpose and nature of the game. For weak solutions, alpha-beta search [13] is often used, while retrograde analysis [14] is frequently used for strong solutions. Additionally, algorithms like depth-first proof-number (df-pn) search [15, 16], which is based on proof-number (pn) search [17], have been developed to solve puzzles with very long solution sequences. In our study, we utilized alpha-beta search because our goal was to obtain a weak solution.
2.3 Algorithms for Parallel Search
Alpha-beta search is an algorithm that sequentially performs depth-first search of a game graph, and naive parallelization does not improve search efficiency very much. Many algorithms have been developed for efficient parallelization. Young Brothers Wait Concept (YBWC) [18] and Lazy SMP [19] are popular methods for shared memory environments (e.g., a single computer). Algorithms suited for distributed memory environments (e.g., supercomputers or cloud computing) might include Asynchronous Parallel Hierarchical Iterative Deepening (APHID) [20] and ABDADA [21].
\
However, distributed memory environments greatly differ due to various factors including the bandwidth and latency of interconnects between nodes, and thus the appropriate algorithms may also differ. Therefore, developers who work with current or future distributed memory environments may need to choose or develop algorithms that are appropriate for those environments.
\
:::info
This paper is available on arxiv under CC 4.0 license.
:::
\
Welcome to Billionaire Club Co LLC, your gateway to a brand-new social media experience! Sign up today and dive into over 10,000 fresh daily articles and videos curated just for your enjoyment. Enjoy the ad free experience, unlimited content interactions, and get that coveted blue check verification—all for just $1 a month!
Account Frozen
Your account is frozen. You can still view content but cannot interact with it.
Please go to your settings to update your account status.
Open Profile Settings