# アルファベータ法
アルファベータ法は、[ミニマックス法](/shogi/shogiwiki/search/minimax/)と同じ答えを保ったまま、結果に影響しない枝を途中で打ち切る探索手法である。
コンピュータ将棋では、[negamax](/shogi/shogiwiki/search/negamax/)を土台に実装されることが多く、現代的な探索の中心にある。
## 概要
アルファベータ法では、探索中に
- `alpha`
現在の手番側が少なくとも確保できる下限
- `beta`
相手が許してしまう上限
を管理する。
ある枝を読んだ結果、すでに別の手の方が確実に良いことが分かったなら、
その先を全部読まなくても結論は変わらない。
この「読まなくてよい枝を省く」のが枝刈りである。
## 何がうれしいのか
[ミニマックス法](/shogi/shogiwiki/search/minimax/)は原理として分かりやすいが、全部の枝を読むため計算量が非常に大きい。
アルファベータ法は、手の良い順に調べられれば大幅にノード数を減らせる。
そのため実戦的な将棋AIでは、
- [手の並べ替え](/shogi/shogiwiki/search/move-ordering/)
- [反復深化](/shogi/shogiwiki/search/iterative-deepening/)
- [置換表](/shogi/shogiwiki/search/transposition-table/)
と組み合わせることで、限られた時間でより深く読めるようにしている。
## 基本的な考え方
たとえば、ある局面で手 A を読んだ結果、
「少なくとも評価値 +100 は確保できる」と分かったとする。
次に手 B を読んでいる途中で、相手にうまい応手があり
「この手はどう頑張っても +100 を超えない」と判明したなら、
手 B の残りの枝を読む必要はない。
なぜなら、すでに手 A の方が良いと分かっているからである。
このように、探索の途中で
- これ以上読んでも改善しない
- 相手がその局面を選ばせてくれない
と分かった枝を打ち切る。
## 実装例
実装では [negamax](/shogi/shogiwiki/search/negamax/) 形式がよく使われる。
```cpp
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;
}
```
この枠組みに[静止探索](/shogi/shogiwiki/search/quiescence-search/)や各種枝刈りを足していくのが、典型的な将棋エンジンの探索になる。
## fail-hard と fail-soft
アルファベータ法の実装では、
- 範囲を外れたら境界値を返す `fail-hard`
- 実際に得られた値を返す `fail-soft`
の2系統がある。
現代的な実装では、情報をより多く残せる `fail-soft` が使われることが多い。
## 将棋AIでの位置づけ
将棋では分岐数が大きく、単純な全幅探索だけでは深さが足りない。
そのため、アルファベータ法はほぼ必須の基盤技術である。
特に重要なのは次の点である。
- 手の順序が良いほど枝刈りが増える
- [置換表](/shogi/shogiwiki/search/transposition-table/)の最善手は強力な並べ替え材料になる
- [反復深化](/shogi/shogiwiki/search/iterative-deepening/)と組み合わせるとさらに効率が上がる
- [Null Window Search](/shogi/shogiwiki/search/null-window-search/)や[PVS](/shogi/shogiwiki/search/principal-variation-search/)の土台になる
## 注意点
- 手の並べ替えが悪いと、理論上の効率向上を活かしにくい
- [評価関数](/shogi/shogiwiki/search/evaluation-function/)が弱いと、深く読んでも判断を誤る
- 終端付近では[地平線効果](/shogi/shogiwiki/search/horizon-effect/)を避けるため[静止探索](/shogi/shogiwiki/search/quiescence-search/)が重要になる
## 関連項目
- [探索](/shogi/shogiwiki/search/)
- [ミニマックス法](/shogi/shogiwiki/search/minimax/)
- [negamax](/shogi/shogiwiki/search/negamax/)
- [反復深化](/shogi/shogiwiki/search/iterative-deepening/)
- [手の並べ替え](/shogi/shogiwiki/search/move-ordering/)
- [置換表](/shogi/shogiwiki/search/transposition-table/)
- [静止探索](/shogi/shogiwiki/search/quiescence-search/)
## 参考にしたホームページ
- [Chessprogramming Wiki: Alpha Beta](https://www.chessprogramming.org/Alpha-Beta)
- [Chessprogramming Wiki: Search](https://www.chessprogramming.org/Search)
- [YouTube](https://www.youtube.com/watch?v=OISGnuUH32E)