两肖两码中特资料网|六合两码中特
 
國際象棋程序設計(一):引言
 
François Dominic Laramée/
 
  這是國際象棋程序設計連載的第一部分,本連載共有六部分,他們不僅僅是針對象棋【譯注:以后如不特別指出,都指國際象棋】的,還可以運用到別的益智類游戲中。
  在人工智能領域中,專家對象棋進行了大量卓有成效的研究,這其中就有電腦對抗卡斯帕羅夫等世界冠軍的比賽。象棋在人工智能上的地位,就相當于果蠅在遺傳學上的地位,舉足輕重。我的連載將著重介紹人工智能的程序設計藝術,這其中包括“深藍”(Deep Blue)等著名程序。
  我的連載從20004月開始,每個月一次,到10月結束的時候,我會用Java寫一個簡單的程序來實現對弈。到時候你們可以從我的網站上隨便下載,耐心地等吧。
 
信息完備的游戲
 
  象棋是“信息完備”的游戲,因為游戲雙方面對的局面是同一個局面,任何一方所掌握的棋子及其位置的信息是一樣的。除了象棋以外,西洋跳棋(Checkers)、圍棋(Go)、五子棋(Go-Moku)、西洋雙陸棋(Backgammon)、黑白棋(Othello)【也有稱Reversi的,可譯為“翻棋”】可等也屬于這一范疇。但是紙牌游戲卻不是,因為你不知道對手手上的牌是什么【在中國的棋類游戲中,陸站棋(起源于歐洲)和四國大戰棋也不是】
  我的連載中將提到各種算法,大多數算法對所有的信息完備的游戲都是有效的,只是細節上有所不同罷了。很明顯,無論棋盤、著法、位置等因素有那些,搜索算法就是搜索算法,它不會因為游戲規則而改變。
 
我們需要什么?
 
  能下棋的電腦軟件至少要包括下列組件:
 
  1. 棋盤的表示方法,即局面在存儲器中的存儲方法,程序是根據它來分析局面的;
  2. 掌握規則,即什么樣的著法是合理的,如果程序連不合理的著法都不能檢測出來,那么對手就可以利用這種著法來欺騙程序;
  3. 找出所有合理著法的算法,這樣程序就可以從這些著法中找到最好的,而不是隨便找一種著法;
  4. 比較方法,包括比較著法的方法和比較局面的方法,這樣程序就可以選擇最佳的著法;
  5. 用戶界面。
 
  本連載將涉及以上除了用戶界面以外的所有內容,用戶界面在所有二維棋類游戲中都是差不多的,這里就不作介紹了。接下來將對以上幾個部分作逐一介紹,并且引出許多重要的概念。
 
棋盤的表示方法
 
  在早期的程序設計過程中,存儲器是非常有限的(有些程序只用8K或更少的存儲器),所以最簡單、最節省的表示方法就是最有效的方法。一個典型的國際象棋棋盤可以用一個8x8的數組表示,棋盤上的每個格子用一個字節表示——空的格子用0,黑方的王用1,等等。
  如今,象棋程序可以在64位計算機上運行了,精心設計的“位棋盤”表示誕生了。在60年代后期,位棋盤在蘇聯誕生,一個位棋盤由一個64位的字【“字”是計算機中一次運算所涉及的存儲單元,我認為當時還沒有字長為64位的計算機,所以一個位棋盤應該由多個較短的字來構成,如88位的字或416位的字,即便是現在的個人電腦上,一個位棋盤也必須由兩個32位的字構成】來表示局面中的某個狀態,一位代表一個格子。例如,一個位棋盤能表示“所有被黑兵占有的格子”,或者“處于e3格的后可以走的格子”,或者“被黑馬攻擊的白子所處的格子”,等等。位棋盤用途廣泛,并且具有很快的運算速度,因為局面分析時要做大量的邏輯運算【就是“與或非”運算,也稱布爾代數】,而一個位棋盤的運算只需要一次操作就可以了。
  這部分內容將在連載的第二部分作詳細介紹。
 
