The maximum number of legal moves of Othello in reachable positions is 33

Takizawa, Hiroki

doi:10.51094/jxiv.480

##article.authors##

Takizawa, Hiroki Preferred Networks, Inc.

DOI:

https://doi.org/10.51094/jxiv.480

キーワード:

Othello、 Branching Factor、 SAT solver、 SMT solver

抄録

We prove that the maximum number of moves among all reachable positions in a game of Othello is 33. We also construct a game record to achieve such a position. Additionally, including positions that are not reachable from the initial position, we prove that this maximum is 34 and construct such a position. We utilized Satisfiability (SAT) and Satisfiability Modulo Theories (SMT) solvers to obtain these computational proofs. These new findings not only clarify properties of the game of Othello, but also provide hints for the efficient and robust implementation of Othello software, and also present practical examples of using SAT and SMT solvers.

利益相反に関する開示

The author declares that there are no competing interests.

ダウンロード *前日までの集計結果を表示します

ダウンロード実績データは、公開の翌日以降に作成されます。

引用文献

Michael Buro. How machines have rearnea to play othello. IEEE intelligent systems & their applications, 14(6):12–14, 1999.

Richard Delorme. edax-reversi. https://github.com/abulmo/edax-reversi, 2021. Last retrieved 2023-07-07.

Bruce Abramson. Control strategies for two-player games. ACM Comput. Surv., 21(2):137–161, jun 1989.

Armin Biere and Mathias Fleury. Gimsatul, IsaSAT and Kissat entering the SAT Competition 2022. In Tomas Balyo, Marijn Heule, Markus Iser, Matti Järvisalo, and Martin Suda, editors, Proc. of SAT Competition 2022 – Solver and Benchmark Descriptions, volume B-2022-1 of Department of Computer Science Series of Publications B, pages 10–11. University of Helsinki, 2022.

Claude E Shannon. Xxii. programming a computer for playing chess. The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 41(314):256–275, 1950.

Murray Campbell, A.Joseph Hoane, and Feng hsiung Hsu. Deep blue. Artificial Intelligence, 134(1):57–83, 2002.

Jonathan Schaeffer, Robert Lake, Paul Lu, and Martin Bryant. Chinook the world man-machine checkers champion. AI magazine, 17(1):21–21, 1996.

David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484–489, 2016.

Tomoyuki Kaneko and Takenobu Takizawa. Computer shogi tournaments and techniques. IEEE Transactions on Games, 11(3):267–274, 2019.

David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap, Karen Simonyan, and Demis Hassabis. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419):1140–1144, 2018.

Gnu general public license, version 3. http://www.gnu.org/licenses/gpl.html, June 2007. Last retrieved 2020-01-01.

Edward M Reingold, Jurg Nievergelt, and Narsingh Deo. Combinatorial algorithms: theory and practice. Prentice Hall College Div, 1977.

primenumber. issen/src/move_generator.cpp. https://github.com/primenumber/issen/blob/72f450256878094ffe90b75f8674599e6869c238/src/move_generator.cpp, 2016. Last retrieved 2023-07-07.

Leonardo De Moura and Nikolaj Bjørner. Z3: An efficient smt solver. In International conference on Tools and Algorithms for the Construction and Analysis of Systems, pages 337–340. Springer, 2008.8