ゲーム木探索とは、チェスや将棋などの対戦ゲームにおいて、盤面の状態とプレイヤーの指し手を木の枝分かれに見立てて展開し、最善の行動を見つけ出す手法です。相手の最善手を想定して先読みを行うことで、勝率の高い指し手を決定します。
ゲーム木探索とは
ゲーム木探索とは、手番ごとに変化する盤面や状況を樹形図（ツリー構造）として表現し、先々の展開をシミュレーションして最適な手を選択する計算手法です。
詳しく解説
ゲーム木探索は、自分と相手が交互に行動する二人零和有限確定完全情報ゲームを中心に発展してきました。現在の盤面を根ノードとし、可能な指し手を枝、進んだ先の盤面を子ノードとして展開します。基本的なアルゴリズムには、相手も自分にとって最も都合の悪い手を選ぶ前提で最善手を求めるミニマックス法があります。しかし、展開するノード数が指数関数的に増大する「組み合わせ爆発」が起きるため、不要な探索を省くアルファベータ剪定や、探索途中の盤面を数値化する評価関数を組み合わせることが不可欠です。近年ではランダムシミュレーションを用いるモンテカルロ木探索や、強化学習と組み合わせた手法が主流となっています。
具体例・使われ方
チェス、将棋、オセロなどのボードゲームAIで指し手を決める際に用いられます。例えば将棋AIでは、数手から数十手先までの互いの応手をゲーム木として広げ、評価関数で点数化しながら最善手を選びます。また、自動運転における他車の動きの予測など、相手の行動を考慮した意思決定にも応用されます。
似た用語との違い
一般的な経路探索（A*探索など）は単一のエージェントが目標地点を目指す探索ですが、ゲーム木探索は敵対する相手の手番が存在し、相手の行動によって状況が変化する点が異なります。また、純粋なミニマックス法とモンテカルロ木探索の違いとして、前者がすべての分岐を網羅的に評価しようとするのに対し、後者は試行回数に基づいて有望な枝を重点的に掘り下げる点があります。
注意点
盤面の選択肢や手数が膨大なゲームでは、全ての局面を調べ尽くす完全探索は計算量の限界から不可能です。そのため、探索の深さを制限したり枝刈りを行ったりしますが、評価関数の精度が低い場合や探索を打ち切った直後に大きな変化がある場合には、悪手を選択してしまうリスク（地平線効果など）があります。