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

桂義勇

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

0 引 言

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

1 國(guó)際跳棋規(guī)則簡(jiǎn)述

1.1 棋盤表示

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

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

1.2 走棋規(guī)則

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

圖1 國(guó)際跳棋棋盤Fig.1 Checkers board

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

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

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

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

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

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

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

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

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

圖5 對(duì)弈流程圖Fig.5 Game flow chart

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

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

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

3.1 局面評(píng)估算法

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

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

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

3.2 棋盤價(jià)值矩陣

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

黑棋的價(jià)值矩陣為

白棋的價(jià)值矩陣為

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

如果只是通過靜態(tài)評(píng)估算法會(huì)造成送子太多、不積極稱王和兵落后等問題。 對(duì)這些問題通過增加棋子的價(jià)值矩陣，能夠有效的改善靜態(tài)評(píng)估算法出現(xiàn)的問題，對(duì)己方的棋子起到保護(hù)防守的作用；能有效地向?qū)Ψ桨l(fā)起進(jìn)攻，提高了棋子稱王的積極性；能夠?qū)置娴钠遄拥囊苿?dòng)趨勢(shì)更加準(zhǔn)確和有效，選擇出最優(yōu)的落子方法。

3.3 搜索算法

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

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

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

4 結(jié)束語

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

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