國際象棋博弈系統的研究與實現

馬鉦鴻，寧慧，張汝波

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

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

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

1 相關技術

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

1.1 FEN 格式串

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

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

圖1 FEN 格式串舉例

1.2 博弈算法

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

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

1.3 原生JavaScript、HTML 和CSS

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

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

2 系統設計與實現

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

2.1 棋盤顯示及頁面交互

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

2.1.1 棋盤棋子顯示

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

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

2.1.2 點擊響應事件綁定、行棋及刷新

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

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

圖2 棋盤顯示及頁面交互

2.2 行棋校驗

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

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

2.3 電腦行棋決策算法

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

2.3.1 走法生成算法

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

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

2.3.2 博弈算法

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

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

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

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

圖3 極大值極小值搜索樹

2.4 決策算法的研究與修改

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

2.4.1 基本思路及實現

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

2.4.2 存在問題及解決方式

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

遍歷結束后，計算機在10 種走法中隨機任選一種走法執行。

3 測試與驗證

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

表1 平衡博弈算法測試

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

4 結論

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