Deterministic Solving of Problems with Uncertainty (Problem Solving)(Special Issue:Doctorial Theses on Aritifical Intelligence)

スポンサーリンク

概要

• 論文の詳細を見る

• 完全情報問題の問題解決はAND/ORグラフ探索になるが, 同一状態が頻繁に生じない場合はAND/OR木探索が使われる.近年, AND/OR木探索では証明数・反証数を用いた極めて効率的な数種の探索法pn-search, PN^*, PDS, dfpn(以下では証明数探索と総称する)が生まれた.詰将棋・6×6オセロの終盤について, これらや全幅深さ優先探索の性能を比較したところ, 詰将棋では証明数探索, 特にPDSが高い問題解決能力を示した.完全情報でない問題の解決は不確定性のため非常に複雑・困難で, 一般には蓋然論的な解決しかできないが, ある種の問題では不完全情報にもかかわらず決定論的な解が存在する.しかし不完全情報の決定論的問題解決を単純な探索で行う研究はなされていなかった.新しく導入した考え方・手法によって, 複数の状態の重ね合せである不確定性状態をメタ状態として捉えて一つの節とし, また, 複数の選択(行動)の重ね合せである不確定性選択をメタ選択として捉えて一つの弧とすることで, 探索空間は単なるAND/ORグラフ(あるいは木)に帰着できた.適用例として一人パズル「贋金貨問題」および二人ゲームを題材とするパズル「衝立詰将棋」を選んだ.贋金貨問題では手法の適用可能性・正当性を確認できた.衝立詰将棋では完全情報AND/OR木の探索手法を応用することにより探索の効率化を図り, いくつかの難問題を含むすべての問題を解くことができた.

• 社団法人人工知能学会の論文
• 2001-11-01

著者

• 作田 誠

  静岡大学大学院理工学研究科

• 作田 誠

  静岡大学大学院理工学研究科:(現)静岡大学大学院理工学研究科

関連論文

• コンピュータ将棋における指し手の順序付けによる探索効率化(ゲームプログラミング)
• 将棋終盤で発展してきた探索手法のLines of Actionへの適用(ゲームプログラミング)
• 不確定性を持つ問題を解くためのAND/OR木探索 : 衝立詰将棋を題材として
• 必至問題を解くプログラムとその評価
• Deterministic Solving of Problems with Uncertainty (Problem Solving)(Special Issue:Doctorial Theses on Aritifical Intelligence)

スポンサーリンク