{"created":"2021-03-01T07:09:47.329390+00:00","id":48966,"links":{},"metadata":{"_buckets":{"deposit":"e2aedd05-20cb-4f0a-bc04-1d20fb44729d"},"_deposit":{"id":"48966","owners":[],"pid":{"revision_id":0,"type":"depid","value":"48966"},"status":"published"},"_oai":{"id":"oai:repository.dl.itc.u-tokyo.ac.jp:00048966","sets":["34:95:96","9:10:15"]},"item_2_biblio_info_7":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"2002-10-01","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"10","bibliographicPageEnd":"1653","bibliographicPageStart":"1645","bibliographicVolumeNumber":"E85-D","bibliographic_titles":[{"bibliographic_title":"IEICE TRANSACTIONS on Information and Systems"}]}]},"item_2_description_5":{"attribute_name":"抄録","attribute_value_mlt":[{"subitem_description":"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.","subitem_description_type":"Abstract"}]},"item_2_description_6":{"attribute_name":"内容記述","attribute_value_mlt":[{"subitem_description":"PAPER","subitem_description_type":"Other"}]},"item_2_publisher_20":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"Institute of Electronics, Information and Communication Engineers"}]},"item_2_relation_25":{"attribute_name":"関係URI","attribute_value_mlt":[{"subitem_relation_type_id":{"subitem_relation_type_id_text":"https://search.ieice.org/","subitem_relation_type_select":"URI"}}]},"item_2_rights_12":{"attribute_name":"権利","attribute_value_mlt":[{"subitem_rights":"copyright©2002 IEICE"}]},"item_2_select_14":{"attribute_name":"著者版フラグ","attribute_value_mlt":[{"subitem_select_item":"publisher"}]},"item_2_text_4":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"NASDA"},{"subitem_text_value":"the Department of Information Science, The University of Tokyo"},{"subitem_text_value":"the Department of Computer Science, The University of Tokyo"}]},"item_creator":{"attribute_name":"著者","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"NAGAI, Ayumu"}],"nameIdentifiers":[{"nameIdentifier":"145500","nameIdentifierScheme":"WEKO"}]},{"creatorNames":[{"creatorName":"IMAI, Hiroshi"}],"nameIdentifiers":[{"nameIdentifier":"145501","nameIdentifierScheme":"WEKO"}]}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2017-12-15"}],"displaytype":"detail","filename":"Proof for the Equivalence between Some Best-First Algorithms and Depth-First Algorithms for AND OR Trees  2002.pdf","filesize":[{"value":"265.8 kB"}],"format":"application/pdf","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"Proof for the Equivalence between Some Best-First Algorithms and Depth-First Algorithms for AND OR Trees  2002.pdf","url":"https://repository.dl.itc.u-tokyo.ac.jp/record/48966/files/Proof for the Equivalence between Some Best-First Algorithms and Depth-First Algorithms for AND OR Trees  2002.pdf"},"version_id":"d784173e-93f4-4100-8a0b-b4899a717c24"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"eng"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourcetype":"journal article","resourceuri":"http://purl.org/coar/resource_type/c_6501"}]},"item_title":"Proof for the Equivalence between Some Best-First Algorithms and Depth-First Algorithms for AND/€OR Trees","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"Proof for the Equivalence between Some Best-First Algorithms and Depth-First Algorithms for AND/€OR Trees"}]},"item_type_id":"2","owner":"1","path":["15","96"],"pubdate":{"attribute_name":"公開日","attribute_value":"2017-12-14"},"publish_date":"2017-12-14","publish_status":"0","recid":"48966","relation_version_is_last":true,"title":["Proof for the Equivalence between Some Best-First Algorithms and Depth-First Algorithms for AND/€OR Trees"],"weko_creator_id":"1","weko_shared_id":null},"updated":"2022-12-19T04:23:38.256480+00:00"}