基于BDI推理模型的麻將游戲機器人設(shè)計

徐玉朋+朱明富

摘 要：在分析麻將游戲基本規(guī)則的基礎(chǔ)上，引入BDI推理模型，構(gòu)建了一種麻將游戲機器人結(jié)構(gòu)，介紹了對機器人信念、愿望、目標(biāo)等元素的實現(xiàn)，并提出一種游戲中機器人的使用策略，為不同規(guī)則的麻將游戲機器人開發(fā)提供參考。

關(guān)鍵詞：BDI推理模型；麻將；游戲機器人

DOIDOI：10.11907/rjdk.171235

中圖分類號：TP319

文獻(xiàn)標(biāo)識碼：A 文章編號：1672-7800（2017）007-0090-03

0 引言

麻將游戲深受人們喜愛，網(wǎng)絡(luò)載體的麻將游戲有著廣泛的群眾基礎(chǔ)，設(shè)計能夠與玩家互動的麻將游戲機器人具有廣闊的應(yīng)用前景。作為真實玩家的對手，機器人的表現(xiàn)直接影響著游戲的趣味性，由于機器人是計算機操控的角色，開發(fā)人員可以為機器人賦予真人玩家沒有的能力，例如獲取別的玩家手中牌的信息。受商業(yè)元素影響，為了縮短產(chǎn)品開發(fā)周期，這種作弊手段在現(xiàn)有網(wǎng)絡(luò)麻將游戲開發(fā)中常常用到。該開發(fā)方法有一定優(yōu)勢，但與真實世界的脫離會降低玩家對游戲的認(rèn)同感，進(jìn)而影響市場占有率，故不可取。BDI模型已經(jīng)被證實符合正常人的推理思維，因此，設(shè)計基于BDI推理模型的麻將游戲機器人是很好的選擇。

1 BDI推理模型

20世紀(jì)80年代，M E Bratman[1]在斯坦福大學(xué)的理性Agent項目研究中提出了信念—愿望—意圖（Belief-Desire-Intention，BDI）模型。在Bratman工作的基礎(chǔ)上，Cohen和Levesque[2]構(gòu)建了基于正規(guī)模態(tài)邏輯的BDI模型，而Rao和Georgeff[3]則采用計算樹邏輯對BDI模型的組成與推理作了更詳細(xì)的刻畫。BDI模型結(jié)構(gòu)是慎思型Agent的主要結(jié)構(gòu)，信念、愿望、意圖是Agent的3種心智狀態(tài)。信念是Agent對世界的認(rèn)知，代表著對獲得信息的一種評價；愿望是Agent希望達(dá)到的一種事件狀態(tài)，是Agent的一些可選目標(biāo)集合，并且這些目標(biāo)可以是相互沖突的；意圖是Agent當(dāng)前想要達(dá)到的工作狀態(tài)，可以是愿望中的一個。BDI推理過程如圖1 所示。

目前，關(guān)于BDI推理模型的研究方法主要有兩種，一是基于邏輯系統(tǒng)對BDI推理模型的研究和擴展[4]，二是從應(yīng)用角度利用BDI推理模型進(jìn)行仿真研究[5]和實用系統(tǒng)開發(fā)[6]。仿真研究多借助于現(xiàn)有成熟的仿真平臺，如Netlog、Jade、Jack等，實用系統(tǒng)的開發(fā)多基于現(xiàn)有的開發(fā)平臺，如Microsoft Agent。

BDI模型符合正常人的思維過程，但BDI模型只提供一個抽象的模式化結(jié)構(gòu)，在具體應(yīng)用中如何將BDI推理模型中抽象的組成實例化是開發(fā)工作人員面臨的問題，麻將游戲機器人的設(shè)計也不例外。

2 麻將游戲機器人建模

2.1 麻將游戲基本規(guī)則

