鄭昌松+賈麗娟+權(quán)賀+王彪

摘要：為了提高計(jì)算機(jī)博弈水平，以西洋跳棋為研究對象設(shè)計(jì)博弈程序，采用Min-Max搜索算法實(shí)現(xiàn)對博弈樹的搜索，根據(jù)α-β剪枝算法研究博弈樹的估值深度，設(shè)計(jì)了搜索深度可以剪枝的博弈模型，該博弈模型解決了博弈程序布局方式、估值深度和搜索耗時等問題，提高了程序搜索效率和博弈性能，博弈程序在全國大學(xué)生博弈比賽中獲得二等獎，在實(shí)際中得到了檢驗(yàn)和應(yīng)用，比賽結(jié)果表明了該博弈模型是可行和有效的。

關(guān)鍵詞：計(jì)算機(jī)博弈；深度；搜索；布局；博弈樹

DOI：10.15938/j.jhust.2016.03.005

中圖分類號：TP311 文獻(xiàn)標(biāo)志碼：A 文章編號：1007-2683（2016）03-0024-05

0引言

當(dāng)前計(jì)算機(jī)博弈正越來越受到歡迎，它所具有的復(fù)雜性和挑戰(zhàn)性吸引了許多學(xué)生和學(xué)者前去研究，西洋跳棋也稱為國際跳棋，目前64格西洋跳棋已被研究完善，100格西洋跳棋其復(fù)雜性和難度都有所提升，布局和估值深度是當(dāng)前主要的問題，搜索效率也是沒有完全解決的難點(diǎn)，因此，人們更多地專注于100格西洋跳棋算法上的研究，100格西洋跳棋雙方子力較多，布局變化萬千，走法更是多種多樣，本文致力于研究布局、估值和搜索，運(yùn)用博弈樹理論、極大一極小值搜索、虛擬靜態(tài)估值等方法設(shè)計(jì)一種比較完善方案提高博弈水平，

1西洋跳棋的規(guī)則與棋盤

本文中提到的西洋跳棋是指100格西洋跳棋。

1.1基本規(guī)則

西洋跳棋規(guī)則相對比較復(fù)雜，棋盤是100格，上面有50個格可供棋子行走，如圖1所示。對弈雙方各有20顆普通棋子，當(dāng)對方普通棋子走到自己方底線時就成為王子。在行棋過程中普通棋子只能向前走，當(dāng)棋子具備連殺條件時必須連殺，當(dāng)局面存在能吃掉對方棋子時必須吃子；王子可以向任意方向移動，比普通棋子更具有攻擊力和防御力。當(dāng)一方棋子被吃完或者沒有可以移動的棋子時該方就輸了。

1.2棋盤表示

西洋跳棋棋盤在程序中的常用表示方法有兩種：一是二維數(shù)組表示棋盤，二是用比特棋盤。其中二維數(shù)組表示棋盤簡單直觀，易于訪問，操作簡單，比特棋盤訪問效率高于數(shù)組棋盤，但是綜合考慮各自優(yōu)缺點(diǎn)后，本文選用10×10二維數(shù)組表示棋盤。

如圖1所示，共有10×10個方格，故用10×10的（int型）二維數(shù)組表示，其中：0表示空白（無棋子），1表示黑棋，2表示黑王，-1表示白棋，-2表示白王，當(dāng)普通棋子成王后，其棋子圖形會由圓形變成正方形以區(qū)分普通棋子與王，即黑王用一個黑色正方形表示，白王用一個白色正方形表示。

2西洋跳棋的走法生成

走法生成用專門的走法生成函數(shù)表示，生成函數(shù)包含西洋跳棋基本規(guī)則，行棋時必須嚴(yán)格遵循這些規(guī)則，它是程序正確博弈的保證。走法生成函數(shù)本身不產(chǎn)生任何行棋信息，它只負(fù)責(zé)按規(guī)則行棋。當(dāng)布局函數(shù)、估值函數(shù)和搜索函數(shù)配合完成后會產(chǎn)生最優(yōu)走法的相關(guān)信息，然后把這些函數(shù)傳遞給走法生成函數(shù)，最后由走法生成函數(shù)行棋，如圖2所示。

2.1布局

