《棋战顺序基本手艺》专题
 
置换表
 
Bruce Moreland /
 
一个多功用的数据组织
 
  国际象棋的搜索树能够用图来透露表现,而置换结点能够引向之前搜索过的子树上。置换表能够用来检测这类状况,从而制止一次又一次休息。若是“1. e4 d6 2. d4”以后的局势以前搜索过了,那就没有需要再搜索“1. d4 d6 2. e4”以后的局势了。
  这个缘由能够勉励着早期的计算机国际象棋顺序的设想师们,而现在现实上这照样置换表的主要用途。在某些局势,譬喻在没有通路兵的王兵残局中,搜检到的置换的数目是惊人的,以致于搜索能够在短达时刻内到达很深的深度。
  省去一次又一次的事情,这是置换表的一大特征,然则在一样寻常的中局局势里,置换表的其余一个功用越发主要。每一个散列项里都有局势中最好的着法,我在“迭代加深”这一章里注释过,首先搜索好的着法能够大幅度提升搜索效能。因而若是你在散列项里找到最好的着法,那末你首先搜索这个着法,这样会革新你的着法递次,增加分枝因子,从而在短的时刻内搜索得更深。
 
完成
 
  主置换表是一个散列数组,每一个散列项看上去像这样:
 
#define hashfEXACT 0
#define hashfALPHA 1
#define hashfBETA 2
typedef struct tagHASHE {
 U64 key;
 int depth;
 int flags;
 int value;
 MOVE best;
} HASHE;
 
  这个散列数组是以“Zobrist键值”为目的的。你求得局势的键值,除以散列表的项数失掉余数,这个散列项就象征该局势。由于许多局势都有能够跟散列表中统一项功用,因而散列项要求包罗一个校验值,它能够用来确认该项就是你要找的。一般校验值是一个64位的数,也就是下面谁人案例的第一个域。
  你从搜索中失掉效果后,要生存到散列表中。若是你计划用散列表来制止一次又一次事情,那末主要的是记住搜索有多深。若是你在一个结点上搜索了3层,厥后又计划做10层搜索,你就不能以为散列项里的信息是准确的。因而子树的搜索深度也要纪录。
  在Alpha-Beta搜索中,你很少能失掉搜索结点的准确值。AlphaBeta的存在有助你裁剪掉没有用的子树,然则用Alpha-Beta有个小的瑕玷,你一般不会知道一个结点究竟有多坏也许有多好,你只是知道它足够坏或足够好,从而不要求虚耗更多的时刻。
  固然,这就引发了一个问题,散列项里究竟要生存甚么值,而且当你要取得它时怎样来做。谜底是贮存一个值,另加一个符号来说明这个值是甚么寄义。在我下面的案例中,譬喻说你在评定域中生存了16,而且在符号域生存了“hashfEXACT”,这就意味着该结点的评定是准确值16;若是你在符号域中生存了“hashfALPHA”,那末结点的值最多是16;若是生存了“hashfBETA”,这个值就最少是16
  当你在搜索中遇到特定状况时,很随意纰漏注定评定和符号应当生存哪些内容。然则制止毛病长短常主要的,散列表长短常随意纰漏出毛病的,而且一旦犯下毛病就很难捕捉出来。
  我的散列项的最终一个域,生存着上次搜索到这个局势时的最好着法。有时我没有失掉最好着法,例如任何低出界限的状况(前往一个小于或即是Alpha的值),而其他状况一定有最好着法,例如凌驾界限的状况(前往一个大于或即是Beta的值)【译注:只需叶子结点才没有最好着法,纵使是Alpha结点,一切的着法都是差的,也应当从中找一个最好的着法,它对更深一层的搜索会带来很大的有益之处。】
  若是找到最好着法,那末它应当首先被搜索。
  下面是树模顺序,是依据Alpha-Beta函数修正的,改动的中央用扎眼的字标出:
 
int AlphaBeta(int depth, int alpha, int beta) {
 int hashf = hashfALPHA;
 if ((val = ProbeHash(depth, alpha, beta)) != valUNKNOWN) {
  // 【valUNKNOWN必需小于-INFINITY或大于INFINITY,否则会跟评定值殽杂。】
  return val;
 }
 if (depth == 0) {
  val = Evaluate();
  RecordHash(depth, val, hashfEXACT);
  return val;
 }
 GenerateLegalMoves();
 while (MovesLeft()) {
  MakeNextMove();
  val = -AlphaBeta(depth - 1, -beta, -alpha);
  UnmakeMove();
  if (val >= beta) {
   RecordHash(depth, beta, hashfBETA);
   return beta;
  }
  if (val > alpha) {
   hashf = hashfEXACT;
   alpha = val;
  }
 }
 RecordHash(depth, alpha, hashf);
 return alpha;
}
 
  以下就是两个新的函数的代码:
 
int ProbeHash(int depth, int alpha, int beta) {
 HASHE *phashe = &hash_table[ZobristKey() % TableSize()];
 if (phashe->key == ZobristKey()) {
  if (phashe->depth >= depth) {
   if (phashe->flags == hashfEXACT) {
    return phashe->val;
   }
   if ((phashe->flags == hashfALPHA) && (phashe->val <= alpha)) {
    return alpha;
   }
   if ((phashe->flags == hashfBETA) && (phashe->val >= beta)) {
    return beta;
   }
  }
  RememberBestMove();
 }
 return valUNKNOWN;
}
 
