The search functionality is under construction.
The search functionality is under construction.

Keyword Search Result

[Keyword] AO*(1hit)

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

    Ayumu NAGAI  Hiroshi IMAI  

     
    PAPER-Artificial Intelligence, Cognitive Science

      Vol:
    E85-D No:10
      Page(s):
    1645-1653

    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.