邱虹坤，鄭曉東，王亞杰

(沈陽(yáng)航空航天大學(xué) a.計(jì)算機(jī)學(xué)院;b.工程訓(xùn)練中心，沈陽(yáng) 110136)

機(jī)器博弈是人工智能領(lǐng)域最重要的研究方向之一，而非完備信息博弈是近期機(jī)器博弈研究的熱點(diǎn)。現(xiàn)實(shí)生活中，處處充滿了非完備信息博弈的例子，如拍賣、投標(biāo)、競(jìng)價(jià)等。其中，投標(biāo)過程與橋牌博弈極為相似。因?yàn)樵谕稑?biāo)時(shí)，首先要分析對(duì)方的可能出價(jià)和己方合理出價(jià)。這與橋牌中的叫牌相互吻合，同樣是通過逐級(jí)遞增的加價(jià)方式來實(shí)現(xiàn)互通牌情的過程(包含己方和對(duì)方)。而在打牌過程中的贏墩策略也與投標(biāo)公司的戰(zhàn)略相契合，同是在掌握信息有限的情況下進(jìn)行博弈。因此，對(duì)橋牌博弈AI引擎的研究，是極具現(xiàn)實(shí)意義的[1]。

目前，更為精準(zhǔn)的橋牌模型，逐漸成為研究者們關(guān)注的熱點(diǎn)之一。在AMMAS2019入選論文中，就有一篇研究了基于神經(jīng)網(wǎng)絡(luò)構(gòu)建叫牌系統(tǒng)的方法[2]。而所有叫牌方式的側(cè)重點(diǎn)無(wú)一不是在于消除叫牌時(shí)產(chǎn)生的模糊信息，旨在得到唯一且精確的結(jié)果。但是連續(xù)3年獲得冠軍的Wbridge5是基于規(guī)則的，他們通過消除已有規(guī)則中的歧義和沖突來優(yōu)化自己的系統(tǒng)，這樣就會(huì)有一定的局限性，把系統(tǒng)的性能的上限局限在了人類已有的知識(shí)中。因此，想要繼續(xù)提升橋牌AI的能力，需要從叫牌、打牌和評(píng)估函數(shù)3個(gè)方面分別給出優(yōu)化的新思路。即構(gòu)建精確叫牌體系、分階段牌局策略及更為準(zhǔn)確的評(píng)估函數(shù)。

1 叫牌優(yōu)化

1.1 構(gòu)建精確叫牌體系

橋牌主流的叫牌體系分為2種：自然叫牌體系和精確叫牌體系。傳統(tǒng)的程序大多采用自然叫牌體系。自然叫牌法是最為常用的叫牌方式，并且大多數(shù)橋牌好手也在使用。但是對(duì)于計(jì)算機(jī)來說，由于其普適性與模糊性，對(duì)于同一牌型在不同的特定場(chǎng)合給出的不同叫品，這反而是模糊的[3]。與之相反，對(duì)于充滿各種定約的精確叫牌體系更加適合程序理解人類的叫牌。

對(duì)于叫牌的初始狀態(tài)，有6.35×1011種可能的牌局。首先對(duì)于手牌的大牌點(diǎn)數(shù)進(jìn)行條件分類，細(xì)化為14類，再對(duì)每一類中的情況進(jìn)行牌型分類，來決定開叫叫品。此時(shí)每一種牌局狀況對(duì)應(yīng)唯一叫品，同伴可以通過該叫品準(zhǔn)確定位該叫品所對(duì)應(yīng)的牌型及牌點(diǎn)范圍[4]。從而構(gòu)建出精確叫牌體系。

下面給出其中一組示例：11-15 4-4-1-4或4-4-0-5牌型，單缺為D，開叫2D。

pgame->honorCardPoint>=11&&pgame->honorCardPoint <=15

pgame->suit[1].cardnum==1&&pgame->suit[0].cardnum==4 &&pgame->suit[1].cardnum==4

