一般来说，程序搜索得越深，程序的棋力就越强。如果搜索深度足于算到终盘，就能得到真正的最佳棋步和精确比分。但是随着搜索深度的增加，搜索所花费的时间也将急剧上升。而在现实下棋或比赛中，时间往往是有限的。比如在常规黑白棋比赛中，一般限定每一方的总用时为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;
}

实践表明，迭代加深搜索所花费的时间只比固定深度的搜索略微多一点;更重要的是，这种算法可以适用于信赖时间进行搜索的场合。

在对每步棋思考时间的分配上，也有不少文章可做。例如前面所提到的，当某一深度的搜索在进行中发生超时，这一轮搜索将强行中止。由于搜索过程不完整，其结果往往需丢弃，这就难免会造成一定的浪费。一个解决此问题的思路是，虽然每一轮搜索所需的时间无法预先确定，但搜索过程还是有一定规律可循的。根据前几轮搜索的情况，可以大致预测出本轮搜索的时间。如果预测表明，剩余时间已经不足于完成本轮的搜索，那么就不再继续进行本轮搜索，而把剩余的时间留给下一步棋。