Lambda Depth-First Proof Number Search and Its Application to Go
Proceedings of the Twentieth International Joint Conference on Artificial Intelligence. Pages 2404-2408.
Abstract
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.
@inproceedings{ijcai2007p387,
title = {Lambda Depth-First Proof Number Search and Its Application to Go},
author = {Yoshizoe, Kazuki and Kishimoto, Akihiro and Müller, Martin},
booktitle = {Proceedings of the Twentieth International Joint Conference on
Artificial Intelligence, {IJCAI-07}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Ramon López de Mántaras},
pages = {2404--2408},
year = {2007},
url = {https://ijcai.org/proceedings/2007/387},
}
TY - CPAPER TI - Lambda Depth-First Proof Number Search and Its Application to Go AU - Yoshizoe, Kazuki AU - Kishimoto, Akihiro AU - Müller, Martin T2 - Proceedings of the Twentieth International Joint Conference on Artificial Intelligence, IJCAI-07 PB - International Joint Conferences on Artificial Intelligence PY - 2007 SP - 2404 EP - 2408 UR - https://ijcai.org/proceedings/2007/387 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
