《對弈程序基本技術》專題
 
空著向前裁剪
 
Bruce Moreland /
 
沒有副作用即可獲得額外的速度
 
  空著向前裁剪(Null-Move Forward Pruning),運用可能忽視重要路線的冒險策略,使得國際象棋的分枝因子銳減,它導致搜索深度的顯著提高,因為大多數情況下它明顯降低了搜索的數量。它的工作原理是裁剪大量無用著法而只保留好的。
  這個技術在很多刊物上報道過,但是使得大家都來關注空著的,則是由Chrilly Donniger發表在19939月的ICCA雜志上的一篇文章。
  試想國際象棋搜索樹中的某個局面,你的程序將以D層搜索這個局面的每個著法。如果其中任何一個著法的分數超過Beta,你就會馬上返回Beta。如果任何一個超過Alpha,但是沒有超過Beta,你就要記住著法和分值,因為這有可能是主要變例的一部分。如果它們全部小于或等于Alpha,你就要返回Alpha
  空著向前裁剪是你搜索任何著法之前要做的事。你要問一個問題:“如果我在這里什么都不做,對手能做什么?”
  記得在剛才,你沒有問這個問題。你只是去找最佳的著法去打擊對手。問對手是否會打擊你,這個問題卻有所不同。
  但是事實證明很多情況下對手無法打擊你。比如說你送了一個車,而其他棋子都沒有作用,在這種情況下,對手隨便走哪步你都吃虧,因為你丟了一個車。空著向前裁剪的要點,就是簡單地去掉那些沒用的著法,而不要在這上面多花時間。
  這就好比像打架時,根據自己的能力給對手一個出擊的機會,來增加自己的信心。如果任憑對手攻擊也無法擊倒你,那么你攻擊他的時候他會輸掉。
  我們不討論這個策略了,現在來談它是如何運用在電腦國際象棋中的。在你搜索著法以前(事實上在你生成著法以前),你做一個減少深度的搜索,讓對手先走,如果這個搜索的結果大于或等于Beta,那么你簡單地返回Beta而不需要搜索任何著法。
  這個思想就給了對手出擊的機會,如果你的局面仍然好到超過Beta的程度,你就假設如果你搜索了所有的著法也會超過Beta
  這個方法能節省時間的原因是,開始時用了減少深度的搜索。深度減少因子稱為R,因此跟你用深度D搜索所有的著法相比,現在你是先以D - R搜索對手的著法。一個比較好R2,如果你要對所有的著法搜索6層,你最終只對對手所有的著法搜索了4層。【譯注:因為放棄著法后層數應該減1,所以實際在對手上面搜索的層數是D - 1 - R。】
  這就使得很多時間節約下來了,實踐證明可以使搜索增加一到兩層。效果真的非常可觀!
  代碼如下,醒目的文字是在Alpha-Beta搜索的基礎上增加的部分:
 
#define R 2
int AlphaBeta(int depth, int alpha, int beta) {
 if (depth == 0) {
  return Evaluate();
 }
 MakeNullMove();
 val = -AlphaBeta(depth - 1 - R, -beta, -beta + 1);
 UnmakeNullMove();
 if (val >= beta) {
  return beta;
 }
 GenerateLegalMoves();
 while (MovesLeft()) {
  MakeNextMove();
  val = -AlphaBeta(depth - 1, -beta, -alpha);
  UnmakeMove();
  if (val >= beta) { // 把這部分去掉,就用純粹的最小-最大代替了Alpha-Beta。
   return beta;
  }
  if (val > alpha) {
   alpha = val;
  }
 }
 return alpha;
}
 
  在這個代碼中我用了一個訣竅。我需要知道空著搜索的值是否是Beta或更好,如果還不如Beta,我不關心它到底比Beta有多糟,因此我用了極小窗口,試圖讓裁剪做得更快。實際上我用(Beta - 1, Beta)調用了搜索,但是由于遞歸時必須把AlphaBeta顛倒并取負數,這就變成源代碼中的樣子了。
  不用說,這個代碼在一方被將軍時不能發揮作用(因為對手立刻把王吃掉了)。什么地方允許調用空著向前裁剪,必須掌握好分寸,因為如果你允許一次連續地這么做,那么搜索將退化成什么都不做了。一個很簡單的嘗試,就是當中沒有間隔一個實在著法的時候,不要讓兩個空著搜索連在一起。另一個思想是在一個實在著法之前,允許連續兩個空著裁剪。實踐證明這兩個方法都做得很好。
 
