國際象棋程序設計(三):著法的產生
 
François Dominic Laramée/
 
  上個月,我完成了連載的第二部分,介紹了在著法產生的預處理中涉及的數據結構。現在我們把話題回到著法產生,詳細介紹兩種著法產生的策略,并解釋一下在特定的情況下如何在這兩個策略中作出選擇。
 
困境
 
  不管你怎么對付象棋,它就是一個復雜的游戲,對于電腦來說就更是如此了。
  在通常局面下,棋手要在30多種著法中選擇,有些是好的,有些則是自殺棋。對于受過訓練的人來說,他能判斷出大多數愚蠢和沒有目的著法,甚至初學者都知道,后處于被吃的位置時該怎么逃跑。專家(多數是通過直覺而非推理)則知道哪幾步棋會比較有力。
  但是,把這些信息(特別是無意識的那些)編寫到計算機里去,被證明是極端困難的,連那些最強的象棋程序(除了個別程序以外,例如Hans BerlinerHitech和它的姊妹程序)都已經放棄這條路線了,取而代之的是“蠻力”——如果你能以足夠快的速度分析所有的著法,并且足夠深遠地預測他們的結果,無論你是否有一個清晰的思路,你最終會走出一步好棋。所以,著法的產生和搜索必須越快越好,以減小蠻力方法的花費。
  搜索技術將在連載的第四和第五部分介紹。這個月,我們會關注著法產生。歷史上有以下三條主要的策略:
 
  1. 選擇生成:檢測棋盤,找到一部分可能的著法,把其他的全不要;
  2. 漸進生成:產生一些著法,希望沿著某個著法下去,可以證明這條路線好到(或壞到)足以中止搜索的程度(而不必再去找其他的著法)【譯注:即后面要提到的“截斷”】
  3. 完全生成:產生所有的著法,希望置換表(在第二部分曾討論過)會包含有關的信息,從而沒有必要對這些著法進行搜索。
 
  選擇生成(由之衍生出的搜索技術稱為“朝前裁剪”(Forward Pruning)),上世紀70年代中期以前,幾乎所有的程序都這么做的,但是從那以后就突然消失了。另外兩個方法代表了一枚硬幣的兩面——著法產生和搜索之間的權衡。對于那些著法產生簡單并且有很多路線可以到達相同局面的游戲(或者具備其中一個特征),例如黑白棋(Othello)和五子棋(GoMoku),完全生成效率會更高些,而當著法產生的規則復雜的時候,漸進生成的速度會更快。不過兩種策略都是很好的策略。
  【這里就黑白棋發揮幾句。可能原作者認為,凡是只由黑白兩子構成的游戲就一定具有這兩個特征了,就像圍棋和五子棋。但是我曾經做過黑白棋的程序并發現兩個特點,一是著法產生并不像想象中的那么容易,它有點類似于中國象棋中的炮的著法,二是殊途同歸的局面比起國際象棋來說少得多,原因就在于走一步棋最多會改變18個格子的顏色,這與原作者的觀點大相徑庭。】
 
早期的策略:朝前裁剪
 
  在1949(確實如此)Claude Shannon提出了兩個象棋程序的算法:
 
  1. 著眼于對于所有的著法及其應對著法,循環下去;
  2. 只檢查“最好”的著法,這個著法由對局面的分析來確定,然后也只選擇“最好”的應對著法,循環下去。
 
  起初,第二種選擇看上去成功的可能更大。畢竟人就是這么做的,從邏輯上說在每個結點上只考察某些著法,總比考慮所有的著法要快。不幸的是,這條理論被事實推翻了,用選擇搜索的程序,棋下得并不怎么樣。它們最好的也只能達到中等俱樂部棋手的水平,最壞的情況下還會犯低級錯誤。打敗世界冠軍(現實一點,水平發揮得穩定一些)是遙不可及的。
  在上世紀70年代中期,著名的美國西北大學SlateAtkin的小組決定放棄復雜的“最佳著法”生成辦法,后來證明,他們繞過復雜分析所省下來的時間,足以進行全面的搜索(檢查所有的著法)。無論怎么說,這項改革善意地把“朝前裁剪”埋葬了。
  下面介紹一下鮑特維尼克的工作。
  上世紀70年代到80年代早期,在前世界冠軍鮑特維尼克(Mikhail Botvinnik)的領導下,蘇聯發展了一個特別的朝前裁剪的例子。鮑特維尼克認為,計算機要達到特級大師級水平,唯一的途徑就是像特級大師一樣,即只考慮少量著法,但是要足夠深遠足夠細致。他的程序試圖判定世界級選手才能掌握的局面,還要實現很高水平的作戰計劃。盡管這個過程中誕生了一些吸引人的著作,揭示了只有鮑特維尼克本人才具備的特級大師級思路,但是這項工作最終沒有達到預期的目標。
 
