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.