Proof for the Equivalence between Some Best-First Algorithms and Depth-First Algorithms for AND/OR Trees

Ayumu NAGAI  Hiroshi IMAI  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E85-D   No.10   pp.1645-1653
Publication Date: 2002/10/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Artificial Intelligence, Cognitive Science
Keyword: 
AND/OR tree,  AO*,  pn-search,  df-pn,  

Full Text: PDF>>
Buy this Article




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/OR-tree search is a method for getting a proof solution (win) or a disproof solution (loss) for such a problem. AO* is well-known 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 pn-search which uses the idea of proof number and disproof number. Both of them are best-first algorithms. There was no efficient depth-first algorithm using (dis)proof number, until Seo developed his originative algorithm which uses only proof number. Besides, Nagai recently developed PDS which is a depth-first algorithm using both proof number and disproof number. In this paper, we give a proof for the equivalence between AO* which is a best-first algorithm and Seo's depth-first algorithm in the meaning of expanding a certain kind of node. Furthermore, we give a proof for the equivalence between pn-search which is a best-first algorithm and df-pn which is a depth-first algorithm we propose in this paper.