Studies on Tsuitate-Tsume-Shogi (Mating Problems of Screen Shogi)

Makoto Sakuta (作田 誠 in Japanese character)
Fukuoka Institute of Technology

• M. Sakuta and H. Iida.
  Solving problems with uncertainty: A case study using Tsuitate-Tsume-Shogi.
  In Proceedings of Game Programming Workshop in Japan '99, pages 145-152, Hakone, Japan, Oct. 1999.
  
  
• M. Sakuta, H. Iida, and J. Yoshimura.
  Solving problems under Uncertainty Paradigm.
  In Proceedings of International Conference on Advances in Infrastructure for Electronic Business, Science and Education on the Internet (SSGRR 2000), L'Aquila, Italy, Aug. 2000. (in CD-ROM).
  
  
• M. Sakuta and H. Iida.
  Solving Kriegspiel-like problems: Exploiting a transposition table.
  ICGA Journal, 23(4):218-229, 2000.
  
  
• M. Sakuta and H. Iida.
  Solving screen-chess-type problems: Examining the ability to distinguish solvable and unsolvable problems.
  In H. Nakatani and H. Iida, editors, Proceedings of the Joint International Conference on Advanced Science and Technology (JICAST 2000), pages 107-110, Shizuoka University, Hamamatsu, Japan, Dec. 2000.
  
  
• Makoto Sakuta and Hiroyuki Iida.
  Solving Kriegspiel-like problems: Examining efficient search methods.
  In Tony Marsland and Ian Frank, editors, Computers and Games: Second International Conference, Vol. 2063 of Lecture Notes in Computer Science, pages 55-73. Springer-Verlag, 2001.
  

  NOTICE FOR THE USE OF THIS MATERIAL:

  The copyright of this material is retained by the Springer (© Springer-Verlag). You can get the book or the online version via the LNCS series page.

• Makoto Sakuta and Hiroyuki Iida.
  AND/OR-tree search for solving problems with uncertainty - A case study using Screen-shogi problems.
  Transactions of Information Processing Society of Japan, 43(1):1-10, 2002. (in Japanese).

  NOTICE FOR THE USE OF THIS MATERIAL:

  The copyright of this material is retained by the Information Processing Society of Japan (IPSJ). This material is published on this web site with the agreement of the author(s) and the IPSJ. Please be complied with Copyright Law of Japan and the Code of Ethics of the IPSJ if any users wish to reproduce, make derivative work, distribute or make available to the public any part or whole thereof.
  All Rights Reserved, Copyright (C) Information Processing Society of Japan.

  Abstract:
  This paper explores a deterministic approach to solving problems with uncertainty, using Screen-shogi problems, which are the mating problems of Kriegspiel-like Shogi variant. Our programs resolve a search space into an AND/OR tree and solve a problem by searching the tree. The AND/OR tree, each of which node has an uncertainty, is more generic than that in solving a problem of a two-person complete-information game such as Tsume-Shogi. The search algorithms are implemented using a full-width depth-first iterative deepening (ID), and using PDS, which is one of the depth-first variants of the proof-number search. In addition, UPDS, which is a specialized version of PDS for an AND/OR tree with uncertainty, is proposed and examined with changing the parameters. Moreover, some search variations are developed and examined. One variation is dpUPDS, which performs iteration with changing the parameters of UPDS. The others are uidUPDS based on UPDS and uidID based on ID. Both variations perform iteration with increasing the search threshold of uncertainty. The solving abilities of dpUPDS, uidUPDS and uidID are high. Especially, the uidUPDS program has solved all problems. However, an efficient algorithm that always finds an optimal solution even for a hard problem still needs to be investigated.

You can also find the collection of the above studies in my Ph.D. thesis.

PhD thesis (Shizuoka University, Japan, 2001)

• Makoto Sakuta.
  Deterministic Solving of Problems with Uncertainty.
  Kurofune Shuppan, Toro, Shizuoka, Japan, May 2001.

The online thesis is available via SURE: Shizuoka University REpository.