不確定性を持つ問題を解くためのAND/OR木探索 : 衝立詰将棋を題材として

概要

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