《對弈程序基本技術》專題
 
國際象棋程序剖析
 
T.A. Marsland */
* 阿爾伯達大學計算機科學系
 
一、簡介
 
  從理論上說,讓機器下國際象棋是一個簡單的游戲,只要每一步都考慮各種可能的著法,以及每種著法的后續變化,如此下去直到將死或和棋。但是實際操作中,這種策略是不可行的,因為需要考慮的每種著法加起來會是天文數字。
  不管人類還是機器去下棋,都有一整套下棋的理論,人類好幾百年前就開始下棋,在近二百年里有很多理論資料,而機器下棋只有五十多年的歷史,在機器下棋的諸多理論中,最著名的屬Claude Shannon1949-50年提出的兩個完全對立的策略——用蠻力考慮所有著法的策略(A策略),以及靠知識來選擇其中一部分著法的策略(B策略)。盡管早在Shannon以前,就有一些電子機械可以下比國際象棋簡單的棋類,然而Shannon的理論卻是現代電腦象棋發展的基礎。
 
  如今的象棋程序把棋局看成樹狀結構,每個局面表示成棋局樹中的一個結點,每個著法代表它的一個分枝(一個結點和深一個結點的連接)。這樣,樹就由雙方不同層面上的所有著法組成(樹的一個層面用“層”(Ply)這個術語表示,代表一方走的一步棋)
  現在通常的策略是,把樹由淺至深分為三個階段,第一階段用蠻力搜索(ShannonA策略),第二階段用選擇性搜索(B策略),第三階段用稱為“靜態搜索”(Quiescence Search)的策略,來處理最后變化非常劇烈的局面,在最后一個階段里,程序只評價吃子著法,兵升變的潛力,將軍產生的后果,以及一些強制性著法。所有的程序都使用相同的算法——深度優先的Alpha-Beta算法,而不同之處在于每個階段選擇什么樣的深度。
  通常搜索的深度不是固定的,而是根據當前搜索到的著法在小范圍內變動,例如某個結點是將軍的局面,那么它的分枝數很少,這個區域內搜索應當加深一些。策略上有非常多的選擇,使得程序使用相同模型的時,他們的走棋風格和搜索速度會有顯著的差別。
 
二、樹狀搜索
 
  人類下棋時,往往分析一小部分著法并作展開,相比選擇著法而言,機器更愿意考慮得完備,所以需要發展一套逐步求精的技術。“迭代加深”(Iterative Deepening)這一技術取代了固定的深度,讓機器一次次做更深層的搜索(先是搜索N層,然后搜索N + 1層,N + 2層,等等),直到按計劃分配的時間用完為止,這樣就可以讓機器在有限的時間內找出最好的著法。諸如反駁表和置換表等技術,在與迭代加深結合起來后,可以對著法重新排序,使得下一次迭代時“主要變化”(Principal Variation)(上一次找到的最好著法)優先考慮。
  另一個排序著法的技術就是記錄一些“殺手”著法,這些著法要優先試探,殺手著法就是在搜索樹的其他位置能產生截斷或裁剪的著法。殺手著法通常是吃子的著法,因此可以簡單地認為,吃子的著法應該在其他著法之前考慮。在很多程序中,這個技術被拓展為“歷史啟發表”(History Heuristic Table),通常是64x64的數組,每個元素存放了該著法引起裁剪的次數。
 
  排序著法可以大幅度提高深度優先Alpha-Beta搜索的效率,此外還有三個算法也起到同樣作用——Pearl的偵察(Scout)算法以及相關的負值偵察(NegaScout)和主要變例搜索(Principal Variation Search,簡稱PVS)方法,它們具有同一個思想:當主要變例找到時,可以先去驗證其他著法是否都不如這個著法好,如果驗證下來不是這樣,那么它們必須重新搜索(因為它們是更好的著法,必須做完全的搜索)
  另一個能減少搜索量的技術稱為“期望搜索”(Aspiration Search),根據當前局面估計一個范圍(通常正負半個兵),用這樣一個窗口進行搜索。盡管期望搜索并不那么有效,但是用它的人還是很多的,因為它比主要變例搜索更容易理解。
 
  深層次的搜索到底能提高多少精確度,這是很難衡量的。任意局面其搜索樹的大小有很大的差異,很多殘局每方有約8種著法,而復雜的中局里每方可能有多達80種著法,就現在的技術而言,一般程序在中局階段能完全考慮710層的變化(有個程序設計師聲稱選擇性地搜索能達到40層!)
  “選擇性延伸”(Selective Extension)是對一些關鍵著法作更深入的探索,每個程序設計師對這些著法都有自己的界定——可以是防御殺棋的著法,或是為避免失子而作的反擊。選擇性延伸不能和“單步延伸”(Singular Extension)混淆起來,后者是對最好的一步著法進行的更深層次的檢查,來驗證這個著法是否仍舊是最好的。從某種意義上說它對主要變例進行了短的延伸,是一種很花時間但很有意義的方法。
 
  而用得最廣泛的做法是“空著啟發”(Null-Move Heuristic),即假設一方連走兩步,如果產生的結果更糟的話,后面那步變化就應該拋棄掉。由于水平線效應,一些看不到的不可避免的失子,通過這種方法能看到。很多向前裁剪方法起不到很好的效果,但空著向前裁剪往往是很有效的。
 
