Solving Kriegspiel-Like Problems: Examining Efficient Search Methods

摘要: We recently proposed a deterministic approach for solving problems with uncertainty, called the Uncertainty Paradigm. Under this paradigm, of such problem is resolved into plain AND/OR-tree search. The search under paradigm denoted by Paradigm Search (UPS). As an application, we have chosen domain Tsuitate-Tsume-Shogi, which mating Kriegspiel-like variant Shogi. early implementation UPSwas based on simple depth-first full-width iterative deepening (ID), was unable to solve several hard problems. This paper explores efficient method using UPDS (Uncertainty PDS) algorithm, specialized version PDS (Proof-number and Disproof-number Search) UPS. generally performs better than ID or PDS, but fails some easy In addition, variations also been examined tackle hardest All in test set solved particular variation UPDS, shows superiority variants proof-number