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.
Get full access to this article
View all access options for this article.