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

📄 高级搜索方法——简介(一).htm

📁 象棋程序设计全资料集(介绍编写象棋程序的方法思路）
💻 HTM
📖 第 1 页 / 共 2 页
字号:
🔍
12 
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0056)http://www.elephantbase.net/computer/advanced_intro1.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.536" 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=隶书 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="Times New Roman">Alpha-Beta</FONT>告诉我们怎样搜索，但是我们仍然需要知道，何时需要展开结点<FONT 
  face="Times New Roman">(</FONT>搜索它的子结点<FONT 
  face="Times New Roman">)</FONT>，以及何时停下来从而调用评价函数。 
  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><STRONG>水平线效应</STRONG></FONT> 
  <DT>　 
  <DT>　　在前面我给你们看的伪代码中，每一步棋都搜索到一个固定的深度，这个深度被称为“水平线”<FONT 
  face="Times New Roman">(Horizon)</FONT>。对于看到水平线以内会发生的威胁，这个方法非常有效，但是它显然不能检查到水平线以后的威胁。例如在<FONT 
  face="Times New Roman">8</FONT>层的搜索中<FONT 
  face="Times New Roman">(</FONT>即搜索<FONT 
  face="Times New Roman">4</FONT>个回合<FONT 
  face="Times New Roman">)</FONT>，就可能得不到在<FONT 
  face="Times New Roman">5</FONT>步内有杀棋的任何信息。它不知道的事情，就无法作出防御，而且只是简单地忽略那些遥远的威胁。然而当局势面临中等深度的威胁而丢子不可避免时，固定深度的搜索有时会走出更糟的棋，因为某些丢子会在搜索水平线以内，而有些却不在。在这种情况下，程序会走出糟糕的并且无意义的棋，试图来延缓丢子的发生，使得它出现在程序看不到的未来。这种现象称为“水平线效应”<FONT 
  face="Times New Roman">(Horizon Effect)</FONT>。 
  <DT>　　这里有个例子。在下面的局势中，黑象被白兵包围，不管黑的怎么走，象总是会在几步内被吃掉；例如白车可以沿着<FONT 
  face="Times New Roman">h2-h1-a1-a2</FONT>吃掉象。这是一个<FONT 
  face="Times New Roman">8</FONT>层深的变化，那么假设黑方的程序也搜索<FONT 
  face="Times New Roman">8</FONT>层。可能当前局面对黑方来说，最好的走法就是用象换兵，即象吃掉兵，兵吃掉象。在后面的残局里，黑方的三个连兵足以战胜或守和白车。<FONT 
  color=#0000ff>【译注：其实守和的希望也不大，译者认为黑方还是会输掉的，因为白王的位置非常好，可以独挡三黑兵，使得白车有时间拔掉</FONT><FONT 
  face="Times New Roman" color=#0000ff>b</FONT><FONT 
  color=#0000ff>线的黑兵。】</FONT>但是程序搜索<FONT 
  face="Times New Roman">8</FONT>层，很有可能会挺黑兵将军白王。白必须应对<FONT 
  face="Times New Roman">(</FONT>例如自己来吃掉兵<FONT 
  face="Times New Roman">)</FONT>，这个应对使得丢象被暂时避免，拖延到程序看不到的步数内，并且程序认为象是安全的。实际上在这个局面里，固定深度的程序可能会连续地送吃兵，把象被吃的结果延缓几步，但是最终可能输掉整盘棋。 

  <DT>　 
  <DIV align=center>
  <CENTER></DIV>
  <DT><IMG height=256 src="高级搜索方法——简介(一)_files/advanced_intro1.gif" width=256> 
  </CENTER>
  <DIV></DIV>
  <DT>　 
  <DT>　　对付水平线效应的一个方法，就是在你的程序里增加一些知识：如果从评价中知道象被包围，那么搜索程序就不会通过弃兵来延缓丢象。另一个方法是让搜索更快更深：你的程序搜索的层数越多，因超过水平线而延缓丢象的做法，发生的可能性就越小。但是对于普通局面来说，最有效的做法就是让搜索深度更灵活，使得程序在丢兵的路线上搜索得更深，而在其它路线上不必要搜索得很深。 

  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><STRONG>蛮力和选择性</STRONG></FONT> 
  <DT>　 
  <DT>　　在<FONT face="Times New Roman">Shannon</FONT><FONT 
  color=#0000ff>【申朗，参阅译文《</FONT><A 
  href="http://www.elephantbase.net/computer/history.htm" target=_blank><FONT 
  color=#0000ff>电脑国际象棋简史</FONT></A><FONT 
  color=#0000ff>》】</FONT>最早关于电脑国际象棋的文章中，提到程序调整搜索深度的两种策略。 
  <DT>　　最明显的就是我给你们看的伪代码：全部范围，固定深度的蛮力搜索。只要把“深度”这个参数输入到你的程序中，每搜索一层就减一，到达零时停下来。这样做的好处在于，只要在搜索水平线以内，一些甚至很怪异的线路也看得到。但是高的分枝因子就意味着任何线路都不可能很深<FONT 
  face="Times New Roman">(</FONT>即学士程度，对任何事物都只知道个皮毛<FONT 
  color=#0000ff>【原文是“</FONT><FONT face="Times New Roman" 
  color=#0000ff>Bachelor's degree: knows nothing about everything</FONT><FONT 
  color=#0000ff>”】</FONT><FONT 
  face="Times New Roman">)</FONT>。更遭的是，程序可能会栽倒在水平线效应下。 
  <DT>　　<FONT 
  face="Times New Roman">Shannon</FONT>提到的另外一个方法就是选择性裁剪：不是搜索固定的深度，而是通过搜索每个结点的部分着法来减少分枝因子<FONT 
  face="Times New Roman">(</FONT>避免那些“明显是坏棋”的着法<FONT 
  face="Times New Roman">)</FONT>。因此这样可以搜索得很深，但是有些线路完全看不见<FONT 
  face="Times New Roman">(</FONT>即博士程度，只对某个狭窄方面的懂得很多<FONT 
  color=#0000ff>【原文是“</FONT><FONT face="Times New Roman" color=#0000ff>Ph.D.: 
  knows everything about nothing</FONT><FONT 
  color=#0000ff>”，源于一句用来讽刺博士的笑话：“</FONT><FONT face="Times New Roman" 
  color=#0000ff>A PhD knows more and more about less and less until he knows 
  everything about nothing</FONT><FONT color=#0000ff>”】</FONT><FONT 
  face="Times New Roman">)</FONT>。<FONT 
  face="Times New Roman">Shannon</FONT>认为这个思想非常好，因为它更接近人类的思考方式。<FONT 
  face="Times New Roman">Turing</FONT><FONT color=#0000ff>【图灵，参阅译文《</FONT><A 
  href="http://www.elephantbase.net/computer/history.htm" target=_blank><FONT 
  color=#0000ff>电脑国际象棋简史</FONT></A><FONT 
  color=#0000ff>》】</FONT>的思想有所不同，只搜索吃子的着法。更典型的做法是，对所有的子结点作评价，而只对最好的<FONT 
  face="Times New Roman"><EM>k</EM></FONT>个作展开，这里<FONT 
  face="Times New Roman"><EM>k</EM></FONT>是小于实际分枝因子的一个参数。 
  <DT>　　不幸的是，“明显是坏棋”的着法往往根本不坏，而是取得胜利的精彩弃子。如果你没有找到你应该走的那步着法，你就必须更努力地去找其他可以获胜的方法。更糟的是，对手可能会在后面几步作出有力的反击，如果你没有看出来，那么你会掉入陷阱从而输掉棋局。 

  <DT>　　如今没有哪个思想会被单纯地使用的。我们把两者结合起来：选择性地延伸。每条路线都搜索固定的深度，但是某些路线要搜索得比水平线深。有时我们也会做裁剪<FONT 
  face="Times New Roman">(</FONT>不是像<FONT 
  face="Times New Roman">Alpha-Beta</FONT>那样的安全裁剪<FONT 
  face="Times New Roman">)</FONT>，这通常也是非常保守的，因为只挑出好的着法实在太困难了，但是有时对于确实很坏的着法，我们可以挑出并且忽略它们。除了国际象棋以外，有些棋类有更高的分枝因子，这就有必要使用更冒进的裁剪技术了。<FONT 
  color=#0000ff>【例如五子棋，每个局面都有</FONT><FONT face="Times New Roman" 
  color=#0000ff>100</FONT><FONT 
  color=#0000ff>种以上的合理着法，但是我们只会挑有意义的着法，要么有进攻作用</FONT><FONT 
  face="Times New Roman" color=#0000ff>(</FONT><FONT 
  color=#0000ff>己方棋子周围的一些着点</FONT><FONT face="Times New Roman" 
  color=#0000ff>)</FONT><FONT color=#0000ff>，要么有防守作用</FONT><FONT 
  face="Times New Roman" color=#0000ff>(</FONT><FONT 
  color=#0000ff>敌方棋子邻近的着点</FONT><FONT face="Times New Roman" 
  color=#0000ff>)</FONT><FONT color=#0000ff>，除此以外一概不予考虑。】</FONT> 
  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><STRONG>什么时候需要延伸？</STRONG></FONT> 
  <DT>　 
  <DT>　　延伸的目标是什么呢？是获得更好<FONT face="Times New Roman">(</FONT>更准确<FONT 
  face="Times New Roman">)</FONT>的评价。所以下面的结点必须延伸： 
  <DT>　　<FONT face="Times New Roman">(1) </FONT>目前的评价可能不准确时； 
  <DT>　　<FONT face="Times New Roman">(2) </FONT>目前的着棋路线在整个博弈搜索树中是非常重要的； 
  <DT>　　或者以上两个情况的组合。 
  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><STRONG>静态搜索</STRONG></FONT> 
  <DT>　 
  <DT>　　在国际象棋或其他棋类中，有吃子和不吃子的着法<FONT face="Times New Roman">(</FONT>西洋跳棋、围棋、<FONT 
  face="Times New Roman">Fanorano</FONT>等<FONT 
  face="Times New Roman">)</FONT>，如果有吃子的情况，那么每次吃子时评价都会改变。 
  <DT>　　“静态搜索”<FONT face="Times New Roman">(Quiescence 
  Search)</FONT>的思想是，到达主搜索的水平线后，用一个图灵型的搜索只展开吃子<FONT 
  face="Times New Roman">(</FONT>有时是吃子加将军<FONT 
  face="Times New Roman">)</FONT>的着法。其他棋类不同于国际象棋，可能只包括一些会很大程度上改变评价的着法。静态搜索还必须包括放弃的着法，来决定停止吃子。因此，主<FONT 
  face="Times New Roman">Alpha-Beta</FONT>搜索中每个调用评价函数的地方，都会被一个类似<FONT 
  face="Times New Roman">Alpha-Beta</FONT>的但只搜索吃子着法的函数代替，如果当前结点的评价函数足以高出边界，那么就让搜索停下来。代码如下： 

  <DD>　 
  <DD>// 静态搜索 
  <DD>// 主Alpha-Beta搜索中，原来出现“eval()”的地方现在调用这个函数 
  <DD>quiesce(int alpha, int beta) { 
  <DD>　int score = eval(); 
  <DD>　if (score &gt;= beta) { 
  <DD>　　return score; 
  <DD>　} 
  <DD>　for (每个吃子着法 m) { 
  <DD>　　执行着法 m; 
  <DD>　　score = -quiesce(-beta,-alpha); 
  <DD>　　撤消着法 m; 
  <DD>　　if (score &gt;= alpha) { 
  <DD>　　　alpha = score; 
  <DD>　　　if (score &gt;= beta) { 
  <DD>　　　　break; 
  <DD>　　　} 
  <DD>　　} 
  <DD>　} 
  <DD>　return score; 
  <DD>} 
  <DT>　 
  <DT>　　有人还把将军加入到静态搜索中，但是你要当心，由于没有深度参数，静态搜索会有巨大的结点数。吃子通常是有限的<FONT 
  face="Times New Roman">(</FONT>在棋子全部吃完以前你只能有<FONT 
  face="Times New Roman">16</FONT>次子<FONT 
  face="Times New Roman">)</FONT>，而将军可以一直进行下去并导致无限制递归。<FONT 
  color=#0000ff>【对于是否展开将军着法的问题，可以尝试一种做法，如果局面被将军，就展开全部着法，即做应将处理，而不对当前局面作评价，参阅“</FONT><A 
  href="http://www.elephantbase.net/computer/advanced_quiescent.htm" 
  target=_blank><FONT color=#0000ff>静态搜索</FONT></A><FONT
12

⌨️ 快捷键说明

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