《棋战顺序基本手艺》专题
 
散列手艺和着法排序
 
David Eppstein */
* 加州爱尔文大学(UC Irvine)信息与盘算机迷信系
 
  我还没有讲完Alpha-Beta呢,由于我的伪代码里包罗隐秘的“排序着法”还没有注释,暂时先扔在一边,在讲完散列手艺后,我将连续这局部内容。
  散列手艺的头脑异常简朴,许多棋类会显现“置换”的着法,即着法递次的分歧会致使一样的局势。譬喻在国际象棋中,残局走“1. d4 Nf6 2. c4”和“1. c4 Nf6 2. d4”都邑致使一样的局势(称为印度进攻),白方两次进兵能够按分歧的递次走。再看一个越发庞大置换:“1. e4 c6 2. d4 d5 3. ed Qxd5 4. Nc3 Qd6(卡罗-卡恩进攻),“1. e4 d5 2. ed Qxd5 3. Nc3 Qd6 4. d4 c6(斯堪的那维亚进攻),以及“1. e4 Nf6 2. e5 Ng8 3. d4 d6 4. ed Qxd6 5.Nc3 c6(阿廖欣进攻)都邑在走分歧的步数后抵达一样的局势。
  由于换位,一样的局势能在Alpha-Beta搜索树的许多职位上找到。若是有一种数据组织能够生存之前找过的每一个职位,那末咱们没需要重新搜索,取而代之的是查找局势。然则有两个难题摆在眼前,一是咱们没有足够的存储器来寄存一切搜索过的局势,二是查找速率要足够快以致于凌驾搜索的时刻。侥幸的是,找不到以前搜索过的局势也没紧要,再搜索一遍就是了,由于究竟结果这类状况不会经常发作。
  这类数据组织就是“散列表”(Hash Tables),一个很大的数组,大到不超越物理存储器为止(不要扩展到虚拟存储器,否则会异常慢的)
 
struct {
 long checksum; // long long 能够会更好
 int depth;
 enum { exact, lower_bound, upper_bound } entry_type;
 double eval;
} hashtable[HASH_TABLE_SIZE]; //【译注:完整的散列表还应纪录最好着法。】
 
  关于每一个要求搜索的局势,先盘算散列值x作为散列表的目的,另盘算散列值y来搜检这个局势是否是是所要找的局势。
  在搜索一个局眼前,先去找 hashtable[x],若是 hashtable[x].checksum == yhashtable[x].entry_type == exact,而且 hashtable[x].depth 不比现在要求搜索的深度浅,那末就能够够前往 hashtable[x].eval
  每搜索完一个局势,就把散列值y、以后搜索的深度和搜索的评分生存到 hashtable[x] 里。
 
怎样盘算散列值?
 
  Zobrist 散列手艺(以前在“一次又一次检测”这个话题中讨论过了)是指:不才棋之前(但在顺序里)发生随机数组Z[square, piecetype]。棋盘的散列值就是棋盘上各个棋子的Z[s, p]相加,再加上一些分外的信息如是否是能王车易位等。一般求和被“异或”运算所替代,由于它支配轻易且快速,但算术加法会更好些。走完一步棋后,不要把散列值悉数都算一遍,只需减去正本职位的棋子和格子值,并加上新职位的棋子和格子值,就完成了散列值的更新。这个手艺同时适用于散列值x和校验值y(但要运用分歧的随机数表)
  在散列手艺中,尚有一些特别有用的窍门:
  (1) 在走完一步后,不要把散列表清空,这样不只虚耗时刻,而且正本的内容也许对前面的走法有用。【这里指的是计算机完成悉数局势的搜索,走完一步后不要求清空散列表,计算机停止下一回应时,上一回合留下的信息也许有用。固然,是否是清空散列表不能一视同仁,还要取决于散列表的掩盖战略,以后的美文将谈到这个问题。】
  (2) 若是一样的局势显现在搜索树的分歧深度中(例以下面讲到置换时的第二个案例),那末你能够失掉比预期更深的搜索效果,这样会异常好。【译者把这个状况称为“搜索树的迁移式延长”,当这类状况显现在残局时反而不是坏事,由于你有能够找到一步杀棋,而它却不是最短线路,你就住手了搜索。前面的美文会说明一个问题,当你搜索到杀棋时,若是你的着法不是最短线路,那末在实战中能够明知杀棋但怎样也杀不了。】
  (3) 不要在搜索树靠近叶子的局势上用散列手艺,由于这些局势太多了(它们能够庖代其余更主要的局势),而且不去搜索这些局势也不会省却许多时刻。【若是把搜索分为完整搜索和静态搜索两个阶段,那末静态搜索的效果是一定不写入散列表的,由于静态搜索的分枝因子异常小(只斟酌吃子着法),以是查找散列表的时刻也许比搜索的时刻还长。在完整搜索中,这条轨则是就“一直掩盖”这一战略而言的,若运用“深度优先”战略则无所谓。】
 
