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

Ayumu NAGAI; Hiroshi IMAI

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

Ayumu NAGAI, Hiroshi IMAI

Full Text Views

0

Cite this

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.

Publication: IEICE TRANSACTIONS on Information Vol.E85-D No.10 pp.1645-1653

Publication Date: 2002/10/01

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Artificial Intelligence, Cognitive Science

Cite this

Copy

Ayumu NAGAI, Hiroshi IMAI, "Proof for the Equivalence between Some Best-First Algorithms and Depth-First Algorithms for AND/OR Trees" in IEICE TRANSACTIONS on Information, vol. E85-D, no. 10, pp. 1645-1653, October 2002, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/e85-d_10_1645/_p

Copy

@ARTICLE{e85-d_10_1645,
author={Ayumu NAGAI, Hiroshi IMAI, },
journal={IEICE TRANSACTIONS on Information},
title={Proof for the Equivalence between Some Best-First Algorithms and Depth-First Algorithms for AND/OR Trees},
year={2002},
volume={E85-D},
number={10},
pages={1645-1653},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={October},}

Copy

TY - JOUR
TI - Proof for the Equivalence between Some Best-First Algorithms and Depth-First Algorithms for AND/OR Trees
T2 - IEICE TRANSACTIONS on Information
SP - 1645
EP - 1653
AU - Ayumu NAGAI
AU - Hiroshi IMAI
PY - 2002
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E85-D
IS - 10
JA - IEICE TRANSACTIONS on Information
Y1 - October 2002
AB - 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.
ER -