Tester les inégalités : le Negascout/PVS

Plutôt que lancer aveuglement une nouvelle recherche alpha-bêta coûteuse en temps pour explorer les branches sœurs, une recherche rapide avec une fenêtre nulle (bêta = alpha+1) nous informerait de l'utilité de celle-ci.

l'algorithme Principal Variation Search

int alphabêta(int depth, int alpha, int bêta)
{
if (game over or depth <= 0)
return winning score or eval();
move bestMove = first move;
make move bestMove;
int current = -alphabêta(depth - 1, -bêta, -alpha);
unmake move bestMove;
if (current >= alpha)
alpha = current;
if (current < bêta) {
for (each remaining move m) {
make move m;
int score = -alphabêta(depth - 1, -(alpha+1), -alpha)
if (score > alpha && score < bêta)
score = -alphabêta(depth - 1, -bêta, -alpha)
unmake move m;
if (score >= current) {
current = score;
bestmove = m;
if (score >= alpha){
alpha = score;
if (score >= bêta)
break;
}
}
}
return current;
}