探索木とは

探索木は、パズルや迷路、ゲームのような問題を、コンピュータが手順を試しながら解くための表し方です。第1次AIブームの「探索・推論」の中心にあった考え方です。

木の形で表す

出発点の状態を「根」に置きます。そこから1回の操作で移れる状態を、子ノードとしてつなぎます。これを繰り返すと、可能な手順が枝分かれした木になります。ゴールの状態にたどり着く経路が見つかれば、それが解です。実際の探索では、木の全体を先に作るのではなく、調べる順に枝を広げていきます。

迷路なら、分かれ道がノード、進む方向が枝にあたります。ハノイの塔なら、円盤の置き方の1通りが1つのノードです。

どの順に調べるか

ノードを調べる順番によって、探索の方法が分かれます。根に近いノードから順に調べるのが幅優先探索です。手数が最も少ない解を見つけられますが、メモリを多く使います。1本の枝を行き止まりまでたどるのが深さ優先探索です。メモリは少なくて済みますが、最初に見つかる解が最短とは限りません。

対戦ゲームでは、自分と相手の手番が交互に並ぶ探索木を作ります。Mini-Max法で指す手を選び、αβ法で調べなくてよい枝を刈ります。

組合せ爆発

1つのノードからの枝分かれが多いと、深くなるにつれてノードの数は指数関数的に増えます。分岐が10通りなら、5手先で10万通りです。すべてを調べるブルートフォースは現実的でなくなるため、枝刈りや、モンテカルロ法による評価などの工夫が使われます。

また、探索木で解けるのは、ルールとゴールがはっきりした問題に限られます。現実の複雑な問題を解けないことは、トイ・プロブレムしか解けないという批判につながりました。

覚え方

「根は出発点、枝は操作、たどった先にゴール」と覚えます。