最小-最大搜索

从浅显的地方开始
 
  在国际象棋里,双方棋手都知道每个棋子在哪里,他们轮流走并且可以走任何合理的着法。下棋的目的就是将死对方,或者避免被将死,或者有时争取和棋是最好的选择。
  国际象棋程序通过使用“搜索”函数来寻找着法。搜索函数获得棋局信息,然后寻找对于程序一方来说最好的着法。
  一个浅显的搜索函数用“树状搜索”(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;
}
 
  在这个函数里,当走子一方改变时就要对返回值取负值,以反映当前局面评价的更改。就根结点是白先走的情况,如果没有剩下的层数,那么“评价”返回的值是就白方而言的,如果有剩下的层数,就产生后续局面,函数对这些局面逐一做递归,每个次递归都得到就黑方而言的评价,黑方走得越好值就越大。当评价值返回时,它们被取负数,变成就白方而言的评价。
  该函数在遍历时结点的顺序同“最小-最大”搜索的函数是一样的,产生的返回值也一样。它的代码更短,同时减少了移植代码时出错的可能,代码维护起来也比较方便。
引用通告地址: 点击获取引用地址
标签: 算法
评论: 13 | 引用: 0 | 阅读: 8349
更多




david [ 2020-05-19 10:05 网址 | 回复 | 编辑 删除 ]
sandra [ 2020-05-18 19:28 网址 | 回复 | 编辑 删除 ]
jennifer [ 2020-04-17 02:21 网址 | 回复 | 编辑 删除 ]
frank [ 2020-03-29 17:08 网址 | 回复 | 编辑 删除 ]
ronald [ 2020-03-21 01:36 网址 | 回复 | 编辑 删除 ]
wilma [ 2020-03-10 11:54 网址 | 回复 | 编辑 删除 ]
ernestine [ 2020-02-22 13:37 网址 | 回复 | 编辑 删除 ]
david [ 2020-02-12 05:18 网址 | 回复 | 编辑 删除 ]
thelma [ 2020-02-06 04:05 网址 | 回复 | 编辑 删除 ]
ernestine [ 2019-09-24 18:52 网址 | 回复 | 编辑 删除 ]
发表评论
昵 称: 密 码:
网 址: 邮 箱:
验证码: 验证码图片 选 项:
头 像:
内 容:
  • 粗体
  • 斜体
  • 下划线
  • 插入图像
  • 超链接
  • 电子邮件
  • 插入引用