《棋战顺序基本手艺》专题
 
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