Lambda depth-first proof number search and its application to go

Kazuki Yoshizoe, Akihiro Kishimoto, Martin Müller

Research output: Contribution to journalConference articlepeer-review

31 Citations (Scopus)


Thomsen's λ search and Nagai's depth-first proof-number (DFPN) search are two powerful but very different AND/OR tree search algorithms. Lambda Depth-First Proof Number search (LDFPN) is a novel algorithm that combines ideas from both algorithms. λ search can dramatically reduce a search space by finding different levels of threat sequences. DFPN employs the notion of proof and disproof numbers to expand nodes expected to be easiest to prove or disprove. The method was shown to be effective for many games. Integrating λ order with proof and disproof numbers enables LDFPN to select moves more effectively, while preserving the efficiency of DFPN. LDFPN has been implemented for capturing problems in Go and is shown to be more efficient than DFPN and more robust than an algorithm based on classical λ search.

Original languageEnglish
Pages (from-to)2404-2409
Number of pages6
JournalIJCAI International Joint Conference on Artificial Intelligence
Publication statusPublished - 2007
Externally publishedYes
Event20th International Joint Conference on Artificial Intelligence, IJCAI 2007 - Hyderabad, India
Duration: Jan 6 2007Jan 12 2007

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence


Dive into the research topics of 'Lambda depth-first proof number search and its application to go'. Together they form a unique fingerprint.

Cite this