探索木

探索木は、問題解決において取り得る選択肢や状態の遷移を、根から枝分かれする木構造で表現したものです。ゲームの対戦やパズルなど、次にどの手を選ぶかによって状況が変化する問題において、全容を把握するために用いられます。

この構造において、根は現在の状態を表し、枝は可能な行動、ノードは行動の結果到達する新しい状態を表します。この木を辿りながら、最終的に勝利条件やゴールに到達するルートを探すのが探索です。幅優先探索や深さ優先探索など、木を効率的に辿るアルゴリズムが多数存在します。

G検定では、ゲームAIや最適化問題に関連するトピックとして登場します。モンテカルロ木探索など、木構造を用いた高度な探索アルゴリズムは近年のAI進化を支えてきました。AIがどのように先読みを行っているのかを理解する上で、この基本的な構造の知識は不可欠です。