?? 高級搜索方法——簡介(二).htm
字號:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0056)http://www.elephantbase.net/computer/advanced_intro2.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.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=Arial size=6><STRONG>Alpha-Beta</STRONG></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>
<DIV align=center>
<CENTER>
<DT> </CENTER></DT></DIV>
<DT><FONT size=3> 盡管我們已經討論過</FONT><FONT face="Times New Roman"
size=3>Alpha-Beta</FONT><FONT
size=3>搜索簡單有效，還是有很多方法試圖更有效地對博弈樹進行搜索。它們中的大部分思想就是，如果認為介于</FONT><FONT
face="Times New Roman" size=3>Alpha</FONT><FONT size=3>和</FONT><FONT
face="Times New Roman" size=3>Beta</FONT><FONT
size=3>間的評價是感興趣的，而其他評價都是不感興趣的，那么對不感興趣的評價作截斷會讓</FONT><FONT
face="Times New Roman" size=3>Alpha-Beta</FONT><FONT
size=3>更有效。如果我們把</FONT><FONT face="Times New Roman" size=3>Alpha</FONT><FONT
size=3>和</FONT><FONT face="Times New Roman" size=3>Beta</FONT><FONT
size=3>的間距縮小，那么感興趣的評價會更少，截斷會更多。</FONT>
<DT> 首先讓我們回顧一下原始的<FONT face="Times New Roman">Alpha-Beta</FONT>搜索，忽略散列表和“<A
href="http://www.elephantbase.net/computer/other_winning.htm"
target=_blank>用當前層數調整勝利值</A>”的細節。
<DT>
<DD>// 基本的Alpha-Beta搜索
<DD>int alphabeta(int depth, int alpha, int beta) {
<DD> move bestmove;
<DD> if (棋局結束 || depth <= 0) {
<DD> return eval();
<DD> }
<DD> for (每個合理著法 m) {
<DD> 執行著法 m;
<DD> score = -alphabeta(depth - 1, -beta, -alpha);
<DD> if (score >= alpha) {
<DD> alpha = score;
<DD> bestmove = m;
<DD> }
<DD> 撤消著法 m;
<DD> if (alpha >= beta) {
<DD> break;
<DD> }
<DD> }
<DD> return alpha;
<DD>}
<DT>
<DT><FONT face=楷體_GB2312 size=5><STRONG>超出邊界</STRONG></FONT><FONT face=Arial
size=5><STRONG>(Fail-Soft)</STRONG></FONT><FONT face=楷體_GB2312
size=5><STRONG>的</STRONG></FONT><FONT face=Arial
size=5><STRONG>Alpha-Beta</STRONG></FONT>
<DT>
<DT> 以上代碼總是返回<FONT face="Times New Roman">Alpha</FONT>、<FONT
face="Times New Roman">Beta</FONT>或在<FONT
face="Times New Roman">Alpha</FONT>和<FONT
face="Times New Roman">Beta</FONT>之間的數。換句話說，當某個值不感興趣時，從返回值無法得到任何信息。原因就是當前值被變量<FONT
face="Times New Roman">Alpha</FONT>所保存，它從感興趣的值的窗口下沿開始一直增長的，沒有可能返回比<FONT
face="Times New Roman">Alpha</FONT>更小的值。一個對<FONT
face="Times New Roman">Alpha-Beta</FONT>的簡單改進就是把當前評價和<FONT
face="Times New Roman">Alpha</FONT>分開保存。下面的偽代碼用常數“<FONT
face="Times New Roman">WIN</FONT>”表示最大評價，它可以在<FONT
face="Times New Roman">Alpha-Beta</FONT>搜索中返回任何評價。
<DT>
<DD>// 超出邊界的Alpha-Beta搜索
<DD>int alphabeta(int depth, int alpha, int beta) {
<DD> move bestmove;
<DD> int current = -WIN;
<DD> if (棋局結束 || depth <= 0) {
<DD> return eval();
<DD> }
<DD> for (每個可能的著法 m) {
<DD> 執行著法 m;
<DD> score = -alphabeta(depth - 1, -beta, -alpha);
<DD> 撤消著法 m;
<DD> if (score >= current) {
<DD> current = score;
<DD> bestmove = m;
<DD> if (score >= alpha) {
<DD> alpha = score;
<DD> }
<DD> if (score >= beta) {
<DD> break; // <FONT
color=#0000ff>【譯注：這里可以直接返回score、current或alpha，如果返回beta，則是不會高出邊界的Alpha-Beta搜索。】</FONT>
<DD> }
<DD> }
<DD> }
<DD> return current;
<DD>}
<DT>
<DT> 這樣改動以后，就可以知道比以前稍多一點的信息。如果返回值<FONT
face="Times New Roman"><EM>x</EM></FONT>等于或小于<FONT
face="Times New Roman">Alpha</FONT>，我們仍然不知道局面的確切值<FONT
face="Times New Roman">(</FONT>因為我們可能在搜索中裁剪了一些線路<FONT
face="Times New Roman">)</FONT>，但是我們知道確切值最多是<FONT
face="Times New Roman"><EM>x</EM></FONT>。類似地，如果<FONT
face="Times New Roman"><EM>x</EM></FONT>大于或等于<FONT
face="Times New Roman">Beta</FONT>，我們就知道搜索值至少是<FONT
face="Times New Roman"><EM>x</EM></FONT>。這些微小的上界和下界變化不會影響搜索本身，但是它們能導致散列表命中率的提高。超出邊界的<FONT
face="Times New Roman">Alpha-Beta</FONT>搜索對下面要介紹的<FONT
face="Times New Roman">MTD(<EM>f</EM>)</FONT>算法有重要作用。
<DT>
<DT><FONT face=楷體_GB2312 size=5><STRONG>期望搜索</STRONG></FONT>
<DT>
<DT> 這個方法不是代替<FONT
face="Times New Roman">Alpha-Beta</FONT>的，只是從外部改邊一個途徑來調用搜索過程。通常用<FONT
face="Times New Roman">Alpha-Beta</FONT>找最好路線時，可以調用：
<DD>
<DD>alphabeta(depth, -WIN, WIN)
<DT>
<DT> 這里 <FONT face=Symbol>-</FONT><FONT face="Times New Roman">WIN </FONT>和
<FONT face="Times New Roman">WIN
</FONT>之間的范圍很大，表明我們不知道搜索值是多少，因此任何可能的值都必須考慮。隨后，要走的那步保存在搜索函數外部的變量中。
<DT> 期望搜索的不同之處在于，我們可以人為地指定一個狹窄窗口<FONT
face="Times New Roman">(</FONT>用前一個搜索值為中心<FONT
face="Times New Roman">)</FONT>，對搜索通常是有幫助的。如果你搜索失敗，必須加寬窗口重新搜索：
<DT>
<DD>// 期望搜索
<DD>int alpha = previous - WINDOW;
<DD>int beta = previous + WINDOW;
<DD>for ( ; ; ) {
<DD> score = alphabeta(depth, alpha, beta);
<DD> if (score <= alpha) {
<DD> alpha = -WIN;
<DD> } else if (score >= beta) {
<DD> beta = WIN;
<DD> } else {
<DD> break;
<DD> }
<DD>}
<DT>
<DT> 權衡狹窄搜索所節約的時間，和因為失敗而重新搜索的時間，可以決定常數 <FONT face="Times New Roman">WINDOW
</FONT>的大小。在國際象棋中，典型的值也許是半個兵。期望搜索的變體有，搜索失敗時適當增加窗口寬度，或者用初始窗口而沒必要以前一次搜索結果為中心，等等。
<DT>
<DT><FONT face=Arial
size=5><STRONG>MTD(</STRONG><EM><STRONG>f</STRONG></EM><STRONG>)</STRONG></FONT>
<DT>
<DT> 這個技術跟期望搜索一樣，只是在調用<FONT
face="Times New Roman">Alpha-Beta</FONT>時對初始值進行調整。搜索窗口越窄搜索就越快，這個技術的思想就是讓搜索窗口盡可能的窄：始終用“<FONT
face="Times New Roman">beta = alpha + 1</FONT>”來調用<FONT
face="Times New Roman">Alpha-Beta</FONT>。用這樣一個“零寬度”搜索的作用是用<FONT
face="Times New Roman">Alpha</FONT>和確切值作比較：如果搜索的返回值最多是<FONT
face="Times New Roman">Alpha</FONT>，那么確切值本身最多是<FONT
face="Times New Roman">Alpha</FONT>，相反確切值大于<FONT
face="Times New Roman">Alpha</FONT>。
<DT> 我們可以用這個思想對確切值作二分搜索：
<DT>
<DD>int alpha = -WIN;
<DD>int beta = +WIN;
<DD>while (beta > alpha + 1) {
<DD> int test = (alpha + beta) / 2;
<DD> if (alphabeta(depth, test, test + 1) <= test) {
<DD> beta = test;
<DD> } else {
<DD> alpha = test + 1;
<DD> }
<DD>}
<DT>
<DT> 但是，這樣會導致大規模的搜索<FONT face="Times New Roman">(</FONT>即 <FONT
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -