《對弈程序基本技術》專題
 
什么樣的結點需要搜索?全部還是選擇性的?
 
David Eppstein */
* 加州愛爾文大學(UC Irvine)信息與計算機科學系
 
  Alpha-Beta告訴我們怎樣搜索,但是我們仍然需要知道,何時需要展開結點(搜索它的子結點),以及何時停下來從而調用評價函數。
 
水平線效應
 
  在前面我給你們看的偽代碼中,每一步棋都搜索到一個固定的深度,這個深度被稱為“水平線”(Horizon)。對于看到水平線以內會發生的威脅,這個方法非常有效,但是它顯然不能檢查到水平線以后的威脅。例如在8層的搜索中(即搜索4個回合),就可能得不到在5步內有殺棋的任何信息。它不知道的事情,就無法作出防御,而且只是簡單地忽略那些遙遠的威脅。然而當局勢面臨中等深度的威脅而丟子不可避免時,固定深度的搜索有時會走出更糟的棋,因為某些丟子會在搜索水平線以內,而有些卻不在。在這種情況下,程序會走出糟糕的并且無意義的棋,試圖來延緩丟子的發生,使得它出現在程序看不到的未來。這種現象稱為“水平線效應”(Horizon Effect)
  這里有個例子。在下面的局勢中,黑象被白兵包圍,不管黑的怎么走,象總是會在幾步內被吃掉;例如白車可以沿著h2-h1-a1-a2吃掉象。這是一個8層深的變化,那么假設黑方的程序也搜索8層。可能當前局面對黑方來說,最好的走法就是用象換兵,即象吃掉兵,兵吃掉象。在后面的殘局里,黑方的三個連兵足以戰勝或守和白車。【譯注:其實守和的希望也不大,譯者認為黑方還是會輸掉的,因為白王的位置非常好,可以獨擋三黑兵,使得白車有時間拔掉b線的黑兵。】但是程序搜索8層,很有可能會挺黑兵將軍白王。白必須應對(例如自己來吃掉兵),這個應對使得丟象被暫時避免,拖延到程序看不到的步數內,并且程序認為象是安全的。實際上在這個局面里,固定深度的程序可能會連續地送吃兵,把象被吃的結果延緩幾步,但是最終可能輸掉整盤棋。
 
 
  對付水平線效應的一個方法,就是在你的程序里增加一些知識:如果從評價中知道象被包圍,那么搜索程序就不會通過棄兵來延緩丟象。另一個方法是讓搜索更快更深:你的程序搜索的層數越多,因超過水平線而延緩丟象的做法,發生的可能性就越小。但是對于普通局面來說,最有效的做法就是讓搜索深度更靈活,使得程序在丟兵的路線上搜索得更深,而在其它路線上不必要搜索得很深。
 
