散列表

在黑白棋中,不同的下棋顺序有时会出现相同的局面。例如十分典型的Tiger开局,可以按f5、d6、c3、d3、c4和f5、d6、c4、d3、c3两种顺序开局,最终都将形成同一个局面,这种现象就称为同形(Transposition)。程序在分析这两种下棋顺序时,将对该局面重复进行搜索。而在PVSMTD等算法中,许多局面也往往需要进行多次搜索。如果能将搜索过的局面及其结果保存下来,那么当程序再次遇到相同局面时,就可以直接调用以前的搜索结果,从而缩短搜索时间。保存局面信息的表,就称为同形表(Transposition Table)。不过,程序搜索过的局面成千上万,如果全部保存下来将耗费大量存储空间。而且要从大量的保存数据中找出某一局面,也是十分费时的。通常较典型的做法是使用散列表(Hash Table,又称为哈希表)来实现同形表。

简单地说,散列表是通过散列机制,把一个信息空间映射到一个相对有限的存储空间上。例如,对于某个黑白棋局面,我们需要保存该局面及其估值等相关信息。在确定该信息的存储地址时,我们选择当前局面做为关键值,再由这个关键值算出一个唯一的散列码(Hash Code)。计算散列码的过程称为散列(Hashing),这是由散列函数完成的。在棋类程序中,常用的散列函数是Zobrist散列。由于散列码必须唯一代表一个局面,散列码的位数就取决于可能出现的局面数。对于8×8棋盘,理论上有364种局面,为了得到唯一的散列码,散列码至少要达到102位。但是考虑到有些局面是不可能出现的,而且程序在有限的时间内也不可能搜索到所有的局面,因此散列码一般取64位就足够了。

现在将散列码转换为散列表的存储地址,一般可以直接取散列码的某些位做为存储地址。例如,当散列表的存储单元数为64k时,我们就可以取散列码的低16位做为存储地址,在该存储单元保存局面及其估值等相关信息。从上述过程我们可以看出,因为可以由存储信息直接计算出存储地址,无需对大量存储局面逐一进行比较,所以存取十分迅速,其存取速度基本上与存储空间大小无关。但是这种散列表技术也有不足之处,散列函数是无法保证存储信息一一映射到存储地址的,不同的信息可能会映射到同一个存储地址上,这就称为冲突。当发生冲突时,必须妥善处理好同一映射地址上不同信息的存取问题。不过对于程序搜索来说,这不算什么难题,最简单的处理方法就是直接舍弃这些发生冲突的信息。因为如果程序在散列表中找不到以前的局面,它只需重新再搜索一遍即可。除了多花费点时间外,并不会影响搜索结果。

下面通过一个实例来说明散列表的具体实现。值得注意的是,这并不是唯一的或者最好的方法,散列表还有许许多多不同的实现形式。如何建立高效、实用的散列表,需要通过实践不断地去摸索。

假设我们想用散列表保存各局面的最佳棋步、估值等信息。由于搜索结果可能是准确值,也可能只是取值范围,为了不失一般性,我们保存估值的上、下限。

struct Hashtable_Node{
	// 锁值
	unsigned int lock;
	// 估值上、下限
	int lower, upper;
	// 最佳棋步
	int best_move;
	// 搜索深度
	int depth;
};

结构中的锁值是用来识别各个局面用的,最简单的方法就是取散列码做为锁值,但这里为了方便运算,仅取散列码的高32位。从某种意义上说,这样取锁值实际造成散列码的有效位达不到64位。如果在实践中发现散列码满足不了唯一性要求,应适当增加锁值的位数。

解决散列表冲突的方法是舍弃发生冲突的信息,而舍弃信息的策略一般有“更深替换”和“始终替换”两种,它们各有优缺点。“更深替换”是用搜索较深的局面替换搜索较浅的局面,“始终替换”是始终用新的局面替换老的局面。本例综合了两种策略的优点,在一个散列表单元中同时保存了两个局面节点,一个按“更深替换”策略更新,另一个按“始终替换”策略更新。

struct Hashtable{
	// “更深替换”和“始终替换”节点
	struct Hashtable_Node deepest, newest;
};

更新散列表的函数代码如下:

// 散列表单元数为64k
const int HASHTABLE_BIT_NUM = 16;
const int HASHTABLE_SIZE = 1u << HASHTABLE_BIT_NUM;
// 取址掩码
const int HASHTABLE_MASK = HASHTABLE_SIZE - 1;
// 散列表
struct Hashtable hashtable[HASHTABLE_SIZE];

