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

📄 基本搜索方法——简介(一).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_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.2759" name=GENERATOR></HEAD>
<BODY background=基本搜索方法——简介(一)_files/background.gif>
<DL>
  <DIV align=center>
  <CENTER>
  <DT><FONT size=3>《对弈程序基本技术》专题</FONT> </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">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">(Tic-tac-toe)</FONT>的搜索树： 
  <DT>　 
  <DIV align=center>
  <CENTER></DIV>
  <DT>　 </CENTER>
  <DIV></DIV>
  <DIV align=center>
  <CENTER></DIV>
  <DT><IMG height=287 src="基本搜索方法——简介(一)_files/search_intro1.gif" width=393> 
  </CENTER>
  <DIV></DIV>
  <DT>　 
  <DT>　　<FONT face="Times New Roman">(</FONT>实际上，这个搜索树的根结点应该有<FONT 
  face="Times New Roman">9</FONT>个子结点，但是我去掉了一些对称的情况。如果同样的棋盘是由两个不同的着法顺序形成的，那么我们就建立两个结点，所以这的确是树的结构。稍后我们会在讨论散列技术的时候谈到如何利用重复的结点来提高搜索速度——我们只要搜索第一个，另一个就用第一个搜索结果来代替。另外我们假设棋手是轮流下棋的，没有人一次走多步或跳过不走的，那些复杂的情况可以把它走的一系列着法看作一个着法来处理。<FONT 
  color=#0000ff>【译注：复杂的情况是指一些一次能走很多步的棋类游戏，例如跳棋、西洋跳棋、黑白棋等，按照原作者的方案，可以把一方连续走的几步棋看成一步棋。而译者更愿意把一方连续的几步棋拆成几个回合，只是另一方都别无选择地走了空着。】</FONT>最后，我们假设搜索树是有限的，这样我们就不会遇到永无止境的棋局或者一步有无限多种着法的棋局。<FONT 
  face="Times New Roman">)</FONT> 
  <DT>　　搜索树中有三种类型的结点： 
  <DT>　　<FONT face="Times New Roman">(1) </FONT>偶数层的中间结点，代表棋手甲要走的局面； 
  <DT>　　<FONT face="Times New Roman">(2) </FONT>奇数层的中间结点，代表棋手乙要走的局面； 
  <DT>　　<FONT face="Times New Roman">(3) </FONT>叶子结点，代表棋局结束的局面，即棋手甲或棋手乙获胜，或者是和局。 

  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><STRONG>博弈树的评价</STRONG></FONT> 
  <DT>　 
  <DT>　　假设某个中间结点的所有子结点都是叶子结点，那么棋局会在一回合内结束。现在我们假设棋手会挑选最好的着法，如果有一个着法能使他赢下棋局，那么他一定会走这步。如果没有可以赢的着法，但是有取得和局的着法，那么他会走这步取得和局的着法。但是，如果所有的着法都使得对手获胜，那么无论如何他都会输。 

  <DT>　　因此在叶子结点的上一层结点，我们就能知道棋局的结果。现在我们知道了这个结点的结果，那么我们可以用同样的方法作推演，知道叶子结点的上两层结点的结果，然后是上三层结点，等等，直到我们达到搜索树的根结点。在每个结点上，棋手只要找到一个子结点能让他获胜，那么他就可以赢下棋局；他只要找到一个形成和局的子结点，棋局就和了；如果获胜与和局的子结点都没有，那么肯定是输的。如果我们有足够多的时间来计算，那么这就给了我们一个可以下棋的完美算法。但是对于任何常规的棋类游戏，我们都不可能有足够的计算时间，因为搜索树实在太大了。 

  <DT>　　另外，“正确”的评价函数只有三个值，赢、输或者和局。在实际的棋类程序中，我们通常使用一个更宽泛的实数来作评价值，就是因为赢、输或者和局是不确定的。如果棋手甲获胜的值用<FONT 
  face="Times New Roman">+1</FONT>表示，和局的值用<FONT 
  face="Times New Roman">0</FONT>表示，棋手乙获胜的值用<FONT face=Symbol>-</FONT><FONT 
  face="Times New Roman">1</FONT>表示，那么博弈树的每个中间结点的值就是子结点的最大值或最小值，这取决于棋手甲还是棋手乙着棋。 
  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><STRONG>部分的博弈树</STRONG></FONT> 
  <DT>　 
  <DT>　　在实战中，我们的搜索算法只能对博弈树展开一部分。我们用一些“中止规则”来决定搜索树展开到哪个结点就停下来，例如我们在<FONT 
  face="Times New Roman">8</FONT>步变化以后听下来。由于棋局没有在叶子结点结束，我们只能用评价函数来猜哪一方获胜。现在我们来假设在我们展开的结点中，棋手甲总是希望棋局到达评价函数大的局面，而棋手乙总是希望棋局到达评价函数小的局面。 

  <DT>　　如果双方都用这种方法来下棋，那么我们可以使用同样的最小<FONT 
  face="Times New Roman">-</FONT>最大过程，来确定到达的叶子结点的评价值，这个过程如下：对每个中间结点，计算子结点的最大值或最小值，这取决于是棋手甲还是棋手乙走棋。到达叶子结点的线路称为“主要变例”<FONT 
  face="Times New Roman">(Principal Variation)</FONT>。最小<FONT 
  face="Times New Roman">-</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>。然而实战中，我们使用深度优先<FONT 
  face="Times New Roman">(</FONT>即后序遍历<FONT 
  face="Times New Roman">)</FONT>的递归过程来遍历搜索树，即要得到一个结点的值，就对子结点做递归，然后根据它们的返回值来决定自身的返回值。这样要节省很多空间，因为不需要来存储整个博弈树，而只是存储一条线路<FONT 
  face="Times New Roman">(</FONT>相对来说非常短，例如上面提到的<FONT 
  face="Times New Roman">8</FONT>步中止的规则<FONT 
  face="Times New Roman">)</FONT>。下次我们讨论<FONT 
  face="Times New Roman">Alpha-Beta</FONT>搜索时，会发现深度优先的遍历会有很大的优势，你可以用目前得到的信息来决定某些结点是不需要访问的，这样就节省下很多的时间。 

  <DT>　　只要对搜索树的值作一个很小的改动，就可以用一个求最大值的操作来代替最小值和最大值交替的过程。在搜索树的奇数层<FONT 
  face="Times New Roman">(</FONT>即轮到棋手乙下棋的结点<FONT 
  face="Times New Roman">)</FONT>，就对上面提到的评价值取负数。因此在每个结点上，这些值都可以由子结点的负值求得。我把博弈树搜索的源代码写出来，恐怕就会清楚很多了。 

  <DT>　 
  <DD>// 将博弈树搜索到一定的深度，返回根结点的评价值 
  <DD>double negamax(int depth) { 
  <DD>　if (depth &lt;= 0 || 棋局结束) 
  <DD>　　return eval(pos); 
  <DD>　else { 
  <DD>　　double e = -infty; 
  <DD>　　for (当前局面所有可能的着法 m) { 
  <DD>　　　执行着法 m; 
  <DD>　　　e = max(e, -negamax(depth - 1)); 
  <DD>　　　撤消着法 m; 
  <DD>　　} 
  <DD>　　return e; 
  <DD>　} 
  <DD>} 
  <DT>　 
  <DT>　　注意，这个过程只能找到评价值，但是无法得知着法。我们只要在搜索树的根结点找到着法<FONT 
  face="Times New Roman">(</FONT>尽管很多程序都返回整个主要变例<FONT 
  face="Times New Roman">)</FONT>就可以了，要做到这一点，可以对根结点的搜索稍作改动： 
  <DD>　 
  <DD>// 将博弈树搜索到一定的深度，返回根结点的着法 
  <DD>move rootsearch(int depth) { 
  <DD>　double e = -infty; 
  <DD>　move mm; 
  <DD>　for (当前局面所有可能的着法 m) { 
  <DD>　　执行着法 m; 
  <DD>　　double em = -negamax(depth - 1); 
  <DD>　　if (e &lt; em) {
12

⌨️ 快捷键说明

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