國際象棋博弈系統(tǒng)的研究與實現(xiàn)

馬鉦鴻，寧慧，張汝波

1.哈爾濱工程大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150001 2.大連民族大學(xué) 機電工程學(xué)院，遼寧 大連 116600

隨著計算機、互聯(lián)網(wǎng)相關(guān)技術(shù)的不斷發(fā)展，素未謀面的人們同樣可以通過網(wǎng)絡(luò)進行社交或共同游戲。游戲這一人類不可或缺的概念，隨著科學(xué)技術(shù)的發(fā)展不斷的改變，不僅僅各種五花八門的電子游戲應(yīng)運而生，那些早已存在了幾百年，甚至上千年的古老游戲，也完成了從實體化向數(shù)字化的轉(zhuǎn)變。

國際象棋又稱西洋棋，是世界上最為流行的雙人博弈的戰(zhàn)術(shù)棋盤游戲之一。在計算機技術(shù)高速發(fā)展的今天，有許多人使用電腦進行國際象棋游戲。同時，隨著人工智能以及編程技術(shù)的不斷發(fā)展，計算機博弈算法也獲得了極大的發(fā)展，現(xiàn)如今頂尖的棋手也很難勝過電腦[1]。但就棋類運動的意義上來講，單純的輸贏并非其意義所在，心理、智力的對抗以及其帶給人們的成長更加重要[2]。因而如何使用計算機技術(shù)促使人們對國際象棋保持樂趣的同時又能在一定程度上提高棋藝，應(yīng)當(dāng)成為計算機博弈的發(fā)展方向之一。

1 相關(guān)技術(shù)

為了研究和實現(xiàn)一個可以保持樂趣、同時提升玩家棋藝的國際象棋博弈系統(tǒng)，本文主要使用的基礎(chǔ)性技術(shù)有FEN 格式串、博弈算法以及原生的JavaScript、html 和CSS。

1.1 FEN 格式串

FEN 格式串來源于FEN 記號法，即“福斯夫-愛德華茲記號法”，是一種將ASCII 碼用于描述國際象棋局面的方法。一份標(biāo)準(zhǔn)的局面記號對于國際象棋程序這種需要對大量的局面數(shù)據(jù)進行交換與共享的工作，具有十分重要的作用。

本系統(tǒng)將棋盤表示為一個二維數(shù)組，再轉(zhuǎn)變成一維數(shù)組，最終變換為FEN 格式串，其中分別使用“K、Q、B、R、N、P”來表示“國王、王后、主教、戰(zhàn)車、騎士、士兵”，并按照大小寫進行顏色的區(qū)分；對于換行處，使用“/”進行標(biāo)記；對于空位則使用數(shù)字進行標(biāo)記。使用FEN 格式串，使得在數(shù)據(jù)傳輸時只需要傳遞一個字符串而非整個二維數(shù)組，極大地節(jié)省了空間，也為在數(shù)據(jù)傳輸以及與其他國際象棋軟件共享棋局時提供了便利。圖1 是將國際象棋的初始局面表示為FEN 格式串之后的結(jié)果。

圖1 FEN 格式串舉例

1.2 博弈算法

博弈算法，即通過計算機模擬人類下棋時決策所使用的算法，它通過對棋局進行評估、比較，選擇出對己方有利的行棋方式。博弈算法有許多種類，本系統(tǒng)中采用了博弈樹作為算法的基礎(chǔ)，以對計算機的走法決策進行支持。

博弈樹是在組合博弈理論中用來表達一個博弈行為中各種后續(xù)可能性的樹。在一棵完整的博弈樹中，其起始點表示博弈過程中的某一個情形，下一層的子節(jié)點表示其父節(jié)點博弈下一步的可能性，依此類推，直至博弈結(jié)束。博弈樹在各種棋類的游戲程序中被廣泛地應(yīng)用，本系統(tǒng)對博弈樹的應(yīng)用方式如下：選擇一種走法，計算依此法行棋可獲得的局面分?jǐn)?shù)，然后撤銷此步，選擇下一種走法，直到取遍所有的走法；默認(rèn)雙方都會選取對自己獲得勝利最有利的點；以白方的局勢評估結(jié)果(即局勢所獲得的評分)為標(biāo)準(zhǔn)進行行棋的比較，白方希望局勢中的分?jǐn)?shù)盡可能的高，而黑方希望對方的分?jǐn)?shù)盡可能的低。這便是極大值極小值搜索算法的思路，也是本系統(tǒng)中計算機行棋時博弈樹構(gòu)建所使用方法的基礎(chǔ)。