// 更新散列表,加入一个局面
void hash_update(unsigned int hashcode[], int lower, int upper, int best_move, int depth){
	Hashtable *p = hashtable + (hashcode[0] & HASHTABLE_MASK);
	Hashtable_Node *deepest = &(p->deepest), *newest = &(p->newest);
	// 如果与“更深替换”的局面相同
	if ((hashcode[1] == deepest->lock) && (depth == deepest->depth)) {
		// 更新下限
		if (lower > deepest->lower) {
			deepest->lower = lower;
			// 保存最佳棋步
			deepest->best_move = best_move;
		}
		// 更新上限
		if (upper < deepest->upper) {
			deepest->upper = upper;
		}
	// 如果与“始终替换”的局面相同
	} else if ((hashcode[1] == newest->lock) && (depth == newest->depth)) {
		// 更新下限
		if (lower > newest->lower) {
			newest->lower = lower;
			// 保存最佳棋步
			newest->best_move = best_move;
		}
		// 更新上限
		if (upper < newest->upper) {
			newest->upper = upper;
		}
	// 否则表明发生冲突,进入冲突处理。如果搜索深度更大,进行“更深替换”
	} else if (depth > deepest->depth) {
		// 原先保存的局面仍有保留价值
		*newest = *deepest;
		// 保存当前搜索结果
		deepest->lock = hashcode[1];
		deepest->lower = lower;
		deepest->upper = upper;
		deepest->best_move = best_move;
		deepest->depth = depth;
	// 否则进行“始终替换”
	} else {
		// 保存当前搜索结果
		newest->lock = hashcode[1];
		newest->lower = lower;
		newest->upper = upper;
		newest->best_move = best_move;
		newest->depth = depth;
	}
}

上述代码中,散列码保存在hashcode数组内,其中hashcode[0]为散列码低32位,hashcode[1]为高32位。更新散列表时,如果新加入的局面已经存在于散列表中,则对以前的搜索结果进行修正;否则进入冲突处理。

查找散列表的函数代码如下:

// 查找散列表,取出一个局面
Hashtable_Node *hash_get(unsigned int hashcode[], int depth){
	Hashtable *p = hashtable + (hashcode[0] & HASHTABLE_MASK);
	Hashtable_Node *deepest = &(p->deepest), *newest = &(p->newest);
	// 如果与“更深替换”的局面相同,则返回该局面节点
	if ((hashcode[1] == deepest->lock) && (depth == deepest->depth)) {
		return deepest;
	// 如果与“始终替换”的局面相同,则返回该局面节点
	} else if ((hashcode[1] == newest->lock) && (depth == newest->depth)) {
		return newest;
	// 否则表明无此局面,返回空指针
	} else {
		return NULL;
	}
}

有了散列表,我们就可以在剪枝算法中应用散列表,以下是一个示例:

int alpha_beta_with_hashtable(int alpha, int beta, int depth, int pass){
	unsigned int hashcode[];
	// 计算当前局面的散列码
	get_hashcode(hashcode);
	// 查询散列表
	Hashtable_Node *node = hash_get(hashcode, depth);
	// 如果散列表中存在当前局面
	if (node) {
		// 如果保存的下限大于alpha值,则修正alpha值
		if (node.lower > alpha) {
			alpha = node.lower;
			// 如果下限大于或等于beta值,则发生剪枝
			if (alpha >= beta) {
				return alpha;
			}
		}
		// 如果保存的上限小于beta值,则修正beta值
		if (node.upper < beta) {
			beta = node.upper;
			// 如果上限小于或等于alpha值,则向下剪枝
			if (beta <= alpha) {
				return beta;
			}
		}
	}
	// 进行常规的剪枝算法
	int best_value = alpha_beta(alpha, beta, depth, pass);
	// 在散列表中保存当前搜索结果
	if (best_value >= beta) {
		hash_update(hashcode, best_value, INF_VALUE, best_move, depth);
	} else if (best_value <= alpha) {
		hash_update(hashcode, -INF_VALUE, best_value, best_move, depth);
	} else {
		hash_update(hashcode, best_value, best_value, best_move, depth);
	}
	return best_value;
}

在实际应用中,有两个问题值得注意。其一,是散列表的初始化问题。当散列表较大时,对整个散列表进行一次初始化将花费较多时间。因此有些人建议最多只在程序开头进行一次初始化,而不需要每一步运算前都进行初始化。其二,是散列表本身的运算时间问题。虽然使用散列表可以减少搜索次数,但是散列表运算本身需要花费额外的时间。实际上,其他一些优化技术也有类似问题。因此当搜索深度很少时,搜索次数的减少可能不足以弥补优化技术所需花费的额外时间,这时就不要使用优化技术,而只使用最基本的剪枝算法。