產生全部著法
 
  自從朝前裁剪被淘汰以后,最直接的實現完全搜索的方法是:
 
  1. 找到局面中所有合理的著法;
  2. 對他們進行排列,想要提高搜索速度就必須選擇最佳的順序;
  3. 對他們逐一進行搜索,直到全部搜索完成或者被截斷【運用Alpha-Beta等搜索方法,可以在特定的情況提前中止搜索,以后的搜索就沒有必要,這種情況就稱為“截斷”(Cut-off),連載的第四部分會介紹這類搜索方法】
 
  早期的程序(例如Sargon)每次都掃描棋盤的每個格子,找有沒有可以移動的棋子,然后計算可能的著法。當時存儲器是稀有礦產,額外花費CPU的時間每次把著法重新計算一遍,是別無選擇的蠢事。
  如今,預處理的數據結構(就像我上個月描述的那個)可以避免大量計算,而復雜的代碼會多花費幾十KB的空間。當這個超快的著法產生方法和置換表結合在一起的時候,程序員眼前又多了一條思路——如果某些著法已經被搜索過,它的價值(保存在置換表中)足以產生截斷,那么根本就不需要搜索任何著法了。很明顯,置換表越大,并且置換可能越多(它由游戲規則決定),置換表的作用就越明顯。
  這個技術不僅在概念上簡單,而且普遍適用于其他游戲(但著法卻不是普遍適用的,象棋著法可以分為吃子和不吃子,其他游戲像黑白棋就不那么容易分類了)。因此,如果試圖讓你的程序不止能玩一種游戲,你應該盡可能地用這個技術來代替下面要介紹的一個技術。
 
一次只產生一步棋
 
  老牌的象棋程序(至少是CHESS 4.5以前的)則采取了相反的策略——一次產生少量著法,然后搜索,如果產生截斷,就不需要產生剩下的著法了。
  這種方法的流行是因為下列因素結合在一起了:
 
  1. 搜索是不需要太大的存儲器的。上世紀70年代以前的程序只能處理很小的置換表,也沒有預處理的數據結構,這些都限制了完全搜索方案(就是上一節提到的方案)的運用。
  2. 在象棋著法產生的預處理比其他游戲復雜得多,有上王車易位、吃過路兵,不同的棋子要區別對待。
  3. 通常,這個方案的說服力(就是某步棋可以產生截斷的例子)在于吃子。例如,某棋手送吃他的后,對手就會毫不猶豫地吃掉它,棋局也因此結束了。因為一個局面中能吃子的著法不多,而且產生吃子著法相對要容易一些,所以計算吃子的著法有很多產生截斷的機會。
  4. 吃子是靜態搜索(Quiescence Search,這個將在后面幾部分提到)中需要檢查的著法(不是唯一一類著法【可能除了吃子以外就是將軍了】),所以單獨產生吃子的著法是非常有效的。
 
  所以,很多程序都是先產生吃子的著法的,而且從吃最有價值的子開始,來找到最快的截斷。有些技術是專門提高吃子著法的產生速度的,多數運用了位棋盤的技術:
  CHESS 4.5 用了兩個組64個的位棋盤,棋盤上的每一格對應一個位棋盤。一組由 “這個格子上的子可以攻擊的格子”的位棋盤組成,另一組正好相反,由“可以攻擊這個格子的棋子所占的格子”的位棋盤組成。所以,如果程序去找吃黑后的著法,它先從基本位棋盤的數據庫中找到黑后的位置,然后用這兩組位棋盤來確定【其實只要用后一組就可以了】攻擊后的棋子的位置,并且只產生這些子的著法。
  每走一步都需要維護這些位棋盤,這就需要引進很多技術,有一個稱為“旋轉的位棋盤”(Rotated Bitboard)的作用最顯著。對于第一組位棋盤的產生辦法,我見過的最好的論述是由James F. Swafford寫的,這篇文章是在網上找到的,網址是:http://sr5.xoom.com/_XMCM/jswaff/chessprg/rotated.htm
  【可以參閱我從Allan Liu那里整理的譯文《對弈程序基本技術》專題之《數據結構() ——旋轉的位棋盤》,現在Swafford教授的那個網站關了(這至少是5年以前的網站了),但事實證明,他的那套方案并不那么有效,有誤導之嫌。】
 
