主要变例搜索(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)时,这就成了零宽窗口(也称为极小窗口)。这种零宽窗口的搜索结果只有二种,要么是估值在窗口之下的alpha节点,要么是估值在窗口之上的beta节点。利用零宽窗口搜索一分为二的特点,可以很方便地判别估值的取值范围。因为零宽窗口搜索不会出现PV节点,这种判别过程非常高效,所以它广泛应用于各种优化的α-β剪枝算法中。

主要变例搜索(Principal Variation Search,简称PVS)算法就是一种采用零宽窗口技术、针对PV节点进行优化的剪枝算法,也称为极小窗口搜索(Minimal Window Search)算法。Tony Marsland和Murray Campbell(1982)首先提出了PVS算法[1],其后Alexander Reinefeld(1983)也提出了相类似的NegaScout算法[2],并证明其正确性[3]

下面我们来看看PVS算法是怎样进行优化的。在前面所介绍的α-β剪枝算法中,每下完一步棋,我们总是采用以下形式进行递归搜索:

value = -alpha_beta(-beta, -alpha);

而对于PVS算法,它首先假设之前已经找到最佳估值(其值为alpha),然后应用零宽窗口搜索,以便快速判别此假设的正确性:

value = -alpha_beta(-alpha-1, -alpha);

如果零宽窗口搜索的结果是value≤alpha,那么表明之前的假设是正确的,即这步棋不会有更好的估值,程序将直接舍弃这步棋。在这种情况下,由于采用了零宽窗口搜索,搜索时间将大大缩短。

但是如果零宽窗口搜索的结果表明之前的假设是错误的,那么还需要重新进行一次常规窗口的搜索。在这种情况下,PVS算法实际上多进行了一次零宽窗口搜索。但由于零宽窗口搜索耗时相对较少,而出现前一种情况的概率一般较大,额外进行一次零宽窗口搜索所花费的代价还是值得的。PVS算法的代码如下:

int pvs(int alpha, int beta, int depth, int pass = 0){
	// 当前最佳分值,预设为负无穷大
	int best_value = -INF_VALUE;
	// 尝试每个下棋位置
	for (int pos=A1; pos<=H8; ++pos) {
		// 试着下这步棋,如果棋步合法
		if (make_move(pos)) {
			int value;
			// 如果到达预定的搜索深度,直接给出局面估值
			if (depth <= 1) value = -evaluation();
			// 如果尚未找到有效节点……
			else if (best_value == -INF_VALUE
				// ……或者零宽窗口搜索表明存在更好的结果……
				|| (value = -pvs(-alpha-1, -alpha, depth-1, 0)) > alpha
				// ……且不会引发剪枝
				&& (alpha = value) < beta) {
					// 进行常规窗口搜索
					value = -pvs(-beta, -alpha, depth-1, 0);
			}
			// 撤消棋步
			undo_move(pos);
			// 如果这步棋引发剪枝
			if (value >= beta) {
				// 立即返回当前最佳结果
				return value;
			}
			// 如果这步棋更好
			if (value > best_value) {
				// 保存更好的结果
				best_value = value;
				// 更新估值下限
				if (value > alpha) alpha = value;
			}
		}
	}
	// 如果没有合法棋步
	if (best_value == -INF_VALUE) {
		// 如果上一步棋也是跳步,表明对局结束
		if (pass) {
			// 直接给出精确比分
			best_value = get_score();
		// 否则这步棋跳步
		} else {
			make_pass();
			// 递归搜索,并标明该跳步
			best_value = -pvs(-beta, -alpha, depth, 1);
			// 撤消跳步
			undo_pass();
		}
	}
	// 返回最佳结果
	return best_value;
}

由于PVS算法的高效性是建立在已找到最佳估值的假设之上,因此在尚未找到有效节点时,只需进行常规窗口搜索。

一般来说,PVS算法的总体速度会比常规α-β剪枝算法快一些。如果将PVS算法与棋步排序、散列表等优化技术相结合,算法的高效性将得到更充分的体现。

[1] Tony Marsland, Murray Campbell. Parallel Search of Strongly Ordered Game Trees. ACM Comput. Surv. 1982, 14(4): 533-551.

[2] Alexander Reinefeld. An Improvement to the Scout Tree-Search Algorithm. ICCA Journal, 1983, Vol. 6, No. 4, pp. 4-14.

[3] Alexander Reinefeld. Spielbaum-Suchverfahren. Informatik-Fachbericht 200, Springer-Verlag, Berlin, 1989, ISBN 3-540-50742-6.