邱虹坤,鄭曉東,王亞杰

(1.沈陽航空航天大學 計算機學院, 沈陽 110136;2.沈陽航空航天大學 工程訓練中心, 沈陽 110136)

0 引言

在圍棋被攻破之后，機器博弈領域現(xiàn)在唯一尚未被攻破的頂級智力運動(按照國際智力運動會的項目)就只剩下橋牌。橋牌博弈中包含的人類行為難以被計算機理解，特別是叫牌部分，短時間內人工智能很難在橋牌上與人類抗衡[1]。在叫牌過程中，有意義的叫品僅有5×7=35種，但配合熟練的橋手通過這些有限叫品，與不同的牌情相結合可以傳遞出大量信息，如圖1所示。對于AI來說，最難的就是如何在這些叫品中，實現(xiàn)牌局信息的傳遞，并且嘗試理解對手之間傳遞的信息甚至加以干擾。

目前橋牌叫牌數(shù)據(jù)庫更多在于如何詳細地描述自然叫牌法或者精確叫牌法，對于構建橋牌叫牌數(shù)據(jù)庫本身的研究較少，并且目前數(shù)據(jù)庫大多未能考慮在實際牌局中人類牌手通過叫品結果想要傳達出來的信息。事實上，對于牌局而言，在不斷達成定約過程中所暴露出來的信息恰恰是最重要的。這是解決橋牌博弈問題，必須要經過的一環(huán)。由此可見，對于能夠存儲牌情信息的數(shù)據(jù)庫的設計與研究非常有必要。

圖1 有意義叫品

1 數(shù)據(jù)預處理

在橋牌開局后，每人分配13張手牌。此時每人所掌握的信息，便只有這13張牌，直至在叫牌過程中通過逐漸溝通牌局信息，信息才初步展露。所以在進行信息溝通之前，要將自己的手牌信息整理好，才能在接下來有限叫品空間中實現(xiàn)更為全面的信息溝通[2]。數(shù)據(jù)預處理流程如圖2所示。

圖2 數(shù)據(jù)預處理流程框圖

由于手牌有限，所以直接可以推斷出來的信息同樣有限，可以將其分為3類信息：

2) 4種花色的K，Q，J均為大牌，在吃墩的時候有很大的潛力，對于牌力的提升起到很大作用，稱它為大概率吃墩。

3) 對于剩余的小牌，通過某些固定配合，如將吃等，仍然可以贏得墩數(shù)。為了盡可能多地分析手牌信息，稱它為小概率吃墩。

引入這些標識的目的在于，在叫牌階段開始前，先通過評估自己的手牌信息，來預測自己能夠達成的定約[3]，為后續(xù)開始叫牌提供扎實的基礎。

2 設計叫牌數(shù)據(jù)庫

2.1 數(shù)據(jù)庫格式

數(shù)據(jù)庫范式分為1NF，2NF，3NF，BCNF，4NF，5NF。符合高一級的范式，必定符合低一級范式。低級的范式容易滿足，但同時有可能帶來一些操作異常[4]。更高級的范式相對穩(wěn)定，但可能帶來處理速度緩慢和處理邏輯復雜的問題。

如果構建符合1NF的數(shù)據(jù)庫，此時同樣的一組手牌信息將會多次重復存儲，造成冗余過大，不利于大量叫牌信息的存儲。當數(shù)據(jù)庫滿足2NF規(guī)則時，如果牌局信息中存在傳遞函數(shù)依賴[5]，則會體現(xiàn)為不同的手牌信息可以間接推出同一個結論，造成了空間浪費。對于符合3NF規(guī)則的數(shù)據(jù)庫，可以認為其在時間和空間上均可以滿足橋牌叫牌數(shù)據(jù)庫的要求。故構建一個符合3NF標準的橋牌叫牌數(shù)據(jù)庫是合理的。

2.2 橋牌叫牌數(shù)據(jù)庫的具體構建

有了數(shù)據(jù)庫的格式規(guī)范后，可以開始設計數(shù)據(jù)庫中表的結構，在橋牌中叫牌結果由叫牌階數(shù)和叫牌花色組成。對于不同的手牌信息，數(shù)據(jù)庫應該返回不同的叫牌結果[6]。這時需要用到的信息有數(shù)據(jù)預處理信息，長套標識，己方預估達成定約的階數(shù)，等等。通過這些信息的多重組合來得到數(shù)據(jù)元素之間的關系，如圖3所示。

圖3 數(shù)據(jù)庫元素關系圖

數(shù)據(jù)庫需要根據(jù)僅有的13張手牌，進行牌力評估，刻畫出此時想要傳達給隊友的信息。比如通過查找對應牌型、牌張信息下的牌力，得到對應推薦的叫牌階數(shù)與花色[7]。同樣，在得到隊友或者對手的回復后，應該通過其反饋的新一輪叫牌階數(shù)與花色繼續(xù)更改自己的期望叫牌。

