一般来说，程序搜索得越深，程序的棋力就越强。如果搜索深度足于算到终盘，就能得到真正的最佳棋步和精确比分。但是随着搜索深度的增加，搜索所花费的时间也将急剧上升。而在现实下棋或比赛中，时间往往是有限的。比如在常规黑白棋比赛中，一般限定每一方的总用时为20分钟。由于受到时间的制约，程序的搜索深度无法事先确定，而需要在下棋过程中动态地进行调整。为此，程序在下每步棋时，可以根据己方剩余时间的多少，合理分配当前这步棋的思考时间。但由于程序软硬件环境的不同和局面的不断变化，搜索深度和搜索时间之间没有一成不变的关系，搜索深度仍然无法确定。前面所介绍的固定深度的搜索已无法适用，这时可以采用迭代加深搜索(Iterative Deepening Search)。迭代加深搜索的代码如下：
……
// 如果进一步搜索的深度未超过剩余空位数
while (++depth <= n_empty) {
// 进一步搜索
value = alpha_beta(-INF_VALUE, INF_VALUE, depth);
// 如果超时
if (TIME_OUT) break;
}
……
为了保存所搜索到的最佳棋步结果，我们还引入了全局变量result。
// 无穷大分值 #define INF_VALUE 10000 // 初始搜索深度 #define MIN_DEPTH 4 // 测试是否超时 #define TIME_OUT (stop_clock && clock() >= stop_clock) // 最佳棋步结果 static int result; // 搜索终止时刻 static int stop_clock; int alpha_beta(int alpha, int beta, int depth, int pass = 0){ // 当前最佳棋步 int best_move = PASS; // 当前最佳分值，预设为负无穷大 int best_value = -INF_VALUE; // 尝试每个下棋位置 for (int pos=A1; pos<=H8; ++pos) { // 试着下这步棋，如果棋步合法 if (make_move(pos)) { int value; // 如果到达预定的搜索深度，直接给出局面估值 if (dept <= 1) value = -evaluation(); // 否则，对所形成的局面进行递归搜索 else value = -alpha_beta(-beta, -alpha, depth - 1); // 撤消棋步 undo_move(pos); // 如果超时 if (TIME_OUT) return -INF_VALUE; // 如果这步棋引发剪枝 if (value >= beta) { // 立即返回当前最佳结果 result = pos; return value; } // 如果这步棋更好 if (value > best_value) { // 保存更好的结果 best_move = pos; best_value = value; // 更新估值下限 if (value > alpha) alpha = value; } } } // 如果没有合法棋步 if (best_value == -INF_VALUE) { // 如果上一步棋也是跳步，表明对局结束 if (pass) { // 直接给出精确比分 best_value = get_score(); // 否则这步棋跳步 } else { make_pass(); // 递归搜索，并标明该跳步 best_value = -alpha_beta(-beta, -alpha, depth, 1); // 撤消跳步 undo_pass(); } } // 返回最佳结果 result = best_move; return best_value; } int ids(int time_remain){ // 开始时刻 int start_clock = clock(); // 初始搜索深度 int depth = MIN_DEPTH; // 初始搜索不限时，以确保得到一个正确的棋步 stop_clock = 0; // 进行搜索深度 int best_value = alpha_beta(-INF_VALUE, INF_VALUE, depth); int best_move = result; // 如果进一增加搜索深度步搜索的深度未超过剩余空位数 while (++depth <= n_empty) { // 根据已进行的搜索情况重新调整搜索终止时刻 stop_clock = start_clock + (clock_t)(time_remain * (CLOCKS_PER_SEC / 1000.) - (clock() - start_clock)) / ((n_empty - depth + 2) / 2); // 进行常规的剪枝算法 int value = alpha_beta(-INF_VALUE, INF_VALUE, depth); // 如果超时 if (TIME_OUT) break; // 更新最佳结果 best_move = result; best_value = value; } // 返回最佳结果 result = best_move; return best_value; }
迭代加深搜索的思路十分简单，先从很浅的搜索深度(比如初始搜索深度为1)开始进行搜索，然后逐渐加深搜索深度进行下一轮搜索，直至时间用完为止。这样就可以做到有多少时间，就搜索多少深度。当然，上面这段代码只是个示意，在实际应用中，alpha_beta()内部也应进行超时判断。如果在某一深度的搜索过程中时间用完，搜索应立即中止，以免因等待本轮搜索结束而造成时间耗尽。
你也许会注意到，只有最后一轮搜索才是真正需要的，在这之前的搜索似乎都是在浪费时间。事实上，程序的搜索深度每增加一层，搜索时间往往成倍增长。程序大部分的时间将花在最后一轮搜索上，之前的搜索时间基本可以忽略。而且，迭代加深搜索还可以与散列表结合使用，这样较浅度搜索的结果将保存在散列表中，可对更深度搜索起一定的指导作用。如果采用MTD(f)算法，前一次搜索的结果还可以做为更深一层搜索的初始试探值：
int deepening() {
int value = 0;
// 初始搜索深度
int depth = 1;
do {
// 进行常规的MTD(f)算法
value = mtd(value, depth);
// 增加搜索深度
depth++;
// 直到时间用完
} while (!time_out) ;
return value;
}
实践表明，迭代加深搜索所花费的时间只比固定深度的搜索略微多一点;更重要的是，这种算法可以适用于信赖时间进行搜索的场合。
在对每步棋思考时间的分配上，也有不少文章可做。例如前面所提到的，当某一深度的搜索在进行中发生超时，这一轮搜索将强行中止。由于搜索过程不完整，其结果往往需丢弃，这就难免会造成一定的浪费。一个解决此问题的思路是，虽然每一轮搜索所需的时间无法预先确定，但搜索过程还是有一定规律可循的。根据前几轮搜索的情况，可以大致预测出本轮搜索的时间。如果预测表明，剩余时间已经不足于完成本轮的搜索，那么就不再继续进行本轮搜索，而把剩余的时间留给下一步棋。
