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

徐玉朋+朱明富

摘 要：在分析麻將游戲基本規則的基礎上，引入BDI推理模型，構建了一種麻將游戲機器人結構，介紹了對機器人信念、愿望、目標等元素的實現，并提出一種游戲中機器人的使用策略，為不同規則的麻將游戲機器人開發提供參考。

關鍵詞：BDI推理模型；麻將；游戲機器人

DOIDOI：10.11907/rjdk.171235

中圖分類號：TP319

文獻標識碼：A 文章編號：1672-7800（2017）007-0090-03

0 引言

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

1 BDI推理模型

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

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

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

2 麻將游戲機器人建模

2.1 麻將游戲基本規則

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

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

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

2.2 機器人結構建模

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

3 機器人實現

3.1 麻將值表示

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

3.2 狀態集

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

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

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

玩家的狀態集表示為：

3.3 目標集

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

3.4 策略庫

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

3.5 意圖集

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

3.6 行為集

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

3.7 執行器

執行器將要執行的動作及牌值按規定的協議打包好后，調用外部接口將動作請求發送給游戲邏輯控制單元。

4 策略分析

4.1 重排算法

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

R：A → （Ar，p）

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

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

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

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

4.2 手中牌狀態計算

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

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

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

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

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

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

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

（5） 若ai的張數僅有1張，則轉到（2），否則轉到（6）。

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

（7） 結束。

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

4.3 目標篩選策略

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

4.4 目標分解策略

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

5 結語

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

參考文獻：

[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].系統仿真學報，2012，24（5）：1076-1081.

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

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