paint-brush
Solving Othello: Related Works You Should Be Aware Ofby@precedent
190 reads

Solving Othello: Related Works You Should Be Aware Of

tldt arrow

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
Precedent Publishing House HackerNoon profile picture

Author:

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

Abstract and Intro

Related Works

Methods

Results

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.

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.


This paper is available on arxiv under CC 4.0 license.