1.3 原生JavaScript、HTML 和CSS

本系統(tǒng)的后臺邏輯以及人機交互等功能通過原生的JavaScript 實現(xiàn)，以HTML 作為頁面，并使用CSS 對頁面進行修飾。JavaScript 是一種具有函數(shù)優(yōu)先的輕量級、解釋型或即時編譯型的編程語言，也正因為這些優(yōu)點，使得本系統(tǒng)無需復(fù)雜的環(huán)境配置，也沒有過大的空間占用，下載后使用瀏覽器打開即可，十分方便快捷。

本項目的后臺邏輯部分主要由3 個部分組成：名為Board 的類負(fù)責(zé)棋盤的顯示以及與用戶之間的交互；名為Position 的類負(fù)責(zé)棋子走法的校驗和棋子走法的生成；名為search 的類負(fù)責(zé)電腦行棋所使用的博弈算法。整個系統(tǒng)是一個可以在本地完成所有功能的Web 網(wǎng)頁。

2 系統(tǒng)設(shè)計與實現(xiàn)

本系統(tǒng)作為一個游戲程序，希望玩家只需一臺安裝了支持JavaScript 瀏覽器的設(shè)備就可以隨時隨地進行游戲，因而以一個Web 網(wǎng)頁的形式提供給用戶。

2.1 棋盤顯示及頁面交互

棋盤棋子顯示，點擊響應(yīng)函數(shù)的綁定、編寫，刷新棋盤以及開局、重開局等基礎(chǔ)功能均在Board 類中實現(xiàn)，并反映在用戶的操作界面中，方便用戶進行游戲。

2.1.1 棋盤棋子顯示

棋盤棋子的顯示即用戶游戲界面的顯示。界面是用戶操作的對象，一個簡潔、美觀、易用的界面十分重要。本系統(tǒng)中的棋盤主體為一個HTML中的div 標(biāo)簽，其中id 為container，該標(biāo)簽的背景為一張棋盤的圖片；而棋盤上的每一個位置，都是一個添加進div 標(biāo)簽中的img 標(biāo)簽，每個img 都指向一張準(zhǔn)備好的圖片；選中框的顯示通過為img 標(biāo)簽添加背景圖片來實現(xiàn)。

其中div 容器的修改，包括大小的設(shè)定、背景圖片的路徑以及img 標(biāo)簽及其相關(guān)參數(shù)的動態(tài)添加均在初始化Board 對象時進行；而選中框的消除則是由點擊響應(yīng)函數(shù)運行后調(diào)用Board 類中的drawSquare()方法實現(xiàn)[3]。

2.1.2 點擊響應(yīng)事件綁定、行棋及刷新

點擊響應(yīng)函數(shù)clickSquare()同樣屬于Board類中的方法之一，在Board 類初始化時，通過JavaScript提供的onmousedown 方法添加至img 標(biāo)簽。

點擊響應(yīng)函數(shù)發(fā)生后，調(diào)用Board 中的addMove()方法進行行棋，并通過調(diào)用postAddMove()對選中框的顯示問題進行處理，在行棋結(jié)束后調(diào)用Board中的flush()方法實現(xiàn)棋盤的刷新，從而反饋至用戶界面。圖2 為棋盤顯示及頁面交互界面。

圖2 棋盤顯示及頁面交互

2.2 行棋校驗

國際象棋中每一種棋子都有其自己的走法，當(dāng)選擇的走法不符合規(guī)則時，應(yīng)拒絕執(zhí)行這一步棋并重新選擇走法，這就需要對行棋進行校驗，該功能主要在Position 類中實現(xiàn)。當(dāng)用戶點擊并觸發(fā)Board 類中的clickSquare()函數(shù)后，將會調(diào)用addMove()函數(shù)以執(zhí)行行棋功能。行棋時首先便會調(diào)用Position 類中的legal()函數(shù)對走法是否合法進行校驗，合法則進行后續(xù)的工作，否則會阻止進程，重新等待用戶的選擇。

