著者

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.

著者

Yannan Hu Hideki Hashimoto Shinji Imahori Takeaki Uno Mutsunori Yagiura

出版者

日本オペレーションズ・リサーチ学会

雑誌

日本オペレーションズ・リサーチ学会論文誌 (ISSN:04534514)

巻号頁・発行日

vol.59, no.1, pp.110-129, 2016 (Released:2016-02-02)

参考文献数

17

被引用文献数

2

---

This paper focuses on a two-dimensional strip packing problem where a set of arbitrarily shaped rectilinear blocks need be packed into a larger rectangular container without overlap. A rectilinear block is a polygonal block whose interior angles are either 90∘or 270∘. This problem involves many industrial applications, such as VLSI design, timber/glass cutting, and newspaper layout. We generalized a bottom-left and a best-fit algorithms to the rectilinear block packing problem in our previous paper. Based on the analysis of the strength and weakness of these algorithms, we propose a new construction heuristic algorithm called the partition-based best-fit algorithm (PBF algorithm), which takes advantages of both the bottom-left and the best-fit algorithms. The basic idea of the PBF algorithm is that it partitions all the items into groups and then packs the items in a group-by-group manner. The best-fit algorithm is taken as the internal tactics for each group. The proposed algorithm is tested on a series of instances, which are generated from benchmark instances. The computational results show that the proposed algorithm significantly improves the performance of the existing construction heuristic algorithms and is especially effective for the instances having large differences in the sizes of given shapes.