pgame->suit[1].cardnum==0&&pgame->suit[0].cardnum==4 &&pgame->suit[2].cardnum==4

pgame->Open_RecordBid[0]=′2′;

pgame->Open_RecordBid[1]=′2′;

pgame->Open_RecordBid[2]=pgame->position;

sprintf_s(r_bid，80，"BID%c22"，pgame->position);

因?yàn)槭峙瓶倲?shù)為13張，故對(duì)于4-4-1-4和4-4-0-5只需要寫出其中任意3個(gè)即可，返回叫牌結(jié)果為2D。

通過結(jié)構(gòu)體數(shù)組對(duì)于手牌的存儲(chǔ)，記錄手牌花色、數(shù)量、牌型信息，通過record數(shù)組實(shí)現(xiàn)隊(duì)友之間互通牌情，從而構(gòu)建出精確叫牌體系。

1.2 叫牌體系二次優(yōu)化

上述構(gòu)建的精確叫牌體系，解決了叫牌模糊的問題，通過大量定約實(shí)現(xiàn)精準(zhǔn)叫牌，更加適用于計(jì)算機(jī)。與此同時(shí)，大量定約所形成的代碼量巨大，通常，僅僅實(shí)現(xiàn)部分定約，就需要代碼量約 7 000行。代碼冗余的問題瞬間暴露得一覽無(wú)余。

出現(xiàn)此問題的原因在于程序之間的大量重復(fù)，比如相似的定約，卻需要重新構(gòu)建完整的if判斷邏輯。為了簡(jiǎn)化代碼，增加程序的可維護(hù)性和擴(kuò)充性，提煉出共同因子，用struct Pai[]結(jié)構(gòu)體數(shù)組進(jìn)行表示。

綜合考慮到牌力、牌型對(duì)于叫牌過程的影響，歸納出的共同因子可以分成三大類，即存儲(chǔ)牌力上下限、存儲(chǔ)手牌信息、返回叫牌結(jié)果[5]。

這三大類又可以細(xì)分為12個(gè)小類，即牌點(diǎn)上限、牌點(diǎn)下限、梅花張數(shù)、方片張數(shù)、黑桃張數(shù)、紅桃張數(shù)、梅花大牌張數(shù)、方片大牌張數(shù)、黑桃大牌張數(shù)、紅桃大牌張數(shù)、返回的叫牌花色和階數(shù)。如圖1所示。

圖1 Pai數(shù)組具體實(shí)現(xiàn)

構(gòu)建好數(shù)組后，每次叫牌不需要再進(jìn)行n行if查詢，只需要對(duì)應(yīng)叫牌查詢表，如開叫查詢開叫表，爭(zhēng)叫查詢爭(zhēng)叫表即可[6]。此處給出開叫表數(shù)組的部分示例(表1)，對(duì)于17×12的開叫表，其功能等價(jià)于500行左右代碼量的if查詢。

表1 開叫查詢表部分示例

例如，第一行數(shù)據(jù)應(yīng)理解為，通過評(píng)估函數(shù)計(jì)算得到的牌力范圍在12～15之間時(shí)，并且4個(gè)花色的牌，數(shù)量均大于等于3(表現(xiàn)為average均勻牌型)，并且在梅花上有3張及3張以上大牌，那么開叫1梅花。

此時(shí)，如果想繼續(xù)擴(kuò)充定約，那么只需要在表格中新增行數(shù)據(jù)，省去了動(dòng)輒成百上千行的代碼量。至此，叫牌部分模糊性和代碼冗余的問題得以解決。

2 打牌優(yōu)化

2.1 傳統(tǒng)經(jīng)驗(yàn)打牌

傳統(tǒng)的橋牌程序大多采用經(jīng)驗(yàn)出牌，按照經(jīng)驗(yàn)出牌的程序在遇到特定場(chǎng)景下的牌張組合，著實(shí)能打出不錯(cuò)的配合，但幾率極小。如果試圖窮盡橋牌的打牌組合，按照目前計(jì)算機(jī)的算力，又難以實(shí)現(xiàn)。

