Principal Variation Search（PVS）は、アルファベータ法をさらに効率化する探索手法である。 最初に調べた有望手だけを通常の探索窓で読み、残りの手はまずNull Windowで軽く調べる。 必要なときだけ再探索することで、探索量を減らす。
PVS の基本的な考え方は、
というものである。
そのため、各ノードで
alpha-beta 窓で探索する[-alpha-1, -alpha] のような狭い窓で探索するという流れを取る。
反復深化と手の並べ替えがうまく働くと、 多くのノードで最初の手が本当に最善手に近くなる。
その場合、2手目以降は
ことだけ確かめれば十分なので、狭い探索窓で安く済む。 このため、通常のアルファベータ法より少ないノードで済むことが多い。
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;
}PVS と NegaScout は、実用上かなり近い手法として扱われる。 どちらも「最初の手以外は狭い窓で試し、必要なら再探索する」という発想に基づいている。
実装上の細部や再探索の扱いに違いはあるが、現代エンジンではほぼ同系統の最適化とみなしてよい。
Aspiration Windowsと組み合わせると、 ルート探索全体の窓も狭くできるため、さらに効率が上がることが多い。 ただし、探索が不安定だと fail-high / fail-low による再探索が増えやすい。
現代的な将棋AIでは、探索の中心は
という積み重ねでできていることが多い。
そのため、単体の新アルゴリズムというより、 現代的な alpha-beta 系探索の実装形のひとつと考えると分かりやすい。