| Item type |
SIG Technical Reports(1) |
| 公開日 |
2018-05-18 |
| タイトル |
|
|
タイトル |
Othello Font |
| タイトル |
|
|
言語 |
en |
|
タイトル |
Othello Font |
| 言語 |
|
|
言語 |
eng |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_18gh |
|
資源タイプ |
technical report |
| 著者所属 |
|
|
|
University of Kurdistan |
| 著者所属 |
|
|
|
Japan Advanced Institute of Science and Technology |
| 著者所属 |
|
|
|
National Institute of Informatics |
| 著者所属 |
|
|
|
Japan Advanced Institute of Science and Technology |
| 著者所属(英) |
|
|
|
en |
|
|
University of Kurdistan |
| 著者所属(英) |
|
|
|
en |
|
|
Japan Advanced Institute of Science and Technology |
| 著者所属(英) |
|
|
|
en |
|
|
National Institute of Informatics |
| 著者所属(英) |
|
|
|
en |
|
|
Japan Advanced Institute of Science and Technology |
| 著者名 |
Amanj, Khorramian
Tomoko, Taniguchi
Takeaki, Uno
Ryuhei, Uehara
|
| 著者名(英) |
Amanj, Khorramian
Tomoko, Taniguchi
Takeaki, Uno
Ryuhei, Uehara
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
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. |
| 論文抄録(英) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
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. |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AN1009593X |
| 書誌情報 |
研究報告アルゴリズム（AL）
巻 2018-AL-168,
号 2,
p. 1-8,
発行日 2018-05-18
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
2188-8566 |
| Notice |
|
|
|
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-AL18168002.pdf (3.3 MB)
