モンテカルロ木探索

モンテカルロ木探索はMCTSと略され、すべての変化を同じ深さまで調べようとはしない。探索木を少しずつ成長させ、蓄積した結果を使って次の計算をどこへ割り当てるか決める。訪問回数の多い手が自動的に良いわけではないが、その推定は通常、より多くの探索に支えられている。

MCTSの1サイクル

1. 選択: 開始局面から既存の枝をたどり、すでに強そうな手と、まだ不確かな手のバランスを取る。
2. 展開: 探索木でまだ発展させていない局面または手を追加する。
3. 評価: 新しい局面からの結果を推定する。古典的手法では模擬対局を最後まで進めることがあり、現代的システムではパターンを認識するよう学習したモデルであるニューラルネットワークを使って評価することもある。
4. 逆伝播: 結果を訪問した経路に沿って戻し、訪問回数と推定値を更新する。

このサイクルの反復は、活用と探索のバランスを取る。活用とは、すでに好ましい根拠がある場所へより多くの労力を使うこと。探索とは、意外な選択肢を早く捨てすぎないよう、不確かな代案を試すことである。両者を均衡させる正確な規則は実装によって異なる。

ミニマックスと異なり、MCTSは一様な深度だけでなく、探索中に集めた根拠に基づいて枝をどれほど調べるか決めることが多い。ニューラルネットワークを使うチェスプログラムの一部では、ネットワークが有望な手を示す方策と、結果を推定する価値を提供する。価値は評価関数と関連する役割を持つが、探索全体の手順は異なる。