
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Proof for the Equivalence between Some BestFirst Algorithms and DepthFirst Algorithms for AND/OR Trees
Ayumu NAGAI Hiroshi IMAI
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E85D
No.10
pp.16451653 Publication Date: 2002/10/01 Online ISSN:
DOI: Print ISSN: 09168532 Type of Manuscript: PAPER Category: Artificial Intelligence, Cognitive Science Keyword: AND/OR tree, AO^{*}, pnsearch, dfpn,
Full Text: PDF>>
Summary:
When we want to know if it is a win or a loss at a given position of a game (e.g. chess endgame), the process to figure out this problem corresponds to searching an AND/OR tree. AND/ORtree search is a method for getting a proof solution (win) or a disproof solution (loss) for such a problem. AO^{*} is wellknown as a representative algorithm for searching a proof solution in an AND/OR tree. AO^{*} uses only the idea of proof number. Besides, Allis developed pnsearch which uses the idea of proof number and disproof number. Both of them are bestfirst algorithms. There was no efficient depthfirst algorithm using (dis)proof number, until Seo developed his originative algorithm which uses only proof number. Besides, Nagai recently developed PDS which is a depthfirst algorithm using both proof number and disproof number. In this paper, we give a proof for the equivalence between AO^{*} which is a bestfirst algorithm and Seo's depthfirst algorithm in the meaning of expanding a certain kind of node. Furthermore, we give a proof for the equivalence between pnsearch which is a bestfirst algorithm and dfpn which is a depthfirst algorithm we propose in this paper.

