电脑黑白棋最核心的部分就是搜索算法，它实际上是反映了黑白棋程序的算棋过程。搜索算法的好坏，将直接影响着程序的算棋速度和棋力。下面我们就从最基本的搜索算法开始。
例如，对于图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年)所提出了负极大值(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甚至更大。
参考文献
Donald E. Knuth, Ronald W. Moore.An Analysis of Alpha-Beta Pruning. Artificial Intelligence, 1975, 6(4): 293-326.
