在黑白棋中,不同的下棋顺序有时会出现相同的局面。例如十分典型的Tiger开局,可以按f5、d6、c3、d3、c4和f5、d6、c4、d3、c3两种顺序开局,最终都将形成同一个局面,这种现象就称为同形(Transposition)。程序在分析这两种下棋顺序时,将对该局面重复进行搜索。而在PVS、MTD等算法中,许多局面也往往需要进行多次搜索。如果能将搜索过的局面及其结果保存下来,那么当程序再次遇到相同局面时,就可以直接调用以前的搜索结果,从而缩短搜索时间。保存局面信息的表,就称为同形表(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; }
在实际应用中,有两个问题值得注意。其一,是散列表的初始化问题。当散列表较大时,对整个散列表进行一次初始化将花费较多时间。因此有些人建议最多只在程序开头进行一次初始化,而不需要每一步运算前都进行初始化。其二,是散列表本身的运算时间问题。虽然使用散列表可以减少搜索次数,但是散列表运算本身需要花费额外的时间。实际上,其他一些优化技术也有类似问题。因此当搜索深度很少时,搜索次数的减少可能不足以弥补优化技术所需花费的额外时间,这时就不要使用优化技术,而只使用最基本的剪枝算法。