探索
現在の状態を開始点として、数手先をどう展開するかを先読みし、展開先の状態を評価します。
その状態評価をもとに現在の状態での最良の一手を選ぶ手法です。
探索では状態の展開を表すのにゲーム木でモデル化します。
完全ゲーム木
ゲームの開始から選択できるすべての手を含んだゲーム木です。
これがあれば絶対に負けない戦略を立てることができますが、完全ゲーム木のノード数は膨大なため計算が不可能なことがほとんどです。
部分ゲーム木
現在の状態から時間内に探索できる分だけを含んだゲーム木です。
有効だと思われるノードは深く探索し、有効でないノードは途中で探索を打ち切ります。
強さはいかに効率が高い部分ゲーム木を手に入れられるかということにかかってきます。