蠻力和選擇性
 
  在Shannon【申朗,參閱譯文《電腦國際象棋簡史》】最早關于電腦國際象棋的文章中,提到程序調整搜索深度的兩種策略。
  最明顯的就是我給你們看的偽代碼:全部范圍,固定深度的蠻力搜索。只要把“深度”這個參數輸入到你的程序中,每搜索一層就減一,到達零時停下來。這樣做的好處在于,只要在搜索水平線以內,一些甚至很怪異的線路也看得到。但是高的分枝因子就意味著任何線路都不可能很深(即學士程度,對任何事物都只知道個皮毛【原文是“Bachelor's degree: knows nothing about everything”】)。更遭的是,程序可能會栽倒在水平線效應下。
  Shannon提到的另外一個方法就是選擇性裁剪:不是搜索固定的深度,而是通過搜索每個結點的部分著法來減少分枝因子(避免那些“明顯是壞棋”的著法)。因此這樣可以搜索得很深,但是有些線路完全看不見(即博士程度,只對某個狹窄方面的懂得很多【原文是“Ph.D.: knows everything about nothing”,源于一句用來諷刺博士的笑話:“A PhD knows more and more about less and less until he knows everything about nothing”】)Shannon認為這個思想非常好,因為它更接近人類的思考方式。Turing【圖靈,參閱譯文《電腦國際象棋簡史》】的思想有所不同,只搜索吃子的著法。更典型的做法是,對所有的子結點作評價,而只對最好的k個作展開,這里k是小于實際分枝因子的一個參數。
  不幸的是,“明顯是壞棋”的著法往往根本不壞,而是取得勝利的精彩棄子。如果你沒有找到你應該走的那步著法,你就必須更努力地去找其他可以獲勝的方法。更糟的是,對手可能會在后面幾步作出有力的反擊,如果你沒有看出來,那么你會掉入陷阱從而輸掉棋局。
  如今沒有哪個思想會被單純地使用的。我們把兩者結合起來:選擇性地延伸。每條路線都搜索固定的深度,但是某些路線要搜索得比水平線深。有時我們也會做裁剪(不是像Alpha-Beta那樣的安全裁剪),這通常也是非常保守的,因為只挑出好的著法實在太困難了,但是有時對于確實很壞的著法,我們可以挑出并且忽略它們。除了國際象棋以外,有些棋類有更高的分枝因子,這就有必要使用更冒進的裁剪技術了。【例如五子棋,每個局面都有100種以上的合理著法,但是我們只會挑有意義的著法,要么有進攻作用(己方棋子周圍的一些著點),要么有防守作用(敵方棋子鄰近的著點),除此以外一概不予考慮。】
 
什么時候需要延伸?
 
  延伸的目標是什么呢?是獲得更好(更準確)的評價。所以下面的結點必須延伸:
  (1) 目前的評價可能不準確時;
  (2) 目前的著棋路線在整個博弈搜索樹中是非常重要的;
  或者以上兩個情況的組合。
 
靜態搜索
 
  在國際象棋或其他棋類中,有吃子和不吃子的著法(西洋跳棋、圍棋、Fanorano),如果有吃子的情況,那么每次吃子時評價都會改變。
  “靜態搜索”(Quiescence Search)的思想是,到達主搜索的水平線后,用一個圖靈型的搜索只展開吃子(有時是吃子加將軍)的著法。其他棋類不同于國際象棋,可能只包括一些會很大程度上改變評價的著法。靜態搜索還必須包括放棄的著法,來決定停止吃子。因此,主Alpha-Beta搜索中每個調用評價函數的地方,都會被一個類似Alpha-Beta的但只搜索吃子著法的函數代替,如果當前結點的評價函數足以高出邊界,那么就讓搜索停下來。代碼如下:
 
// 靜態搜索
// 主Alpha-Beta搜索中,原來出現“eval()”的地方現在調用這個函數
quiesce(int alpha, int beta) {
 int score = eval();
 if (score >= beta) {
  return score;
 }
 for (每個吃子著法 m) {
  執行著法 m;
  score = -quiesce(-beta,-alpha);
  撤消著法 m;
  if (score >= alpha) {
   alpha = score;
   if (score >= beta) {
    break;
   }
  }
 }
 return score;
}
 
  有人還把將軍加入到靜態搜索中,但是你要當心,由于沒有深度參數,靜態搜索會有巨大的結點數。吃子通常是有限的(在棋子全部吃完以前你只能有16次子),而將軍可以一直進行下去并導致無限制遞歸。【對于是否展開將軍著法的問題,可以嘗試一種做法,如果局面被將軍,就展開全部著法,即做應將處理,而不對當前局面作評價,參閱“靜態搜索”一文。】
 
選擇性延伸
 
  如果局面在前面的路線中非常活躍,那么這就證明后面會有進一步的手段,或者前面的著法使得這些手段推遲了,從而在很深的地方會有好的局面。因此如果搜索到一個“感興趣”的著法例如吃子或將軍,就要增加搜索深度。在Alpha-Beta的偽代碼中,調用搜索過程時參數“depth - 1”可以用“depth - 1 + extension”來代替。你必須小心不要經常做這些事,否則最終會把搜索樹延伸得特別龐大(甚至可能無限大)
  有一個技巧可以使這樣的延伸終止,即延伸一個分數的層數。比較好的做法是,“深度”參數記錄的是你想要搜索的層數乘上一個因子,比如說“深度 = 層數 x 24”。在遞歸調用Alpha-Beta搜索的時候,就傳遞參數“Depth - 24 + Extension”。如果延伸值總是小于24,那么這個方法能保證終止,這個方法還可以有選擇地多延伸些或少延伸些。
  在評價函數里加上“局面如何難以評價”這個知識,也是有用的,這樣就可以在局面太難評價的時候延伸搜索。我的程序就做到了這點,程序對當前結點調用評價函數。如果局面十分復雜,而且深度接近零,那么評價會返回一個特殊的值【表示評價失敗,這個值不能在“-Infinity”和“Infinity”之間,否則會和正常值混淆】,通知搜索繼續進行下去。如果深度達到一個負得很大的數【原作者的意思是評價連續失敗導致延很長】,那么評價函數總是成功的,這樣搜索將會終止。
 
如何把準確性和重要性結合起來?
 
  到目前為止,我們都在討論并試圖找到評價局面可能不準確的原因。但是對于搜索樹的一些不重要的部分,或許我們不在乎它不準確,而我們真正關心的是主要變例上的結點。我們如何來關注選擇性延伸的重要性呢?
  (1) Alpha-Beta搜索時,不要只根據準確性作延伸,而忽視了重要性;
  (2) 對主要變例部分(或附近)的線路作延伸,例如單步延伸(Singular Extension),深藍(Deep Blue)及其前身就用這個方法,如果一個局面的某個著法遠比其他著法好,就延伸這個著法。
  (3) 把視線從Alpha-Beta上移開。有一個稱為“對策數搜索”(Conspiracy Number Search)的策略,即某些局面會使得能應對的好的著法很少【根據原文,譯者也無法了解這個策略的確切含義】,這些局面要搜索得深一些。
  【選擇性延伸通常運用在強制著法上,強制著法的界定在各個程序中有所不同,但主要有以下幾種判斷方法:
  (1) 將軍:此時必須應將,顯然屬于強制著法;
  (2) 單一應著:走子的一方只有一種合理著法時,顯然屬于強制著法;
  (3) 殺棋威脅:當一方不走子時就會被對方在幾步內殺掉,那么解除殺棋威脅也屬于強制著法,這種判斷比較困難,通常利用下面所介紹的“空著搜索”來做判斷。
  (4) 吃回被吃棋子:這很有可能是兌子過程,因此大多數情況下為強制著法;
  (5) 通路兵挺進:在王兵殘局中,最簡單的處理就是搜索到兵升變時的局面,從而繞開正方型法則、關鍵格理論等知識,這就需要對通路兵的挺進作延伸。(如果兵挺5格才能到達升變格,那么原來搜索8層還看不到升變,作了延伸以后搜索5層就能看到了,因為在連續挺兵的這條線路上已經延伸到了10層。)
  大多數程序都結合以上若干種判斷,以決定是否進行延伸。】
 
空著搜索
 
  這個思想符合本文的整個主題,即在適當時機調整搜索層數,但是它是通過相反的方式來表現的。這個思想不是在復雜的局面上延伸,而是在簡單的局面上減少搜索。
  這個思想是建立在國際象棋知識的基礎上的:有害的著子是非常罕見的(除了殘局以外)。通常如果輪到你走,你一定能讓局面更好些。所有可能的著法都使局面變得更糟,這樣的局面稱為“無等著”(Zugzwang)(德語,意思為強迫著子),通常只發生在殘局中。像其他棋類,例如五子棋,無等著根本不會發生。因此,如果你改變國際象棋的規則,允許有“棄權”的著法,那么棄權通常是錯誤的,它不會使棋局有進展。
  因此,假設你搜索一個希望高出邊界的結點(Alpha-Beta搜索的返回值至少是Beta),空著搜索就是先搜索“棄權”著法【即“空著”(Null-Move),即使它通常不是最好的。如果棄權著法高出邊界,那么真正最好的著法也可能高出邊界,你就可以直接返回Beta而不要再去搜索了。要把搜索做得更快,棄權著法搜索的深度通常比常規著法淺。
  你必須小心,這種啟發會改變搜索結果,也可能使你忽略棋局中的一些重要的線路。不要連續兩次用空著(因為這樣你的搜索會退化,結果只返回評價函數),而且要小心,只能在不會出現無等著的情況下使用。在國際象棋中,這就意味著當局面還有很多子的時候才能使用。
 
// 帶空著啟發的Alpha-Beta搜索
alphabeta(int depth, int alpha, int beta) {
 if (贏棋 || depth <= 0) {
  return score;
 }
 放棄著子;
 if (上一步不是空著 && 局面不是無等著局面 &&
   alphabeta(depth - 3, beta, beta + 1) >= beta) {
  // 【深度參數如果是 depth - 1,那就是純粹的“啟發”算法,而現在搜索淺了(depth - 3),因此稱為“空著裁剪”更為恰當。】
  return beta;
 }
 /* 【“放棄著子”蘊涵著交換著子方的操作,空著啟發做完后還必須交換回來。這樣,上面用醒目顏色標出的代碼(是由譯者標出的)就存在一些問題,應該改為:
 
 if (上一步不是空著 && 局面不是無等著局面) {
  放棄著子;
  int val = alphabeta(depth - 3, beta, beta + 1);
  撤消放棄著子; // 如果只作簡單處理,放棄著子和撤消放棄著子都只交換著子方。
  if (val >= beta) {
   return beta;
  }
 }
*/
 for (每個可能的著法 m) {
  執行著法 m;
  alpha = max(alpha, -alphabeta(depth - 1, -beta, -alpha);
  撤消著法 m;
  if (alpha >= beta) {
   break;
  }
 }
 return alpha;
}
 
  原文:http://www.ics.uci.edu/~eppstein/180a/990204.html
  譯者:象棋百科全書網 ([email protected])
  類型:全譯加譯注
  • 上一篇 基本搜索方法——置換表
  • 下一篇 高級搜索方法——簡介()
  • 返 回 象棋百科全書——電腦象棋
  • www.ejnwjd.tw
    快乐双彩今晚开奖结果