著者

作田 誠 飯田 弘之

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.43, no.1, pp.1-10, 2002-01-15

---

不完全情報2人ゲームである衝立将棋の詰め問題を題材として,不確定性を持つ問題をAND/OR木探索として決定論的に解く手法を導入する.このAND/OR木は詰将棋など通常の完全情報2人ゲーム問題において生成されるものに比べてより一般化されており,節点はそれぞれ不確定性を持つ.探索アルゴリズムとして,局面表を活用した全幅深さ優先反復深化探索(ID),および証明数探索の深さ優先版の一種であるPDSを実装し動作を調べた.またPDSを不確定性のあるAND/OR木の探索に特化させたUPDSを開発しパラメータを変化させて動作を調べた.さらに,UPDSにおいて実行時にパラメータを順次変化させて解けるまで繰り返し探索を行うdpUPDS,および,UPDS,IDにおいて不確定性の探索閾値を小さな値から順次増加させて解けるまで繰り返し探索を行うuidUPDS,uidIDというバリエーションを考案・実装し動作を調べた.dpUPDS,uidUPDS,uidIDは解答能力が高く,特にuidUPDSはすべての問題を解いた.しかし,確実に最適解を得る効率の良い探索法は課題として残る.