基本搜索

电脑黑白棋最核心的部分就是搜索算法,它实际上是反映了黑白棋程序的算棋过程。搜索算法的好坏,将直接影响着程序的算棋速度和棋力。下面我们就从最基本的搜索算法开始。

例如,对于图1所示的局面,白棋有三步棋可下:D6、F4、F6,黑白棋程序将如何找出最佳的棋步呢?

算棋局面
图1 白先,三步棋可下

其实程序的算棋过程和人类棋手很相似,它将对当前局面的所有可下棋步分别进行尝试,计算出每种棋步变化之后的局面,并对形成的局面结果分别进行评估。例如对于图1的局面,白棋分别下D6、F4、F6后,将形成图2、图3、图4三种局面。

第一种变化
图2 黑先,估值为+5
第二种变化
图3 黑先,估值为+5
第三种变化
图4 黑先,估值为+4

程序对局面的评估过程一般由估值函数来完成,它将根据盘面上棋子的分布情况,给出一个表示局面优劣程度的评估数值,这就称为估值。我们最先所能想到的估值函数可能就是行动力,因为它是我们在下黑白棋时评估局面极其重要的指标之一。虽然行动力并不算是一个很有效的估值函数,但它不失为一个简单的实例。根据行动力计算不难看出,图2、图3、图4的估值分别为:+5、+5、+4。由于这些估值是相对于各自的局面而言的,换句话说,估值是从黑棋的角度来看的;如果回到图1所示的局面上,白棋将从完全相反的角度来看待估值,因此这些估值都要取其负值,就如图5所示的那样。

局面
图5 白先,三步棋的估值

很显然,白棋将从这些取负值的估值中选择最大的那步棋F6。这就是高德纳与Moore(1975年)[1]所提出了负极大值(Negamax)算法,它是对之前广泛使用的极大极小值(Minimax)算法的改进。黑白棋的负极大值搜索伪代码如下:

int negamax(){
	// 当前最佳分值,预设为负无穷大
	int best_value = -INF_VALUE;
	// 尝试每个下棋位置
	for (int pos=A1; pos<=H8; ++pos) {
		// 试着下这步棋,如果棋步合法
		if (make_move(pos)) {
			// 对所形成的局面进行评估
			int value = -evaluation();
			// 撤消棋步
			undo_move(pos);
			// 如果这步棋更好
			if (value > best_value) {
				// 保存更好的结果
				best_value = value;
			}
		}
	}
	// 如果没有合法棋步
	if (best_value == -INF_VALUE) {
		// 直接评估当前局面
		best_value = evaluation();
	}
	// 返回最佳结果
	return best_value;
}

当然,这里所提供的伪代码只是一个示意,实际编程中还需要考虑搜索效率等问题,而且还可能需要对最佳棋步进行保存。在这段代码中,当前最佳估值预设为实际棋局中永远到不了的负估值-INF_VALUE(如-10000)。然后程序尝试每一个下棋位置,由make_move()函数对下棋后的局面进行更新(如果遇到非法棋步,make_move()将忽略这步棋,并返回0)。再由估值函数evaluation()对下棋所形成的局面进行评估(例如,可以直接引用mobility()计算行动力);这里由于下棋方轮换,估值应取负值。如果这步棋的估值更好,程序将保存更好的结果。然后由undo_move()函数撤消棋步,恢复原来的局面,并准备尝试下一种变化。最终,程序将得到所有棋步中的最佳估值。

在黑白棋中,有时还会遇到无棋可下的局面,这时下棋方应跳步(即Pass)。对于这种特殊局面,我们可以直接评估当前局面,也可以另行处理(例如交给对方去评估,再取负值)。

实际使用的估值函数可能会更复杂些,而估值的取值范围一般为[-64, +64],以便直观地表示对终局比分的评估。估值为正时,表示局面处于优势,正值越大,优势越大;反之,负值表示劣势。例如,“估值为+6”则表示当前局面具有胜6子的优势。当然,也有一些程序则将估值表示为对终局胜率的评估,或者采用其他一些取值范围。

但由于影响局面优劣的因素很多,目前还没能找出一个完全精确的黑白棋估值函数,因此上述搜索过程所找到的并不一定是真正的最佳棋步。不过根据人类棋手的算棋经验,如果我们能向前多算几步棋,那么对局面评估的准确性将得到提高。为了实现前瞻更多步棋,程序在试下某一步棋后并不直接进行局面评估,而是递归调用上述搜索过程,以便尝试更深层的棋步;直到搜索达到预定的棋步深度后,才调用估值函数。一般来说,程序搜索得越深,准确性也就越高。在极端情况下,如果程序搜索足够的深度,可以一直算到终局,这时得到的结果就是完全精确的。深层搜索的伪代码如下:

int negamax(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 value = -negamax(depth - 1);
			// 撤消棋步
			undo_move(pos);
			// 如果这步棋更好
			if (value > best_value) {
				// 保存更好的结果
				best_value = value;
			}
		}
	}
	// 如果没有合法棋步
	if (best_value == -INF_VALUE) {
		// 如果上一步棋也是跳步,表明对局结束
		if (pass) {
			// 直接给出精确比分
			best_value = get_score();
		// 否则这步棋跳步
		} else {
			make_pass();
			// 递归搜索,并标明该跳步
			best_value = -negamax(depth, 1);
			// 撤消跳步
			undo_pass();
		}
	}
	// 返回最佳结果
	return best_value;
}

为了跟踪搜索深度,我们引进了参数depth。搜索每深入一层,depth递减一。当搜索深度达到预定值时,就不再进一步递归搜索。而参数pass则表示上一步棋是否为跳步,这样可以方便判断对局提前结束的情况。如果程序在搜索中遇到了双方都跳步的局面,那么表明对局已经结束。这时不再需要进行估值,而只需调用get_score()直接给出双方的比分;这是个精确值。

对于出现上述对局提前结束的情况,精确值和估值的权重问题也是值得探讨的。设想一下,如果有两步棋供你选择,一步棋的估值为+10;而另一步棋会出现对局提前结束的情况,其精确比分为+1。你会选择哪一步棋呢?虽然前者胜10子看上去似乎更好些,但它毕竟只是个估值;其实际结果很有可能变成负于对方。而后者虽然只是胜1子,但这是个精确结果;它可以确保你获胜。如果你对估值函数的准确性存有疑问,也许你会更倾向于选择后者。为了达到这种效果,你可以采用加权比分,例如当精确比分为胜1子时,加权比分输出+10甚至更大。

参考文献

[1] Donald E. Knuth, Ronald W. Moore. An Analysis of Alpha-Beta Pruning. Artificial Intelligence, 1975, 6(4): 293-326.