SOLVING KRIEGSPIEL-LIKE PROBLEMS: EXPLOITING A TRANSPOSITION TABLE

Article type: Research Article

Authors: Sakuta, Makoto | Iida, Hiroyuki^{; 1}

Affiliations: Shizuoka University, Hamamatsu, Japan

Note: [1] Faculty of Information, Department of Computer Science, Shizuoka University, 3-5-1 Johoku, Hamamatsu, 432-8011 Japan, email: {sakuta, iida}@cs.inf.shizuoka.ac.jp.

Abstract: We recently proposed Uncertainty Paradigm Search (UPS), a novel deterministic approach for solving problems with uncertainty. One of its applications is in Tsuitate-Tsume-Shogi (mating problems in a Kriegspiel-like variant of Shogi). This approach relies on the use of metapositions. A metaposition is a hybrid complex of possible positions that are not distinguishable for the solver. In this contribution, we examine four methods for encoding a metaposition into some value with fewer bits in order to use a transposition table. Each encoding method is tested in a search process, using a benchmark test set of 102 problems. They show us that the efficiency of search by using a transposition table is improved by a factor of eight. The four encoding methods make use of (1) arithmetic sum, (2) exclusive-OR sum, (3) two cyclic redundancy check codes, and (4) a secure hash function. The method of exclusive-OR sum proves not to be acceptably resistant to type-1 errors in this domain; the others are. Though the execution time is roughly comparable among the other three methods, the arithmetic sum is slightly superior in our implementation.

DOI: 10.3233/ICG-2000-23403

Journal: ICGA Journal, vol. 23, no. 4, pp. 218-229, 2000