【正文】 else { 可否走棋 =false。 x++) { for (int y = 0。 !isRed(ChessMan)) { continue。 } if (isRedGo amp。 for (int x = 0。 break。j=maxJ1。 對(duì)弈功能的實(shí)現(xiàn) 對(duì)弈是用戶對(duì)象棋游戲最基本的需求，本系統(tǒng)的對(duì)弈功能包括人人對(duì)戰(zhàn)和人機(jī)對(duì)戰(zhàn)。 y 軸長(zhǎng) =c。 ChessPiece 黑車 1,黑車 2,黑馬 1,黑馬 2,黑將 ,黑士 1,黑士 2, 黑卒 1,黑卒 2,黑卒 3,黑卒 4,黑卒 5,黑象 1,黑象 2,黑炮 1,黑炮 2。 for(char c=39。 } } (point[4][1].x,point[4][1].y,point[6][3].x,point[6][3].y)。j++) { (point[1][j].x,point[1][j].y,point[x 軸長(zhǎng) ][j].x,point[x 軸長(zhǎng) ][j].y)。 } public int getHeight() { return height。 } public void paint(Graphics g) { (foreColor)。 int width,height。 (b)查詢后續(xù)局面 這種開局庫查詢是與搜索結(jié)合在一起的，并不是查詢當(dāng)前局面是否在開局庫中，而是展開根節(jié)點(diǎn)的所有 走法，也就是當(dāng)前局面下所有可能走法 。 這種方法是使用置換表來統(tǒng)計(jì)開局 庫中的一些走法的優(yōu)劣。小寫 \“ w\”表示紅方走 棋；小寫 \“ b\”表示黑方走棋；因?yàn)槠鸪蹙置媸羌t先，所以上面就是 \“ w\” . (5) 吃過路兵目標(biāo)格（ En Passant Target Square） 如果沒有，就用 \“ \”表示。單純的 FEN 記錄文件后綴應(yīng)該是“ .fen”，比如 :，在中國(guó)象棋開局庫的 fen 串形式的開局庫文件后綴為 .DAT。下面我們來看看什么是 fen 串。所以中國(guó)象棋開局階段是整個(gè)對(duì)弈過程中變化最多的階段，開局的好壞對(duì)之后的中、殘局意義重大。 置換表 (TransposilionTable)是用一張表把搜索過的信息記錄下來，在后續(xù)的搜索中，察看記錄在表中的這些信息，如 果將要搜索的某個(gè)節(jié)點(diǎn)已經(jīng)有記錄，就直接利用記錄下來的結(jié)果引入到當(dāng)前的搜索中，以減少搜索。 在 αβ剪枝搜索中，剪枝效率幾乎完全取決于節(jié)點(diǎn)的排列順序，如何調(diào)整待展開的走法的順序，是提高搜索效率的關(guān)鍵。顯然此 β值可作為 MIN 方可能實(shí)現(xiàn)著法指標(biāo)的上界。這個(gè)技術(shù)叫αβ剪枝搜索。 極大極小值算法的原則是 :博弈雙方所要達(dá)到的目的相反，一方要尋找的利益是另一 方失去 的利益，博弈的一方總是希望下一步是子節(jié)點(diǎn)中取值最大者，而另一方 希望下一步是子節(jié)點(diǎn)中取值最小者。 博弈樹搜索技術(shù) 中國(guó)象棋博弈樹非常龐大，完全建立博弈樹是不可能的，唯一的解決方法就是讓博弈樹擴(kuò)展到計(jì)算機(jī)運(yùn)算可以接受的深度，然后對(duì)沒有分出勝負(fù)的葉子節(jié)點(diǎn)給出一個(gè)盡量準(zhǔn)確的打 分，表示此局面下取得勝利的可能性，這個(gè)打分是由評(píng)估函數(shù)計(jì)算給出的，將搜索樹展開是著法生成的功能，而搜索引擎則是盡可能縮小樹的規(guī)模，避免一切冗余的計(jì)算，這也是計(jì)算機(jī)博弈中搜索引擎研究的重點(diǎn)。這種方法很慢，并且受初始采樣值的限制，很容易陷入局部最優(yōu)，即評(píng)價(jià)可能很差，但是任何很小的改變都會(huì)使評(píng)價(jià)更差。這樣的條件越多，合適的權(quán)重組合就越少。這種方法是利用人類的象棋經(jīng)驗(yàn)知識(shí)來調(diào)整參數(shù)值，比如，從經(jīng)驗(yàn)上可以知道，一個(gè)車的價(jià)值要比一個(gè)兵大，給車賦予比兵大的數(shù)值，馬炮則賦予位于其間的值 。因此過于簡(jiǎn)單的估值函數(shù)和過于復(fù)雜的估值函數(shù)同樣性能不佳。 在中國(guó)象棋博弈中，每個(gè)棋子都不是孤立存在的，他們之間構(gòu)成了各種相互關(guān)系。本方棋子可以走的點(diǎn)越多，說明本方棋子的靈活性越大。根據(jù)經(jīng)驗(yàn)，可以讓一個(gè) 車價(jià)值為 500，一個(gè)馬價(jià)值為 300，一個(gè)兵價(jià)值為 100 等等。從象棋的棋力上考慮，在搜索之外，局面估值是最重要的部分，因?yàn)閷?duì)實(shí)際局面的評(píng)價(jià)的好壞，影響著今后局勢(shì)發(fā)展的趨勢(shì)。同樣的，可以對(duì)象、將、士、卒使用模板匹配生成著法。著法生成 是博弈程序中一個(gè)相當(dāng)復(fù)雜而且耗費(fèi)運(yùn)算時(shí)間的方面 ，要生成所有著法只能用窮舉 。如果能在尋找棋子 和定位棋子上使用位運(yùn)算代替加減乘除和取余，這將很大程度上提高運(yùn)算速度。 (2) 隨時(shí)保持這兩個(gè)數(shù)組之間的聯(lián)系，棋子移動(dòng)時(shí)必須同時(shí)更新這兩個(gè)數(shù)組。而己被吃掉的棋子用坐標(biāo)范圍以外的數(shù)表示。 第三章 給出實(shí)驗(yàn)環(huán)境和 程序?qū)崿F(xiàn) 。如何把各種增強(qiáng)手段有機(jī)組合起來達(dá)到最優(yōu)，文章對(duì)基于迭代加深、置換表、歷史啟發(fā)的 Negascout 算法進(jìn)行改進(jìn)。對(duì)弈過程機(jī)器自動(dòng)調(diào)整評(píng)估函數(shù)參數(shù)的權(quán) 值 進(jìn)行優(yōu)化，發(fā)現(xiàn)一些棋子之間潛在的聯(lián)系 :之二是采用模式識(shí)別，學(xué)習(xí)的過程是通過對(duì)博弈過程的識(shí)別統(tǒng)計(jì)，自行豐富模式庫中的內(nèi)容，以提高程序的博弈性能。“蠻力搜索”肯定是不可取的。在一定程度上形成了程序的性能瓶頸。 表 11 著名中國(guó)象棋計(jì)算機(jī)博弈程序 程序 作者 地區(qū) 縱馬奔流 涂志堅(jiān) 廣州中山大學(xué) 謝謝象棋大師 法國(guó)電腦公司 法國(guó) ELP 鄭武堯、陳志呂 臺(tái)灣 SHIGA（象棋世家） 鄭明政、顏士?jī)? 臺(tái)灣 SHCC（神乎棋技） SAI team 美國(guó) Cyclone（象棋旋風(fēng)） 陳朝陽 北京 CONTEMPLATION 千慮 陳志昌、許舜欽 臺(tái)灣 棋天大圣 王驕 東北大學(xué) 象棋奇兵 趙明陽 中國(guó) 每年也會(huì)有中國(guó)象棋計(jì)算機(jī)博弈的國(guó)際奧林匹克大賽，這其中有 2020 年的世界冠軍“縱馬奔流”， 2020 年的世界冠軍“謝謝象棋大師”， 2020 年的世界冠軍“象棋奇兵”，20 2020 年的世界冠軍“棋天大圣” ， 2020 年的世界冠軍“倚天”。 1981 年張耀騰發(fā)表的《人造智慧在電腦象棋上的應(yīng)用》，他提出審局函數(shù)為 靜態(tài)子力值，棋子位置值，棋子靈活度值，威脅與保護(hù)等四項(xiàng)之和。人類對(duì)機(jī)器博弈的研究衍生了大量的研究成果，這些成果對(duì)更廣泛的領(lǐng)域產(chǎn)生了重要影響。 本文 結(jié)合 在中國(guó)象棋機(jī)器博弈方面的實(shí)踐經(jīng)驗(yàn) ，在分析了中國(guó)象棋游戲需求基礎(chǔ)上，設(shè)計(jì)并實(shí)現(xiàn)了智能中國(guó)象棋系統(tǒng)。 本 系統(tǒng) 的實(shí)現(xiàn) 滿足了人們對(duì)中國(guó)象棋的基本需求，解決了傳統(tǒng)象棋游戲?qū)W習(xí)性差、棋譜不易保存、不易演示等問題。 而當(dāng)今對(duì)中國(guó)象棋的研究也 正如專家們所期望的那樣 在蓬勃地發(fā)展著。 1983 年黃少龍、周玉龍合作制成《象棋排局系列軟盤》專家系統(tǒng)與人對(duì)弈。 系統(tǒng)概述 棋盤表示 (Board Representations) 棋盤表示就是使用一種數(shù)據(jù)結(jié)構(gòu)來描述棋盤及棋盤上的棋子，以方便計(jì)算機(jī)處理。目前象棋程序的靜態(tài)評(píng)價(jià)函數(shù)主要有子力價(jià)值，子力靈活性，子力對(duì)棋盤的控制，和一些對(duì)棋局影響比較大的重要特征計(jì)算幾部分組成。 開局庫 (Opening Book) 把開局幾步的走法建成數(shù)據(jù)庫供程序直接取用。在產(chǎn)生走法時(shí)直接從中取出數(shù)據(jù)，進(jìn)行少量判斷以得到該棋子的合法走步。 第二部分研究本系統(tǒng)的著法生成，包括預(yù)置表法和模板匹配法，進(jìn)一步提高了搜索效率。 棋盤的基本表示法 （ Board Representions） 棋盤表示就是使用一種數(shù)據(jù)結(jié)構(gòu)來描述棋盤上的信息，以便程序知道博弈的狀態(tài)。 兩種棋盤表示方法：一是做一個(gè)棋盤數(shù)組；二是做一個(gè)棋子數(shù)組。 “棋盤由 bool 型棋盤數(shù)組（屬于棋盤的位置為 true，否則為 false），判斷棋子是否走出棋盤邊界只要返回該數(shù)組對(duì)應(yīng)的值即可，速度快。 模板匹配法 當(dāng)動(dòng)子確定以后，其“落址”和“提址”的相對(duì)關(guān)系便確定下來了，這樣可以為某些動(dòng)子設(shè)計(jì)其著法生成的“模板”，只要匹配到提址，便可以迅速找到落址。預(yù)置表看起來似乎很大，但是只需在程序開始運(yùn)行時(shí)初始化一次就可以了 ，這些耗費(fèi)對(duì)整個(gè)程序的影響不大，但是對(duì)著法生成的作用卻是非常明顯的。同時(shí)由于隨著搜索層數(shù)的加深，葉子節(jié)點(diǎn)的數(shù)目迅速上升，估值函數(shù)被數(shù)以百萬次的調(diào)用，花費(fèi)大量的運(yùn)算時(shí)間，如何提高估值函數(shù)的速度，也成了博弈性能改進(jìn)的重要話題 。如果紅色的棋子價(jià)值總和大于黑色的棋子價(jià)值總和，通常這意味著紅方的局勢(shì)優(yōu)于黑方。 Mobility 就是所有棋子的靈活性分?jǐn)?shù)。棋子關(guān)系的評(píng)估應(yīng)考慮到該誰走棋的問題。在速度和知識(shí)量二者的相互作用下，開發(fā)者要尋找的是一種平衡，是能夠使性能最大化的速度和知識(shí)量。 (1)規(guī)格化 (Normalize) 如果只 是關(guān)心評(píng)價(jià)的順序，而不怎么關(guān)心評(píng)價(jià)值，那么可以把每一項(xiàng)都乘以同樣 的常數(shù)。這個(gè)方法可以很快得到合理的結(jié)果，但是需要對(duì)棋類知識(shí)有足夠的了解，便于根據(jù)程序的對(duì)局來做分析，從而知道程序的問題在哪里。這個(gè)方法需要給定一些幾率，從幾 率高、梯度大的條件開始，然后逐漸減小。中國(guó)象棋中最常用 裁剪算法是空著裁剪 (Null Move)等。例如，如果紅方為走棋方，它在偶數(shù)層的著法選擇是要在其全部子節(jié)點(diǎn)中找到評(píng)估值最大的一個(gè)，實(shí)行“ Max 搜索”，稱為 MAX 方，而其敵對(duì)方即黑方在奇數(shù)層的著法選擇則是在其全部子節(jié)點(diǎn)中要找到評(píng)估值最小的一個(gè)，實(shí)行“ Min 搜索”，稱為 MIN 方。在搜索中路分枝時(shí)，因?yàn)榈诙又ǖ倪x擇是取第三層節(jié)點(diǎn)的最小值，即取 M 州 (8， 3，“ □ ” )，而無論“ □ ”中為何值，都不會(huì)比 5 大 (最大為 3)，故可以將“ □ ”表示的節(jié)點(diǎn)及其后繼節(jié)點(diǎn)剪掉，不再考慮此節(jié)點(diǎn)的延伸。此類剪枝稱為 β剪枝。 歷史啟發(fā) (History Heuristic)實(shí)際上就是記錄搜索過的好的走法，并在后續(xù)著法中優(yōu)先搜索?？罩阉髅黠@降低了搜索的數(shù)量，導(dǎo)致搜索深度顯著提高，并且危險(xiǎn)性比較小，實(shí)現(xiàn)較為簡(jiǎn)單。 這對(duì)于整個(gè)博弈系統(tǒng)來說有三點(diǎn)好處：一是防止戰(zhàn)略性錯(cuò)誤；二是形成較為穩(wěn)妥和有利的局面；三是節(jié)省了大量的搜索時(shí)間。 D 看看一個(gè) FEN 的五個(gè)區(qū)域及其含義，以中國(guó)象棋為例： Rnbakabnr/9/1C5C1/P1P1P1P1P/9/9/P1P1P1P1P/1C5C1/9/RNBAKABNR w—0 1 這就是每盤常規(guī)對(duì)局的最初局面，一個(gè)子都沒有動(dòng)，如圖 ： 圖 象棋初始局面 (3) 棋子位置數(shù)值區(qū)域（ Piece placement data） 就是表示雙方棋子各在棋盤哪個(gè)格子上的。 (6) 半回合數(shù)（ Halfmove Clock） 用一個(gè)非負(fù)數(shù)表示自從上一次動(dòng)兵或吃子之后目前走了的半回合數(shù)。置換表存儲(chǔ)的內(nèi)容主要用于搜索，開局庫存儲(chǔ)的內(nèi)容主要是走法的權(quán)重、輸贏比率，用于選擇最佳的走法。 運(yùn)行完成的 程序，本系統(tǒng)界面如圖 所示： 圖 象棋系統(tǒng)界面 界面的實(shí)現(xiàn)分為 棋盤的表示和棋子的表示兩部分，棋盤和棋子通過數(shù)組連接起來，形成一個(gè)完整的界面系統(tǒng)。 backColor=bc。 (new Font(隸書 ,28))。 } public void set棋子類別 (String 類別 ) { 顏色類別 = 類別 。i++) { if(i!=1amp。 (point[4][y 軸長(zhǎng) ].x,point[4][y 軸長(zhǎng) ].y,point[6][8].x,point[6][8].y)。J39。 addMouseMotionListener(this)。 紅車 2=new ChessPiece(車 ,bc,w4,h4,this)。 ...... int minI=(startI,endI)。 } } if(j==maxJ)