⭐ 欢迎来到虫虫下载站！ | 📦 资源下载 📁 资源专辑 ℹ️ 关于我们
⭐ 虫虫下载站
📤 上传资源

📄 基本搜索方法——最小-最大搜索.htm

📁 象棋程序设计全资料集(介绍编写象棋程序的方法思路）
💻 HTM
字号:
🔍 
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0055)http://www.elephantbase.net/computer/search_minimax.htm -->
<HTML><HEAD><TITLE>基本搜索方法——最小-最大搜索</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb_2312-80">
<META content="MSHTML 6.00.3790.2759" name=GENERATOR></HEAD>
<BODY background=基本搜索方法——最小-最大搜索_files/background.gif>
<DL dir=ltr>
  <DIV align=center>
  <CENTER>
  <DT>《对弈程序基本技术》专题 </CENTER></DT></DIV>
  <DIV align=center>
  <CENTER>
  <DT>　 </CENTER></DT></DIV>
  <DIV align=center>
  <CENTER>
  <DT><FONT face=隶书 size=6>最小</FONT><FONT face=Arial size=6>-</FONT><FONT 
  face=隶书 size=6>最大搜索</FONT> </CENTER></DT></DIV>
  <DIV align=center>
  <CENTER>
  <DT>　 </CENTER></DT></DIV>
  <DIV align=center>
  <CENTER>
  <DT><FONT face="Times New Roman">Bruce Moreland (</FONT><A 
  href="mailto:brucemo@seanet.com"><FONT 
  face="Times New Roman">brucemo@seanet.com</FONT></A><FONT 
  face="Times New Roman">) / </FONT>文 </CENTER></DT></DIV>
  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><STRONG>从浅显的地方开始</STRONG></FONT> 
  <DT>　 
  <DT>　　在国际象棋里，双方棋手都知道每个棋子在哪里，他们轮流走并且可以走任何合理的着法。下棋的目的就是将死对方，或者避免被将死，或者有时争取和棋是最好的选择。 

  <DT>　　国际象棋程序通过使用“搜索”函数来寻找着法。搜索函数获得棋局信息，然后寻找对于程序一方来说最好的着法。 
  <DT>　　一个浅显的搜索函数用“树状搜索”<FONT 
  face="Times New Roman">(Tree-Searching)</FONT>来实现。一个国际象棋棋局通常可以看作一个很大的<FONT 
  face="Times New Roman"><EM>n</EM></FONT>叉树<FONT 
  face="Times New Roman">(</FONT>“<FONT 
  face="Times New Roman"><EM>n</EM></FONT>叉树”意思是树的每个结点有任意多个分枝通向其他结点<FONT 
  face="Times New Roman">)</FONT>，棋盘上目前的局面就是“根局面”<FONT 
  face="Times New Roman">(Root Position)</FONT>或“根结点”<FONT 
  face="Times New Roman">(Root Node)</FONT>。从根局面走一步棋，局面就到达根局面的“分枝”<FONT 
  face="Times New Roman">(Branch)</FONT>，这些局面称为“后续局面”<FONT 
  face="Times New Roman">(Successor Position)</FONT>或“后续结点”<FONT 
  face="Times New Roman">(Successor 
  Nodes)</FONT>。每个后续局面后面还有一系列分枝，每个分枝就是这个局面的一个合理的着法。 
  <DT>　　国际象棋的树非常庞大<FONT face="Times New Roman">(</FONT>通常每个局面有<FONT 
  face="Times New Roman">35</FONT>个分枝<FONT face="Times New Roman">)</FONT>，又非常深。 

  <DT>　　每盘棋局都是一棵巨大的<FONT 
  face="Times New Roman"><EM>n</EM></FONT>叉树，如果能通过树状搜索找到棋局中对双方来说都最好的着法就好了。这个浅显的算法在这里称为“最小<FONT 
  face="Times New Roman">-</FONT>最大搜索”<FONT face="Times New Roman">(Min-max 
  Search)</FONT>。 
  <DT>　　用最小<FONT face="Times New Roman">-</FONT>最大搜索来解诸如井字棋的简单棋局是可行的<FONT 
  face="Times New Roman">(</FONT>即完全了解每一种变化<FONT 
  face="Times New Roman">)</FONT>。井字棋的博弈树既不烦琐也不深，所以整个树可以遍历，棋局的所有变化都可以知道，任何局面都可以保证找到一步最佳着法。 

  <DT>　　数学上用这种方法处理国际象棋也是可以的，但是目前和不久的将来用计算机去实现，却是不可行的。即便如此，我们仍然可以用基于最小<FONT 
  face="Times New Roman">-</FONT>最大搜索的程序来下国际象棋。相比最小<FONT 
  face="Times New Roman">-</FONT>最大地搜索整个树，在一个给定的局面下搜索前几步则是可能的。由于叶子结点的局面没能搜索出杀棋或和棋，所以要用一个称为“评价”<FONT 
  face="Times New Roman">(Evaluate)</FONT>的启发函数给这些局面赋值。尽管程序设计师希望这些值能够通过知识来得到，但它们确实都是猜的。 

  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><STRONG>基于最小-最大的评价函数</STRONG></FONT> 
  <DT>　 
  <DT>　　我不打算在这里谈很多关于评价函数的细节。这里我只说明它是怎样确定的，在以后的章节中会详细展开。评价函数首先应该返回局面的准确值，在没办法得到准确值的情况下，如果可能的话启发值也可以。它可以由两种方法来决定： 

  <DT>　　<FONT face="Times New Roman">(1) 
  </FONT>如果黑方被将死了，那么评价函数返回一个充分大的正数；如果白方被将死了，那么返回一个充分大的负数；如果棋局是和棋<FONT 
  face="Times New Roman">(</FONT>例如某一方逼和，或者双方都只有王<FONT 
  face="Times New Roman">)</FONT>，那么返回一个常数，通常是零或接近零。如果不是棋局结束局面，那么它返回一个启发值。我将不详细介绍这个启发值是如何确定的，但是我有把握说子力平衡是首先要考虑的<FONT 
  face="Times New Roman">(</FONT>如果白方盘面上多子的话，这个值就大<FONT 
  face="Times New Roman">)</FONT>，而其他位置上的考虑<FONT 
  face="Times New Roman">(</FONT>兵型、王的安全性、重要的子力等等<FONT 
  face="Times New Roman">)</FONT>也需要加上。如果白方是赢棋或者很有希望赢，那么启发函数通常会返回正数；如果黑方是赢棋或者很有希望赢，那么返回负数；如果棋局是均势或者是和棋，那么返回在零左右的数值。 

  <DT>　　<FONT face="Times New Roman">(2) 
  </FONT>这个函数的工作原理跟第一个一样，只是如果当前局面要走子的一方优势，那么它返回正数，反之是负数。 
  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><STRONG>最小</STRONG></FONT><FONT face=Arial 
  size=5><STRONG>-</STRONG></FONT><FONT face=楷体_GB2312 
  size=5><STRONG>最大搜索是如何运作的</STRONG></FONT> 
  <DT>　 
  <DT>　　最小<FONT 
  face="Times New Roman">-</FONT>最大搜索是一对几乎一样的函数，或者说两个逻辑上重复的函数。我写了很少的代码，用一个更好的函数来完成同一件事，但是写出来时却收到一些意见，因此我首先写出纯粹的<FONT 
  face="Times New Roman">(</FONT>不完美的<FONT 
  face="Times New Roman">)</FONT>最小<FONT 
  face="Times New Roman">-</FONT>最大函数，代码如下： 
  <DD>　 
  <DD>int MinMax(int depth) { 
  <DD>　if (SideToMove() == WHITE) {　// 白方是“最大”者 
  <DD>　　return Max(depth); 
  <DD>　} else {　　　　　　　　　　　// 黑方是“最小”者 
  <DD>　　return Min(depth); 
  <DD>　} 
  <DD>} 
  <DD>　 
  <DD>int Max(int depth) { 
  <DD>　int best = -INFINITY; 
  <DD>　if (depth &lt;= 0) { 
  <DD>　　return Evaluate(); 
  <DD>　} 
  <DD>　GenerateLegalMoves(); 
  <DD>　while (MovesLeft()) { 
  <DD><FONT face=宋体>　　</FONT>MakeNextMove(); 
  <DD>　　val = Min(depth - 1); 
  <DD><FONT face=宋体>　　</FONT>UnmakeMove(); 
  <DD>　　if (val &gt; best) { 
  <DD>　　　best = val; 
  <DD>　　} 
  <DD>　} 
  <DD>　return best; 
  <DD>} 
  <DD>　 
  <DD>int Min(int depth) { 
  <DD>　int best = INFINITY;　// 注意这里不同于“最大”算法 
  <DD>　if (depth &lt;= 0) { 
  <DD>　　return Evaluate(); 
  <DD>　} 
  <DD>　GenerateLegalMoves(); 
  <DD>　while (MovesLeft()) { 
  <DD>　　MakeNextMove(); 
  <DD>　　val = Max(depth - 1); 
  <DD>　　UnmakeMove(); 
  <DD>　　if (val &lt; best) { 　// 注意这里不同于“最大”算法 
  <DD>　　　best = val; 
  <DD>　　} 
  <DD>　} 
  <DD>　return best; 
  <DD>} 
  <DT>　 
  <DT>　　上面的代码可以这样调用： 
  <DD>　 
  <DD>val = MinMax(5); 
  <DT>　 
  <DT>　　这样可以返回当前局面的评价，它是向前看<FONT face="Times New Roman">5</FONT>步的结果。 
  <DT>　　这里的“评价”函数用的是我上面所说第一种定义，它总是返回对于白方来说的局面。 
  <DT>　　我简要描述一下这个函数是如何运作的。假设根局面<FONT face="Times New Roman">(</FONT>棋盘上当前局面<FONT 
  face="Times New Roman">)</FONT>是白方走，那么调用的是“<FONT 
  face="Times New Roman">Max</FONT>”函数，它产生白方所有合理着法。在每个后续局面中，调用的是“<FONT 
  face="Times New Roman">Min</FONT>”函数，它对局面作出评价并返回。由于现在是白走，因此白方需要让评价尽可能地大，能得到最大值的那个着法被认为是最好的，因此返回这个着法的评价。 

  <DT>　　“<FONT face="Times New Roman">Min</FONT>”函数正好相反，当黑方走时调用“<FONT 
  face="Times New Roman">Min</FONT>”函数，而黑方需要尽可能地小，因此选择能得到最小值的那个着法。 
  <DT>　　这两个函数是互相递归的，即它们互相调用，直到达到所需要的深度为止。当函数到达最底层时，它们就返回“<FONT 
  face="Times New Roman">Evaluate</FONT>”函数的值。 
  <DT>　　如果在深度为<FONT face="Times New Roman">1</FONT>时调用“<FONT 
  face="Times New Roman">MinMax</FONT>”函数，那么“<FONT 
  face="Times New Roman">Evaluate</FONT>”函数在走完每个合理着法之后就调用，选择一个能达到最佳值的那个着法导致的局面。如果层数大于<FONT 
  face="Times New Roman">1</FONT>，那么另一方有权选择局面，并找一个最好的。 
  <DT>　　以上内容应该不难理解，但是代码很长，下面有个更好的办法。 
  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><STRONG>负值最大函数</STRONG></FONT> 
  <DT>　 
  <DT>　　负值最大只是对最小-最大的优化，“评价”函数返回我所说的第二种定义，对于当前结点上要走的一方，占优的情况返回正值，其他结点也是对于要走的一方而言的。这个值返回后要加上负号，因为返回以后就是对另一方而言了。代码如下： 

  <DD>　 
  <DD>int NegaMax(int depth) { 
  <DD>　int best = -INFINITY; 
  <DD>　if (depth &lt;= 0) { 
  <DD>　　return Evaluate(); 
  <DD>　} 
  <DD>　GenerateLegalMoves(); 
  <DD>　while (MovesLeft()) { 
  <DD>　　MakeNextMove(); 
  <DD>　　val = -NegaMax(depth - 1); // 注意这里有个负号。 
  <DD>　　UnmakeMove(); 
  <DD>　　if (val &gt; best) { 
  <DD>　　　best = val; 
  <DD>　　} 
  <DD>　} 
  <DD>　return best; 
  <DD>} 
  <DT>　 
  <DT>　　在这个函数里，当走子一方改变时就要对返回值取负值，以反映当前局面评价的更改。就根结点是白先走的情况，如果没有剩下的层数，那么“评价”返回的值是就白方而言的，如果有剩下的层数，就产生后续局面，函数对这些局面逐一做递归，每个次递归都得到就黑方而言的评价，黑方走得越好值就越大。当评价值返回时，它们被取负数，变成就白方而言的评价。 

  <DT>　　该函数在遍历时结点的顺序同“最小<FONT 
  face="Times New Roman">-</FONT>最大”搜索的函数是一样的，产生的返回值也一样。它的代码更短，同时减少了移植代码时出错的可能，代码维护起来也比较方便。 

  <DT>　 
  <DT>　　原文：<A href="http://www.seanet.com/~brucemo/topics/minmax.htm" 
  target=_blank><FONT 
  face="Times New Roman">http://www.seanet.com/~brucemo/topics/minmax.htm</FONT></A> 

  <DT>　　译者：黄晨 <FONT face="Times New Roman">(</FONT><A 
  href="mailto:webmaster@elephantbase.net"><FONT 
  face="Times New Roman">webmaster@elephantbase.net</FONT></A><FONT 
  face="Times New Roman">)</FONT> 
  <DT>　　类型：全译 </DT></DL>
<DIR>
<LI>上一篇　<A 
href="http://www.elephantbase.net/computer/search_intro3.htm">基本搜索方法——简介<FONT 
face="Times New Roman">(</FONT>三<FONT face="Times New Roman">)</FONT></A> 
<LI>下一篇　<A 
href="http://www.elephantbase.net/computer/search_alphabeta.htm">基本搜索方法——<FONT 
face="Times New Roman">Alpha-Beta</FONT>搜索</A> 
<LI>返　回　<A href="http://www.elephantbase.net/computer.htm">象棋百科全书——电脑象棋</A> 
</LI></DIR>
<DIV align=center>
<CENTER>
<TABLE border=0>
  <TBODY>
  <TR>
    <TD>
      <P align=center><A href="http://www.elephantbase.net/" target=_blank><IMG 
      height=31 src="基本搜索方法——最小-最大搜索_files/elephantbase.gif" width=88 
      border=0></A></P></TD></TR>
  <TR>
    <TD><A href="http://www.elephantbase.net/" target=_blank><FONT face=Arial 
      size=2><STRONG>www.elephantbase.net</STRONG></FONT></A></TD></TR></TBODY></TABLE></CENTER></DIV></BODY></HTML>

⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -