一種國際跳棋的博弈系統研究

桂義勇

（北京信息科技大學 計算機學院， 北京100101）

0 引 言

一直以來人們都想讓計算機來戰勝人類，從戰勝世界棋王卡斯帕羅夫的國際象棋深藍到戰勝李世石的圍棋博弈程序AlphaGo［1］。 人們一直以來都在為了這個目標而不懈努力。 國際跳棋是在全世界熱門的一個棋種，因為其簡單的規則和多樣的走棋方式在世界范圍內備受歡迎。 目前國際跳棋8×8 的研究已經被完善，但10×10 的研究還在進行中。 本文研究的是國際跳棋10×10，通過棋盤界面的構建、棋盤局面的評估和對局面的搜索，實現了一個國際跳棋的計算機博弈系統。

1 國際跳棋規則簡述

1.1 棋盤表示

西洋跳棋的棋盤為10×10 黑白相間的方格棋盤，每個玩家的右下角應該是白色格子，如圖1所示。

黑格為合理棋位，棋位統一編碼如圖2 所示。開局時黑白雙方的棋子各擺在棋盤靠近自己一方的4 行黑格當中，如圖3 所示。 黑方先手，然后雙方輪流走動自己一方的棋子。

1.2 走棋規則

在整個對弈過程中，淺色格子是用不到的。 棋子自始至終都是在黑格子中沿對角線方向移動和停止。 對弈的目標是將對方所有的棋子吃掉或者形成一個局面逼使對方棋子不能移動。

圖1 國際跳棋棋盤Fig.1 Checkers board

圖2 棋盤統一編碼Fig.2 Checkerboard unified coding

圖3 開局的布局Fig.3 Start layout

只要對角線方向鄰近的黑格內有對方的棋子并且再過去的黑格是空位，就可以跳過對方的棋子并將對方棋子吃掉。 如果沒有跳吃的著法，就只能沿對角線方向前移一格。 當某一著法結束之后才將吃掉的棋子從棋盤上移出，任何被吃掉的棋子雖然還沒有從棋盤上移出也不許再跳經該棋子。 跳吃的時候，在具有多種選擇的情況下，必須選擇吃子最多的著法。

任何一個棋子到達對方底線便立刻加冕，從此便成為“王”。 只有停止在對方底線上的棋子才能加冕。 所以，如果一個棋子在跳吃過程中行進到底線又離開了底線，最后沒有停止在底線上，則該棋子不能升王。 王可以在對角線方向上移動任意多個空格。 同樣在跳吃的時候，王可以跳過對方棋子前后任意數量的空格。

2 國際跳棋博弈系統的結構設計

2.1 博弈系統設計

國際跳棋博弈系統主要由兩個方面組成，博弈平臺和博弈算法。 計算機博弈系統的目的是讓計算機能夠像人一樣進行分析、判斷和作出決策的智能系統。 博弈平臺的主要功能是信息的傳遞、規則判斷和界面顯示等；博弈算法主要研究的是搜索算法、局面評估算法和走法生成等工作。 博弈算法是整個博弈系統中的核心部分，是一個博弈系統的大腦［2］，決定了系統的能力。 博弈系統架構如圖4 所示。

圖4 博弈系統架構圖Fig.4 Game system architecture diagram

架構設計完成后，需要進行博弈流程的設計。根據國際跳棋的規則對弈雙方需要交替下棋，每次交替后換手。 在每次下棋時搜索棋子位置并返回到前端的界面，顯示能夠下棋的位置，行棋結束后更新棋盤界面。 如在連續跳吃的情況下，每次行棋時先不換手，當連續跳吃結束之后再輪到對方下棋。 博弈流程如圖5 所示。

圖5 對弈流程圖Fig.5 Game flow chart

2.2 數據結構設計

結構設計包括：棋盤存儲類型的設計、棋盤、棋子以及對棋盤規則的實現。 變量的定義對程序的編寫有著重要的作用，合理設計變量不僅能夠提高程序的可讀性，而且還能在之后對程序的維護中提供更加清晰標識。 棋盤通過一個二維矩陣來記錄局面，其中黑子表示為1、黑王表示為10、白棋表示為－1、白王表示為－10。 這種設計的方式在后面的評估函數設計時，便于評估棋盤中棋子的棋力。

3 系統后端詳細設計

3.1 局面評估算法