值得一提的是，單純基于經(jīng)驗(yàn)打牌策略，沒有考慮到橋牌中存在的明手這一規(guī)則，使得己方相較于對(duì)方缺失了13張手牌的信息。而在比賽中，占據(jù)1/4的信息量。這部分信息所影響的牌局信息會(huì)成指數(shù)式增長(zhǎng)，直接影響到整輪對(duì)局的發(fā)展趨勢(shì)。

2.2 “monte Carlo+Dummy”打牌

針對(duì)于橋牌的信息非完備性，或者說對(duì)于所有的非完備信息博弈，一個(gè)重要的思路就是將非完備轉(zhuǎn)換為完備。目前橋牌的主流算法就是“蒙特卡洛+雙明手求解器”[7]打牌。通過蒙特卡洛算法大量生成對(duì)于牌型的限制，將這個(gè)限制傳入到一個(gè)約束數(shù)組里，通過(爆炸式)生成牌局的方式，使得信息變?yōu)橥陚?。此時(shí)，可以使用雙明手求解器進(jìn)行求解。

但該思路存在明顯的不足之處：當(dāng)牌局剛剛開始進(jìn)行時(shí)，所掌握的信息極為有限，約束遠(yuǎn)遠(yuǎn)不足，爆炸式生成牌局過多，會(huì)發(fā)生棧溢出[8]。并且生成樣本所需時(shí)間長(zhǎng)，精準(zhǔn)度低。通過實(shí)驗(yàn)測(cè)試，發(fā)現(xiàn)在前幾墩牌中，程序往往會(huì)呈現(xiàn)“亂打”的現(xiàn)象。

該如何解決這個(gè)問題呢？如何既能夠保證程序不會(huì)朝著錯(cuò)誤的方向前進(jìn)，又能進(jìn)行非完備信息與完備信息之間的轉(zhuǎn)化。給出的方案就是分階段生成牌局，不同階段采用不同策略。

2.3 新型混合打牌策略

首先將牌局分為2個(gè)階段[9]，前一部分因?yàn)檎莆盏男畔O為有限，適合采用精準(zhǔn)度高，要求性高的經(jīng)驗(yàn)打牌策略，后一部分因?yàn)樾畔⒅饾u暴露，掌握信息更多，采用蒙特卡洛+雙明手求解器打牌方式。

經(jīng)驗(yàn)打牌：

這里的經(jīng)驗(yàn)打牌并不指?jìng)鹘y(tǒng)的特定牌型下經(jīng)驗(yàn)打牌，而是通過人為大量分析對(duì)局得到的。值得注意的是，在不同方位下，程序的打牌策略應(yīng)該是完全不同的。

比如首攻，它的打牌原則應(yīng)該是：穿強(qiáng)擊弱。攻擊己方最強(qiáng)的或者對(duì)方最弱的。通過存儲(chǔ)己方叫牌信息，掌握己方叫過的花色，比如在和上，己方有過叫品，而對(duì)方在上也有過叫品，那么根據(jù)穿強(qiáng)擊弱的原則[10]，此時(shí)應(yīng)該主打的花色為。

下面給出偽代碼，其功能是在程序中養(yǎng)成出頂張連續(xù)大牌的習(xí)慣。

bignum ←0

/*設(shè)置臨時(shí)變量來存放大牌數(shù)量*/

for i ←0 to num do

if(putCard[i]/4)>0 then

bignum++;

if bignum>=5 then

for i ←0 to num do

if(putCard[i]/4)>0 then

index=i;

這樣做有非常明顯的好處。如圖2所示牌局。

圖2 牌局示意圖