各地的麻將游戲融合了當(dāng)?shù)厝说闹腔?，?guī)則略顯不同，但具有通用的麻將游戲基本規(guī)則。麻將按花色分為條萬筒3種序數(shù)牌、東西南北4種風(fēng)字牌，以及中發(fā)白3種箭牌。每種序數(shù)牌由1到9組成，共27種，每種牌有4張，整副牌共（3*9+4+3）*4=136張。玩家共有4人，開局后每個玩家分發(fā)13張牌。從莊家開始，獲得牌權(quán)的玩家做動作，獲得牌權(quán)的方式有順序獲取、碰、吃、杠4種。獲得牌權(quán)的玩家如果手中牌的數(shù)目除以3余1，則先從牌堆中取出一張，然后出牌，直至贏牌或者牌堆剩余數(shù)目低于約定數(shù)目（一般為1）。

贏牌牌型必須符合m*AAA+n*ABC+DD的形式，其中m、n可以為0 。玩家游戲的過程可以描述為通過不斷替換手中的牌，直至達(dá)到贏牌狀態(tài)。

麻將游戲是棋牌類游戲的代表，棋牌游戲具有離散事件、動態(tài)系統(tǒng)的特點，其狀態(tài)變化均發(fā)生在離散的時間點[7]。麻將游戲的參與者都要遵守游戲規(guī)則，機器人也不例外，故機器人的行為是受限的，其做出的每一個行為都要包含于有限的可選動作集中。

2.2 機器人結(jié)構(gòu)建模

圖2為根據(jù)BDI推理模型構(gòu)建的機器人結(jié)構(gòu)，感知器捕獲觸發(fā)此機器人的消息，并更新記憶庫和行為集；狀態(tài)集存儲機器人對當(dāng)前牌局的認(rèn)識，是形成目標(biāo)的依據(jù)；記憶庫表示機器人對已經(jīng)發(fā)生的事件的記憶，包含自己手中牌、玩家已出牌、不確定牌，其中不確定牌可能在牌堆中，也可能在別的玩家手中；規(guī)則庫則存儲牌局規(guī)則，如贏牌的判斷方法；行為集中為當(dāng)前機器人可以執(zhí)行的行為提示，如吃牌、杠牌、出牌，機器人的行為必須從行為集中選擇；更新器負(fù)責(zé)根據(jù)當(dāng)前狀態(tài)集、記憶庫以及規(guī)則更新目標(biāo)集和狀態(tài)集。目標(biāo)為Agent可以達(dá)到的某種理想狀態(tài)，目標(biāo)集中有多個目標(biāo)，每個目標(biāo)的實現(xiàn)難度不同，有的永遠(yuǎn)不能實現(xiàn)。篩選器對目標(biāo)集進(jìn)行篩選，得到一個或一組具有共性的目標(biāo)；分解器根據(jù)策略進(jìn)行目標(biāo)分解，得到諸多可一步達(dá)到的狀態(tài)，存入意圖集；最后匹配器將行為集中的行為與意圖集中的意圖相匹配，做出可執(zhí)行的動作交由執(zhí)行器執(zhí)行。在該結(jié)構(gòu)中，規(guī)則庫、記憶庫、行為集、狀態(tài)集和策略庫共同構(gòu)成機器人的信念。

3 機器人實現(xiàn)

3.1 麻將值表示

麻將牌值用一個字節(jié)表示，高4位表示花色，其中0-萬，1-條，2-筒，3-箭或風(fēng)，低4位表示牌值，序數(shù)牌低4位值大小即為牌值大小。若花色值為3，則牌值1～7依次表示為東南西北中發(fā)白。

3.2 狀態(tài)集

對于相同花色的一個牌的序列，可以通過將其中的一些牌剔除并增加一些牌的方式，使該序列能夠組成m*AAA+n*ABC的完整形式。剔除牌的張數(shù)和需要獲得牌的張數(shù)組成了p=（m，n）的形式，可以稱之為出取對。其中m為出數(shù)，表示剔除牌的張數(shù)；n為取數(shù)，表示需要取得牌的張數(shù)。

玩家手中牌最多有4種花色，將每種花色牌的狀態(tài)用如下五元組表示：

其中，A為該花色牌組成的序列。在贏牌狀態(tài)下，可以將玩家手中牌的花色按是否是對子的花色分為兩類；Ar為當(dāng)不把該花色作為對子花色時，按出牌優(yōu)先級由低到高重排后的序列 ；p為達(dá)到贏牌狀態(tài)需要完成的出取對；Ar′為當(dāng)不把該花色作為對子的花色時，按出牌優(yōu)先級由低到高重排后的序列；p′為達(dá)到贏牌狀態(tài)需要完成的出取對。endprint