散列手艺怎样跟Alpha-Beta联系起来?
 
  国际象棋顺序中许多的毛病都跟散列手艺有关,缘由是它们要跟Alpha-Beta搜索联系起来,但你没有设施绕开这个话题,由于散列手艺和Alpha-Beta都长短常有用的搜索要领。现在重新来看Alpha-Beta,当你在一个局势中调用 alphabeta(depth, alpha, beta) 时,能够有三种状况发作:(1) 凌驾界限(Fail High),即前往评分最少是Beta,但究竟若干却不知道;(2) 低出界限(Fail Low),即前往评分最多是Alpha,但究竟若干也不知道;(3) 准确止墁即前往评分在AlphaBeta之间。若是咱们知道准确效果,那末散列表中只纪录准确评分,然则凌驾界限和低出界限的状况,依然在以后的裁剪中有用。能够跟纪录准确评分一样,散列表中也能够纪录这两种状况的评分,“下界符号”(lower_bound)象征评分最少是Beta,“上界符号”(up_bound)象征评分最多是Alpha,咱们用 entry_type 这个域来透露表现评分属于哪一个类型。若是搜索散列表时前往这两个类型,那末咱们要求看它是否是在搜索结点之前发作裁剪,若是能发作裁剪,那末直接前往该评分,否则连续搜索。下面是用散列手艺的Alpha-Beta搜索的伪代码,散列表的索引值x和校验值y是全局变量,而且在执行着法和吊销着法的时刻更新。
 
double alphabeta(int depth, double alpha, double beta) {
 if (depth <= 0 || 棋局完毕) {
  return evaluation();
 }
 if (hashtable[x].checksum == y && hashtable[x].depth >= depth) {
  switch (hashtable[x].entry_type) {
  case exact: //【就C言语的语法而言是错的,应当写成“case hashtable[x].exact:”,下同】
   return hashtable[x].eval;
  case lower_bound:
   if (hashtable[x].eval >= beta) {
    return (hashtable[x].eval);
   }
   break;
  case upper_bound:
   if (hashtable[x].eval <= alpha) {
    return (hashtable[x].eval);
   }
   break;
  }
 }
 int eval_is_exact = 0;
 就以后局势,天生并排序一系列着法;
 for (每一个着法 m) {
  执行着法 m;
  double val = -alphabeta(depth - 1, -beta, -alpha);
  吊销着法 m;
  if (val >= beta) {
   hashtable[x].checksum = y;
   hashtable[x].depth = depth;
   hashtable[x].entry_type = lower_bound;
   hashtable[x].eval = val; //【译者以为 eval = beta 越发恰当。】
   return val;
  }
  if (val > alpha) {
   alpha = val;
   eval_is_exact = 1;
  }
 }
 hashtable[x].checksum = y;
 hashtable[x].depth = depth;
 if (eval_is_exact) {
  hashtable[x].entry_type = exact;
 } else {
  hashtable[x].entry_type = upper_bound;
 }
 hashtable[x].eval = alpha;
 return alpha;
}
 
Alpha-beta和着法递次
 
  咱们现在就回到Alpha-Beta。上次咱们的剖析指出,在最消极的状况下,若是能裁剪的中央都裁剪了,那末搜索深度将增长一倍。“能裁剪的中央都裁剪了”这个条件说得再简朴一些,就是好的着法在坏的着法之前搜索。着法没有需要完整排序好,然则最好的着法必需首先搜索,也许最好的几个着法必需在对照前面的几个职位搜索。若是不这样做,就不会有裁剪而且不会搜索得很深。
  咱们把结点分为A(一切的子结点都搜索过)B(在搜索到好的子结点后即裁剪掉了),那末着法的递次对两种结点都很主要:在B型结点中,要求从最好的子结点最先,以裁剪掉盈余的节点;而在A型结点中,要求找到足够好的结点,来通知其他结点,它们都是B型的。
  找到最好的着法固然是很难的,这就是咱们要求停止搜索的缘由。【言下之意,要在搜索之前找到最好的着法,实际上是不能够的。】然则咱们能够依据以下线索来找:(1) 迭代加深时,散列表会纪录前面一次搜索过的结点,散列表中的值能够用来作近似(由于这是一样局势浅一些的搜索)【原作者在散列表中没有纪录最好着法,事实上这个着法最应当被首先搜索。】(2) 重点一定特定的棋类游戏,咱们要求一些知识,譬喻在国际象棋中,吃子的着法往往是好的着法,应当首先实验;(3) 杀手启示:若是相邻结点有好的着法,而且在现在的结点上该着法也恰当,那末应当首先实验。
  因而在搜索子结点之前要加上一步:依照着法的质量来排序,然后依照这个递次来搜索。(有时你们能够直接修正着法天生器,让它停止大略的排序,例如师长西席成吃子的着法,从而节约下重新排序的时刻。)
  另有一个窍门:若是你希冀发作裁剪,那末你没需要对一切着法排序,只需排序前面很少几个着法就能够够了。那末你应当用这样的搜索算法,最好着法能够一个一个地挑出,然后早早地住手排序,譬喻选择排序和堆排序。【译者以为冒泡排序是最相符原作者的希图的,由于排序时每扫描一趟就可以找到一个最好着法,在扫描第二趟之前先搜索这个着法。而险些没有顺序是用堆排序的,只管它的庞漂亮是一切排序算法中最低的,而且不斲丧分外的存储器,然则对100个以下的数停止排序,它的速率长短常缓慢的。】
 
  原文:http://www.ics.uci.edu/~eppstein/180a/970424.html
  译者:象棋百科全书网 (webmaster@xqbase.com)
  类型:全译加译注
  • 上一篇 基本搜索要领——简介()
  • 下一篇 基本搜索要领——最小-最大搜索
  • 返 回 象棋百科全书——计算机象棋
  • www.xqbase.com