嗯,還是有副作用的
 
  不幸的是,空著向前裁剪在某些地方不能正常運行。我們作了一個重要的假定——假定走了一步棋會比不走棋有更高的分值。不幸的是,這個假定在很多典型的局面上并不成立,這些局面非常普遍,并且有一個名稱——無等著局面(Zugzwang)。無等著局面指的是,如果你不走棋,局勢會好些,但是你被強迫走子,這使得你的局勢會崩潰。下面是個典型的例子:
 
 
  在這個局面里,如果白方被迫走子,他走 Kb2,而黑走 Kd2 助兵變后。如果白方不走棋,那么黑的走 Kc3,局面就是和棋。(事實上這是一個互相的無等著局面,因為雙方都被先走棋所困擾,這個問題不在我們的討論范圍內。)
  如果到達這個局面,而且試圖用空著向前裁剪,那么可能會認為黑方沒有威脅白方,因為現在黑方確實沒威脅白方。而現在黑方在等待白方毀掉局勢,這就完全不同了。
  由于這個原因,空著向前裁剪不能在殘局中使用,或者至少不能直接地使用。如果你試圖在殘局中用,則會出現很糟糕的事情。
  有一個更困擾人的例子,是這樣的:
 
 
  這個局面選自GoetschCampbell的《空著啟發的試驗》(Experiments with the Null-Move Heuristic)一文,發表在《電腦、象棋與認知》(Computers, Chess and Cognition)(ISBN 0-387-97415-6)一書中。
  這個局面輪到白方走,白的下一步就被將死了,而且無能為力。對這個局面做兩層的搜索,毫無疑問:1. <任何著法> Qg2#
  如果你在這里試圖用空著向前裁剪,那么不幸發生了。我們原來打算做兩層的完全搜索,現在要做的是對對方做零層搜索,并試圖找到威脅。在零層搜索中,黑方不走子,所以調用“評價”函數,由于白方領先一個車而返回 +5 左右。這或許會大于Beta,因此搜索返回Beta
  這是我們不希望發生的!搜索應該返回一個很小的值,表示白方被殺。
  我們這里看到的是一種水平線效應,經常發生在啟用空著向前裁剪的時候。沒有空著向前裁剪時,白方走了一步沒用的著法,然后有足夠的搜索深度(在這個例子中只需要一層)讓黑殺掉白。用了空著向前裁剪并且用一個足夠高的R(例如R = 2),白方不做任何事情,但是黑方也沒有足夠深度來看到勝利了。
  這個例子或許讓你感到奇怪,或許它只會在很淺的搜索中才發生,但是有很多例子在足夠的搜索深度下仍然會發生這樣的事,即用正常的搜索可以看到的棋,用了空著向前裁剪后就被忽視了。實際上,這個黑后在h3格并且黑兵在f3格的棋型,對于國際象棋程序來說都是很危險的。【原作者的意思是,如果程序遇到這種棋型,應該考慮適當延伸搜索深度,或者用更小的R值做空著裁剪。】
  空著向前裁剪的另一個問題在于它會導致“搜索的不穩定性”。空著搜索的成功與否取決于Beta的值。這個結點下次訪問時,Beta可能不同,因此搜索會有不同的值,這是很不合理的。你可能在傳遞窗口(7, 30)時搜索高出邊界,但是傳遞(7, 50)時,卻低出邊界。
  在實戰中,比起遇到偶然的對策錯誤,以及搜索不穩定性的增加來說,搜索速度的加快重要得多。
 
一些思想
 
  嘗試調整一個不同于2R值,這是非常有趣的事。你可以試試134或更大的數,或者根據搜索深度、棋盤上的子力等等因素改變。我從來沒有得到比直接用R = 2更好的結果,但是一些研究表明其他值或許會更好,而且有些人至少在搜索樹的部分結點上用R = 3的。
  通過一些驗證式的搜索,我們也可以試圖找到殘局中使用空著向前裁剪的方法。如果你的空著搜索高出邊界,你就減少深度來做常規搜索,看它是否也高出邊界。我覺得這看上去有些破費,但是還是值得嘗試的。
  還有其他的改進方法值得嘗試,但是我不想把它們一一列舉出來。你可以去看Donninger的文章,看《電腦、象棋與認知》(Computers, Chess and Cognition)的文章,或者看Ernst Heinz的跟空著向前裁剪有關的文章。
  【譯者有必要在這里介紹一下這兩個思想:
 
  (1) 根據不同情況來調整R值的做法,稱為“適應性空著裁剪”(Adaptive Null-Move Pruning),它首先由Ernst Heinz發表在1999年的ICCA雜志上。其內容可以概括為:
  a. 深度小于或等于6時,用R = 2的空著裁剪進行搜索;
  b. 深度大于8時,用R = 3
  c. 深度是67時,如果每方棋子都大于或等于3(譯者沒注意到是否包括王),則用 R = 3,否則用 R = 2
  參閱:Heinz EA: Adaptive Null-Move Pruning, ICCA J. 22 (3): 123-132, 1999
 
  (2) 驗證空著裁剪是否安全的做法,稱為“帶驗證的空著裁剪”(Verified Null-Move Pruning),它首先由Tabibi發表在2002年的ICGA(ICCA)雜志上。其內容可以概括為:
  a. R = 3的空著裁剪進行搜索;
  b. 如果高出邊界,那么做淺一層的搜索(這就意味著一層的搜索是無法做帶驗證的空著裁剪的)
  c. 做淺一層的搜索時,子結點用R = 3的不帶驗證的空著裁剪;
  d. 如果淺一層的搜索高出邊界,那么帶驗證的空著裁剪是成功的,否則必須重新做完全的搜索。
  參閱:Tabibi OD, Netanyahu NS: Verified Null-Move Pruning, ICGA J. 25 (3): 153-161, 2002
 
  原文:http://www.seanet.com/~brucemo/topics/nullmove.htm
  譯者:象棋百科全書網 ([email protected])
  類型:全譯加譯注
  • 上一篇 高級搜索方法——靜態搜索
  • 下一篇 高級搜索方法——期望窗口
  • 返 回 象棋百科全書——電腦象棋
  • www.ejnwjd.tw
    快乐双彩今晚开奖结果