這幅牌局是叫的2◆，南北兩家主打◆，如果北家攻擊一張◆K，那么此時(shí)在固定了攻擊連續(xù)大牌中的頂張，作為其隊(duì)友(南家)完全可以意識(shí)到隊(duì)友的K是其在◆上最大的一張牌，立刻反推出他一定有◆J◆Q◆K，并且沒有◆A。再加上自己手里沒有◆A，那么◆A一定在對(duì)方手里，通過這一張大牌，可以實(shí)現(xiàn)傳遞牌情信息量是原來的數(shù)倍[11]。

其余的各家都根據(jù)位置的不同，有其對(duì)應(yīng)專屬的打牌策略，所以在這里只列出首攻的部分打牌函數(shù)，其余類似但不相同，不做贅述。

在開局時(shí)，根據(jù)經(jīng)驗(yàn)打牌旨在搶得一個(gè)良好的開局，但隨著牌局情況的逐漸復(fù)雜，將很難再用經(jīng)驗(yàn)去描述打牌過程。此時(shí)，應(yīng)該采用具有完備信息博弈能力的蒙特卡洛算法加上雙明手求解器進(jìn)行求解的策略(圖3)。

圖3 蒙特卡洛算法+雙明手求解器策略圖

對(duì)于打牌來說，其主要的2個(gè)限制條件分別為“經(jīng)驗(yàn)打牌策略所帶來的復(fù)雜程度”以及“完備信息求解的準(zhǔn)確性”。此時(shí)問題轉(zhuǎn)化為“當(dāng)牌局進(jìn)行到何種程度時(shí)，由經(jīng)驗(yàn)打牌轉(zhuǎn)換為蒙卡算法+求解器求解”。

這里設(shè)置2個(gè)變量：N(牌的總數(shù)，在橋牌中為52)，D(牌局進(jìn)行的輪數(shù)，在橋牌中為13)。

不妨假設(shè)，每位牌手在打牌時(shí)打出任意一張牌的可能性是相同的。此時(shí)則有，打出任意張牌的概率為：P打牌=1/(13-D+1)，而對(duì)于進(jìn)行中的牌局來說，牌是動(dòng)態(tài)的，即第一次出牌時(shí)牌張總數(shù)為N，那么下一次出牌，牌的總數(shù)為N-1，在每一墩中，牌況總數(shù)最多為：W牌況=(N)(N-4(D-1)-1)(N-4(D-1)-2)(N-4(D-1)-3)。此時(shí)可以將牌況的復(fù)雜程度近似看成是D的4次方函數(shù)。

這里對(duì)于每一墩的可能牌況為：V可能=C2X(X=N-13-4D)，表示目前仍然未知的牌中，選擇兩張(自己和隊(duì)友每人一張)打出。這里減去的13是指，明手信息的13張牌可以被所有牌手看到，即可利用的信息。由于求解器的算法已經(jīng)固定。求解器的能力正比于牌局預(yù)測(cè)的準(zhǔn)確度。比值可以取K，給出一個(gè)衡量牌局準(zhǔn)確性的指標(biāo)(任何牌局適用)：S=K(N-13-4D)2/2-N4。將相關(guān)數(shù)據(jù)帶入可以得到解，當(dāng)進(jìn)行到第三輪時(shí)，由經(jīng)驗(yàn)分析策略轉(zhuǎn)變?yōu)榍蠼馄鞣治隹梢垣@得的程序，準(zhǔn)確度最高，收益最大[12]。

至此，提供了叫牌與打牌的新型策略。相應(yīng)的，也需要一個(gè)更為精確的評(píng)估函數(shù)作為支撐。

3 評(píng)估函數(shù)優(yōu)化

傳統(tǒng)的評(píng)估函數(shù)采用高倫計(jì)點(diǎn)法來評(píng)估一手牌的力量，即A=4，K=3，Q=2，J=1。但如果牌值評(píng)估只做到這種程度，其準(zhǔn)確性顯然不足以滿足中級(jí)以上橋手的需求。

為此，分為3點(diǎn)進(jìn)行評(píng)估函數(shù)優(yōu)化：

1)短門上的大牌進(jìn)行調(diào)整(主要體現(xiàn)為扣點(diǎn))；