布局是走法生成的關(guān)鍵部分，特別是開局決定著棋局后續(xù)發(fā)展的好壞。西洋跳棋棋子數(shù)量較多，布局時可以運(yùn)用大量戰(zhàn)術(shù)配合行棋規(guī)則，在博弈中往往可以反敗為勝，使博弈時戰(zhàn)斗激烈，精彩紛呈。布局既要考慮雙方子力的差別，又要考慮當(dāng)前這一步棋走完后對整個棋局的影響。布局可以采用虛擬走法，把每一顆能走棋子所有能走的方式都模擬走一遍，對走完后的局面做出評判，從所有能走方式中選取最優(yōu)方式。布局時需要考慮的因素很多，要對局勢整體把握，綜合考慮，可運(yùn)用的戰(zhàn)術(shù)多種多樣。例如布局可以利用能殺子時必須殺子規(guī)則來設(shè)置陷阱，犧牲一顆棋子換取對方多顆棋子，布局深度是決定棋局勝敗的一個重要因素，行棋時要考慮棋局的未來發(fā)展。西洋跳棋是一種具有深度搜索的棋種，一步行棋往往能決定局勢優(yōu)劣甚至成敗，估值深度可采用追蹤方式，對能夠移動的棋子各種行走軌跡追蹤到底，分析該步行棋走后對后續(xù)局面造成什么影響。布局過程通過布局函數(shù)完成，完整的布局過程如圖3所示。

3.2估值

在行棋過程中行棋者需要時刻掌握棋局的發(fā)展，掌握行棋方處于優(yōu)勢還是劣勢，從而根據(jù)局勢的優(yōu)劣布局，估值可以分為靜態(tài)估值和動態(tài)估值，估值方式采用估值函數(shù)評分，每個函數(shù)中有評分標(biāo)準(zhǔn)且相互之間不影響，分?jǐn)?shù)可正可負(fù)可為零，棋子模擬行棋后調(diào)用估值函數(shù)評出相應(yīng)的分?jǐn)?shù)，估值時先把我方每一顆能走的棋子和能行走的方式都模擬走出來，再調(diào)用靜態(tài)估值函數(shù)和動態(tài)估值函數(shù)給該模擬行棋估分并記錄分?jǐn)?shù)與行棋方式，找出所有方式中最高的分?jǐn)?shù)，再比較所有能行走方式棋子中分?jǐn)?shù)最高的棋子分?jǐn)?shù)和行棋方式，最后生成相應(yīng)的走法。估值過程如圖4所示。

2.2.1靜態(tài)估值

靜態(tài)估值時要考慮行棋過程中的多種特性，但估值深度有限，需要動態(tài)估值共同配合完成整個估值過程。

1）靜態(tài)估值。行棋過程中，特性考慮的越多越完善，估值就越好。經(jīng)過反復(fù)研究，本文主要考慮幾種典型的特性進(jìn)行研究。例如棋子分布陣型、棋子數(shù)量、子力分布、王的數(shù)量等。單個估值函數(shù)有獨(dú)立的評分公式，依據(jù)各自的性能評分。特性估值函數(shù)采用計(jì)算雙方特性差的方式，如雙方棋子數(shù)量差、具有攻擊力棋子數(shù)量差等，以求獲得比較完整的估值信息。例如子力估值函數(shù)評分公式可以采用式（1）～（4）。value_1、value_2、value_3代表子力估值函數(shù)中棋子數(shù)量、具有攻擊力棋子數(shù)量以及具有防御力棋子數(shù)量所占的權(quán)重；Fen_value表示加權(quán)后算出的分值。根據(jù)局勢發(fā)展，這些權(quán)重會根據(jù)棋子數(shù)量、位置等動態(tài)改變值的大小。因?yàn)槠遄釉谄灞P不同位置，面臨不同陣型等因素都會使其具有不同價(jià)值，我們在估值時必須時刻給其打分才能比較完善的評出有價(jià)值的分?jǐn)?shù)，其它特性估值函數(shù)都是運(yùn)用相同的原理。

2）靜態(tài)估值深度。靜態(tài)估值只考慮一步范圍內(nèi)的行棋估值，當(dāng)行棋方模擬走出一步后就調(diào)用靜態(tài)估值函數(shù)評出相應(yīng)的分?jǐn)?shù)。靜態(tài)估值易于實(shí)現(xiàn)，考慮的范圍廣，當(dāng)多個估值一起合作時會大大加強(qiáng)程序的博弈能力，但是靜態(tài)估值畢竟沒有深度，無法預(yù)測自己和對方行棋后對未來局面的影響。所以我們的估值必須要有深度。深度就是當(dāng)我們行一步棋后模擬出對方和自己后面可以行棋的方式，當(dāng)我們模擬完成后會評價(jià)該局面對我們是否有利，如果有利我們在實(shí)際行棋時就走這步棋，反之就放棄這步棋，尋找其它對我們有利的行棋方式。深度對博弈程序來說非常重要，深度決定了博弈程序的思考能力，當(dāng)深度越深時程序看的就越遠(yuǎn)，可以看出對方行棋中的意圖和陷阱并提前預(yù)防，這樣在博弈過程中就可以占有利地位。結(jié)合動態(tài)估值就可以完成深度搜索。

2.2.2動態(tài)估值

