# Principal Variation Search
Principal Variation Search（PVS）は、[アルファベータ法](/shogi/shogiwiki/search/alpha-beta/)をさらに効率化する探索手法である。
最初に調べた有望手だけを通常の探索窓で読み、残りの手はまず[Null Window](/shogi/shogiwiki/search/null-window-search/)で軽く調べる。
必要なときだけ再探索することで、探索量を減らす。
## 概要
PVS の基本的な考え方は、
- 最善手候補は前回反復の Principal Variation 手である可能性が高い
- それ以外の手は「本当にそれより良いか」だけ先に判定すればよい
というものである。
そのため、各ノードで
1. 最初の手を通常の `alpha-beta` 窓で探索する
2. 残りの手を `[-alpha-1, -alpha]` のような狭い窓で探索する
3. 狭い窓で fail-high したときだけ通常窓で再探索する
という流れを取る。
## なぜ速くなるのか
[反復深化](/shogi/shogiwiki/search/iterative-deepening/)と[手の並べ替え](/shogi/shogiwiki/search/move-ordering/)がうまく働くと、
多くのノードで最初の手が本当に最善手に近くなる。
その場合、2手目以降は
- 「今の最善手より悪い」
ことだけ確かめれば十分なので、狭い探索窓で安く済む。
このため、通常の[アルファベータ法](/shogi/shogiwiki/search/alpha-beta/)より少ないノードで済むことが多い。
## 実装例
```cpp
int pvs(Position pos, int depth, int alpha, int beta) {
if (depth == 0 || pos.isTerminal()) {
return evaluate(pos);
}
bool firstMove = true;
for (Move move : generateMoves(pos)) {
Position next = doMove(pos, move);
int score;
if (firstMove) {
score = -pvs(next, depth - 1, -beta, -alpha);
firstMove = false;
} else {
score = -pvs(next, depth - 1, -alpha - 1, -alpha);
if (score > alpha && score < beta) {
score = -pvs(next, depth - 1, -beta, -alpha);
}
}
if (score >= beta) {
return score;
}
if (score > alpha) {
alpha = score;
}
}
return alpha;
}
```
## NegaScout との関係
PVS と [NegaScout](/shogi/shogiwiki/search/negascout/) は、実用上かなり近い手法として扱われる。
どちらも「最初の手以外は狭い窓で試し、必要なら再探索する」という発想に基づいている。
実装上の細部や再探索の扱いに違いはあるが、現代エンジンではほぼ同系統の最適化とみなしてよい。
## Aspiration Windows との関係
[Aspiration Windows](/shogi/shogiwiki/search/aspiration-windows/)と組み合わせると、
ルート探索全体の窓も狭くできるため、さらに効率が上がることが多い。
ただし、探索が不安定だと fail-high / fail-low による再探索が増えやすい。
## 将棋AIでの位置づけ
現代的な将棋AIでは、探索の中心は
- [negamax](/shogi/shogiwiki/search/negamax/)
- [アルファベータ法](/shogi/shogiwiki/search/alpha-beta/)
- PVS
という積み重ねでできていることが多い。
そのため、単体の新アルゴリズムというより、
現代的な alpha-beta 系探索の実装形のひとつと考えると分かりやすい。
## 注意点
- [手の並べ替え](/shogi/shogiwiki/search/move-ordering/)が悪いと再探索が増えて効率が落ちる
- [探索不安定性](/shogi/shogiwiki/search/search-instability/)が強いと、狭い窓での判定が当てにならないことがある
- 葉付近では通常探索との差が小さいので、浅い深さでは単純化されることもある
## 関連項目
- [アルファベータ法](/shogi/shogiwiki/search/alpha-beta/)
- [negamax](/shogi/shogiwiki/search/negamax/)
- [Null Window](/shogi/shogiwiki/search/null-window-search/)
- [Aspiration Windows](/shogi/shogiwiki/search/aspiration-windows/)
- [反復深化](/shogi/shogiwiki/search/iterative-deepening/)
- [Principal Variation](/shogi/shogiwiki/search/principal-variation/)
## 参考にしたホームページ
- [Chessprogramming Wiki: Principal Variation Search](https://www.chessprogramming.org/Principal_Variation_Search)
- [Chessprogramming Wiki: Principal Variation](https://www.chessprogramming.org/Principal_Variation)
- [Chessprogramming Wiki: Aspiration Windows](https://www.chessprogramming.org/Aspiration_Windows)