問題解決における不確定性パラダイムの提案と適用

概要

論文の詳細を見る
不確定性のある問題を解決するための新しいパラダイム「不確定性パラダイム」を提案する。この下では任意の不確定性のある問題を決定論的に解決することが純粋なAND/ORグラフ(または木)の探索に帰着される。この探索を不確定性パラダイム探索(UPS)と名づける。通常のゲーム木は節点として局面、枝として指手を持つが、このパラダイム下では節点は可能な局面の重ね合せであるメタ局面、枝は可能な指手の重ね合せであるメタ指手になる。理論的にはUPSはあらゆる不完全情報のパズル・ゲームの終盤を決定論的に解決することに適用可能である。しかし、多くの問題領域において実際に適用するためには厳しい限界がある。また、二人ゲームを題材としたパズルへの適用例として「ついたて詰将棋」を選び、このパラダイム下で問題を探索し解決するプログラムを作成した。さらに、ついたて詰将棋についてメタ局面のコード化を行い、transposition tableを利用した全幅反復深化探索および長井のPDSを不確定性パラダイム探索に特化させたUPDS(Uncertainty Paradigm PDS)を実装し良い結果を得た。
一般社団法人情報処理学会の論文
2000-05-31