動態(tài)估值涉及估值深度，可以通過具有一定搜索算法的博弈樹完成深度搜索。

1）博弈樹。博弈樹是博弈程序設(shè)計(jì)中常用的一種行棋信息載體，它是行棋時生成的一棵可以完成記錄行棋信息的樹。在模擬行棋時模擬棋子所有可以行棋的方式并記錄，樹中每一個結(jié)點(diǎn)代表棋盤上的一個局面，對每一個局面（結(jié)點(diǎn)）根據(jù)不同的走法又產(chǎn)生不同的局面即生出新的結(jié)點(diǎn)，如此不斷直到再無可選擇的走法，即到達(dá)葉子結(jié)點(diǎn)（棋局結(jié)束），博弈樹可以完整的記錄行棋中的信息并將其保存到葉結(jié)點(diǎn)，再通過搜索算法進(jìn)行訪問。

2）動態(tài)估值。在博弈樹中對每一層局面調(diào)用估值函數(shù)評分，找出每一層行棋中最好的行棋方式，記錄每一層最高的分?jǐn)?shù)走法生成，再求出每層的最優(yōu)值。

因?yàn)槲餮筇迤遄訑?shù)量較多，行棋時可以移動的棋子數(shù)量和方式也很多，所以涉及估值深度時要記錄的信息量大，訪問時耗費(fèi)的時間也較多，利用博弈樹可以很好的記錄大量數(shù)據(jù)和快速訪問，再結(jié)合合適的搜索算法能設(shè)計(jì)出很好的估值程序。

2.2.3估值評分

估值最后對所有靜態(tài)估值函數(shù)和所有動態(tài)估值函數(shù)用統(tǒng)一公式評分，即：

可以看出每個權(quán)重大小是固定且相之間不同，這些權(quán)重系數(shù)需要經(jīng)驗(yàn)獲得，權(quán)重的不同說明每個特性估值函數(shù)的重要程度不同，模擬行棋后評出該步行棋的估值分?jǐn)?shù)并記錄。

估值可謂程序的大腦，在博弈過程中大多數(shù)的行棋都是估值決定的，所以估值的好壞直接決定著程序的博弈能力，在設(shè)計(jì)博弈程序的估值部分還可以加入許多其它算法以提高程序的博弈能力。

2.3搜索

搜索相當(dāng)于程序的靈魂，在西洋跳棋博弈中搜索方式有很多，如Alpha-Beta搜索、Min-Max搜索、負(fù)極大值搜索、MTD（λ）搜索及PV搜索等，搜索深度越深，程序就看的越遠(yuǎn)，能力就越強(qiáng)。各種搜索方式都有各自的優(yōu)缺點(diǎn)，經(jīng)過精心考慮比較，本文采用Min-Max搜索，以博弈樹為基礎(chǔ)，結(jié)合Min-Max搜索方式設(shè)計(jì)程序的搜索。

2.3.1 Min-Max搜索

Min-Max搜索是一種比較基本的搜索方法，算法本質(zhì)是白方總是試圖尋找對自己最有利的行棋方式，而黑方總是尋找對白方最不利的行棋方式，如果將白方當(dāng)作極大方，黑方就是極小方，結(jié)合博弈樹Min-Max搜索過程如圖5所示。

在博弈樹搜索過程中，當(dāng)白方搜索該層最大值后停止搜索，向下層搜索黑方最小值，當(dāng)找到該層最小值時停止搜索，向下層搜索白方最大值，如此反復(fù)，直到遍歷完整棵博弈樹。

2.3.2α-β剪枝

生成博弈樹過程中會生成許多葉結(jié)點(diǎn)，但是每一步行棋的時間是需要控制的，如果每一樹枝都進(jìn)行訪問必然會耗費(fèi)CPU大量時間，在博弈過程中如果行一步棋等很長時間是不允許的，所以訪問博弈樹時需要剪枝。剪枝的方式有很多，考慮到剪枝復(fù)雜程度和效率，確定采用α-β剪枝，該剪枝方法原理是設(shè)計(jì)一個評價(jià)函數(shù)，該函數(shù)可以對所有的棋局進(jìn)行評估。當(dāng)評價(jià)函數(shù)值大于0時，表示棋局對我方有利，對對方不利。當(dāng)評價(jià)函數(shù)小于0時，表示棋局對我方不利，對對方有利，而評價(jià)函數(shù)值越大，表示對我方越有利。當(dāng)評價(jià)函數(shù)值等于正無窮大時，表示我方必勝。評價(jià)函數(shù)值越小，表示對我方越不利。當(dāng)評價(jià)函數(shù)值等于負(fù)無窮大時，表示對方必勝。假設(shè)博弈雙方都是高手，在只看一步棋的情況下，我方一定走評價(jià)函數(shù)值最大的一步棋，而對方一定走評價(jià)函數(shù)值最小的一步棋。需要注意的是，在只看一步棋的情況下最好的行棋，從全局來說不一定就最好，還可能很不好，因此為了走出好棋，必須多看幾步，從多種可能狀態(tài)中選擇一步好棋，這就需要有搜索深度，所以也需要剪枝。