著法的產生
 
  所謂棋類游戲的規則,指的就是某一方可以走哪些著法。某些游戲很容易就找到合理著法,例如在井字棋中Tic-Tac-Toe,在3x3的棋盤上輪流占格子,先在同一條線(橫線、縱線或斜線)上占有3枚棋子者得勝】,所有空的格子都是合理著法。但是在象棋中,情況就有些復雜了,每個棋子都有它特定的著法,例如兵吃子時走斜線,而不吃子時走縱線,又例如把王走到被將軍的格子是不允許的,還有諸如“吃過路兵”【法語en passant、兵的升變、王車易位等著法只有在特殊場合才是合理的。
  事實上在象棋程序設計中,著法的產生已經被證實為最復雜和最費時的事。幸運的是,著法的產生有一些預處理的技巧,我還會介紹一些數據結構,它們能顯著提高著法產生的速度。
  這部分內容將在連載的第三部分作詳細介紹。
 
搜索技巧
 
  對于計算機來說,判斷一個著法是好的或壞的,并不是件容易的事。判斷著法優劣的最佳辦法,就是看它們的后續結果,只有推演以后一系列的著法,才能確定看那步是好的。在保證不犯錯誤的前提下,我們要設想對手會走出最好的應著。這一基本原理稱為“最小-最大”搜索算法,它是所有象棋程序的基礎。
  不幸的是,“最小-最大”法的運算量是O(bn)【數學上指它和bn是一個數量級的】b(分支因子)指平均每步的合理著法【有研究表明,在國際象棋中這個值約為38,中國象棋則更多些,為42(這是中國象棋程序“七星大師”的作者趙德志的研究結果)n(深度)指思考的步數(一回合有兩步)。所以當步數增長時,運算量以幾何級數迅速增長,如果要思考得更深一些,就必須用更為合理的算法。其中,迭代加深的Alpha-Beta搜索、NegaScout搜索和MTD(f)搜索是最基本的算法,這些會在連載的第四部分介紹。除此以外,還要依靠數據結構和啟發式算法的幫助,啟發式算法是增強棋力的算法,例如置換表(Transposition Tables)、歷史啟發和將殺啟發(History/Killer Heuristic)等。
  在象棋程序設計中,另一個頭痛的問題是“水平線效應”(Horizon Effect),它首先由Hans Berliner提出。假設你的程序的搜索深度是8步,并且程序算出對手會在第六步捉死你的后。按照程序自己的設想,它會獻出象來延緩后的捉死(假定這樣做可以讓后在第10步才被捉死),因為程序只能看到8步。從程序的角度看,后是被“保住”了,因為在它的搜索范圍內后沒有被捉死,但事實上卻多丟了一個象。從這個例子可以看出,要把程序的工作重心放置到位,并不是一件簡單的事情【意思是,某些變化沒有必要搜索得太深,而關鍵的變化需要更深層次的搜索】,如果把每條變化都搜索到同一深度,那么結果是自取滅亡。很多技術是用來克服水平線效應,在連載的第五部分關于高級搜索的闡述中,將要介紹靜態搜索(Quiescence Search)和深藍(Deep Blue)的單步延伸(Singular Extensions)
 
評價局面
 
  最后,程序必須有一個估計局面(占優或處于劣勢)的方法。局面估計方法完全取決于規則(即子的走法)——在象棋中,“子力平衡”(Material Balance)是主導因素,因為一個小小的兵的領先就可能足以保證優勢一方取得勝利【而在中國象棋中,多一個兵算不了什么,這足以證明本節的觀點——局面估計方法完全取決于規則】,而在五子棋中卻沒什么影響,在黑白棋里,根據子力上的數值分析局面則完全會成為誤導,你可能一直處于領先狀態,但最后幾步局面卻翻了盤。
  建立有效的局面評估方法,這常常會成為程序設計中的難點和焦點。連載的第六部分將詳細闡述著名象棋程序的局面評估方法,其中包括Chess 4.5Cray BlitzBelle(尤物)
 
結論
 
  我們已經找到了完成拼版的所需要的碎片,現在是開始動手做的時候了。下個月我將介紹最常用的棋盤表示方法,敬請關注。
 
  François Dominic Laramée20004
 
  原文:http://www.gamedev.net/reference/programming/features/chess1/
  譯者:象棋百科全書網 ([email protected])
  類型:全譯加譯注
  • 上一篇 棋弈軟件基礎——殘局庫對引擎棋力的負面影響
  • 下一篇 國際象棋程序設計():數據結構
  • 返 回 象棋百科全書——電腦象棋
  • www.ospsfq.shop
    两肖两码中特资料网 福彩体育彩票官网个人中心 十一选五黑龙江十一选五开奖结果 江苏时时彩走势 湖北麻将卡五星打法 山西泳坛夺金 福建彩票大奖排行榜 大众麻将四人麻将下载 三点一线炒股法 福彩012路断路分析法 广西打麻雀打多大才违法