ミニマックス法(αβ法)の神話
ミニマックス法は条件付き確率P( 自分が勝つ | 相手が最善手のみ打つ )を最大化する探索法でありαβ法はその高速版だ。ここでP(ω)は事象ω∈Ωの確率。
より正確に言うと、通常はゲーム木の高さより小さい値の深さ制限d_maxをつけて探索するから、
- P( 現局面からd_max手後の局面の評価値上自分が優位 | 現局面からd_max手後までの間相手が最善手のみ打つ )・・・(1)
が最大化される。
最大化されるのは確率であって勝てないときは勝てない。その事実は次のケースで端的に表れる。
- 先手必勝の二人零和有限確定完全情報ゲームにおいて最善手を打つ先手相手に後手が行うαβ探索：
一昨日の定理により、先手が最善手のみ打つ限り後手が勝つ確率は0であり、仮に後手がαβ法で葉ノードまで完全に読み切ったとしても0の集合の最大値は0という当然の事実が明らかにされるにすぎない。
それはともかくとして、問題なのは(1)の確率がP(自分が勝つ)とイコールもしくはその近似になっている保証が一般に無いことだ。
(1)の確率とP(自分が勝つ)の間には、d_max制限による評価誤差と、相手が最善手のみ打つとは限らないという不確定性とが横たわっている。一昨日の定理があるから現実には後者はあまり問題ではないが*1、前者は容易には回避できない。見ての通り前者(d_max制限による評価誤差)とは水平線問題そのものである。
実際、葉ノードまでいつも完全に読み切れて水平線が発生しないなら話は単純で、自己が勝つ局面を1、相手が勝つ局面を-1、引き分けを0とする3値の評価関数でmin-max探索すればケリがつくから(そのかわり葉ノードまで読まない限りその評価関数は計算できない)、勝負強さに響く評価関数の複雑精妙さはd_maxまでしか読まないことの代償と言える。端的に言って、あるd_maxの下で最適化された評価関数はd_max以外を探索深度とした場合最適でなくなる*2。