玩家的狀態(tài)集表示為：

3.3 目標(biāo)集

設(shè)padd=p0+p1+p2+p3，pwini=padd-pi+pi′。玩家的目標(biāo)是贏牌，當(dāng)一個或多個pwini（i=0，1，2，3）出數(shù)和取數(shù)之和為0時，即為贏牌狀態(tài)。玩家希望的贏牌方式組成了目標(biāo)集。在實現(xiàn)中，用一個字節(jié)表示目標(biāo)集，只利用目標(biāo)字節(jié)的低4位，每一位上置位和清零分別表示對該位代表的贏牌方式是否堅持。例如，0x03表示玩家的目標(biāo)是以萬字牌或條子牌為對子的贏牌方式。

3.4 策略庫

策略庫中分為3部分內(nèi)容：①計算出取對的方法，供更新器調(diào)用；②目標(biāo)篩選方法，目標(biāo)集中目標(biāo)達(dá)成的可能性取決于當(dāng)前狀態(tài)，這部分方法從目標(biāo)集中選擇一個“合理”的目標(biāo)，供篩選器調(diào)用；③目標(biāo)分解方法，最終得到一個出牌序列，供分解器調(diào)用。具體策略將在下文作詳細(xì)分析。

3.5 意圖集

由篩選器得到花色的重排序列Ar和Ar′為玩家出牌提供了優(yōu)先級，p和p′為出牌張數(shù)和取牌張數(shù)，二者共同組成了玩家的意圖集。

3.6 行為集

行為集為機器人當(dāng)前可以選擇的動作，在實現(xiàn)中用一個字節(jié)表示，字節(jié)中的每一位分配給一個動作，置位為可以執(zhí)行，清零為不可執(zhí)行，匹配器即可將行為集字節(jié)與定義的動作及操作判斷為是否可以執(zhí)行。

3.7 執(zhí)行器

執(zhí)行器將要執(zhí)行的動作及牌值按規(guī)定的協(xié)議打包好后，調(diào)用外部接口將動作請求發(fā)送給游戲邏輯控制單元。

4 策略分析

4.1 重排算法

玩家手中的牌按花色分成了4個序列A0、A1、A2、A3，下標(biāo)表示花色。重排算法表示為：

R：A → （Ar，p）

A為重排之前牌的序列，Ar是重排后的序列，p=（m，n）為出取對。算法步驟為：

對于風(fēng)字牌和箭字牌：①初始化Ar為空，p=（0，0）；②先將張數(shù)為3或4的牌依次從A中取出3張放入Ar；③剩余牌中張數(shù)為2且可以再得的牌取出放入Ar，每放一次取數(shù)加1 ；④剩余牌中張數(shù)為2且不可以再得的牌取出放入Ar，每放一次出數(shù)加2；⑤剩余的牌全為單張，按照可再得張數(shù)從多到少放入Ar，每放一次出數(shù)加1；⑥結(jié)束。

對于序數(shù)牌，每次按牌值從小到大遍歷：①初始化Ar為空，p=（0，0）；②將三連張且不多余的牌取出按順序放入Ar；③將3 或4張的牌取出3張，按順序放入Ar；④將三連張有多余的牌按完整的三連張取出按順序放入Ar；⑤將2張且可以再得的牌取出按順序放入Ar，每次取數(shù)加1；⑥將2張且不可以再得的牌取出按順序放入Ar，每次出數(shù)加2；⑦剩余的牌全為單張，按照可再得張數(shù)從多到少放入Ar，每放一次出數(shù)加1。

對手中牌按花色分別重排，得到一組重排后的序列Ar0、Ar1、Ar2、Ar3和一組出取對p0、p1、p2、p3。

4.2 手中牌狀態(tài)計算

出取對比較算法：設(shè)M=（p1，q1），N=（p2，q2），若p1+q1*2N，否則M≤N。