α-β剪枝的關(guān)鍵是在生成博弈樹和記錄每層每個葉結(jié)點(diǎn)數(shù)據(jù)的時候記錄每層最大值，當(dāng)后面遍歷博弈樹時只要找到每層的最大值后就停止搜索，轉(zhuǎn)向下一層搜索，這樣在有的層次遍歷中就不需要對所有的葉結(jié)點(diǎn)進(jìn)行遍歷，很大程度上節(jié)約了時間。如圖5所示，在搜索到第3層時，如果之前生成博弈樹時記錄該層最大結(jié)點(diǎn)值是該層c2結(jié)點(diǎn)，那搜索到該結(jié)點(diǎn)時就停止搜索而轉(zhuǎn)向下一層搜索，那c3結(jié)點(diǎn)及其以后的結(jié)點(diǎn)就不再進(jìn)行搜索，該枝就相當(dāng)于被剪掉，再比如搜索到第5層時，e9=9是這層最大值，生成博弈樹記錄第五層結(jié)點(diǎn)值中最大值是9，則當(dāng)搜索到e9結(jié)點(diǎn)時就停止搜索，e9后面的樹枝被剪掉，這樣在我們對博弈樹進(jìn)行搜索時會節(jié)約很多時間，大大提高搜索效率，有利于提高博弈程序搜索深度。

當(dāng)然還有很多剪枝算法，它們各具有其優(yōu)勢，運(yùn)用多種算法的結(jié)合可以設(shè)計(jì)出更好的行棋方案。

3結(jié)論

基于本文研究的博弈模型所設(shè)計(jì)的西洋跳棋程序在2015年第四屆中國大學(xué)生計(jì)算機(jī)博弈大賽中，經(jīng)受住了考驗(yàn)，取得了國家二等獎的好成績。該模型可以作為其它棋類博弈程序的研究基礎(chǔ)。

博弈程序設(shè)計(jì)的3個重要過程是布局、估值和搜索，布局采用虛擬走法，從所有能走方式中選取最優(yōu)方式，最優(yōu)行棋方式是通過靜態(tài)估值函數(shù)和動態(tài)估值函數(shù)記錄每次模擬行棋分?jǐn)?shù)和行棋方式，找出所有方式中最高的分?jǐn)?shù)，再比較所有能行走方式中分?jǐn)?shù)最高的棋子分?jǐn)?shù)和行棋方式，最后生成相應(yīng)的走法，這種把靜態(tài)估值和動態(tài)估值相結(jié)合的方式，使程序在行棋過程中對局面有充分的掌控力。估值深度決定了博弈程序的思考能力，深度越深就會在博弈過程中占有更有利地位，動態(tài)估值時通過博弈樹完整的記錄行棋中的信息并將其保存到葉結(jié)點(diǎn)，再通過Min-Max搜索算法進(jìn)行訪問，生成博弈樹過程中會生成許多葉結(jié)點(diǎn)，但是每一步行棋的時間是需要控制的，所以訪問博弈樹時需要剪枝，考慮到剪枝復(fù)雜程度和效率，采用α-β剪枝提高博弈程序在固定時間里的深度。

本文論述的估值方法可能不是非常完善，靜態(tài)估值特性的種類考慮的有限，我們無法考慮到博弈中所有可能出現(xiàn)的局面，還有因?yàn)橛?jì)算機(jī)執(zhí)行速度問題，隨著搜索深度不斷增加搜索所花費(fèi)的時間會越來越多。

在設(shè)計(jì)博弈程序時還可以加入其它高級算法，如神經(jīng)網(wǎng)絡(luò)算法、歷史啟發(fā)算法等。如果估值時能考慮更多的局面特性，用歷史啟發(fā)算法和α-β剪枝算法結(jié)合對博弈樹進(jìn)行剪枝，將會很大程度提高程序博弈水平，博弈往往和人工智能、機(jī)器學(xué)習(xí)密切相聯(lián)，如果研究深入，完善程序設(shè)計(jì)，那么程序就具有了自我學(xué)習(xí)思考的能力和攻擊實(shí)力，博弈是我們研究人工智能很好的一個平臺，其易于實(shí)現(xiàn)、操作簡單、成本低廉，涉及大量算法，可以將很多的想法通過博弈程序?qū)崿F(xiàn)，為我們研究人工智能打下基礎(chǔ)。