《對弈程序基本技術》專題
 
概述
 
象棋百科全書網 ([email protected]) 20059
 
  我花了大量時間翻譯了F. D. Laramée的《國際象棋程序設計》(Chess Programming)連載,現在已經具備了設計象棋引擎的能力,但是還需要一些資料。為此,我查找了各個象棋程序設計的網站,收集了很多專題性的文章,并且整理成Laramée寫他的連載時形成的體系。
  我整理的文章除了T. A. Marsland的《國際象棋程序剖析》一文外,把它們分成四類,它們分別對應了Laramée的連載的四個部分。由于是從不同的網站上收集的,作者也各不相同,他們分別是:
一、數據結構
 
  這部分內容極其豐富,不僅包括棋盤的表示方法,還包括著法產生當中需要用到的數據結構。我把關于“著法產生”的文章也并入其中,因為這部分內容實在很難歸為一類,因此它代表了Laramée的連載的第二和第三部分。
 
1.1 數據結構——簡介(D.Eppstein)
1.2 數據結構——位棋盤(J.Swafford)
1.3 數據結構——旋轉的位棋盤(J.Swarford)
1.4 數據結構——著法生成器(J.Swarford)
1.5 數據結構——0x88著法產生方法(B.Moreland)
1.6 數據結構——Zobrist鍵值(B.Moreland)
 
二、基本搜索方法
 
  目前象棋程序的搜索算法,都是在“帶置換表的啟發式Alpha-Beta搜索”基礎上發展起來的,這就涵蓋了最小-最大搜索、Alpha-Beta搜索、迭代加深和置換表四個內容,把他們歸入基本搜索方法的范疇是非常恰當的。
 
2.1 基本搜索方法——簡介()(D.Eppstein)
2.2 基本搜索方法——簡介()(D.Eppstein)
2.3 基本搜索方法——簡介()(D.Eppstein)
2.3 基本搜索方法——“最小-最大”搜索(B.Moreland)
2.4 基本搜索方法——Alpha-Beta搜索(B.Moreland)
2.5 基本搜索方法——迭代加深(B.Moreland)
2.6 基本搜索方法——換位表(B.Moreland)
 
三、高級搜索方法
 
  這些方法都是“帶置換表的啟發式Alpha-Beta搜索”的擴展,其中靜態搜索和空著裁剪是消除“水平線效應”的基本手段,而期望窗口、主要變例搜索(PVS)MTD(f)都是Alpha-Beta搜索的改進。并非所有的棋類游戲都會用到這些方法,而且使用起來會有一些負作用,因此歸入高級搜索方法一點也不過分。
 
3.1 高級搜索方法——簡介()(D.Eppstein)
3.2 高級搜索方法——簡介()(D.Eppstein)
3.3 高級搜索方法——靜態搜索(B.Moreland)
3.4 高級搜索方法——空著裁剪(B.Moreland)
3.5 高級搜索方法——期望窗口(B.Moreland)
3.6 高級搜索方法——主要變例搜索(B.Moreland)
3.7 高級搜索方法——搜索的不穩定性(B.Moreland)
 
四、局面評估函數
 
  局面評估函數是對弈程序的核心,很少有特別詳細的報道,通常引擎的作者是不愿意公開的。
 
4.1 局面評估函數——簡介()(D.Eppstein)
4.2 局面評估函數——簡介()(D.Eppstein)
 
五、其他策略
 
  這里包含的內容比較雜,除了后臺思考(屬于時間控制的范疇)以外,其他方法都不能提高引擎的效率,但能時程序更完善,這些方法主要是針對國際象棋的。
 
5.1 其他策略——獲勝局面(D.Eppstein)
5.2 其他策略——主要變例的獲取(B.Moreland)
5.3 其他策略——重復檢測(B.Moreland)
5.4 其他策略——藐視因子(B.Moreland)
5.5 其他策略——后臺思考(B.Moreland)
5.6 其他策略——殘局庫(M.Fierz)
5.7 其他策略——開局庫(M.Fierz)
5.8 其他策略——策略和技巧(M.Fierz)
  • 上一篇 國際象棋程序設計():局面評估函數
  • 下一篇 數據結構——簡介
  • 返 回 象棋百科全書——電腦象棋
  • www.ejnwjd.tw
    快乐双彩今晚开奖结果