三、置換表
 
  置換表的作用如同緩沖存儲器,用來記錄前面搜索過的局面,這些局面通常在迭代加深的早期搜索過。之所以稱為“置換表”(Transposition Table),是因為當著法次序發生置換時會有相同的局面。置換表中存儲的信息除了局面以外,還有局面的評分,它的最佳著法,以及前一次搜索的深度。
  “評分”指的是在搜索樹的頂端結點(搜索能夠到達的水平)對局面進行的評價,這個評價通常包括了靜態搜索,來消除由吃子等著法引起的局面的不確定性,包括考慮兵的升變等。
  在殘局的搜索中,置換表的作用發揮得更為明顯,每個局面只有很少的著法需要考慮,其他著法都因為置換的發生而不必再去搜索。
  置換表并不增加代碼的長度和復雜性,為置換表分配空間是小事一樁。置換表的每個局面一般需要約10個字節,通常程序使用可以記錄32K1M個局面的置換表。1993年超級電腦(Supercomputer)程序自稱他們使用了1G個局面的置換表,而對于程序員來說這完全取決于存儲器的容量。
 
四、程序的性能及其測評方法
 
  盡管各種程序基本方法是一樣的,但是在相同硬件條件下,它們的表現有很大程度的差異,一定程度上這體現了程序設計師對程序所作的投入。
  比如說,盡管每個程序都有開局庫,但開局庫是沒有哪本書規定的,每個程序小組都在開發自己的開局庫。現在開局庫的大小從10,000個局面到500,000個局面不等(也有程序試驗過1.7M個局面的開局庫)
  相反,只有少數人使用Ken Tompson制作在CD-ROM上的5子到6子的殘局庫,一方面原因是目前數據的讀取非常緩慢,另一方面原因是大部分棋局都會在用到這些殘局庫之前結束(程序設計師們在利用時間的問題上,可能考慮得比較現實吧)
 
  在運行速度的層面上,當今的程序在單處理器上每秒鐘可以分析3,000500,000個局面。在相同機器上程序速度的差別是巨大的,這當然有很多解釋,用匯編語言寫的程序能有比較快的速度,用同一語言來寫的程序,用不同的編譯器也會導致速度的不同。
  其中更多的因素在于蠻力搜索、選擇性搜索和靜態搜索這三個階段所占的比例。選擇性搜索階段需要額外的時間,因為它還判斷哪些著法需要搜索,而在這個慢速、以知識為基礎的階段中,諸多程序在速度上的差別是非常明顯的。
  另一個影響搜索速度和強度的因素,是程序使用的置換表的大小。
 
  盡管很多象棋程序非常相似,它們的棋力差別仍舊可能非常大。測試棋力是很復雜的過程,由于在正式比賽中程序仍然是可調節的,因此“瑞典排名表”(Swedish Rating List)的制作小組提出了一個傳統的方案——所有的商業程序都連續自動地進行對決,得到幾百場比賽的勝負結果,并從這些結果中計算出ELO等級分,即美國和其他地方棋手們通用的等級分。
  美國棋手的平均等級分從1500開始,專家的分數在2000-2200,大師在2200-2400。世界排名300以內的特級大師,等級分則更高。在第八屆世界電腦象棋錦標賽中,大多數程序的等級分在2100-2500。現在瑞典排名表刊登在每期的《國際電腦象棋協會雜志》(International Computer Chess Association Journal)上。
 
五、展望
 
  如今頂極的電腦可以挑戰特級大師了,尤其是在快棋賽中,單機要比多處理器的并行系統更有優勢。單機之所以快,是因為它們不必通過網絡來傳輸著法,而由10100個處理器組成的多處理器系統,則在兩小時內完成40步的標準賽制中表現得更好。不久我們將會有由1000個高性能處理器組成的系統,到那個時候電腦毫無疑問能比人類棋手算得更遠,這將多少能彌補電腦的不足——不具備人類棋手所擅長的戰略構思。
  人類棋手對于局勢的簡化和基本形勢的判斷方面都具有高超技巧,他們也善于在對手身上找到弱點,除非局面是無法挽回的。盡管人類棋手有這些優勢,我們一直以來都預測說,機器在5年內能擊敗人類,現在這個目標正越來越近。要實現這個目標可能需要花上十多年,但是最終肯定會實現的。
 
《國際象棋程序剖析》參考資料
 
  1. 《電腦象棋概論》(Computer Chess Compendium)D.N.L. Levy著,Springer-Verlag出版社,1988年;
  2. 《電腦象棋與搜索》(Computer Chess and Search)T.A. Marsland文,《人工智能百科全書》(Encyclopedia of Artificial Intelligence)一書的224-241頁,S. Shapiro主編,J. Wiley & Sons出版社,1992年第二版;
  3. ICCA(國際電腦象棋協會)雜志》(International Computer Chess Association Journal),自1983年以來每年四期,ICCA編輯部([荷蘭馬斯特里赫特]林堡大學(University of Limburg)計算機系,P.O. Box 616, 6200 MD Maastricht, The Netherlands)出版;
  4. 電腦、象棋與認知(Computers, Chess and Cognition)T.A. MarslandJ. Schaeffer主編,Springer-Verlag出版社,1990年;
  5. 電腦象棋進展(Advances in Computer Chess),一至七卷,從19771994年由多人主編,由多個出版社出版。
 
  出處:http://www.cs.ualberta.ca/~tony/ICCA/anatomy.html
  譯者:象棋百科全書網 ([email protected])
  類型:全譯
  • 上一篇 其他策略——策略和技巧
  • 下一篇
  • 返 回 象棋百科全書——計算機博弈
  • www.ejnwjd.tw
    快乐双彩今晚开奖结果