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 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. 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 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. 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.

Solving Othello: Related Works You Should Be Aware Of

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

AI Tries (and Fumbles) at Inflation Forecasting

Othello Is Finally Solved

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

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

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

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

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

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