國際象棋共有6 種棋子，這其中使用了3 種不同的校驗方式：對于國王與騎士，使用輔助數(shù)組進行校驗；對于王后、戰(zhàn)車、主教這種走直線的棋子，首先判斷其行進方向，然后每次只移動一步，并依次對路徑中的每一個格子進行判斷；士兵的走法則比較復(fù)雜，通過枚舉出不同的情況，依次進行判斷[4]。

2.3 電腦行棋決策算法

電腦行棋算法是本系統(tǒng)的核心部分之一。在用戶行棋之后，會調(diào)用Board 中的postAddMove()方法。該方法在對棋子顯示相關(guān)的問題進行處理后觸發(fā)，會調(diào)用Board 中的response()算法，隨后進一步調(diào)用Search 類中的searchMain()方法，控制電腦進行行棋決策。電腦行棋決策方法的實現(xiàn)主要分為2 個部分：第一部分是定義在Position 類中的generateMoves()方法，該方法會生成目前棋局中本方所有可能的行棋方法；第二部分則是定義在Search 類中maxminSearch()方法，在生成的算法中進行選擇，本項目中使用了極大值極小值搜索算法。

2.3.1 走法生成算法

走法生成算法用來生成當(dāng)前局面下所有符合規(guī)則的行棋方法，即進行行棋時的走法遍歷。這一功能為之后的走法評估以及最終的行棋決策提供了進行計算以及選擇的對象，該算法主要實現(xiàn)在Position 類中的generateMoves()函數(shù)[5]。

遍歷開始時，該函數(shù)會建立一個用于儲存所有可能的下一步行棋方式的動態(tài)數(shù)組，其中的每一個對象，都記錄了一步棋的起點與終點。遍歷開始后，該函數(shù)會對棋盤上的每一個位置進行遍歷，對于空位及對方棋子不做處理，而對于每一個己方的棋子，則根據(jù)該棋子的行棋規(guī)則，生成當(dāng)前棋盤局勢下所有的、不重復(fù)的行棋位置，并將這些合法的走法保存至建立好的動態(tài)數(shù)組中，遍歷結(jié)束后將動態(tài)數(shù)組返回，用于下一步中的處理。

2.3.2 博弈算法

博弈算法分為棋局評估部分以及搜索算法部分。

評估部分的具體參數(shù)，即不同棋子在不同位置上的評分，主要由棋子在棋盤上某個位置時能夠控制的位置數(shù)量決定，這一分值由不斷地實驗與改進得到。本項目中的取值參考了國際象棋WIKI 中提供的相關(guān)數(shù)據(jù)，而棋局局面的評分通過雙方場上所有存在的棋子的價值總和之差表示[6]。由于棋盤是對稱的，雙方初始分?jǐn)?shù)相同，所以只需在每次行棋后對變化棋子的分值進行計算[7]，評分過程在Position 類中定義的addChess()函數(shù)中實現(xiàn)。

搜索算法部分使用了極大值極小值搜索算法，由Search 類中的maxminSearch()實現(xiàn)，這是一種經(jīng)典算法[8]，基于以下的思路設(shè)計：認(rèn)為雙方都足夠強大，每一次都會選取對自己最有利的點作為下一步的走法；以白方的局勢評估結(jié)果(即局勢所獲得的評分，使用白方總分減去黑方總分)為標(biāo)準(zhǔn)進行行棋比較，白方希望局勢評估中自己的分?jǐn)?shù)盡可能高，而黑方希望對方的評估分?jǐn)?shù)盡可能的低[9]。

該算法的實現(xiàn)基于深度優(yōu)先遍歷。運行時將依次遍歷generateMoves()函數(shù)中生成的走法數(shù)組，每選中一種走法，就執(zhí)行這一步，并重復(fù)執(zhí)行走法生成、棋局評估這一過程，執(zhí)行設(shè)置好的次數(shù)，之后在所有的可能性中選取棋局評分對己方最有利的走法[10]。采用的極大值極小值搜索算法會生成一棵如圖3 所示的搜索樹。

圖3 極大值極小值搜索樹

2.4 決策算法的研究與修改