3 引入合作與競爭向量

在非完備信息博弈中，橋牌由于存在隊友之間的合作與競爭，難以通過已有的算法對其進行表示。這里提出了一種在數(shù)據(jù)庫中，對牌局行為給予合作競爭標識的機制。

通過叫牌方位判斷給予隊友和對手標識。對于北->東->南->西分別標識0,1,2,3。此時設某人行動方位為X，自己行動方位為Y，則 |Y-X|%2=0，此時兩者為隊友，否則為對手。

合作向量主要表達信息為：所要達成的定標位置。如己方在黑桃上點力強勁，隊友叫到3，己方發(fā)現(xiàn)自己上牌力同樣優(yōu)秀，此時直接叫到5，甚至更高。這本身是無可厚非的，但會導致本來可以傳遞更多信息的叫牌空間被浪費[8]。在叫牌中叫牌空間共35格，所以為了能夠節(jié)約叫牌空間，在合作關系中引入一個“over”標志偽代碼為：

while(pass數(shù)量<3):

{

over->0

if BIDnext.order-BIDnow.decor>1：

over->1

BID賦予其他含義

else:

BID表示當前所叫牌的花色與階數(shù)

}

圖4 叫品機會損失示意圖

通過合作向量的使用，可以最大限度地發(fā)揮橋牌叫品的信息傳遞功能，通過空分復用的方式來表達多種含義，增加了有限叫牌空間中叫牌意義的表示能力[10]。

競爭向量主要用來對敵方叫牌信息進行干擾，通過觀察連續(xù)出現(xiàn)次數(shù)最多的相關花色，判斷對方想要達成的花色優(yōu)先級。偽代碼為：

While(pass數(shù)量<3)

{

Init花色優(yōu)先級隊列

If (|Y-X|%==2):

{

開發(fā)者應及時在微信推送下方留言區(qū)與讀者進行互動，這樣有利于了解讀者的想法，采納讀者的建議，并據(jù)此完善公眾號的服務。

記錄敵方連續(xù)叫品:

記錄每個花色出現(xiàn)次數(shù)

}

update花色優(yōu)先級隊列

if：(敵方優(yōu)先級最高花色=我方)

do：合作

else：{

敵方當前花色優(yōu)先級降低

}

}

此時將合作與競爭向量和花色優(yōu)先級隊列融合引入數(shù)據(jù)庫中，使得數(shù)據(jù)可以表達此時牌局中的對局情況，通過記錄合作與競爭之間的次數(shù)來更詳細地表達當前牌局信息。

4 引入模糊數(shù)學

4.1 模糊數(shù)學在橋牌上的理解

模糊數(shù)學是解決界限不分明問題的數(shù)學工具，被廣泛應用于模糊決策、模糊識別等領域。而橋牌比賽的叫牌階段中，橋手會將自己手牌的信息傳遞給自己隊友或者用其來迷惑對手，此時某單一叫品所能表達的含義是模糊的，無法通過一一對應的方式描述。同理，在對手之間捕捉到的信息，往往與表面上看到的不符。此時信息的特點可以歸結為非單一和非具體的，由此觀之，橋牌叫牌中展現(xiàn)出的模糊性是不可避免的。

但是這不應該理解為“模模糊糊”，基于模糊數(shù)學的思想來解決橋牌叫牌問題應該理解為：通過精確的數(shù)學手段對橋牌叫牌所表達的信息進行刻畫，并且該刻畫過程應該是極為嚴密的。

4.2 模糊數(shù)學在橋牌上的應用

橋牌的叫牌部分無法通過的二值邏輯對其進行描述，此時引入模糊數(shù)學中的一個重要概念——模糊集合[11]。對于模糊集合來說，給定范圍內元素具有隸屬關系，對于它的隸屬關系不能通過簡單的“是”或“否”來表示，而應該用一段區(qū)間來刻畫其隸屬程度。

如表1所示，當獲得同伴想要達成的階數(shù)信息時，結合己方手牌牌力，以不同概率的形式將己方的支持程度傳遞出去。值得注意的是，事實上這里的概率應該與手牌的牌力、牌情等信息存在某種函數(shù)關系，這一過程會涉及很多專業(yè)橋牌知識。在這里只通過人為經驗給出部分區(qū)間下，不同應答的隸屬程度。

表1 叫牌階數(shù)信息表

手牌的牌力直接影響著最終能否達成的定約高度，手牌的牌張信息影響著最終定約停留的花色。越是強力的花色，越希望最終定約可以停留在此花色上。同樣，這種希望也不是單一的，即可能希望停留在，又希望停留在，但這2個希望的概率是不一樣的。通過不同花色優(yōu)先級對希望的隸屬程度進行刻畫[12]。叫牌花色信息如表2所示。

表2 叫牌花色信息表