2)長(zhǎng)門上的調(diào)整(主要體現(xiàn)為加點(diǎn))；

3)定約不同時(shí)的調(diào)整。

隨機(jī)生成了一副牌局(隨機(jī)數(shù)種子為135246)，以其中的北家為例進(jìn)行說明：

假設(shè)北家手牌中的大牌和小牌分別如圖4與圖5所示。

圖4 大牌

圖5 小牌

采用如下方法對(duì)評(píng)估函數(shù)進(jìn)行優(yōu)化。

第一步，使用高倫計(jì)點(diǎn)法評(píng)估。

3*J+1*K+2*A=3*1+1*3+2*4=14

第二步，進(jìn)行扣點(diǎn)。

由于單張大牌有被擊落的可能性，所以對(duì)于KQJ分別扣1點(diǎn)。而單張的A由于不會(huì)被擊落，所以只扣半個(gè)點(diǎn)。如果是雙張時(shí)，那么KQJ扣半個(gè)點(diǎn)，A不扣點(diǎn)。A-num=1，牌點(diǎn)-0.5；KQJ-num=1，牌點(diǎn)-1；KQJ-num>1，牌點(diǎn)-0.5。

此時(shí)就有：?jiǎn)螐埣t桃K，單張黑桃J分別扣1點(diǎn)，雙張的梅花JA和方片JA，各扣半個(gè)點(diǎn)。

總計(jì)扣：1+1+0.5+0.5=3

此時(shí)牌點(diǎn)為：14+(-3)=11

第三步，進(jìn)行加點(diǎn)。

此副牌在梅花上有AJ帶頭的6張好套，那么應(yīng)該考慮到它所帶來的贏墩潛力[13]，所以在這里可以+2.5。n張好套對(duì)應(yīng)著(n/2-0.5)的贏墩潛力。

此時(shí)牌點(diǎn)為：11+(+2.5)=13.5

第四步，通過該局的王牌來進(jìn)行加點(diǎn)。

如果在這局中梅花成為王牌，那么作為北家占據(jù)了大部分優(yōu)勢(shì)還應(yīng)該再+2。即王牌花色為己方最強(qiáng)花色，牌力+2，為己方較強(qiáng)花色，牌力+1。

此時(shí)牌點(diǎn)為：13.5+2=15.5

最終得到的牌值，看似與起初差距不大(14—>15.5)，但是所考慮到的信息較于以前是更為完善的，這里考慮到了牌型、牌張、牌況對(duì)于牌力的影響，更吻合牌局中的實(shí)際情況。

4 實(shí)驗(yàn)

為檢測(cè)新型打牌模型所帶來的優(yōu)化效果，設(shè)置2組對(duì)照實(shí)驗(yàn)。第1組實(shí)驗(yàn)是優(yōu)化后的引擎與傳統(tǒng)引擎對(duì)局(注：傳統(tǒng)程序指2020年遼寧省計(jì)算機(jī)博弈競(jìng)賽一等獎(jiǎng)獲獎(jiǎng)程序)，檢驗(yàn)博弈引擎的綜合能力。第2組實(shí)驗(yàn)是分別采用新型混合打牌策略和經(jīng)驗(yàn)打牌策略進(jìn)行對(duì)局。為避免叫牌差異所導(dǎo)致的影響，二者在相同叫牌體系下對(duì)弈。此外，由于精確叫牌體系和自然叫牌體系分屬2個(gè)體系，無(wú)法直接比較好壞，故不設(shè)置打牌相同情況下叫牌準(zhǔn)確度的對(duì)比(注：所有參與對(duì)比實(shí)驗(yàn)的程序均采用優(yōu)化后的評(píng)估函數(shù))。

這里對(duì)局是指，讓兩套程序在同一幅牌中均與測(cè)試程序?qū)?，分別記錄兩套程序贏得的分?jǐn)?shù)，并進(jìn)行對(duì)比，借此檢驗(yàn)優(yōu)化引擎后橋牌程序的實(shí)戰(zhàn)能力。