設(shè)A為玩家手中某一花色所有牌的組成序列，Ar為重排后的序列，p為重排后得到的出取對，Ar′為從中挑出一張或兩張相同牌值的牌后的重排序列，p′為對應(yīng)的出取對。下面介紹由A得到Ar′和p′的算法。

若A為空，則Ar′為空，p′=（0，0）；若A不為空，設(shè)A中牌按牌值從小到大無重復(fù)排列成a1a2…an，出取對初始值為p′=MAX=（14，14）。

（1） 初始值i=0，Ar′為空。

（2） i=i+1，若i>n，則轉(zhuǎn)到（7）。

（3） 若手中僅有1張ai且不可能再得一張，則轉(zhuǎn)到（2）。

（4） 少計一張ai對剩余該花色牌進(jìn)行一遍重排，得到一個出取對（m，n）和序列 At，將p′與（m，n+1）比較，取小的值為p′，Ar′=At。

（5） 若ai的張數(shù)僅有1張，則轉(zhuǎn)到（2），否則轉(zhuǎn)到（6）。

（6） 少計兩張ai對該花色剩余牌進(jìn)行一遍重排，得到一個出取對（m，n）和序列 At，將p′與（m，n）比較，取小的值為p′，Ar′=At，然后轉(zhuǎn)到（2）。

（7） 結(jié)束。

按上述步驟得到4個花色的另一組重排后的序列Ar0′、Ar1′、Ar2′、Ar3′和一組出取對p0′、p1′、p2′、p3′。當(dāng)某種花色牌的記憶發(fā)生變動時，僅對該花色的狀態(tài)si作更新即可。

4.3 目標(biāo)篩選策略

目標(biāo)篩選即從各花色中選擇一個，本設(shè)計中的策略是先由pwini（i=0，1，2，3）得到4個出取對，然后選出出數(shù)與取數(shù)之和最小的花色i。

4.4 目標(biāo)分解策略

基本篩選方法即為目標(biāo)分解策略。選擇目標(biāo)花色i后，對于不為i的花色j，達(dá)到目標(biāo)需要將Ar中后pj的出數(shù)張牌打出，并得到pj的取數(shù)張牌與該花色剩余的牌組成三連張或三同張的組合。對于花色i，達(dá)到目標(biāo)需要將Ar′中后pi′的出數(shù)張牌打出，并得到pi′的取數(shù)張牌與該花色剩余的牌組成三連張或三同張的組合。這些出與取的目的即組成了意圖集。

5 結(jié)語

本文從人的思維推理過程角度對麻將游戲機器人進(jìn)行研究，引入BDI推理模型構(gòu)造麻將游戲機器人。通過分析麻將游戲規(guī)則，提出一種基于BDI推理模型的機器人結(jié)構(gòu)，并對機器人的各個組件作了詳細(xì)的設(shè)計描述，最后提出一種麻將游戲推理策略。本設(shè)計的優(yōu)點在于實例化的BDI推理模型結(jié)構(gòu)清晰，對真實玩家作了模擬，并且策略集中的方法可以替換，使設(shè)計具有可擴展性。更進(jìn)一步的研究需求是引入情緒、性格等非確定性因素，以體現(xiàn)機器人的個性化。

參考文獻(xiàn)：

[1]M E BRATMAN.Intention，plans，and practical reason[M].Cambridge University Press，1987.

[2]COHEN P，LEVESQUE H.Intention is choice with commitment[J].Artificial Intelligence，1990，42（3）：213-261.

[3]RAO A S，GEORGEFF M.BDI agents from theory to practice[C].Proceedingsof the first Conference on Multi-agent System，San Francisco，USA：ACM Press，1995： 312-319.

[4]張曉君，周昌樂.情感等級BDI主體模型研究[J].模式識別與人工智能，2013，7（26）：615-622.

[5]李明峰，李全軍，查亞兵，等.基于BDI的CGF通信行為建模[J].系統(tǒng)仿真學(xué)報，2012，24（5）：1076-1081.

[6]陳童洋，韓玉合，谷新蕾，等.基于BDI的智能垃圾清理系統(tǒng)[J].軟件，2012，33（9）：61-62.

[7]徐心和.棋牌游戲與事件對策[J].決策與控制，2007，22（7） ：787-789.