解剖大象的眼睛——中国象棋程序设计探索(五)：克服水平线效应.htm

象棋程序设计全资料集(介绍编写象棋程序的方法思路）

  <DT>　　<FONT face="Times New Roman">(3) </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>等守子，则禁用空着裁剪。 
  <DT>　　因此，<FONT face="Times New Roman">ElephantEye</FONT>的代码中，和空着裁剪有关的部分如下： 
  <DD>　 
  <DD>const int NULL_REDUCTION = 2 
  <DD>　 
  <DD>int AlphaBeta(int Alpha, int Beta, int Depth, bool Verify = false) { 
  <DD>　…… 
  <DD>　if (!Verify &amp;&amp; !InCheck() &amp;&amp; NullOkay()) { 
  <DD>　　MakeNull(); 
  <DD>　　Value = -AlphaBeta(-Beta, 1 - Beta, Depth - 1 - NULL_REDUCTION); 
  <DD>　　UndoNull(); 
  <DD>　　if (Value &gt;= Beta<FONT color=#ff0000> &amp;&amp; (NullSafe() || 
  AlphaBeta(Beta - 1, Beta, Depth - NULL_REDUCTION, true) &gt;= Beta)</FONT>) { 
  <DD>　　　return Value; 
  <DD>　　} 
  <DD>　} 
  <DD>　…… 
  <DD>} 
  <DT>　 
  <DT>　　这个技术使得<FONT 
  face="Times New Roman">ElephantEye</FONT>在残局中仍旧能启用空着裁剪，而且不会出现走错的情况，因此<FONT 
  face="Times New Roman">ElephantEye</FONT>在几乎不带残局知识的情况下，残局的棋力还是非常高的。 
  <DT>　 
  <DT><FONT face=Arial size=4><STRONG>5.3 </STRONG></FONT><FONT face=楷体_GB2312 
  size=4><STRONG>静态搜索</STRONG></FONT> 
  <DT>　 
  <DT>　　静态搜索尽管实现起来比较简单，但是很多技术细节仍旧是需要考虑的，问题主要有以下几个： 
  <DT>　　<FONT face="Times New Roman">(1) 
  </FONT>如果结点被将军，是否要产生全部着法。绝大多数程序都没有考虑结点被将军的情况，因为将军判断是很花费时间的。而<FONT 
  face="Times New Roman">ElephantEye</FONT>在将军判断上有优势，因此在将军时产生全部的着法。因此有些多步连杀的排局，如果每步将军都吃子，那么<FONT 
  face="Times New Roman">ElephantEye</FONT>只需要搜索<FONT 
  face="Times New Roman">1</FONT>层就可以解出了，因此静态搜索中判断将军对于搜索杀棋是很有好处的。 
  <DT>　　<FONT face="Times New Roman">(2) </FONT>如何使用<FONT 
  face="Times New Roman">MVV/LVA</FONT>启发。<FONT 
  face="Times New Roman">MVV/LVA</FONT>是静态搜索最常用的启发方式，如果棋盘的数据结构精心设计，<FONT 
  face="Times New Roman">SEE</FONT>也是值得尝试的。尽管<FONT 
  face="Times New Roman">MVV/LVA</FONT>很简单，但是究竟根据“被吃子价值<FONT 
  face="Times New Roman">-</FONT>攻击子价值”来排序，还是先排序“被吃子价值”，相同的情况再排序“攻击子价值”呢？<FONT 
  face="Times New Roman">ElephantEye</FONT>是以<FONT 
  face="Times New Roman">MVV(LVA)</FONT>的值为依据的，可参考前一章<FONT 
  face="Times New Roman">(</FONT>吃子启发<FONT face="Times New Roman">)</FONT>。 
  <DT>　　<FONT face="Times New Roman">(3) 
  </FONT>是否需要用其他搜索或启发算法。常规搜索中的很多搜索算法都不适合于静态搜索，这就是静态搜索简单的缘故。静态搜索本身就是空着启发的<FONT 
  face="Times New Roman">(</FONT>第一个着法总是空着<FONT 
  face="Times New Roman">)</FONT>，但由于没有深度参数，所以不可能使用空着裁剪。另外，几乎所有的程序都不在静态搜索中使用<FONT 
  face="Times New Roman">PVS</FONT>、置换表、杀手着法启发、历史表启发等算法。 
  <DT>　　<FONT face="Times New Roman">(4) 
  </FONT>是否所有的吃子都需要考虑。如果搜索全部吃子着法，那么程序在叶子结点上花费的时间就非常浪费。<FONT 
  face="Times New Roman">ElephantEye</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">(</FONT>士<FONT face="Times New Roman">)</FONT>和相<FONT 
  face="Times New Roman">(</FONT>象<FONT face="Times New Roman">)</FONT>在<FONT 
  face="Times New Roman">ElephantEye</FONT>的子力评价中分数很高<FONT 
  face="Times New Roman">(</FONT>轻子价值的<FONT 
  face="Times New Roman">20%</FONT>到<FONT 
  face="Times New Roman">40%)</FONT>，但静态搜索本身就是对局面的粗略评价。 
  <DT>　 
  <DT><FONT face=Arial size=4><STRONG>5.4 </STRONG></FONT><FONT face=楷体_GB2312 
  size=4><STRONG>选择性延伸</STRONG></FONT> 
  <DT>　 
  <DT>　　常用的选择性延伸有这几种策略：<FONT face="Times New Roman">(1) </FONT>将军延伸；<FONT 
  face="Times New Roman">(2) </FONT>单一应着延伸；<FONT face="Times New Roman">(3) 
  </FONT>杀棋威胁延伸；<FONT face="Times New Roman">(4) </FONT>兑子延伸；<FONT 
  face="Times New Roman">(5) </FONT>通路兵挺进延伸。<FONT 
  face="Times New Roman">ElephantEye</FONT>只考虑了将军延伸、杀棋威胁延伸和兑子延伸，代码很简单： 
  <DD>　 
  <DD>int AlphaBeta(int Alpha, int Beta, int Depth) { 
  <DD>　…… 
  <DD>　MoveStruct ThisMove = NextMove(); 
  <DD>　while (ThisMove != NullMove) { 
  <DD>　　MakeMove(ThisMove); 
  <DD><FONT color=#ff0000>　　NewDepth = (InCheck() || MateThreat || 
  ReCapture(LastMove, ThisMove) ? Depth : Depth - 1);</FONT> 
  <DD>　　Value = Search(-Beta, -Alpha, NewDepth); 
  <DD>　　UndoMove(); 
  <DD>　　…… 
  <DD>　　ThisMove = NextMove(); 
  <DD>　} 
  <DD>　…… 
  <DD>} 
  <DT>　 
  <DT>　　是否延伸由三个因素决定，即是否被将军<FONT 
  face="Times New Roman">(InCheck())</FONT>、是否有杀棋威胁<FONT 
  face="Times New Roman">(MateThreat)</FONT>和是否是兑子着法<FONT 
  face="Times New Roman">(ReCapture(LastMove, 
  ThisMove))</FONT>。将军延伸是最容易理解的，如果当前搜索的着法是将军对方的着法，那么就多搜索一层。 
  <DT>　　威胁延伸指的是，对方走出一步催杀的棋时，需要多搜索一层，而判断对方是否催杀则是利用空着裁剪，为此空着裁剪的代码应该作适当的修改： 
  <DD>　 
  <DD>…… 
  <DD>MateThreat = false; 
  <DD>if (!InCheck() &amp;&amp; NullOkay()) { 
  <DD>　MakeNull(); 
  <DD>　Value = -AlphaBeta(-Beta, 1 - Beta, Depth - 1 - NULL_REDUCTION); 
  <DD>　UndoNull(); 
  <DD>　if (Value &gt;= Beta) { 
  <DD>　　return Value; 
  <DD><FONT color=#ff0000>　} else if (Value == Ply + 2 - MATE_VALUE) {</FONT> 
  <DD><FONT color=#ff0000>　　MateThreat = true;</FONT> 
  <DD>　} 
  <DD>} 
  <DD>…… 
  <DT>　 
  <DT>　　如果本方走了空着，而立即被对方将死<FONT face="Times New Roman">(</FONT>该结点的深度是<FONT 
  face="Times New Roman">Ply + 2)</FONT>，那么返回值作<FONT 
  face="Times New Roman">DTM</FONT>调整将变成<FONT face="Times New Roman">Ply + 2 
  </FONT><FONT face=Symbol>-</FONT><FONT face="Times New Roman"> 
  MATE_VALUE</FONT>，因此该值就成为判断是否催杀的依据。 
  <DT>　　兑子延伸指的是，遇到连续两个吃子着法，并且吃同一格子的子，这样的着法称为“吃回”<FONT 
  face="Times New Roman">(ReCapture)</FONT>，需要多搜索一层，为此判断两个着法是否吃回的函数可以写成： 
  <DD>　 
  <DD>inline bool ReCapture(MoveStruct LastMove, MoveStruct ThisMove) { 
  <DD>　return LastMove.Cpt != 0 &amp;&amp; LastMove.Dst == ThisMove.Dst 
  <DD>} </DD></DL>
<DIR>
<LI>上一篇　<A 
href="http://www.elephantbase.net/computer/eleeye_heuristic.htm">中国象棋程序设计探索<FONT 
face="Times New Roman">(</FONT>四<FONT face="Times New Roman">)</FONT>：启发算法</A> 
<LI>下一篇　<A 
href="http://www.elephantbase.net/computer/eleeye_parallel.htm">中国象棋程序设计探索<FONT 
face="Times New Roman">(</FONT>六<FONT 
face="Times New Roman">)</FONT>：并行搜索技术探索</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>