← 概念解説に戻る

Concept Fable

木探索

先に結論:それは一つの意思決定問題を木構造に展開する。現在の状態が根ノードで、各行動が子ノードを生み、さらに未来の可能な状態を展開し続け、最後に評価を通じてより良い経路を選ぶ。

Tree Search · Inference

まず物語を読む。ここでは急いで定義を示さず、まず問題そのものを立ち上がらせる。

寓話

棋士が分かれ道の前に小さな旗を置く

少年棋士が初めて大会に出たとき、一歩一歩を勘で打っていた。師匠が尋ねた。もしこの手を打てば、相手はどう返すか。その次の手はどうなるか。少年は首を振った。目の前の一マスしか見えず、たった今取られた石しか覚えていなかった。

師匠は机の上に逆さまに伸びる木を描いた。根は現在の棋局で、枝の一本一本が打てる手だ。新しいノードに進むと、相手にもいくつかの枝がある。さらに下へ進むと局面はますます増え、まるで森のようになる。

少年はすべての枝を最後まで辿ろうとし、すぐに崩壊した。三手先で既に千以上の局面があり、日が暮れるまで計算しても終わらなかった。彼はまず、達人とはすべての道を見切れる者だと思ったが、師匠は言った。賢さはすべてを窮めることではない。

彼らは各ノードに小旗を立てた。この局面はおおよそ有利か不利か。この道はまだ先を見る価値があるか。すでに負けているなら、もう展開しなくてよい。いくつかの道がほぼ同じなら、不確かだがより良い可能性のある道を先に探索する。

最初の修正は安定しなかった。少年は最も良さそうな枝だけを選び、相手の隠れた反撃を見逃した。その後はどれも少しずつ見たが、深さが足りず、やはり待ち伏せに遭った。師匠は彼に、展開、推定、剪定、後退の間で調整を繰り返すよう教えた。

少年を本当に納得させたのは一盘の残局だった。彼は感覚で目の前の一子を取ったが、三步後に詰まされた。あの一子を先に見逃せば、かえって相手を死角に追い込めた。目の前の利益と後の局面が、初めて彼の頭の中で分かれた。

後に少年の碁は半拍遅くなったが、ずっと安定した。彼の一歩一歩はもはや単なる動作ではなく、頭の中で有限に展開する木を歩むことだった。試探、評価、枝刈り、後退、そして現在最も良いと思われる枝を選ぶ。

その後、少年も毎手を森全体として考えることはなくなった。局面が簡単なときは速く打ち、危険なときは何層も展開する。師匠は言った、小旗はあなたを遅くするためではなく、重要な分かれ道の前で目の前の一石に騙されにくくするためだと。後に彼は一局ごとに振り返るとき、どの枝を早く見すぎたか、どの枝を切り間違えたかを印し、次の展開をより正確にする。

明らかにする

この物語が語るのは:木探索

それは一つの意思決定問題を木構造に展開する。現在の状態が根ノードで、各行動が子ノードを生み、さらに未来の可能な状態を展開し続け、最後に評価を通じてより良い経路を選ぶ。

木探索はチェス、計画、推論、意思決定でよく用いられる。難点は分岐数が爆発することであり、評価関数、枝刈り、バックトラック、ヒューリスティック探索、モンテカルロ法などによって、限られた計算コスト内で十分に良い選択を見つける必要がある。

メタファーのマッピング

  • 現在の局面:探索木の根ノード
  • 打てる各手:行動分岐
  • 相手の応答後の局面:次の層の状態ノード
  • 小旗を立てる:局面評価関数
  • 見込みのない経路を切る:枝刈り、計算コストを下げる

Andy(任旭)判断

木探索は、Agentの計画が一度のひらめきではなく、限られた計算の中で可能な経路を探索することだと教えてくれる。製品では展開の深さ、評価基準、失敗時のフォールバックを制御する必要がある。

MCTStest-time computereasoningプランニング
京ICP备2026014272号