主要变化搜索（PVS）
在α-β剪枝算法中，因为存在剪枝，搜索过程并不完整，所以剪枝算法所得到的估值不一定是准确值。通过分析可知，对于函数调用：
value = alpha_beta(alpha, beta);
当alpha<value<beta时，此估值是准确值；这一搜索节点也称为PV（Principal Variation，主要变化）节点。当value≤alpha时，此估值将不是准确值，而只是估值的上限；这一搜索节点也称为alpha节点。当value≥beta时，此估值也不是准确值，而是估值的下限；这一搜索节点也称为beta节点。
由此可看出，α-β剪枝算法重点关注的是(alpha,beta)区间，它也称为搜索窗口。相对于alpha节点和beta节点而言，程序搜索PV节点的过程是比较费时的。如果把搜索窗口的宽度减小，发生剪枝的可能性就会加大，程序搜索的时间也会短些。特别是当窗口宽度减为零，即搜索窗口为(t-1,t)时，这就成了零宽窗口（也称为极小窗口）。这种零宽窗口搜索的结果只有二种，要么估值在窗口之上，要么估值在窗口之下。利用零宽窗口搜索一分为二的特点，可以很方便地判别估值的取值范围。因为零宽窗口搜索不会出现PV节点，这种判别过程非常高效，所以它广泛应用于各种优化的α-β剪枝算法中。
主要变化搜索（Principal Variation Search，简称PVS）就是一种采用零宽窗口技术、针对PV节点进行优化的剪枝算法，也称为极小窗口搜索（Minimal Window Search）算法。下面我们来看看PVS看法是怎样进行优化的。在α-β剪枝算法中，我们采用以下形式进行递归搜索：
value = -alpha_beta(-beta, -alpha);
对于上面这个(-beta,-alpha)搜索窗口，我们可以先进行一次零宽窗口搜索，以便快速判别出是否可能存在更好的估值。
value = -alpha_beta(-alpha-1, -alpha);
如果零宽窗口搜索的结果是value≤alpha，那么表明局面估值不会超过alpha，即不可能存在更好的估值，程序将直接舍弃这一变化。在这种情况下，由于采用了零宽窗口搜索，它会比直接进行常规搜索省时得多。如果没有出现上述情况，那么程序只得重新进行一次常规的递归搜索。在这种情况下，程序实际上多进行了一次零宽窗口搜索。但是因为零宽窗口搜索耗时很少，而出现前一种情况的概率一般比较大，所以额外进行一次零宽窗口搜索所花的代价是值得的。PVS算法的代码如下：
int pvs(int alpha, int beta, int depth, int passed){
//当前搜索到的最佳估值，预设为负无穷大
int best_value = -INF_VALUE;
//如果到达搜索深度，直接给出估值
if (depth <= 0) {
return evaluation();
}
//尝试每个下棋位置
for (int point=A1; point<=H8; point++) {
//试着下这步棋。如果棋步非法，函数将返回0
if (make_move(point)) {
//如果当前节点是PV节点
if (best_value == alpha) {
//先进行零宽窗口搜索
int value = -pvs(-alpha-1, -alpha, depth-1, 0);
//如果不可能存在更好的估值
if (value <= alpha) {
//返回原来的局面
unmake_move(point);
//舍弃这步棋
continue;
}
//如果发生剪枝
if (value >= beta) {
//返回原来的局面
unmake_move(point);
//搜索提前结束
return value;
}
//由于存在更好的估值，先保存当前结果，为下一步常规搜索做准备
best_value = alpha = value;
}
//进行常规递归搜索。由于下棋方轮换，估值取负
int value = -pvs(-beta, -alpha, depth-1, 0);
//返回原来的局面
unmake_move(point);
//保存更好的结果
if (value > best_value) {
best_value = value;
//更新下限
if (value > alpha) {
//如果发生剪枝
if (value >= beta) {
//搜索提前结束
return value;
}
alpha = value;
}
}
}
}
//如果没有合法棋步
if (best_value == -INF_VALUE) {
//如果上一步弃权（Pass），表明对局结束
if (passed) {
//计算精确比分
return get_exact();
}
//这步弃权（Pass）
pass_move();
//递归搜索
best_value = -alpha_beta(-beta, -alpha, depth, 1);
//返回原来的局面
unpass_move();
}
return best_value;
}
在上述代码中，由于PVS算法需要额外进行一次零宽窗口搜索，为了确保算法的高效性，程序只在当前节点成为PV节点后，才预先进行零宽窗口搜索。一般来说，PVS算法的总体速度会比常规α-β剪枝算法快一些。如果把PVS算法与棋步排序、散列表等优化技术相结合，算法的高效性将会得到更充分的体现。