4.1 叫牌準(zhǔn)確度測(cè)試實(shí)驗(yàn)

優(yōu)化前后的程序分別與測(cè)試程序(優(yōu)化前后程序均自主開發(fā))對(duì)局500輪，共計(jì)1 000輪對(duì)局，檢驗(yàn)優(yōu)化后橋牌程序的綜合能力是否有提升(圖6)。

圖6 綜合能力測(cè)試結(jié)果

從圖6中可以看出，橙色的線在藍(lán)色線上方，比如在傳統(tǒng)程序得到100分時(shí)，優(yōu)化后的程序可以得到200分左右，而在傳統(tǒng)程序得到-100分時(shí)，優(yōu)化后的程序，往往可以負(fù)分更少，甚至少許贏分。那么根據(jù)測(cè)試結(jié)果，可以看出經(jīng)過優(yōu)化后的橋牌AI程序，有著更強(qiáng)的綜合能力。

4.2 打牌能力測(cè)試實(shí)驗(yàn)

整體優(yōu)化后的程序同叫牌部分優(yōu)化的程序分別與測(cè)試程序?qū)?00輪，共計(jì)1 000輪對(duì)局，檢驗(yàn)優(yōu)化后橋牌程序的打牌能力是否有提升(圖7)。由于在同一叫牌體系下，得分相似的可能性較大，所以直接取絕對(duì)值進(jìn)行比較。

圖7 打牌能力對(duì)比曲線

這里取絕對(duì)值旨在更好地區(qū)分打牌能力，對(duì)于正分，取原本值，對(duì)于負(fù)分，在同一組牌局下，負(fù)的越少，證明能力越強(qiáng)，所以取同組中負(fù)分更多的絕對(duì)值進(jìn)行表示。對(duì)照組程序和優(yōu)化后程序均采用同樣的叫牌策略，即精確叫牌法。在這里出現(xiàn)部分牌局下得分相同的情況，因?yàn)椴捎猛耆嗤慕信?，定約相同，得分相同的可能增大。從圖7中可以看出，橘黃色的線在藍(lán)色線的上方，即在采用相同叫牌策略下，優(yōu)化后打牌策略要遠(yuǎn)遠(yuǎn)優(yōu)于傳統(tǒng)打牌策略。

通過上述實(shí)驗(yàn)，說明經(jīng)過優(yōu)化后，橋牌AI引擎對(duì)于牌局的分析更為準(zhǔn)確，擁有更強(qiáng)的打牌能力。

5 結(jié)論

將經(jīng)驗(yàn)性的代碼與求解器混合，實(shí)現(xiàn)分階段模擬牌局。首先，采用開局經(jīng)驗(yàn)、中局和殘局進(jìn)行完備信息處理。接著，通過數(shù)學(xué)推導(dǎo)，計(jì)算得到分割不同策略界線的位置。最后，等信息暴露更完全，再進(jìn)行策略轉(zhuǎn)換，使得程序打牌能力更為穩(wěn)定。此外，對(duì)于大量if造成的代碼冗余問題，其關(guān)鍵部分在于存儲(chǔ)牌局信息數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)。通過牌局信息分析，將所需信息抽象成結(jié)構(gòu)體數(shù)組，對(duì)于程序的規(guī)范性與可維護(hù)性有極大幫助。通過多角度多方位優(yōu)化，橋牌博弈AI的牌力獲得較大提升，大大提高了獲勝幾率。

現(xiàn)實(shí)中，企業(yè)或國(guó)家間的競(jìng)爭(zhēng)與合作是典型的非完備信息問題，與橋牌博弈極為相似。因此，構(gòu)建橋牌混合策略模型，研究橋牌AI，對(duì)解決現(xiàn)實(shí)中的合作競(jìng)爭(zhēng)關(guān)系問題具有重要的現(xiàn)實(shí)意義。