?? 其他策略——主要變例的獲取.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->cmove = 0;</FONT>
<DD> return Evaluate();
<DD> }
<DD> GenerateLegalMoves();
<DD> while (MovesLeft()) {
<DD> MakeNextMove();
<DD> val = -AlphaBeta(depth - 1, -beta, -alpha<FONT color=#ff0000>,
&line</FONT>);
<DD> UnmakeMove();
<DD> if (val >= beta) {
<DD> return beta;
<DD> }
<DD> if (val > alpha) {
<DD> alpha = val;
<DD><FONT color=#ff0000> pline->argmove[0] = ThisMove();</FONT>
<DD><FONT color=#ff0000> memcpy(pline->argmove + 1, line.argmove,
line.cmove * sizeof(MOVE));</FONT>
<DD><FONT color=#ff0000> pline->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, &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 + -