木探索とは、データをツリー（木）構造として表現し、目的のノード（状態や解）を効率的に見つけ出すためのアルゴリズムです。AI分野では、囲碁や将棋などのゲームAIにおける次の一手の決定や、ルート最適化などの意思決定問題で広く活用されています。探索の進め方によって深さ優先探索や幅優先探索、さらには確率的に探索するモンテカルロ木探索などの手法があります。
木探索とは
木探索（ツリーサーチ）とは、開始地点（根ノード）から分岐する選択肢を樹形図のような「木構造」としてモデル化し、その中から最適な解や目標となる状態を効率的に探索・選択するアルゴリズムです。
詳しく解説
木構造は、データが分岐しながら広がる階層的な関係を示します。AIや問題解決の文脈では、各分岐点（ノード）が現在の「状態」を、分岐を繋ぐ線（エッジ）が「行動」や「選択肢」を表します。探索が進むにつれて選択肢が指数関数的に増加する「組合せ爆発」が発生するため、すべての選択肢を調べることは現実的ではありません。そこで、深さ優先探索や幅優先探索といった基本的な手法から、評価関数を用いて有望な経路を優先する手法、さらにはランダムなシミュレーションを繰り返して探索を進めるモンテカルロ木探索など、効率的に探索空間を絞り込む技術が開発されてきました。これにより、複雑な状態空間モデルの中から最適な意思決定を行うことが可能になります。
具体例・使われ方
具体的な活用例として、チェス、将棋、囲碁などのゲームAIにおける思考エンジンが挙げられます。コンピュータは、現在の局面から指し得るすべての手を木構造として展開し、将来の盤面を予測しながら最適な一手を選択します。また、カーナビゲーションシステムにおける最適な目的地までのルート探索や、ロボットの動作計画（プランニング）、自然言語処理における構文解析のプロセスなど、膨大な選択肢から最適解を選ぶあらゆる場面で応用されています。
似た用語との違い
木探索と混同されやすい概念に、グラフ探索があります。グラフ探索は、ノード間に循環（ループ）や網の目の構造が存在する一般的なネットワークを探索するのに対し、木探索は親から子への一方向の流れであり、循環のない「木構造」に特化した探索手法です。また、機械学習の分類問題で用いられる「決定木」はデータを分類するための静的なモデルですが、木探索は動的に選択肢を展開しながら最適な状態を探し出す能動的なアルゴリズムであるという違いがあります。
注意点
木探索の限界は、問題の規模が大きくなると探索空間が膨大になり、計算時間やメモリ使用量が爆発的に増加する点です。特にゲームAIのように分岐数が多い問題では、完全な探索を行うことは不可能に近いため、いかに効率よく不要な枝（選択肢）を切り落とすか（枝刈り）や、実用的な時間内で妥当な解を見つける近似手法の導入が不可欠となります。