具体算法大概如下:
此算法的思想是创建一个hash [ chessman ] [ location ] 的数组,数组中每一个元素都是一个64 位随机数. 对中国象棋来说,就是hash[14 ] [ 90 ] . 求当前局面的哈希值,就是将棋盘上所有棋子在数组中对应的64 位数做异或运算,生成这一局面的唯一标识数. 哈希技术有2 个明显的优点:1) 64 位数使得局面冲突的可能性非常小,基本可以唯一标识当前局面,可以用作哈希表的索引;2)不用每一次展开节点时都计算局面的哈希值.只要在搜索开始时做初始化运算,在着法执行过程中通过异或运算求出变动的棋子及其位置即可.
开局库数据结构定义如下:
typedef st ruct {
Hash position ; / / 64 位哈希值
int stat u played ; / / 32 位局面权值
}BOO K KEY;
此结构包含了一个着法的信息. 开局库即为若干该种数据组成. Hash position 为局面的哈希值,
共64 位,将局面按“簇”存储,根据哈希值的高15 位值将局面分为若干簇,簇数量为215 个,所以哈希值的高15 位可作为哈希表的簇索引,即一级索引,索引数量共为32 768 个. 然后在相应簇中通过哈希值即可搜索到相应局面,哈希值可视为二级索引,这种方式大大提高了搜索开局库的效率。