對著法排序以加快搜索速度
 
  我們下次要提到,搜索效率取決于搜索著法的順序。著法排列的好壞直接影響到效率 好的排列方法可以產生很多的截斷,大大減小搜索樹的大小減小,其結點數只有用最壞的排列的搜索樹的平方根那么多。
  不幸的是,可以證明,最好的順序應該從最佳著法開始。當然,如果你知道哪個著法是最佳的,你還有必要做搜索嗎?不過仍舊有一些“猜”的方法能確定可能比較好的著法。例如,你可以從吃子、兵的升變(它會大幅度改變子力平衡),或者是將軍著法開始(它的應對著法很少)。緊接著是前面搜索過的在搜索樹的同一層【肯定是在搜索樹的不同分枝上】上產生截斷的著法(即所謂的“殺手著法”),然后是剩下的。這就是迭代加深(Iterative Deeping)Alpha-Beta搜索(下個月會詳細討論的)和歷史表(上次討論過了)的原理。要注意的是,這些技巧區別于朝前裁減——所有的著法最終是被檢測的,那些壞的著法只是排在后邊,而不排除在考慮范圍以外。
  最后要注意的是,在象棋中,有些著法因為被將軍而是非法的。但是這些狀況畢竟是罕見情況,可以證明判斷著法的合理性需要花費很多運算量。更有效的辦法是所有的著法都搜索完了再來作檢查,例如某步棋走完后有個吃王的應對著法,這時才來裁定這步棋為非法,搜索就此中止。很明顯,如果搜索到這步棋以前,就產生截斷了,那就不會對這步棋的合法性作出判斷了【這部分的時間不就省下來了嗎】
  【這里就本節提到的“殺手”著法作一些發揮:大多數程序往往不是生成全部著法的,而是先判斷殺手著法的合理性(判斷著法合理性所做花的時間要比產生全部著法少得多),如果是合理著法就先搜索這些著法。因為殺手著法是產生截斷幾率很高的著法,所以很有可能不需要生成著法了。
  另外,排序技術也非常有講究,因為排序所花的時間可能會比著法產生的時間更多。排序的算法很多,常用的有冒泡排序、Shell排序、快速排序等,我個人傾向于最慢的冒泡排序,原因是冒泡排序每掃描一趟會產生一個最大值,希望它能產生截斷而沒有必要對后面的著法再進行排序。】
 
我的選擇
 
  在我的象棋程序里,我選擇產生所有的著法,只是因為以下幾個原因:
  1. 我想讓這個程序作為其他游戲的基礎,這些游戲沒有像象棋一樣的吃子著法;
  2. 我有足夠的存儲器來運行這個游戲;
  3. 這個技術需要的代碼寫起來比較容易,也比較看得懂;
  4. 已經有很多免費的程序,可以實現只產生吃子的著法,有興趣的讀者可以去看Crafty的源程序,還有James SwaffordGalahad
 
  我的程序的整個表現似乎比別人的稍差了些【我想可能就是受了James Swafford的誤導吧】,我的程序(是用Java寫的,沒有用別的)不想和深藍去比,所以我感覺這并不算太壞。
 
下一個月
 
  現在我們準備探索象棋程序的核心部分——搜索技術了。這是一個很大的專題,需要兩篇文章。我們從所有游戲最基本的搜索算法開始說起,然后才是最新發展起來的專門針對象棋的優化方法。
 
  François Dominic Laramée20007
 
  原文:http://www.gamedev.net/reference/programming/features/chess3/
  譯者:象棋百科全書網 ([email protected])
  類型:全譯加譯注
  • 上一篇 國際象棋程序設計():數據結構
  • 下一篇 國際象棋程序設計():基本搜索方法
  • 返 回 象棋百科全書——電腦象棋
  • www.ejnwjd.tw
    快乐双彩今晚开奖结果