モンテカルロ木探索とは
モンテカルロ木探索とは、選択肢を木の枝のように広げ、試行の結果を使って有望な枝へ計算時間を重点配分する探索手法です。英語名の頭文字からMCTSとも呼ばれます。全候補を均等に調べるのではなく、試しながら次に調べる場所を変えることが特徴です。
英語表記：Monte Carlo Tree Search（MCTS）
どうやって有望な手を絞るのか？
MCTSでは、選択、展開、シミュレーション、逆伝播の4段階を反復。まず過去の試行を基に枝を選び、未調査の候補を一つ広げ、その先の結果を試算します。最後に得点を経路上へ戻し、次の選択へ反映する流れです。なおここでの逆伝播は、ニューラルネットワークの学習で使う誤差逆伝播とは別物。試した結果の得点を、通ってきた枝へ書き戻すことを指します。
ここで難しいのが、成績のよい枝をさらに調べる「活用」と、まだ試していない枝を調べる「探索」の配分です。UCTと呼ばれる代表的な選び方は、この二つを数式で調整します。会議に例えると、有望案へ調査費を寄せつつ、未知の案にも一定の予算を残す仕組みです。
囲碁のように選択肢が多く、終局まで先読みしにくい問題で力を発揮しやすい手法です。AlphaGoやAlphaZeroでは、ニューラルネットワークが有望な手や局面の価値を示し、MCTSが先読みを進めました。機械学習と木探索は競合する技術ではなく、組み合わせる構成も可能。
経営では何を見ればよい？
MCTSを使う提案では、試行回数だけで性能を判断しないでください。結果を評価する関数、1回の試行にかかる時間、探索を止める条件、同じ条件での再現性を確認します。評価の置き方がずれると、計算を増やしても望ましくない枝を深く調べる可能性があります。
また、探索中の最善候補と、十分に調べた後の最善候補は一致するとは限りません。限られた時間でどの水準まで答えを出すかを業務要件として決め、計算費用と回答品質を一緒に検証することが重要です。
Topic「モンテカルロ木探索」という名前が生まれた年
ChatGPTの一般公開より16年前の2006年、Rémi Coulomは囲碁プログラム「Crazy Stone」の論文で、この手法にMonte-Carlo Tree Searchという名前を与えました。同じ年、KocsisとSzepesváriがUCTを発表。こちらはスロットマシンの複数のレバー（腕）からどれを引くか選ぶ「バンディット問題」の考え方を、木の枝の選び方へ持ち込んだものです。呼び名と選び方の理論が、同じ年に揃いました。
モンテカルロ木探索に関するよくある質問
- モンテカルロ木探索は毎回同じ答えになりますか？
- シミュレーションに乱数を使う構成では結果が変わる場合があります。比較試験では乱数の種、計算時間、試行回数などの条件をそろえ、複数回の結果を確認します。
- MCTSはゲーム以外にも使えますか？
- 計画、組み合わせ最適化、意思決定など、選択肢が枝分かれし、途中で候補を評価できる課題に応用できます。ただし、状態、行動、評価方法を課題ごとに設計する必要があります。
- 試行回数を増やせば必ず正解になりますか？
- 保証はできません。評価方法や探索範囲が不適切なら、計算を増やしても望ましい結果へ近づかない場合があります。時間上限と品質基準を実データで検証します。
