邱虹坤，鄭曉東，王亞杰

(沈陽航空航天大學 a.計算機學院;b.工程訓練中心，沈陽 110136)

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

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

1 叫牌優(yōu)化

1.1 構建精確叫牌體系

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

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

下面給出其中一組示例：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);

因為手牌總數(shù)為13張，故對于4-4-1-4和4-4-0-5只需要寫出其中任意3個即可，返回叫牌結果為2D。

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

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

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

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

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

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

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

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

表1 開叫查詢表部分示例

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

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

2 打牌優(yōu)化

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

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

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

2.2 “monte Carlo+Dummy”打牌

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

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

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

2.3 新型混合打牌策略

首先將牌局分為2個階段[9]，前一部分因為掌握的信息極為有限，適合采用精準度高，要求性高的經(jīng)驗打牌策略，后一部分因為信息逐漸暴露，掌握信息更多，采用蒙特卡洛+雙明手求解器打牌方式。

經(jīng)驗打牌：

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

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

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

bignum ←0

/*設置臨時變量來存放大牌數(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，那么此時在固定了攻擊連續(xù)大牌中的頂張，作為其隊友(南家)完全可以意識到隊友的K是其在◆上最大的一張牌，立刻反推出他一定有◆J◆Q◆K，并且沒有◆A。再加上自己手里沒有◆A，那么◆A一定在對方手里，通過這一張大牌，可以實現(xiàn)傳遞牌情信息量是原來的數(shù)倍[11]。

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

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

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

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

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

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

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

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

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

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

為此，分為3點進行評估函數(shù)優(yōu)化：

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

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

3)定約不同時的調整。

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

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

圖4 大牌

圖5 小牌

采用如下方法對評估函數(shù)進行優(yōu)化。

第一步，使用高倫計點法評估。

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

第二步，進行扣點。

由于單張大牌有被擊落的可能性，所以對于KQJ分別扣1點。而單張的A由于不會被擊落，所以只扣半個點。如果是雙張時，那么KQJ扣半個點，A不扣點。A-num=1，牌點-0.5；KQJ-num=1，牌點-1；KQJ-num>1，牌點-0.5。

此時就有：單張紅桃K，單張黑桃J分別扣1點，雙張的梅花JA和方片JA，各扣半個點。

總計扣：1+1+0.5+0.5=3

此時牌點為：14+(-3)=11

第三步，進行加點。

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

此時牌點為：11+(+2.5)=13.5

第四步，通過該局的王牌來進行加點。

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

此時牌點為：13.5+2=15.5

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

4 實驗

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

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

4.1 叫牌準確度測試實驗

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

圖6 綜合能力測試結果

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

4.2 打牌能力測試實驗

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

圖7 打牌能力對比曲線

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

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

5 結論

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

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