256 reads

Solving Othello: Related Works You Should Be Aware Of

by Precedent Publishing HouseMay 31st, 2024

Too Long; Didn't Read

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 is often used, while retrograde analysis is frequently used for strong solutions. Young Brothers Wait Concept (YBWC) and Lazy SMP are popular methods for shared memory environments. Algorithms suited for distributed memory environments (e.g., supercomputers or cloud computing) might include ABDADA.

featured image - Solving Othello: Related Works You Should Be Aware Of

‘a reversi board on a table with other board games behind it’ Image created by HackerNoon AI Image Generator

Author:

(1) Hiroki Takizawa, Preferred Networks, Inc., Chiyoda-ku, Tokyo, Japan ([email protected]).

Table of Links

Discussion and Conclusions and Acknowledgements

Additional Information and Declarations and References

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.