《棋战顺序基本手艺》专题
 
最小-最大和负值最大搜索
 
David Eppstein */
* 加州爱尔文大学(UC Irvine)信息与盘算机迷信系
 
搜索树
 
  任何棋类游戏都要界说一棵有根的树(即“博弈树”),一个结点就象征棋类的一个局势,子结点就是这个局势走一步能够抵达的一个局势。例以下图是井子棋(Tic-tac-toe)的搜索树:
 
 
 
  (现实上,这个搜索树的根结点应当有9个子结点,然则我去掉了一些对称的状况。若是异样的棋盘是由两个分歧的着法递次组成的,那末咱们就竖立两个结点,以是这确实是树的组织。稍后咱们会在议论散列手艺的时刻谈到怎样应用一次又一次的结点来提升搜索速率——咱们只需搜索第一个,其余一个就用第一个搜索效果来替代。其余咱们假定棋手是轮替下棋的,没一些人一次走多步或跳过不走的,那些庞大的状况能够把它走的一系列着法看做一个着法来处置责罚。【译注:庞大的状况是指一些一次能走许多步的棋类游戏,譬喻跳棋、西洋跳棋、是非棋等,依照原作者的计划,能够把一方一连走的几步棋算作一步棋。而译者更希冀把一方一连的几步棋拆成几个回合,只是其余一方都别无选择地走了空着。】最终,咱们假定搜索树是有限的,这样咱们就不会遇到永无终点的棋局也许一步有有限多种着法的棋局。)
  搜索树中有三种类型的结点:
  (1) 偶数层的中央结点,象征棋手甲要走的局势;
  (2) 奇数层的中央结点,象征棋手乙要走的局势;
  (3) 叶子结点,象征棋局完毕的局势,即棋手甲或棋手乙失利,也许是和局。
 
博弈树的评定
 
  假定某其中央结点的一切子结点都是叶子结点,那末棋局会在一回合内完毕。现在咱们假定棋手会选择最好的着法,若是有一个着法能使他赢下棋局,那末他一定会走这步。若是没有能够赢的着法,然则有取得和局的着法,那末他会走这步取得和局的着法。然则,若是一切的着法都使得对手失利,那末不论怎样他都邑输。
  因而在叶子结点的上一层结点,咱们就能够知道棋局的效果。现在咱们知道了这个结点的效果,那末咱们能够用异样的要领作推演,知道叶子结点的上两层结点的效果,然后是上三层结点,等等,直到咱们到达搜索树的根结点。在每一个结点上,棋手只需找到一个子结点能让他失利,那末他就能够够赢下棋局;他只需找到一个组成和局的子结点,棋局就和了;若是失利与和局的子结点都没有,那末一定是输的。若是咱们有足够多的时刻来盘算,那末这就给了咱们一个能够下棋的完善算法。然则关于任何通例的棋类游戏,咱们都不能够有足够的盘算时刻,由于搜索树真实太大了。
  其余,“准确”的评定函数只需三个值,赢、输也许和局。在现实的棋类顺序中,咱们一般运用一个更普遍的实数来作评定值,就是由于赢、输也许和局是纷歧定的。若是棋手甲失利的值用+1透露表现,和局的值用0透露表现,棋手乙失利的值用-1透露表现,那末博弈树的每一其中央结点的值就是子结点的最大值或最小值,这取决于棋手甲照样棋手乙着棋。
 
局部的博弈树
 
  在实战中,咱们的搜索算法只能对博弈树睁开一局部。咱们用一些“中缀划定礼貌”来注定搜索树睁开到哪一个结点就停上去,譬喻咱们在8步转变以后听上去。由于棋局没有在叶子结点完毕,咱们只能用评定函数来猜哪一方失利。现在咱们来假定在咱们睁开的结点中,棋手甲总是希冀棋局抵达评定函数大的局势,而棋手乙总是希冀棋局抵达评定函数小的局势。
  若是双方都用这类要领来下棋,那末咱们能够运用异样的最小-最大历程,来一定抵达的叶子结点的评定值,这个历程以下:对每一其中央结点,盘算子结点的最大值或最小值,这取决因而棋手甲照样棋手乙走棋。抵达叶子结点的线路称为“主要变例”(Principal Variation)。最小-最大博弈树的基来源根基理,就是对博弈树作局部睁开,去找主要变例,并走出变例中的第一步。
 
广度优先和深度优先搜索,负值最大代码
 
  正以下面所讲的,盘算博弈树的值是一个广度优先的历程(咱们要自下而上地,一次一层土地算)。然则实战中,咱们运用深度优先(即后序遍历)的递归历程来遍历搜索树,即要失掉一个结点的值,就对子结点做递归,然后依据它们的前往值来注定自身的前往值。这样要节约许多空间,由于不要求来存储悉数博弈树,而只是存储一条线路(一定来说异常短,例以下面说到的8步中缀的划定礼貌)。下次咱们议论Alpha-Beta搜索时,会发现深度优先的遍历会有很大的优势,你能够用现在失掉的信息来注定某些结点是不要求接见的,这样就节约下许多的时刻。
  只需对搜索树的值作一个很小的改动,就能够够用一个求最大值的支配来替代最小值和最大值轮换的历程。在搜索树的奇数层(即轮到棋手乙下棋的结点),就对下面说到的评定值取正数。因而在每一个结点上,这些值都能够由子结点的负值求得。我把博弈树搜索的源代码写出来,生怕就会清晰许多了。
 
