《棋战顺序基本手艺》专题
 
最小-最大搜索
 
Bruce Moreland /
 
从浅易的中央最先
 
  在国际象棋里,双方棋手都知道每一个棋子在那里,他们轮替走而且能够走任何恰当的着法。下棋的目的就是将死对方,也许制止被将死,也许有时争取和棋是最好的选择。
  国际象棋顺序经由历程运用“搜索”函数来寻找着法。搜索函数取得棋局信息,然后寻找关于顺序一方来说最好的着法。
  一个浅易的搜索函数用“树状搜索”(Tree-Searching)来完成。一个国际象棋棋局一般能够看做一个很大的n叉树(n叉树”意义是树的每一个结点有恣意多个分枝通向其他结点),棋盘上现在的局势就是“根局势”(Root Position)或“根结点”(Root Node)。从根局势走一步棋,局势就抵达根局势的“分枝”(Branch),这些局势称为“后续局势”(Successor Position)或“后续结点”(Successor Nodes)。每一个后续局势前面另有一系列分枝,每一个分枝就是这个局势的一个恰当的着法。
  国际象棋的树异常重大(一般每一个局势有35个分枝),又异常深。
  每盘棋局都是一棵伟大的n叉树,若是能经由历程树状搜索找到棋局中对双方来说都最好的着法就好了。这个浅易的算法在这里称为“最小-最大搜索”(Min-max Search)
  用最小-最大搜索来解诸如井字棋的简朴棋局是可行的(即完整相识每一种转变)。井字棋的博弈树既不啰嗦也不深,以是悉数树能够遍历,棋局的一切转变都能够知道,任何局势都能够确保找到一步最好着法。
  数学上用这类要领处置责罚国际象棋也是能够的,然则现在和不久的未来用盘算机去完成,却是弗成行的。纵使这样,咱们依然能够用基于最小-最大搜索的顺序来下国际象棋。相比最小-最大地搜索悉数树,在一个给定的局势下搜索前几步则是能够的。由于叶子结点的局势没能搜索出杀棋或和棋,以是要用一个称为“评定”(Evaluate)的启示函数给这些局势赋值。只管顺序设想师希冀这些值能够经由历程知识来失掉,但它们实在都是猜的。
 
基于最小-最大的评定函数
 
  我不计划在这里谈许多关于评定函数的细节。这里我只说明它是怎样一定的,在以后的章节中会详细睁开。评定函数首先应以后往局势的准确止墁在没设施失掉准确值的状况下,若是能够的话启示值也能够。它能够由两种要领来注定:
  (1) 若是黑方被将死了,那末评定函数前往一个充裕大的正数;若是白方被将死了,那末前往一个充裕大的正数;若是棋局是和棋(譬喻某一方逼和,也许双方都只需王),那末前往一个常数,一般是零或靠近零。若是不是棋局完毕局势,那末它前往一个启示值。我将不详细引见这个启示值是怎样一定的,然则我有掌握说子力平衡是首先要斟酌的(若是白方盘面上多子的话,这个值就大),而其他职位上的斟酌(兵型、王的平安性、主要的子力等等)也要求加上。若是白方是赢棋也许很有希冀赢,那末启示函数一般会前往正数;若是黑方是赢棋也许很有希冀赢,那末前往正数;若是棋局是均势也许是和棋,那末前往在零前后的数值。
  (2) 这个函数的事情原理跟第一个一样,只是若是以后局势要走子的一方优势,那末它前往正数,相反是正数。
 
最小-最大搜索是怎样运作的
 
  最小-最大搜索是一对险些一样的函数,也许说两个逻辑上一次又一次的函数。我写了很少的代码,用一个更好的函数来完成统一件事,然则写出来时却收到一些看法,因而我首先写出地道的(不完善的)最小-最大函数,代码以下:
 
