A Parallel Algorithm for Solving Hard Tsume-Shogi Problems¹

Article type: Research Article

Authors: Nakayama, Yasuichi^{; *} | Akazawa, Tadafumi^{; *} | Noshita, Kohei^{; *}

Affiliations: Tokyo, Japan

Note: [1] A preliminary version of this paper was presented at the Computer Strategy Game Programming Workshop, Hong Kong (1995). This work is supported by the Grant-in-Aid for Scientific Research (C) (Grant No 06680314) and the Grant-in-Aid for Encouragement of Young Scientists (Grant No 07780242) of the Ministry of Education, Science and Culture of Japan.

Note: [*] Department of Computer Science, The University of Electro-Communications, Chofu, Tokyo 182, Japan E-mail: [email protected].

Abstract: For the last four years, the power of Tsume-shogi solvers (i.e., programs for solving Japanese-chess problems) has advanced remarkably. Hard problems with 19 to 25 steps are now being attacked by several different types of search algorithms in the hope of solving all but a small set of these problems within a short time. In this paper, we present a parallel algorithm on network-connected distributed UNIX workstations, and show new computing results by solving 100 hard problems. The results confirm that our parallel program can solve most of the problems much more quickly than the best sequential program on a UNIX workstation.

DOI: 10.3233/ICG-1996-19204

Journal: ICGA Journal, vol. 19, no. 2, pp. 94-99, 1996