📄 其他策略——胜利局面.htm

📁 象棋程序设计全资料集(介绍编写象棋程序的方法思路）
💻 HTM
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0054)http://www.elephantbase.net/computer/other_winning.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">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>
  <DIV align=left>
  <DT>　 </DT></DIV>
  <DIV align=left>
  <DT>　　如果棋局到达一个能用强制着法获胜的局面，那么<FONT 
  face="Times New Roman">Alpha-Beta</FONT>搜索会找到它。但是奇怪的是，每次都走一步能赢棋，不是总能赢下来的。这个问题出现在西洋棋或国际象棋中，可以走一步棋到达强制获胜的局面，但是无法使胜利更近一步。 
  </DT></DIV>
  <DIV align=left>
  <DT>　　例如，考虑下面的国际象棋局面： </DT></DIV>
  <DT>　 
  <DIV align=center>
  <CENTER></DIV>
  <DT><IMG height=256 src="其他策略——胜利局面_files/other_winning.gif" width=256> 
  </CENTER>
  <DIV></DIV>
  <DT>　 
  <DT>　　白先走可以立即获胜：把后走到<FONT 
  face="Times New Roman">e7</FONT>格将死黑王。但是白也可以走其他着法只是赢起来慢些，实际上白方只有一种着法不能取得胜利。例如，假设白把王走到<FONT 
  face="Times New Roman">e6</FONT>，黑只能走<FONT 
  face="Times New Roman">d8</FONT>和<FONT 
  face="Times New Roman">f8</FONT>，两者都会被白将死。如果黑走<FONT 
  face="Times New Roman">d8</FONT>，那么白王走回<FONT 
  face="Times New Roman">d6</FONT>仍然可以赢。但是在走了“<FONT face="Times New Roman">1. 
  Ke6 Kd8 2. Kd6 Ke8</FONT>”之后，我们回到了一开始！白走了获胜的着法，但是他没有在获胜上取得进展。 
  <DT>　　如果<FONT 
  face="Times New Roman">Alpha-Beta</FONT>搜索给任何获胜的局面以相同的评价，就很容易掉进这个陷阱。要防止这种现象，我们需要改变对胜利局面的评价，让着数少的胜法比推延获胜稍微好些。代码很直观：如果我们保留一个层数变量，代表搜索的当前局面距离根局面有多远，我们可以通过减去层数来调整胜利局面的值。以下伪代码用常数 
  <FONT face="Times New Roman">WIN </FONT>代表棋类分值的最大值<FONT 
  face="Times New Roman">(</FONT>在国际象棋中，典型的 <FONT face="Times New Roman">WIN 
  </FONT>可以是兵的价值的<FONT face="Times New Roman">100</FONT>或<FONT 
  face="Times New Roman">1000</FONT>倍<FONT face="Times New Roman">)</FONT>。 
  <DD>　 
  <DD>// 根据层数来调整胜利值的Alpha-Beta搜索 
  <DD>int ply; // 全局变量，在开始搜索时设为零 
  <DD>int alphabeta(int depth, int alpha, int beta) { 
  <DD>　if (棋局结束 &amp;&amp; 当前棋手获胜) { 
  <DD>　　return WIN - ply; 
  <DD>　} else if (棋局结束 &amp;&amp; 当前棋手失利) { 
  <DD>　　return -WIN + ply; 
  <DD>　} else if (depth &lt;= 0) { 
  <DD>　　return eval(); 
  <DD>　} 
  <DD>　ply ++; 
  <DD>　for (每个可能的着法 m) { 
  <DD>　　执行着法 m; 
  <DD>　　alpha = max(alpha, alphabeta(depth 1, beta, alpha)); 
  <DD>　　撤消着法 m; 
  <DD>　　if (alpha &gt;= beta) { 
  <DD>　　　break; 
  <DD>　　} 
  <DD>　} 
  <DD>　ply --; 
  <DD>　return alpha; 
  <DD>} 
  <DT>　 
  <DT>　　现在再来看上面的例子，<FONT face="Times New Roman">ply = 1 </FONT>时立即将死，得到的分值是<FONT 
  face="Times New Roman">999(WIN </FONT><FONT face=Symbol>-</FONT><FONT 
  face="Times New Roman"> 1)</FONT>，而把王走到<FONT 
  face="Times New Roman">e6</FONT>可以在 <FONT face="Times New Roman">ply = 3 
  </FONT>时获胜，分值是<FONT face="Times New Roman">997</FONT>。程序会使局面到达最大的分值，因此选择立即将死。 
  <DT>　　对于像黑白棋一样的棋类，棋局的长度有个适当的限制，每着棋都会在棋盘上增加一个子，因此棋局结束前最多只有<FONT 
  face="Times New Roman">64</FONT>着棋。对于这些棋类，没有可能使局面产生无限循环，因此我们可以只用 <FONT 
  face="Times New Roman">WIN </FONT>或 <FONT face=Symbol>-</FONT><FONT 
  face="Times New Roman">WIN </FONT>而不必考虑层数的调整。 
  <DT>　　这个层数调整的技巧有一个更为复杂的情况：如何跟散列表发生作用？问题是在散列表中存储的局面，其层数可能跟我们搜索到的局面有所不同。为了得到正确的层数调整值，我们应该在散列表中存储相对于当前局的分值，而不是相对于根局面的。 

  <DT>　　这样，把局面存储到散列表中，就用下面的伪代码，这里 <FONT face="Times New Roman">MAX_PLY</FONT> 
  是比搜索中可能的最大深度还大的常数<FONT face="Times New Roman">(WIN = 1000 </FONT>的话，可以让 <FONT 
  face="Times New Roman">MAX_PLY = 100)</FONT>。变量<FONT 
  face="Times New Roman"><EM>x</EM></FONT>只是当前局面在散列表中的指标。 
  <DT>　 
  <DD>if (score &gt; WIN - MAX_PLY) { 
  <DD>　hash[x].score = score + ply; 
  <DD>} else if (score &lt; -WIN + MAX_PLY) { 
  <DD>　hash[x].score = score - ply; 
  <DD>} else { 
  <DD>　hash[x].score = score; 
  <DD>} 
  <DT>　 
  <DT>　　从散列表中获取局面时，需要做相反的调整： 
  <DT>　 
  <DD>if (hash[x].score &gt; WIN - MAX_PLY) { 
  <DD>　score = hash[x].score - ply; 
  <DD>} else if (hash[x].score &lt;-WIN + MAX_PLY) { 
  <DD>　score = hash[x].score + ply; 
  <DD>} else { 
  <DD>　score = hash[x].score; 
  <DD>} 
  <DT>　 
  <DT>　　原文：<A href="http://www.ics.uci.edu/~eppstein/180a/990202a.html" 
  target=_blank><FONT 
  face="Times New Roman">http://www.ics.uci.edu/~eppstein/180a/990202a.html</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/evalue_intro2.htm">局面评估函数——简介<FONT 
face="Times New Roman">(</FONT>二<FONT face="Times New Roman">)</FONT></A> 
<LI>下一篇　<A 
href="http://www.elephantbase.net/computer/other_pvcollect.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>
💿 文件大小 859 K
👤 上传用户 Emouse
📂 所属分类文件格式
🏷️ 相关标签

#程序设计 #程序 #编写
⌨️ 快捷键说明

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