著者

Ryuhei UEHARA

出版者

The Editorial Committee of the Interdisciplinary Information Sciences

雑誌

Interdisciplinary Information Sciences (ISSN:13409050)

巻号頁・発行日

pp.2022.R.06, (Released:2022-12-27)

参考文献数

112

被引用文献数

2

---

Since the 1930s, mathematicians and computer scientists have been interested in computation. While mathematicians investigate recursion theory, computer scientists investigate computational complexity based on Turing machine model to understand what a computation is. Beside them, there is another approach of research on computation, which is the investigation of puzzles and games. Once we regard the rules used in puzzles and games as the set of basic operations of computation, we can perform some computation by solving puzzles and playing games. In fact, research on puzzles and games from the viewpoint of theoretical computer science has continued without any break in the history of theoretical computer science. Sometimes the research on computational complexity classes has proceeded by understanding the tons of puzzles. The wide collection of complete problems for a specific computational complexity class shares a common property, which gives us a deep understanding of the class. In this survey paper, we give a brief history of research on computational complexities of puzzles and games with related results and trends in theoretical computer science.

著者

Amanj Khorramian Tomoko Taniguchi Takeaki Uno Ryuhei Uehara

雑誌

研究報告アルゴリズム(AL) (ISSN:21888566)

巻号頁・発行日

vol.2018-AL-168, no.2, pp.1-8, 2018-05-18

---

Othello, also known as Reversi, is a quite well known strategy board game for two players on a board of size 8 ×8. The set of all reachable patterns is not yet known for this game. In this paper, we finally obtain all reachable patterns on 5 × 6 board by developing nontrivial algorithm on a supercomputer. We observe the scale of complete search-tree is big even for a board of size 5 × 6 and parallelize a distributed frontier search using shared memory to reach the final depth of the tree. To reduce the memory requirement, the tree is horizontally compressed using a novel method, and the frontiers are maintained in a novel data-structure. Moreover, an efficient number system is proposed and utilized for representing the states of the game, and a symmetry of the states is applied during the search. We assume that the board and pattern are rotation symmetry, but we assume that the mirror symmetry gives the different pattern. Eventually, the whole tree is traversed in 2 hours by visiting 257,387,474,170 different states using random access memory shared among 576 processing cores. We aim to find specific font patterns among the states of the final depth. However, 83,175,694 of the states are located at the final depth, at which we start looking for font patterns. Before that, a set of 96 characters of size 6 × 6 is binarized, and their (5 × 6)-compatible patterns are taken for lookup by considering all possible symmetries. In this way, a font of 96 characters is designed.