【正文】 MAX(5， 12，“○” )，而無論“○”中為何值，都不會比 11 小 (至少為 12)，故可以將“ ○ ”表示的節(jié)點及其后繼節(jié)點剪掉，不再考慮此節(jié)點的延伸。此類剪枝稱為 β剪枝。 αβ 剪枝搜索能夠讓我們省略許多節(jié)點的搜索，不只是節(jié)點本身，而且包括節(jié)點下面的子樹，這樣 αβ剪枝搜索需要遍歷的節(jié)點數(shù)遠少于極大極小算法所遍歷的節(jié)點，也就節(jié)省了大量的時間開銷，并且仍不失為窮盡搜索的本性 ， 但 αβ剪枝的剪枝效果即搜 索節(jié)點數(shù)與博弈樹節(jié)點的搜索次序密切相關。但在實際 的博弈系統(tǒng)設計中，要提高程序的搜索速度和搜索深度，還必須利用搜 中得到的一些啟發(fā)式信息來加快搜索，目前己經(jīng)有很多對基本搜索算法的增強算法。在搜索的過程中，往往有一些啟發(fā)性的信息可以利用，如果利用這些信息在相似的局面下對走法進行優(yōu)化排序，或者對相同的局面不再搜索，而直接返回以前搜索的結果，都會對搜索產生明顯的加速作用。 歷史啟發(fā) (History Heuristic)實際上就是記錄搜索過的好的走法，并在后續(xù)著法中優(yōu)先搜索。在 搜索過程中，每找到一個好的著法 ，就將與該走法相應的歷史得分作一 增量，一個多次被搜索并確認為好的走法的歷史記錄分值會較高，當搜索中間節(jié)點時，將走法根據(jù)其歷史得分排序，以獲得較佳的排列順序。殺手啟發(fā)是一種特殊的歷史啟發(fā)，它不依賴于人類的知識，具有普遍性。置換表不同于歷史啟發(fā)表和殺手表，不必在每次搜索之前都清空，而是一直維持這些數(shù)據(jù)，作為以后搜索的信息?？罩阉髅?顯降低了搜索的數(shù)量，導致搜索深度顯著提高，并且危險性比較小，實現(xiàn)較為簡單。“活馬”，即馬與兵陣的配合合理，使馬能有活動的空間 。另外當進行快棋賽時，棋手還會選擇一些冷門開局，使局面很快“脫譜”，迅速進入到中、殘局。 開局庫的作用 象人們記住開局招數(shù)一樣，博弈程序使用一個數(shù)據(jù)庫，里面儲存了開局譜著和局面，于是當對局（開局）中的棋步在開局庫中能找到時，它就可以立即取出來走，不用計算。 這對于整個博弈系統(tǒng)來說有三點好處：一是防止戰(zhàn)略性錯誤；二是形成較為穩(wěn)妥和有利的局面；三是節(jié)省了大量的搜索時間。所以 如何設置一個比較好的開局庫，就成了程序設計中不可或缺的部分。 用 FEN 串表示開局庫的方法比較簡單，該方法僅僅是將開局庫中的存儲的棋盤狀態(tài)與當前棋盤的狀態(tài)進行比較，若相同，則程序根據(jù)庫中的走法走一步。 (1) FEN FEN 就是“福斯夫 愛德華茲記號法”（ ForsythEdwards Notation）， 這是一種使用ASCII 碼字符描述國際象棋局面的標準 。 D后來為了適合象棋軟件的需要，由愛德華茲對此做了少許修改。 (2) 結構描述 一個 FEN 記錄使用長度可不同的一行來表示，由六個區(qū)域組成。 FEN 描述了 :棋子位置、輪走棋方、易位可行性、吃過路兵目標格、半步計數(shù)、以及總回合數(shù)。 看看一個 FEN 的五個區(qū)域及其含義，以中國象棋為例： Rnbakabnr/9/1C5C1/P1P1P1P1P/9/9/P1P1P1P1P/1C5C1/9/RNBAKABNR w—0 1 這就是每盤常規(guī)對局的最初局面，一個子都沒有動，如圖 ： 圖 象棋初始局面 (3) 棋子位置數(shù)值區(qū)域（ Piece placement data） 就是表示雙方棋子各在棋盤哪個格子上的。數(shù)字代表一個橫線上的連續(xù)空格，反斜杠 \“ ∧ ”表示結束一個橫線的描述。 (4) 輪走棋方（ Active Color） 表示目前局面誰該走棋。如果有，就用具體完成吃過路兵的那個格子坐標 表示，顯然對于白兵被吃只可能在第 3 橫線，對于黑兵被吃只可能在第 6 橫線。 (6) 半回合數(shù)（ Halfmove Clock） 用一個非負數(shù)表示自從上一次動兵或吃子之后目前走了的半回合數(shù)。 (7) 回合數(shù)（ Fullmove Number） 當前要進行到的回合數(shù)。 用哈希值開局庫的文件的后綴通常為“ .BIN”。與搜索引擎中的置換表類似，開局庫也是用表示局面的哈希值除以 開局庫的大小作為索引，而表示局面的哈希值作為校驗。 置換表存儲的內容主要用于搜索，開局庫存儲的內容主要是走法的權重、輸贏比率，用于選擇最佳的走法。這也意味著 Zobrist 哈希所要使用的隨機數(shù)組，不能臨時產生，而要包含在開局庫當中。此種開局庫的實現(xiàn)方法 : (a) 查詢當前局面 開局庫中存儲的哈希值表示的是當前局面，查詢到開局庫中所儲存的各種走法，并在各種走法中隨機提取一個走法執(zhí)行，走法選擇的幾率與其權重成正比。 3 系統(tǒng)的實現(xiàn) 系統(tǒng)的整體規(guī)劃 整個智能象棋系統(tǒng)將要實現(xiàn)的主要功能是：人人對戰(zhàn)、人機對戰(zhàn)、制作棋譜、演示棋譜、挑戰(zhàn)英雄榜等，而其中的各個功能又分為幾個小功能模塊，該系統(tǒng)的功能結構圖如圖 所示： 圖 功能結構圖 象棋界面的實現(xiàn) 本系統(tǒng)要實現(xiàn)一個象棋游戲系統(tǒng)，界面是必不可少的 部分。 運行完成的程序，本系統(tǒng)界面如圖 所示： 圖 象棋系統(tǒng)界面 界面的實現(xiàn)分為 棋盤的表示和棋子的表示兩部分，棋盤和棋子通過數(shù)組連接起來，形成一個完整的界面系統(tǒng)。 Color backColor=null,foreColor。 用戶界面 對弈 制作棋譜 演示棋譜 挑戰(zhàn)英雄榜 人人對 戰(zhàn) 人機對 戰(zhàn) 保存 自動播 放 上一步 下一步 輸入姓名并保存 悔棋 ChessBoard board=null。 public ChessPiece(String name,Color fc,Color bc,int width,int height,ChessBoard board) { =name。 backColor=bc。 setBackground(bc)。 addMouseListener(board)。 (2,2,width2,height2)。 (new Font(隸書 ,28))。 ()。 } public int getWidth() { return width。 } public String getName() { return name。 } public void set棋子類別 (String 類別 ) { 顏色類別 = 類別 。 } } 然后在棋盤類（ ChessBoard）里定義棋盤的表示、棋子的類別、顏色以及棋子在棋盤上的位置表示： /*棋盤的表示 */ public void paintComponent(Graphics g) { (g)。j=y 軸長 。 } for(int i=1。i++) { if(i!=1amp。i!=x 軸長 ) { (point[i][1].x,point[i][1].y,point[i][y 軸長 5].x,point[i][y 軸長5].y)。 } else { (point[i][1].x,point[i][1].y,point[i][y 軸長 ].x,point[i][y 軸長 ].y)。 (point[6][1].x,point[6][1].y,point[4][3].x,point[4][3].y)。 (point[4][y 軸長 ].x,point[4][y 軸長 ].y,point[6][8].x,point[6][8].y)。i=x 軸長 。 } int j=1。A39。J39。 j++。 ChessPiece 紅車 1,紅車 2,紅馬 1,紅馬 2,紅相 1,紅相 2,紅帥 ,紅士 1,紅士 2, 紅兵 1,紅兵 2,紅兵 3,紅兵 4,紅兵 5,紅炮 1,紅炮 2。 通過以上兩段本系統(tǒng)就實現(xiàn)了棋盤和棋子的定義，然后通過下面的方法實現(xiàn)棋子在棋盤上的表示： public ChessBoard(int w,int h,int r,int c) { setLayout(null)。 addMouseMotionListener(this)。 unitWidth=w。 x 軸長 =r。 ...... 紅車 1=new ChessPiece(車 ,bc,w4,h4,this)。 紅車 2=new ChessPiece(車 ,bc,w4,h4,this)。 ...... point[1][10].setPiece(紅車 1,this)。 ...... } 實現(xiàn)界面后，就 可以在此基礎上實現(xiàn)象棋系統(tǒng)的其它功能。人人對戰(zhàn)功能的實現(xiàn)其實就是一系列象棋規(guī)則的集中體現(xiàn)，譬如“馬走日”、“相走田”、“炮打隔山”等。 ...... int minI=(startI,endI)。 ...... boolean 可否走棋 =false。 for(j=minJ+1。j++) { if(point[startI][j].isPiece()) { 可否走棋 =false。 } } if(j==maxJ) { 可否走棋 =true。 for(i=minI+1。i++) { if(point[i][startJ].isPiece()) { 可否走棋 =false。 } } if(i==maxI) { 可否走棋 =true。 } } ...... } 如何監(jiān)視棋子在棋盤中移動和消失的實現(xiàn)： public void mousePressed(MouseEvent e)//按下鼠標時發(fā)生事件的情況 {...... } public void mouseDragged(MouseEvent e)//拖動棋子移動時發(fā)生的事件 { ...... } public void mouseReleased(MouseEvent e)//釋放鼠標時發(fā)生的事件 { { (pieceRemoved) 。 (沒吃棋子 )。本文通過 αβ剪枝算法使電腦生成有效的著法來實現(xiàn)人機對戰(zhàn)功能： public ListMotion generatePossibleMoves()//有效著法的生成 { ListMotion ret = new ArrayListMotion()。 x 9。 y 10。 if (ChessMan != 0) { if (!isRedGo amp。 isRed(ChessMan)) { continue。amp。 } switch (ChessMan) { case 7: if (isValidMove(x, y, x, y + 1)) { (new Motion(ChessMan, x, y, x, y + 1, 0)