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

📄 基本搜索方法——简介(二).htm

📁 象棋程序设计全资料集(介绍编写象棋程序的方法思路）
💻 HTM
📖 第 1 页 / 共 2 页
字号:
🔍
12 
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0054)http://www.elephantbase.net/computer/search_intro2.htm -->
<HTML><HEAD><TITLE>基本搜索方法——简介(二)</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb_2312-80">
<META content="" name=Owner>
<META content="" name=Reply-To>
<META content="MSHTML 6.00.3790.2759" name=GENERATOR></HEAD>
<BODY background=基本搜索方法——简介(二)_files/background.gif>
<DL>
  <DIV align=center>
  <CENTER>
  <DT>《对弈程序基本技术》专题 </CENTER></DT></DIV>
  <DIV align=center>
  <CENTER>
  <DT>　 </CENTER></DT></DIV>
  <DIV align=center>
  <CENTER>
  <DT><FONT face=Arial size=6><STRONG>Alpha-Beta</STRONG></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">David Eppstein */</FONT>文 
</CENTER></DT></DIV>
  <DIV align=center>
  <CENTER>
  <DT><FONT face="Times New Roman">* </FONT>加州爱尔文大学<FONT 
  face="Times New Roman">(UC Irvine)</FONT>信息与计算机科学系 </CENTER></DT></DIV>
  <DT>　 
  <DT><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>来搜索下面的树： 
  <DD>　 
  <DIV align=center>
  <CENTER></DIV>
  <DT><IMG height=285 src="基本搜索方法——简介(二)_files/search_intro2.gif" width=346> 
  </CENTER>
  <DIV></DIV>
  <DT>　 
  <DT>　　你搜索到<FONT face="Times New Roman">F</FONT>，发现子结点的评价分别是<FONT 
  face="Times New Roman">11</FONT>、<FONT face="Times New Roman">12</FONT>、<FONT 
  face="Times New Roman">7</FONT>和<FONT 
  face="Times New Roman">9</FONT>，在这层是棋手甲走，我们希望他选择最好的值，即<FONT 
  face="Times New Roman">12</FONT>。所以，<FONT 
  face="Times New Roman">F</FONT>的最小<FONT 
  face="Times New Roman">-</FONT>最大值是<FONT face="Times New Roman">12</FONT>。 
  <DT>　　现在你开始搜索<FONT face="Times New Roman">G</FONT>，并且第一个子结点就返回<FONT 
  face="Times New Roman">15</FONT>。一旦如此，你就知道<FONT 
  face="Times New Roman">G</FONT>的值至少是<FONT 
  face="Times New Roman">15</FONT>，可能更高<FONT 
  face="Times New Roman">(</FONT>如果另一个子结点比<FONT 
  face="Times New Roman">G</FONT>更好<FONT 
  face="Times New Roman">)</FONT>。这就意味着我们不指望棋手乙走<FONT 
  face="Times New Roman">G</FONT>这步了，因为就棋手乙看来，<FONT 
  face="Times New Roman">F</FONT>的评价<FONT 
  face="Times New Roman">12</FONT>要比<FONT face="Times New Roman">G</FONT>的<FONT 
  face="Times New Roman">15(</FONT>或更高<FONT 
  face="Times New Roman">)</FONT>好，因此我们知道<FONT 
  face="Times New Roman">G</FONT>不在主要变例上。我们可以裁剪<FONT 
  face="Times New Roman">(Prune)</FONT>结点<FONT 
  face="Times New Roman">G</FONT>下面的其他子结点，而不要对它们作出评价，并且立即从<FONT 
  face="Times New Roman">G</FONT>返回，因为对<FONT 
  face="Times New Roman">G</FONT>作更好的评价只是浪费时间。 
  <DT>　　一般来说，像<FONT face="Times New Roman">G</FONT>一样只要有一个子结点返回比<FONT 
  face="Times New Roman">G</FONT>的兄弟结点更好的值<FONT 
  face="Times New Roman">(</FONT>对于结点<FONT 
  face="Times New Roman">G</FONT>要走棋的一方而言<FONT 
  face="Times New Roman">)</FONT>，就可以进行裁剪。 
  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><STRONG>深的裁剪</STRONG></FONT> 
  <DT>　 
  <DT>　　我们来讨论更复杂的可能裁剪的情况。例如在同一棵搜索树中，我们评价的<FONT 
  face="Times New Roman">G</FONT>、<FONT face="Times New Roman">H</FONT>和<FONT 
  face="Times New Roman">I</FONT>都比<FONT 
  face="Times New Roman">12</FONT>好，因此<FONT 
  face="Times New Roman">12</FONT>就是结点<FONT 
  face="Times New Roman">B</FONT>的评价。现在我们来搜索结点<FONT 
  face="Times New Roman">C</FONT>，在下面两层我们找到了评价为<FONT 
  face="Times New Roman">10</FONT>的结点<FONT face="Times New Roman">N</FONT>： 
  <DIV align=center>
  <CENTER></DIV>
  <DT>　 </CENTER>
  <DIV></DIV>
  <DIV align=center>
  <CENTER></DIV>
  <DT><IMG height=370 src="基本搜索方法——简介(二)_files/search_intro3.gif" width=373> 
  </CENTER>
  <DIV></DIV>
  <DT>　 
  <DT>　　我们能用更为复杂的路线来作裁剪。我们知道<FONT face="Times New Roman">N</FONT>会返回<FONT 
  face="Times New Roman">10</FONT>或更小<FONT 
  face="Times New Roman">(</FONT>轮到棋手乙走棋，需要挑最小的<FONT 
  face="Times New Roman">)</FONT>。我们不知道<FONT 
  face="Times New Roman">J</FONT>能否返回<FONT 
  face="Times New Roman">10</FONT>或更小，也不知道<FONT 
  face="Times New Roman">J</FONT>的哪个子结点会更好。如果从<FONT 
  face="Times New Roman">J</FONT>返回到<FONT face="Times New Roman">C</FONT>的是<FONT 
  face="Times New Roman">10</FONT>或者更小的值，那么我们可以在结点<FONT 
  face="Times New Roman">C</FONT>上作裁剪，因为它有更好的兄弟结点B。因此在这种情况下，继续找<FONT 
  face="Times New Roman">N</FONT>的子结点就毫无意义。考虑其他情况，<FONT 
  face="Times New Roman">J</FONT>的其他子结点返回比<FONT 
  face="Times New Roman">10</FONT>更好的值，此时搜索<FONT 
  face="Times New Roman">N</FONT>也是毫无意义的。所以我们只要看到<FONT 
  face="Times New Roman">10</FONT>，就可以放心地从<FONT 
  face="Times New Roman">N</FONT>返回。 
  <DT>　 
  <DT><FONT face=Arial size=5><STRONG>Alpha-Beta</STRONG></FONT><FONT 
  face=楷体_GB2312 size=5><STRONG>的伪代码</STRONG></FONT> 
  <DT>　 
  <DT>　　一般来说，如果返回值比偶数层的兄弟结点好，我们就可以立即返回。如果我们在搜索过程中，把这些兄弟结点的最小值<FONT 
  face="Times New Roman">Beta</FONT>作为参数来传递，我们就可以进行非常有效的裁剪。我们还用另一个参数<FONT 
  face="Times New Roman">Alpha</FONT>来保存奇数层的结点。用这两个参数来进行裁剪是非常有效的，代码就写在下边。像上次一样，我们用负值最大<FONT 
  face="Times New Roman">(Negamax)</FONT>的形式，即搜索树的层数改变时取负值。 
  <DT>　 
  <DD>double alphabeta(int depth, double alpha, double beta) { 
  <DD>　if (depth &lt;= 0 || 棋局结束) { 
  <DD>　　return evaluation(); 
  <DD>　} 
  <DD>　就当前局面，生成并排序一系列着法; 
  <DD>　for (每个着法 m) { 
  <DD>　　执行着法 m; 
  <DD>　　double val = -alphabeta(depth - 1, -beta, -alpha); 
  <DD>　　撤消着法 m; 
  <DD>　　if (val &gt;= beta) { 
  <DD>　　　return val; 
  <DD>　　} 
  <DD>　　if (val &gt; alpha) { 
  <DD>　　　alpha = val; 
  <DD>　　} 
  <DD>　} 
  <DD>　return alpha; 
  <DD>} 
  <DT>　 
  <DT>　　下次我们会解释为什么排序这一步是很重要的。 
  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><STRONG>期望搜索</STRONG></FONT> 
  <DT>　 
  <DT>　　在根结点上我们如何为<FONT face="Times New Roman">Alpha</FONT>和<FONT 
  face="Times New Roman">Beta</FONT>设定初值？ 
  <DT>　　<FONT face="Times New Roman">Alpha</FONT>和<FONT 
  face="Times New Roman">Beta</FONT>定义了一个评价的实数区间<FONT 
  face="Times New Roman">(Alpha, Beta)</FONT>，这个区间是我们“感兴趣的”。如果某值比<FONT 
  face="Times New Roman">Beta</FONT>大我们就会做裁剪并立即返回，因为我们知道它不是主要变例的一部分，我们对它的准确值不感兴趣，只需要知道它比<FONT 
  face="Times New Roman">Beta</FONT>大。如果某值比<FONT 
  face="Times New Roman">Alpha</FONT>小，我们不作裁剪，但是仍然对它不感兴趣，因为我们知道搜索树里肯定有一个着法会更好。 
  <DT>　　但是在搜索树的根结点，我们不知道感兴趣的评价是在哪个范围内，如果我们要保证不会因为意外而裁剪掉重要的部分，我们就设<FONT
12

⌨️ 快捷键说明

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