void RecordHash(int depth, int val, int hashf) {
 HASHE *phashe = &hash_table[ZobristKey() % TableSize()];
 phashe->key = ZobristKey();
 phashe->best = BestMove();
 phashe->val = val;
 phashe->hashf = hashf;
 phashe->depth = depth;
}
 
  你所发现的代码,其实不像航天迷信一样准确,而是很能够有毛病的,而且细节上的问题我还没有议论。若是你的顺序中有毛病,也许就是很严重的毛病。
  【上述代码有个速率上的瓶颈,即“ZobristKey() % TableSize()”这个表述式。由于“计算机一做除法就成了傻瓜”,以是“TableSize”最好是一个2n的常量,只需当除数是2n时除法才气够由右移指令庖代。最好的要领是设一个“TableSizeMask”的变量:
 
int TableSizeMask = TableSize() - 1;
HASHE *phashe = &hash_table[ZobristKey() & TableSizeMask];
 
  而这里“TableSize()”也必需是2n。正是这个原理,在许多能够设定置换表巨细的国际象棋顺序中,允许的设定值总是呈倍数增长的,要末是3M6M12M24M等等(若是每一个散列项有12字节),要末是4M8M16M32M等等(若是每一个散列项有16字节)。】
 
替换战略
 
  最主要的细节就包孕,甚么时刻该掩盖散列项。在下面的案例中,我用了“一直替换”的战略,即简朴地掩盖以前存在的值。这也许不是最好的战略,现实上以前有少量的事情试图找出哪一个战略是最好的。
  其余一个战略是“异样深度或更深时替换”。除非新局势的深度大于或即是散列表中以前有的值,否则以前存在的结点将被留下。
  另有许多调研的余地。1994年我在Usenet(音讯组网络系统)的音讯组rec.games.chess(现在是rec.games.chess.computer)上问了这个问题,失掉了Ken Thompson的回复。
  他的回覆是运用两个散列表。一个运用“一直替换”战略,其余一个运用“异样深度或更深时替换”。当你做探索时,两个散列表都去探索,若是其中一个能够发生截断,那就能够够了。若是两者都不能发生截断,那末你能够最少失掉一个最好着法,现实上更多的多是失掉两个分歧的着法,两者都应当首先(或第二个)实验。
  纪录的时刻,你只需简朴地依据替换战略来执行。
  若是你运用“异样深度或更深时替换”的战略,那末你的散列表能够一直会被逾期的但很深的结点所占满。处置责罚计划就是每次你走棋时都消灭散列表,也许在散列项中加入“递次”这个域,从而使这个战略酿成酿成“异样深度,或更深,或正本是旧的搜索,才替换”。
  我在我的顺序Ferret中运用了Thompson的战略,而且运转得异常不错。其余一个顺序Gerbil也运用这个战略,你能够去看它的源代码。
  【依据译者研讨的效果,只用“深度优先掩盖”战略(即“异样深度或更深时替换”),效果会比“一直替换”好很多,而代码则其实不庞大,只需扎眼的局部是新增的:
 
void RecordHash(int depth, int val, int hashf) {
 HASHE *phashe = &hash_table[ZobristKey() & (TableSize() - 1)];
 if (phashe->hashf != hashfEMPTY && phashe->depth > depth) {
  return;
 }
 phashe->key = ZobristKey();
 phashe->best = BestMove();
 phashe->val = val;
 phashe->hashf = hashf;
 phashe->depth = depth;
}
 
  若是运用这个代码,那末每走一步之前都必需把散列表中一切的符号项置为“hashfEMPTY”。】
 
不稳固性的问题
 
  当你用置换表时,若是你允许搜索历程依据散列项来截断,那就会发生其余一个问题,你的搜索会受“不稳固性”的捆扰。
  不稳固性最少是由以下重点要点引发的:
  1. 你能够在做6层的搜索,然则若是你在散列项中失掉10层搜索的效果,就能够够依据这个值来截断。在厥后的搜索中,这个散列项被掩盖了,因而你在这个结点上失掉了两个分歧的值。
  2. Zobrist键值没有办纲纪录抵达结点的线路,这个结点上不是每条线路都有一样效果的。若是某条线路遇到一次又一次局势,那末散列项的值就会跟线路有关。由于一次又一次局势会致使和局的分值,也许最少纷歧样的分值。
  就我所知,还没有甚么设施能处置责罚这些问题。
  【其余,若是搜索历程当中找到杀棋,那末评定值会靠近“INFINITY”或“-INFINITY”,这时候纪录散列表时不能简朴地纪录这些评定值,在前面引见的“胜利局势”的处置责罚中,谈判到这个问题。】
 
  原文:http://www.seanet.com/~brucemo/topics/hashing.htm
  译者:象棋百科全书网 (webmaster@xqbase.com)
  类型:全译加译注
  • 上一篇 基本搜索要领——迭代加深
  • 下一篇 低级搜索要领——简介()
  • 返 回 象棋百科全书——计算机象棋
  • www.xqbase.com