MTD(f)算法

前面已经介绍过,零宽窗口搜索(也称为极小窗口搜索)的结果只有二种,要么估值在窗口之上,要么估值在窗口之下。因此当我们对某段区间进行搜索时,可以选取区间上的一点进行零宽窗口搜索试探,利用其结果一分为二的特点,缩小估值的取值区间。在确定新的估值区间后,我们还可以再次进行试探。通过反复试探,就可以不断地缩小搜索范围,最终找到局面估值。

在选择每一次的试探值时,通常的想法是采用二分法,即每次都选择估值区间的中点进行试探。采用二分法的效率确实比较高,但是荷兰计算机科学家Aske Plaat经研究发现,在多次搜索试探过程中,局面估值往往会出现在前一次搜索的返回值附近,而机械地选取中点做为新的试探值并不是最高效的。于是他提出了一种选取前一次搜索返回值做为新试探值的MTD算法(Memory-enhanced Test Driver,缓存增强试探法)——MTD(f)。MTD(f)算法的代码如下:

int mtd(int alpha, int beta, int depth, int test){
	int best_value;
	do {
		// 进行零宽窗口试探
		best_value = alpha_beta(test-1, test, depth, 0);
		// 如果是alpha节点
		if (best_value < test) {
			// 更新估值上限,并将此做为新的试探值
			test = beta = best_value;
		// 否则是beta节点
		} else {
			// 更新估值下限
			alpha = best_value;
			// 新的试探值
			test = best_value + 1;
		}
	} while (alpha < beta);
	return best_value;
}

MTD(f)算法十分简捷,却又十分高效。但由于MTD(f)算法需要对同一局面多次进行搜索,因此必须采用散列表,否则无法体现其高效性,这也是MTD算法名称中缓存增强(Memory-enhanced)的含义所在。实践表明,在同样应用散列表的情况下,MTD(f)算法的搜索速度一般会比PVS算法略快些,MTD(f)算法的高效性已经得到普遍认可。

在应用MTD(f)算法时,需要一个初始试探值,一般可以简单地选取初始搜索区间的中点,当然也可以根据具体情况选择对搜索更有利的值。由于该算法必须采用散列表,散列表的性能对于整体算法的效率也是至关重要的。另外,估值的取值范围大小,也会影响MTD(f)算法的搜索速度。一般来说,估值越粗略(即取值范围较小),搜索速度会越快;这是由于试探的次数较少所致。

如果算法还涉及最佳棋步的求解,那么最佳棋步的取舍问题应引起注意。虽然MTD(f)每进行一次零宽窗口试探,都会得到一个新的最佳棋步,但对于alpha节点(best_value < test时),我们所得到的“最佳棋步”只是满足估值上限的棋步,而非真正最佳的棋步。因此,我们应丢弃这种虚假的最佳棋步,而保留上一次搜索结果。