一種國際跳棋的博弈系統(tǒng)研究

桂義勇

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

0 引 言

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

1 國際跳棋規(guī)則簡述

1.1 棋盤表示

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

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

1.2 走棋規(guī)則

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

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

圖2 棋盤統(tǒng)一編碼Fig.2 Checkerboard unified coding

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

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

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

2 國際跳棋博弈系統(tǒng)的結(jié)構(gòu)設(shè)計

2.1 博弈系統(tǒng)設(shè)計

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

圖4 博弈系統(tǒng)架構(gòu)圖Fig.4 Game system architecture diagram

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

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

2.2 數(shù)據(jù)結(jié)構(gòu)設(shè)計

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

3 系統(tǒng)后端詳細設(shè)計

3.1 局面評估算法

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

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

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

3.2 棋盤價值矩陣

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

黑棋的價值矩陣為

白棋的價值矩陣為

通過對兩種方法相結(jié)合得到局面評估函數(shù)：

如果只是通過靜態(tài)評估算法會造成送子太多、不積極稱王和兵落后等問題。 對這些問題通過增加棋子的價值矩陣，能夠有效的改善靜態(tài)評估算法出現(xiàn)的問題，對己方的棋子起到保護防守的作用；能有效地向?qū)Ψ桨l(fā)起進攻，提高了棋子稱王的積極性；能夠?qū)置娴钠遄拥囊苿于厔莞訙蚀_和有效，選擇出最優(yōu)的落子方法。

3.3 搜索算法

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

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

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

4 結(jié)束語

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

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