現(xiàn)如今計算機博弈算法發(fā)展已經(jīng)十分完善，人機對弈中人類的勝率不斷地降低。隨著計算機計算性能的進一步發(fā)展，人與計算機的差距的擴大是可以預(yù)見的[11]?？梢哉J(rèn)為人機對戰(zhàn)的勝利與否已經(jīng)失去了懸念，因此，本系統(tǒng)對博弈算法進行了修改，編寫了以保證棋局局面平衡為目標(biāo)的博弈算法，以此降低人機差距，達到保持玩家游戲體驗的同時，提高玩家棋藝的目的。

2.4.1 基本思路及實現(xiàn)

因為棋局對稱，所以對初始局勢的雙方局勢得分進行評估時，雙方得分相同，因此只需計算游戲開始后每一步行棋后局勢的變化即可。故使用與之前相同的棋局評估方式，且棋局評分越接近0，則代表雙方局勢越接近平衡。本算法實現(xiàn)于Search 類中的balSearch()方法，調(diào)用該方法后，首先調(diào)用用于生成所有走法的generateMoves()方法，之后遍歷全部的走法。對于這些不同的走法，依次執(zhí)行，之后評估局面得分，保存執(zhí)行后局面評估的結(jié)果，之后撤銷這一步行棋，以執(zhí)行對下一種走法的操作[10]。將不同的結(jié)果做對比，選出得分絕對值最小的走法作為電腦的走法，通過這樣的方式，使得局面始終比較平衡，避免某一方輕易獲勝或失敗。

2.4.2 存在問題及解決方式

當(dāng)雙方的棋局排列相似度較高(比如開局)時，為保證雙方局勢平衡，電腦經(jīng)過決策并選擇的走法有極大的可能性會與玩家一致，導(dǎo)致棋局效果不佳。因此，算法在進行決策時，不只選用唯一一種走法，而是保存能夠保證局勢較為平衡的10 種走法，并使用隨機抽選的方式選擇出一種走法，這樣就有效地避免了雙方棋局相似時，計算機總是選擇與玩家對稱的行棋方式?；谶@種考慮，本算法首先調(diào)用generateMoves()方法獲得全部可能的走法，并儲存在mvs 數(shù)組中；然后，對數(shù)組中的走法進行遍歷，針對每一種走法，計算執(zhí)行后的局面分值，如果may 數(shù)組中的走法不足10 種，則直接保存，否則將分值與may 數(shù)組中走法對應(yīng)的val 數(shù)組中的分值進行比較，保存最符合要求的走法；最后，撤銷這一步使棋盤還原，繼續(xù)遍歷。算法程序如下所示。

遍歷結(jié)束后，計算機在10 種走法中隨機任選一種走法執(zhí)行。

3 測試與驗證

接下來對新算法進行測試，測試其在面對不同水平的玩家時，能否順利達成保持棋局局勢平衡的目的[6]。這里使用網(wǎng)絡(luò)中現(xiàn)有的國際象棋AI 對本模塊進行測試。為測試本模塊，在項目的實現(xiàn)中加入了新代碼，新代碼會在每一次電腦行棋后，在瀏覽器的控制臺中輸出當(dāng)前的局勢評分。要確定本算法能否保持局勢平衡，只需要觀察能否維持評估的結(jié)果值接近0 即可。測試進行了多次實驗，表1 為部分實驗數(shù)據(jù)。

表1 平衡博弈算法測試

從測試結(jié)果來進行分析，當(dāng)玩家水平低于難度II 的電腦AI 時，本模塊可以較好地保持棋局局面的平衡，可以達成在保證“初學(xué)者”對國際象棋樂趣的同時，經(jīng)驗有所提升這一目標(biāo)；當(dāng)玩家水平進一步的提升后(即在測試時選擇更高的游戲難度時)，本模塊的效果會下降。綜上所述，考慮將本功能的目標(biāo)用戶定位于國際象棋初學(xué)者。

4 結(jié)論

本文提出了以保持對弈雙方局面平衡為目的的計算機博弈決策算法，致力于維持玩家對游戲的樂趣的同時，提高玩家的棋藝水平。同時，因為使用JavaScript 實現(xiàn)系統(tǒng)，使得系統(tǒng)可以跨平臺使用，且無需事先編譯，使用方便?？傊?，本系統(tǒng)提供了一個占用空間小、運行環(huán)境簡單、功能完善的國際象棋游戲程序，為人們提供了一個既可以娛樂，又可以提升自己下棋水平的國際象棋游戲平臺。