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

📄 其他策略——主要变例的获取.htm

📁 象棋程序设计全资料集(介绍编写象棋程序的方法思路）
💻 HTM
字号:
🔍 
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0056)http://www.elephantbase.net/computer/other_pvcollect.htm -->
<HTML><HEAD><TITLE>其他策略——主要变例的获取</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb_2312-80">
<META content="MSHTML 6.00.3790.2817" 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">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>　　经常有人问，如何在搜索完成后提取主要变例。主要变例是程序认为的对双方来说都是最好的着法线路。它不会由未修改的“<A 
  href="http://www.elephantbase.net/computer/search_alphabeta.htm" 
  target=_blank><FONT 
  face="Times New Roman">Alpha-Beta</FONT>函数</A>”来获得，所有的<FONT 
  face="Times New Roman">Alpha-Beta</FONT>都只返回数值。 
  <DT>　　我们需要做的是对普通的<FONT 
  face="Times New Roman">Alpha-Beta</FONT>搜索作修改，使得它能获取主要变例。修改的部分用醒目的颜色标出： 
  <DD>　 
  <DD><FONT color=#ff0000>typedef struct tagLINE {</FONT> 
  <DD><FONT color=#ff0000>　int cmove; 　　　　　　// 路线中着法的数量；</FONT> 
  <DD><FONT color=#ff0000>　MOVE argmove[moveMAX]; // 路线。</FONT> 
  <DD><FONT color=#ff0000>} LINE;</FONT> 
  <DD>　 
  <DD>int AlphaBeta(int depth, int alpha, int beta<FONT color=#ff0000>, LINE 
  *pline</FONT>) { 
  <DD><FONT color=#ff0000>　LINE line;</FONT> 
  <DD>　if (depth == 0) { 
  <DD><FONT color=#ff0000>　　pline-&gt;cmove = 0;</FONT> 
  <DD>　　return Evaluate(); 
  <DD>　} 
  <DD>　GenerateLegalMoves(); 
  <DD>　while (MovesLeft()) { 
  <DD>　　MakeNextMove(); 
  <DD>　　val = -AlphaBeta(depth - 1, -beta, -alpha<FONT color=#ff0000>, 
  &amp;line</FONT>); 
  <DD>　　UnmakeMove(); 
  <DD>　　if (val &gt;= beta) { 
  <DD>　　　return beta; 
  <DD>　　} 
  <DD>　　if (val &gt; alpha) { 
  <DD>　　　alpha = val; 
  <DD><FONT color=#ff0000>　　　pline-&gt;argmove[0] = ThisMove();</FONT> 
  <DD><FONT color=#ff0000>　　　memcpy(pline-&gt;argmove + 1, line.argmove, 
  line.cmove * sizeof(MOVE));</FONT> 
  <DD><FONT color=#ff0000>　　　pline-&gt;cmove = line.cmove + 1;</FONT> 
  <DD>　　} 
  <DD>　} 
  <DD>　return alpha; 
  <DD>} 
  <DT>　 
  <DT>　　这个函数或许效率很低，因为它用到很多的堆栈空间，但是代码工作起来并不慢。有了这些改动后，如果函数返回<FONT 
  face="Times New Roman">Alpha</FONT>和<FONT 
  face="Times New Roman">Beta</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">Alpha-Beta</FONT>： 
  <DD>　 
  <DD>val = AlphaBeta(depth, -INFINITY, INFINITY, &amp;line); 
  <DT>　 
  <DT>　　你得到的是局面的值，以及在“<FONT 
  face="Times New Roman">line</FONT>”这个存储区里保存的预测路线。“<FONT 
  face="Times New Roman">line</FONT>”的数据结构是一个着法数组，以构成一个路线，另有一个整数来告诉你路线中有多少着法。 
  <DT>　　如果你用深度等于零去调用<FONT 
  face="Times New Roman">Alpha-Beta</FONT>，那么这个函数只调用“<FONT 
  face="Times New Roman">Evaluate()</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 
  color=#0000ff>【译注：即函数中的“</FONT><FONT face="Times New Roman" 
  color=#0000ff>*pline</FONT><FONT color=#0000ff>”】</FONT>，并把局部的路线存储区<FONT 
  color=#0000ff>【即函数中的“</FONT><FONT face="Times New Roman" 
  color=#0000ff>line</FONT><FONT color=#0000ff>”】</FONT>也加到传递的存储区中。 
  <DT>　　你可能会问：“既然有传过来的路线存储区，为什么又要在每次递归的堆栈中新分配一个？”因为你在搜索树中找到一个局部的线路，那么原来的线路被推翻了，但你不能毁坏已经建立好的线路。如果你找到某个返回值在<FONT 
  face="Times New Roman">Alpha</FONT>和<FONT 
  face="Times New Roman">Beta</FONT>之间的结点，你就认为这个结点在搜索树的根结点的路线上，这是不对的。有很多零碎的主要变例是被丢弃的。 

  <DT>　　让你们感到惊讶的是，我在循环内用了“<FONT face="Times New Roman">memcpy</FONT>”这个函数<FONT 
  color=#0000ff>【事实上这也是个循环，因此可能会认为它的效率很低】</FONT>，它几乎不花时间，因为它很少被执行。 
  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><STRONG>另一个思想</STRONG></FONT> 
  <DT>　 
  <DT>　　另一个一目了然的方法，就是在搜索值返回后，从主置换表中提取主要变例。置换表项中有一个区域存放这局面的最佳着法。由于每个<FONT 
  face="Times New Roman">PV</FONT>结点都有一个值在<FONT 
  face="Times New Roman">Alpha</FONT>和<FONT 
  face="Times New Roman">Beta</FONT>之间，散列项中必定保存着“最佳着法”。 
  <DT>　　从置换表中提取主要变例，可以沿着散列项组成的链来提取，这就像吃馅饼一样简单。 
  <DT>　　我知道很多程序<FONT face="Times New Roman">(</FONT>包括一些专业程序<FONT 
  face="Times New Roman">)</FONT>是这样做的，但是我没有试过。 
  <DT><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><FONT 
  face="Times New Roman" color=#0000ff>PV</FONT><FONT 
  color=#0000ff>结点优先的策略，因为</FONT><FONT face="Times New Roman" 
  color=#0000ff>PV</FONT><FONT color=#0000ff>结点的数量比</FONT><FONT 
  face="Times New Roman" color=#0000ff>Alpha</FONT><FONT 
  color=#0000ff>结点和</FONT><FONT face="Times New Roman" 
  color=#0000ff>Beta</FONT><FONT 
  color=#0000ff>结点少得多，所以这个覆盖策略对置换表不会产生很大的影响。</FONT> 
  <DT><FONT color=#0000ff>　　另外，直接从</FONT><FONT face="Times New Roman" 
  color=#0000ff>Alpha-Beta</FONT><FONT 
  color=#0000ff>函数提取的主要变例，会因为置换表的运用而中断，除非置换表里有一项用来存储主要变例</FONT><FONT 
  face="Times New Roman" color=#0000ff>(</FONT><FONT 
  color=#0000ff>这不是不可能的，因为</FONT><FONT face="Times New Roman" 
  color=#0000ff>PV</FONT><FONT color=#0000ff>结点的数量非常少</FONT><FONT 
  face="Times New Roman" color=#0000ff>)</FONT><FONT 
  color=#0000ff>。如果要得到完整的主要变例，可以考虑不在置换表中写入</FONT><FONT face="Times New Roman" 
  color=#0000ff>PV</FONT><FONT color=#0000ff>结点</FONT><FONT 
  face="Times New Roman" color=#0000ff>(</FONT><FONT 
  color=#0000ff>某些程序甚至只在置换表中写入</FONT><FONT face="Times New Roman" 
  color=#0000ff>Beta</FONT><FONT color=#0000ff>结点</FONT><FONT 
  face="Times New Roman" color=#0000ff>)</FONT><FONT color=#0000ff>。】</FONT> 
  <DT>　 
  <DT>　　原文：<A href="http://www.seanet.com/~brucemo/topics/pv.htm" 
  target=_blank><FONT 
  face="Times New Roman">http://www.seanet.com/~brucemo/topics/pv.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/other_winning.htm">其他策略——胜利局面</A> 
<LI>下一篇　<A 
href="http://www.elephantbase.net/computer/other_repetition.htm">其他策略——重复检测</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 + -