アルファベータ法は、ミニマックス法と同じ答えを保ったまま、結果に影響しない枝を途中で打ち切る探索手法である。 コンピュータ将棋では、negamaxを土台に実装されることが多く、現代的な探索の中心にある。
アルファベータ法では、探索中に
alpha
現在の手番側が少なくとも確保できる下限beta
相手が許してしまう上限を管理する。
ある枝を読んだ結果、すでに別の手の方が確実に良いことが分かったなら、 その先を全部読まなくても結論は変わらない。 この「読まなくてよい枝を省く」のが枝刈りである。
ミニマックス法は原理として分かりやすいが、全部の枝を読むため計算量が非常に大きい。 アルファベータ法は、手の良い順に調べられれば大幅にノード数を減らせる。
そのため実戦的な将棋AIでは、
と組み合わせることで、限られた時間でより深く読めるようにしている。
たとえば、ある局面で手 A を読んだ結果、 「少なくとも評価値 +100 は確保できる」と分かったとする。
次に手 B を読んでいる途中で、相手にうまい応手があり 「この手はどう頑張っても +100 を超えない」と判明したなら、 手 B の残りの枝を読む必要はない。 なぜなら、すでに手 A の方が良いと分かっているからである。
このように、探索の途中で
と分かった枝を打ち切る。
実装では negamax 形式がよく使われる。
int alphaBeta(Position pos, int depth, int alpha, int beta) {
if (depth == 0 || pos.isTerminal()) {
return evaluate(pos);
}
int bestValue = -INF;
for (Move move : generateMoves(pos)) {
Position next = doMove(pos, move);
int score = -alphaBeta(next, depth - 1, -beta, -alpha);
if (score > bestValue) {
bestValue = score;
}
if (score > alpha) {
alpha = score;
}
if (alpha >= beta) {
break; // beta cut
}
}
return bestValue;
}この枠組みに静止探索や各種枝刈りを足していくのが、典型的な将棋エンジンの探索になる。
アルファベータ法の実装では、
fail-hardfail-softの2系統がある。
現代的な実装では、情報をより多く残せる fail-soft が使われることが多い。
将棋では分岐数が大きく、単純な全幅探索だけでは深さが足りない。 そのため、アルファベータ法はほぼ必須の基盤技術である。
特に重要なのは次の点である。