// 将博弈树搜索到一定的深度,前往根结点的评定值
double negamax(int depth) {
 if (depth <= 0 || 棋局完毕)
  return eval(pos);
 else {
  double e = -infty;
  for (以后局势一切能够的着法 m) {
   执行着法 m;
   e = max(e, -negamax(depth - 1));
   吊销着法 m;
  }
  return e;
 }
}
 
  注重,这个历程只能找到评定值,然则没有设施得知着法。咱们只需在搜索树的根结点找到着法(只管许多顺序都前往悉数主要变例)就能够够了,要做到这一点,能够对根结点的搜索稍作改动:
 
// 将博弈树搜索到一定的深度,前往根结点的着法
move rootsearch(int depth) {
 double e = -infty;
 move mm;
 for (以后局势一切能够的着法 m) {
  执行着法 m;
  double em = -negamax(depth - 1);
  if (e < em) {
   e = em;
   mm = m;
  }
  吊销着法 m;
 }
 return mm;
}
 
负值最大的剖析:分枝因子和深度
 
  人们一般简朴地依据博弈树的形状来对博弈树算法停止剖析。咱们假定每一其中央结点有异样多的子结点,其数目称为分枝因子(Branching Factor)。咱们还假定搜索到流动的深度(就如前面所说到的算法一样),而且棋局不会很早地完毕(在到达搜索深度之前完毕)
  在这些假定下,很随意纰漏写下负值最大顺序所花的时刻,即正比于睁开结点的数目。(看上去要求乘上一个系数,以回响反映调用负值最大时的谁人循环,然则这个循环所花的时刻以前被包孕在递归函数里了。)【译者也不体谅这句话的意义,但译者以为顺序中eval()函数所破费的时刻最多,而它只是在搜索到叶子结点时才被调用,因而只盘算叶子结点的数目就能够够了,即bd。】若是分枝因子是b,深度是d,那末这个数就是:
1 + b + b2 + b3 + ... + bd = bd (1 - 1 / bd) / (1 - 1 / b).
  公式右端括号里的数值靠近于1,以是悉数运算所破费的时刻靠近于bd
  若是棋类游戏不相符上述假定,咱们能够反过去界说一个“有用分枝因子”(Effective Branching Factor),使得这个b能够相符顺序运转所破费的时刻。更简朴些,能够把“分枝因子”形貌为某个棋类游戏中“模范∷刂势的能够着法数的匀称值。
  这个公式能够通知咱们甚么呢?首先它是指数形式的,这就意味着咱们不能够搜索太多层,若是计算机的速率翻了番,那末咱们只能把d增长很小一点。其次搜讨取决于分枝因子b,在分枝因子很小的棋类中(像西洋跳棋,一般每一个局势只需3个着法),咱们就能够够搜索的比国际象棋(一个局势有30种前后的着法)或围棋(一个局势有几百种着法)深很多,因而咱们喜欢让b越小越好。很不幸的是搜索函数更多地决于棋类游戏自身,而不是咱们写顺序的水平。然则下一次咱们要议论一个算法,称为Alpha-Beta裁剪,它能够很大水平地增加分枝因子,若是运气好的话,它能够增加到没有裁剪的博弈树的平方根那末多,这就意味着咱们能够搜索正本深度(即不用Alpha-Beta搜索的深度)的两倍那末深。b的平方根即b1/2,用一下中学数学学过的公式,(b1/2)d = bd/2,还记得吗?】
 
迭代加深
 
  负值极大的代码还留给咱们一个问题:咱们怎样来给定搜索深度?简朴的棋类顺序只把它设成一个流动值,这就能够够使得顺序走的每步棋时花的时刻长短转变异常大。因而你最好依据搜索所需的时刻,来注定搜索的深度。侥幸的是指数特征的搜索有这样一个有益之处:经由历程“迭代加深”(Iterated Deepening)这个手腕,能够很随意纰漏地对搜索停止掌握,刚最先搜索时浅一些,然后增长深度一次又一次搜索直到时刻用完为止:
 
depth = 0
while (有足够的时刻来停止下一层的搜索) {
 depth ++;
 m = rootsearch(depth);
}
执行着法 m;
 
  这看上去似乎在虚耗时刻,由于除了最终一次搜索外,前面的搜索都空费了。然则依据前面剖析过的效果,空费的时刻是很少的:分歧层数所花的时刻加起来是 1 + b + b2 + ...,咱们以前知道它靠近于最终一项bd了。以是,迭代加深所花的价值其实不多,而它给咱们供应了异常不错的时刻掌握的手腕。它另有一个很大的功用:在做较深的搜索时,能够用浅一层搜索失掉的着法递次,在Alpha-Beta搜索中,着法递次是滋扰搜索的速率的注定性重点要点。
  Iterative Deepening,字面意义是“一次又一次加深”,就如上文所讲的。但它最主要的功用是革新着法的递次,它是Alpha-Beta搜索的一种主要的启示体式格局,浅一层最好的着法在深一层的搜索中首先被实验,素质上是一种迭代的历程,以是译为“迭代加深”。】
 
  原文:http://www.ics.uci.edu/~eppstein/180a/970417.html
  译者:象棋百科全书网 (webmaster@xqbase.com)
  类型:全译加译注
  • 上一篇 数据组织——Zobrist键值
  • 下一篇 基本搜索要领——简介()
  • 返 回 象棋百科全书——计算机象棋
  • www.xqbase.com