- 《对弈程序基本技术》专题
-
- 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着法产生方法
下一篇 基本搜索方法——简介(一)
返 回 象棋百科全书——电脑象棋