此時，通過引入模糊數(shù)學中模糊集合的概念，使用不同的隸屬關系來解釋橋牌叫牌過程中同一叫品表現(xiàn)不同含義的情景，并通過經驗分析給出不同情景下所對應的隸屬程度值。

5 實驗測試

5.1 對比結果說明

新數(shù)據(jù)庫與傳統(tǒng)自然叫牌法或精確叫牌法對應的數(shù)據(jù)庫在存儲信息能力上的對比：

1) 使用更少的存儲單元：自然叫牌法需要將4種花色的手牌數(shù)量全部存儲。事實上更應該關心的是不同花色之間的強弱之分，牌張更多、牌點更強勁的花色顯然更值得達成定約。此時可以用一個花色優(yōu)先級來取代4種花色的手牌數(shù)量。(注：這里花色優(yōu)先級所對應的數(shù)字，是將4種花色的牌力優(yōu)先級按照S，H，D，C進行排序的一種排列組合，如1對應S>H>D>C，2對應S>H>C>D，這樣相當于用1個存儲單元存儲了傳統(tǒng)數(shù)據(jù)庫中4個存儲單元的信息。)

2) 增加合作與競爭關系：新數(shù)據(jù)庫增加了額外含義標識。對遇到對手和隊友叫牌的不同情況可以回應不同叫品，使有限的叫品空間被充分利用。

3) 與數(shù)據(jù)預處理關系密切：由于加入數(shù)據(jù)預處理部分，新數(shù)據(jù)庫的表達能力與數(shù)據(jù)預處理的結果聯(lián)系密切。這意味著在數(shù)據(jù)預處理部分的能力越強，數(shù)據(jù)庫的存儲信息能力也變得越強。而傳統(tǒng)數(shù)據(jù)庫能力僅與自然叫牌法，或精確叫牌法相關。

4) 引入模糊數(shù)學概念：傳統(tǒng)數(shù)據(jù)庫每條記錄嚴格對應一個結果，而在任何一種牌局的情況下，叫品結果應該有多種可能性。這里通過經驗對這種可能性予以評估，能夠更真實刻畫牌局情況。

5.2 實例分析

這里隨機生成一副手牌，如圖5所示，對其進行叫牌分析(以開叫為例)。

圖5 隨機手牌

此副手牌大牌點為4+3+2+1+1=11(A=4，K=3，Q=2，J=1；10及以下的牌不計算點力)，牌型為5-4-2-2。精確叫牌法所對應數(shù)據(jù)庫格式如表3所示。

表3 精確叫牌法對應傳統(tǒng)數(shù)據(jù)庫格式(開叫為例)

此時按照精確叫牌法應該選擇1H?？梢詡鬟f出來的信息有：牌點在11～15之間，紅桃有5張?zhí)?。對應在?shù)據(jù)庫中則會經過如下分析：

表4 新數(shù)據(jù)庫對應格式(開叫為例)

該數(shù)據(jù)庫格式可以傳遞出來的信息有：在這副手牌中一定能打贏的牌有幾張、大概率打贏的有幾張、有幾率打贏的有幾張。這副牌預期能夠達到某種定約、達到這個定約的概率是多少。相較于傳統(tǒng)的自然、精確叫牌法數(shù)據(jù)庫所能存儲、表示的信息更為豐富。此外，由于數(shù)據(jù)預處理與概率的引入，計算機可以通過計算來更準確了解此時牌局的進行過程。而這部分，更取決于預處理部分以及隸屬函數(shù)的準確程度，可以通過計算機強大的算力和橋手的豐富經驗可以提升，使其不再僅僅局限于叫牌體系的擴充。

當然，引入了模糊集合概念之后，同樣也帶來了新的問題，比如不同手牌信息下對應的隸屬程度數(shù)值應該與手牌信息存在某種函數(shù)關系，而不是單一的某些區(qū)間某些值。這些需要更多的橋牌專業(yè)知識來支持，通過具體分析多種牌局實例，來構建不同狀態(tài)下，對應吃墩可能性的函數(shù)關系。此外，若數(shù)據(jù)庫擴展到一定規(guī)模后，可能會存在搜索超時等問題，這些都需要后續(xù)繼續(xù)研究。

6 結論

本文將數(shù)據(jù)庫智能化的思想與橋牌叫牌數(shù)據(jù)庫構建相結合，通過引入更多元素實現(xiàn)對于橋牌叫牌過程更為詳細的刻畫。通過概率問題，對叫牌中存在的單一叫品傳遞多種信息問題進行解決，是解決橋牌問題中的模糊性的重要一步。

數(shù)據(jù)庫能夠表示越多、越詳細的信息，可以使橋牌AI環(huán)節(jié)減輕負擔。此時AI可以更多地將注意力放在算法上，一定程度上忽略底層橋牌規(guī)則。相較于人類橋牌選手之間的默契配合，該數(shù)據(jù)庫還有很大優(yōu)化空間，捕捉更多的動作細節(jié)進行描述，使AI能夠更貼切地模擬人類選手打牌。