Depth-first Proof Number Search

For applications, see our research on tsume Go and seki.


A. Kishimoto and M. Müller. About the completeness of depth-first proof-number search. In J. van den Herik, X. Xu, Z. Ma, and M. Winands, editors, Computer and Games. 6th International Conference, volume 5131 of Lecture Notes in Computer Science, pages 146-156, Beijing, China, 2008. Springer. Acceptance rate: 24/40 = 60%.

K. Yoshizoe, A. Kishimoto, and M. Müller. Lambda depth-first proof number search and its application to Go. In Twentieth International Joint Conference on Artificial Intelligence (IJCAI), pages 2404-2409, Hyderabad, India, 2007. Acceptance rate (oral presentation): 212/1353 = 15.7%.

S. Soeda, K. Yoshizoe, A. Kishimoto, T. Kaneko, T. Tanaka, and M. Müller. Lambda search based on proof and disproof numbers. Information Processing Society of Japan (IPSJ) Journal, 48(11):3455-3462, 2007. In Japanese.

J. Schaeffer, Y. Björnsson, N. Burch, A. Kishimoto, M. Müller, R. Lake, P. Lu, and S. Sutphen. Solving Checkers. In International Joint Conference on Artificial Intelligence (IJCAI), pages 292-297, 2005.

A. Kishimoto. Correct and Efficient Search Algorithms in the Presence of Repetitions. PhD thesis, University of Alberta, 2005.

A. Kishimoto and M. Müller. Df-pn in Go: an application to the one-eye problem. In J. van den Herik, H. Iida, and E. Heinz, editors, Advances in Computer Games 10, pages 125 - 141. Kluwer, 2004.

Created: Jun 20, 2009 Last modified: Jun 20, 2009

Martin Müller