不同的走棋方法就會產生不同的局面，如何對棋盤局面進行有效的評估，判斷當前的下棋方法是否對己方有利，是評估函數需要考慮的地方。 如果設定好了博弈程序的評估函數，那么博弈模型下棋的方式就會按照設計的權重來對所有可以下棋的位置進行判斷，選擇對己方利益最大的位置。 因此一個評估函數的優劣在很大程度上決定了計算機博弈程序的好壞。

在國際跳棋中吃子的策略往往是最有效的策略。 進攻可以把棋子的可活動空間變大，讓更多棋子能夠活動。 棋子防守策略會讓棋子的可活動空間減少，使局面變得被動。 王棋的數量在很大的程度上決定了棋局的輸贏。 如果能夠形成王棋，則該方對棋盤的掌控就會有很大提升，棋子活動的范圍也能大幅度增加。 通過對國際跳棋的分析，找出了6個能夠代表棋子能力的因子： x1己方棋子數量；x2對方棋子數量；x3己方王棋數量；x4對方王棋數量；x5己方可以跳吃的棋子個數；x6對方可以跳吃的棋子個數。 通過對評估函數的設計，對棋盤局面的好壞進行判斷。 評估函數為：

其中：w0是一個固定的偏移量，w1～w6是每個因子的權重。 x1～x4可通過棋子列表得出，參數x5和x6可通過棋盤的走子算法得出。

3.2 棋盤價值矩陣

棋子分布在棋盤的不位置會有著不同的價值，分布在棋盤中心的棋子能夠活動的空間也往往最大。 經過人們對國際跳棋的認識，總結出了棋盤對應位置的價值矩陣，通過對當前棋子落點位置計算出當前局面的棋盤價值。

黑棋的價值矩陣為

白棋的價值矩陣為

通過對兩種方法相結合得到局面評估函數：

如果只是通過靜態評估算法會造成送子太多、不積極稱王和兵落后等問題。 對這些問題通過增加棋子的價值矩陣，能夠有效的改善靜態評估算法出現的問題，對己方的棋子起到保護防守的作用；能有效地向對方發起進攻，提高了棋子稱王的積極性；能夠對局面的棋子的移動趨勢更加準確和有效，選擇出最優的落子方法。

3.3 搜索算法

搜索是一個計算機博弈程序的核心，在國際跳棋中搜索算法有很多，比如Min Max 搜索、負極大值搜索和Alpha Beta 搜索等等。 Min Max 算法又叫做極大極小算法［8］，是一種找出失敗的最大可能性中的最小值的算法，即最小化對手的最大收益的算法。極大極小算法是一種窮盡搜索方法的典型代表，通過搜索在所有的走法中找到最優的走子方法。

Alpha Beta 樹搜索算法是一種在Min Max 算法的基礎上改的博弈搜索算法，是一種深度優先的搜索算法。 Alpha Beta 算法與Min Max 算法相比最大的優點是增加搜索的深度。 Alpha Beta 算法通過減少博弈樹的分支，將搜索資源用于更有希望的子樹上的方法，來增加搜索的深度，當遇到沒有必要再去搜索的子樹時進行剪枝。

圖6 Alpha Beta 剪枝算法Fig.6 Alpha Beta pruning algorithm

4 結束語

博弈程序設計主要由3 個部分組成，棋盤的結構設計、評估函數的選定和搜索算法。 棋盤結構的設計是通過二維矩陣來就棋盤局面進行保存，移動棋子是通過對棋子類型的判斷，來選擇棋子的走子選擇。 評估函數通過對棋盤局面諸多因素的判定，得出當前局面的優劣情況，以此來提高模型對棋局的掌控狀態。 在對棋局進行搜索時總希望己方處于更加有利的地位，就需要加深搜索的深度。但是隨著搜索層數的加深，搜索的局面也會成指數級別的增加。 然而對于一些局面沒有必要再去對它們進行搜索。 本文選擇Alpha Beta 剪枝算法，從而增加搜索的層數，提高博弈模型的強度。

雖然本文的設計達到一定的使用效果，但還有待進一步完善。 如評估函數的設計還較為樸素，靜態評估考慮的棋盤因素有限。 在設計博弈模型時還可采用深度學習和強化學習相結合的方法；可采用Alpha Zero 的方法來對博弈模型進行自博弈訓練，通過大量的自對弈讓模型通過自我學習的方式提升棋力。