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