【探索】縦型・横型・反復深化法の探索手法の比較。

探索とは、チェスや将棋や囲碁などのゲームをコンピュータがプレイするときに、どの手を指すかを決定するのに使われます。人間の「読み」にあたる部分です。

状態（state）と行動（action）

ゲームの盤面など意志決定に必要な情報を状態（state）、可能な全ての状態を状態空間と呼びます。また、状態を変化させる選択肢を行動（action、ゲームでは手、moveとも）と呼びます。

• 盤だけが状態ではなく、自分がどっちなのか、先手後手どっちの番なのか、持ち駒なども状態に含まれる。
• 名前、手数、持ち時間などは普通は状態に含めない。

状態空間は、状態を節点（node）、変換操作を枝（edge）とすると、グラフ（節点と枝の集まり）で表現できます。

探索木

探索空間を木状のグラフで表現したものを「探索木」といいます。節点が状態、枝が行動を表します。

探索木による探索とは、「与えられた問題において想定される多くの可能な状態の中から、特定の条件を満たすものに至る経路を見つけ出すための方法」とされます。

探索はおおむね以下の手順の繰り返しで行われます。

• 分かっている情報を候補リストに保管する。
• 候補リストから次に調べる状態・着手を選択する。
• 新しいノードを展開し、リストを更新する。

基本的には、全てを調べ上げればゴールは見つかるため、重複や見落としなしに、しらみつぶしに探索します。

どのような順序で探索するかによって、いくつか探索手法があります。

縦型（深さ優先）探索｜Depth-first search（DFS）

縦型探索は、子節点をどんどん深く（枝の先に）探索していく方法です。

縦型探索の特徴としては、

• 深いゴールが早く見つけられる場合がある（長所）。
• 浅いゴールがなかなか見つけられない（短所）。
• 記憶領域（メモリ使用量）が少ない（むやみに手を広げないため）。
• 得られた解が最善である保証がない。

などが挙げられます。

横型（幅優先）探索｜Breadth-first search（BFS）

横型探索は、同じ深さの節点を全て調べ、ゴールが見つかるまで１つずつ深くしていく手法です。

横型探索の特徴としては、

• 最短の方法でゴールを見つけることができる（最適解がみつかる）。
• 記憶容量が大量に必要になる（致命的な欠点）。

などが挙げられます。

反復深化法｜Iterative deepening（ID）

反復深化法は、縦型探索で閾値（最大探索深さ）を徐徐に上げ、繰り返し探索を行う方法で、縦型探索と横型探索の長所を兼ね備えています。