《对弈程序基本技术》专题
 
Zobrist键值
 
Bruce Moreland /
 
比较局面的方法
 
  国际象棋局面包含了棋盘上的棋子、哪一方走棋、是否能易位、是否能吃过路兵等信息。
  在写国际象棋的程序时,需要比较两个局面看它们是否相同。如果你比较每个棋子的位置,或许不需要花很多时间,但是实战中你每秒种需要做成千上万次比较,因此这样会使比较操作变成瓶颈的。另外,需要比较的局面数量多得惊人,要存储每个棋子的位置,需要占用非常大的空间。
  一个解决方案是建立一个标签,通常是64位。由于64位不足以区别每个局面,所以仍然存在冲突的标签。但是实战中这种情况非常罕见,你可以有充分的把握不会发生冲突。
  用32位是否足够,目前争论很多,而用64位通常是明智的。
  Zobrist键值是一个常用的建立标签的方法。
 
实现
 
  你必须从多维的64位数组开始,每个数组含有一个随机数。在C语言中,“rand()”函数返回一个15位的值(0~32767),所以要得到64位的随机数还需要再加工一下。实际上我已经为你做好了,这个64位随机数的函数是:
 
U64 rand64(void) {
 return rand() ^ ((U64)rand() << 15) ^ ((U64)rand() << 30) ^ ((U64)rand() << 45) ^ ((U64)rand() << 60);
}
 
  这个函数用来填满一个“U64”的元素(你需要自己来定义这个类型,这取决于你的编译器,试一下“long long”或者“__int64),它是通过调用一系列“rand()”来实现的。
  无论如何你的数组要有三维:棋子的类型、棋子的颜色和棋子的位置:
 
U64 zobrist[pcMAX][coMAX][sqMAX];
 
  程序启动时就把这个数组用随机数填满,随机数是必须非常随机的,我看到Usenet(新闻组网络系统)上很多人说“rand()”用在这里随机性不是很好,但是我一直都用“rand()”并且没有出现问题。如果你想使数组更随机,就去找更强大的随机函数,但是你要确保它的随机性不比“rand()”差。
  要为一个局面产生Zobrist键值,首先把键值设成零,然后找棋盘上的每个子,并且让键值跟“zobrist[pc][co][sq]”做异或(通过“^”运算符)运算。
  如果局面由白方走,那么别去动它,如果是黑方走,你还要在键值上异或一个64位的随机常数。
 
为什么Zobrist键值特别有用
 
  用Zobrist技术产生的键值,表面上跟局面没什么关系。如果一个棋子动过了,你会得到完全不同的键值,所以这两个键值不会挤在一块儿或者冲突。当你把它们用作散列表键值的时候会非常有效。
  另一个优点在于,键值的产生是可以逐步进行的。例如,你的白兵在e5格,那么键值里一定异或过一个“zobrist[PAWN][WHITE][E5]”。如果你再次异或这个值,那么根据异或的工作原理,这个兵就从键值里删除了。
  这就是说,如果你有当前局面的键值,并且需要把白兵从e5移到e6,你只要异或一个“白兵在e5”的键值,把兵从e5格移走,并且异或一个“白兵在e6”的键值,把兵放在e6上。比起从头开始一个个棋子去异或,这样做可以得到同样的键值。
  如果你要改变着子的一方,只要异或一个“改变着子方”的键值就可以了。你可以用类似的方法处理王车易位和吃过路兵的标志。
  用这种方法,你可以在搜索根结点的时候构造一个Zobrist键值,在搜索时通过走子函数“MakeMove()”来更新键值,一直让它保持和当前局面同步。
 
Zobrist键值的用途
 
  Zobrist键值通常用在散列键值当中,而散列键值在国际象棋程序里有以下几个作用:
  (1) Zobrist键值来实现置换表。置换表是一个巨大的散列表,来保存以前搜索过的局面,让你节省很多搜索的时间。如果你需要对某个局面搜索9层,你可以从置换表中查找该局面,如果它已经搜索过9层,那么你不必去重复搜索。置换表的一个并不起眼的作用是,它可以帮助你改善着法的顺序。
  (2) Zobrist键值来实现兵型的散列表。你可以用一个键值只记录棋盘上的兵,对兵型做了很复杂的分析后,在散列表中记录分析的结果。在实战中兵型是很少发生变化的,所以这个散列表的命中率会非常高,它可以为你评估兵型节省很多时间。
  (3) 可以用Zobrist键值制造一个很小的散列表,来检测当前着法路线中有没有重复局面,以便发现长将或其他导致和局的着法。
  (4) 可以用Zobrist键值创建支持置换的开局库。
 
  原文:http://www.seanet.com/~brucemo/topics/zobrist.htm
  译者:象棋百科全书网 (webmaster@xqbase.com)
  类型:全译
  • 上一篇 数据结构——0x88着法产生方法
  • 下一篇 基本搜索方法——简介()
  • 返 回 象棋百科全书——电脑象棋
  • www.xqbase.com