邱虹坤,鄭曉東,王亞杰

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

0 引言

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

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

圖1 有意義叫品

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 引入合作與競爭向量

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

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

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

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

{

over->0

if BIDnext.order-BIDnow.decor>1：

over->1

BID賦予其他含義

else:

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

}

圖4 叫品機會損失示意圖

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

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

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

{

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

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

{

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

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

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

}

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

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

do：合作

else：{

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

}

}

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

4 引入模糊數(shù)學(xué)

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

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

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

4.2 模糊數(shù)學(xué)在橋牌上的應(yīng)用

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

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

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

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

表2 叫牌花色信息表

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

5 實驗測試

5.1 對比結(jié)果說明

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

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

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

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

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

5.2 實例分析

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

圖5 隨機手牌

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

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

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

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

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

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

6 結(jié)論

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

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