| 7.2 Multi Prob Cut (MPC) |
前節では単純な枝刈りを導入しましたが、良い効果は現れませんでした。
本節ではより複雑な枝刈り手法であるMulti Prob Cut (MPC)について説明します。
MPCは、Logistelloの作者であるMichael Buroによって提案された手法です。
MPCでは、静的評価によって探索を打ち切るかどうかを決めるのではなく、最初に残り手数よりも浅い探索を行います。
次に、浅い探索から残り手数分の探索（深い探索と呼ぶことにします）の評価値を予想します。
そして予想した評価値から、αカットまたはβカットが発生しそうかどうかを判断します。
浅い探索の手数は、例えば残り手数４手なら浅い探索２手、残り手数８手なら浅い探索４手というようにあらかじめ決めておきます。
探索の残り手数に応じて浅い探索の手数が変わるのもMPCの特徴のひとつです。
MPCでは、「浅い探索による評価値と深い探索による評価値との間には相関関係がある」ことを利用しています。
浅い探索による評価値をv、深い探索による評価値をVとして、vとVの間に以下の関係があると仮定します。
V = f (v) + e
f (v)はvの関数、eは誤差です。
誤差eは平均0、標準偏差σの正規分布に従うと仮定します。
f (v)にはvとVとの関係を適切に表現しそうな関数を選びます。
例えばBuroは以下の式を採用しています。
V = a * v + b + e
ここでaとbはある実数です。
aとbとσは浅い探索による評価値と深い探索による評価値の統計をとることで決定できます。
本解説では、これを簡略化して、a=1とした式を使用することにします。
V = v + b + e
なお、この関係は２手読みと４手読み、４手読みと８手読み等のそれぞれの組み合わせ毎に調べる必要があります。
各ノードでは、浅い探索による評価値vが得られたら、以下のどちらかを満たすかどうかを調べます。
一方を満たす場合にはそこで探索を打ち切ります。
上の式を満たす場合には「深い探索による評価値がα値より小さくなりそう」であることを意味しています。
下の式を満たす場合には「深い探索による評価値がβ値より大きくなりそう」であることを意味しています。
v + b + t * σ < α
v + b - t * σ > β
ここでtは探索の打ち切りやすさを決める値です。
tが小さい程枝刈りが多く発生しますが、評価の精度が落ちます。
具体的なtの決定方法ですが、枝刈りが発生する場合の信頼度によって決めます。
枝刈りを確率pで信頼できるようにするためには、平均０、分散１の正規分布の−∞からtまでの積分値がpになるようにtを決めます
今回はいくつか数式が出てきたので、難しかったでしょうか。
本節ではMPCの説明にとどめ、具体的な実装は次節から行ないます。