int MinMax(int depth) {
 if (SideToMove() == WHITE) { // 白方是“最大”者
  return Max(depth);
 } else {           // 黑方是“最小”者
  return Min(depth);
 }
}
 
int Max(int depth) {
 int best = -INFINITY;
 if (depth <= 0) {
  return Evaluate();
 }
 GenerateLegalMoves();
 while (MovesLeft()) {
  MakeNextMove();
  val = Min(depth - 1);
  UnmakeMove();
  if (val > best) {
   best = val;
  }
 }
 return best;
}
 
int Min(int depth) {
 int best = INFINITY; // 注重这里分歧于“最大”算法
 if (depth <= 0) {
  return Evaluate();
 }
 GenerateLegalMoves();
 while (MovesLeft()) {
  MakeNextMove();
  val = Max(depth - 1);
  UnmakeMove();
  if (val < best) {  // 注重这里分歧于“最大”算法
   best = val;
  }
 }
 return best;
}
 
  下面的代码能够这样调用:
 
val = MinMax(5);
 
  如允许以前往以后局势的评定,它是向前看5步的效果。
  这里的“评定”函数用的是我下面所说第一种界说,它总是前往关于白方来说的局势。
  我简要形貌一下这个函数是怎样运作的。假定根局势(棋盘受骗前局势)是白方走,那末调用的是“Max”函数,它发生白方一符恰当着法。在每一个后续局势中,调用的是“Min”函数,它对局势作出评定并前往。由于现在是白走,因而白方要求让评定尽能够地大,能失掉最大值的谁人着法被以为是最好的,因而前往这个着法的评定。
  “Min”函数正好相反,当黑方走时调用“Min”函数,而黑方要求尽能够地小,因而选择能失掉最小值的谁人着法。
  这两个函数是相互递归的,即它们相互调用,直抵到达所要求的深度为止。当函数抵达最底层时,它们就前往“Evaluate”函数的值。
  若是在深度为1时调用“MinMax”函数,那末“Evaluate”函数在走完每一个恰当着法以后就调用,选择一个能到达最好值的谁人着法致使的局势。若是层数大于1,那末其余一方有权选择局势,并找一个最好的。
  上述内容应当很容易体谅,然则代码很长,下面有个更好的设施。
 
负值最大函数
 
  负值最大只是对最小-最大的优化,“评定”函数前往我所说的第二种界说,关于以后结点上要走的一方,占优的状况前往正值,其他结点也是关于要走的一方而言的。这个值前往后要加上负号,由于前往以后就是对其余一方而言了。代码以下:
 
int NegaMax(int depth) {
 int best = -INFINITY;
 if (depth <= 0) {
  return Evaluate();
 }
 GenerateLegalMoves();
 while (MovesLeft()) {
  MakeNextMove();
  val = -NegaMax(depth - 1); // 注重这里有个负号。
  UnmakeMove();
  if (val > best) {
   best = val;
  }
 }
 return best;
}
 
  在这个函数里,当走子一方改动时就要对前往值取负值,以回响反映以后局势评定的更改。就根结点是白先走的状况,若是没有剩下的层数,那末“评定”前往的值是就白方而言的,若是有剩下的层数,就发生后续局势,函数对这些局势逐一做递归,每一个次递归都失掉就黑方而言的评定,黑方走得越好值就越大。当评定值前往时,它们被取正数,变结果白方而言的评定。
  该函数在遍用时结点的递次同“最小-最大”搜索的函数是一样的,发生的前往值也一样。它的代码更短,同时增加了移植代码时失足的能够,代码珍爱起来也对照轻易。
 
  原文:http://www.seanet.com/~brucemo/topics/minmax.htm
  译者:象棋百科全书网 (webmaster@xqbase.com)
  类型:全译
  • 上一篇 基本搜索要领——简介()
  • 下一篇 基本搜索要领——Alpha-Beta搜索
  • 返 回 象棋百科全书——计算机象棋
  • www.xqbase.com