hackMD原稿

今天要來分享蜜月橋牌跟實作蜜月橋牌殘局庫。

蜜月橋牌

蜜月橋牌是一種兩人橋牌遊戲，比起一般橋牌多加入了換牌階段，整體來說還蠻有趣的，湊不滿四人時也是一個很好打發時間的遊戲。

初始狀態

雙方各發13張牌，剩餘的26張牌置於桌上。

接著我們把蜜月橋牌按照順序拆成三個階段來看，針對不同的階段使用不同的策略。

叫牌階段

這邊同橋牌的叫牌階段，叫牌階段是不完全資訊對局，你沒有辦法知道對方的手牌。
唯一的線索就是在跟對方互相叫牌的時候去推測對方的大概牌力，在介紹Monte Carlo Method的時候有提到可以通過模擬的方式來評估。

換牌階段

每一輪都會從中央牌堆中翻開一張新的牌，接著由叫到王牌的人先出牌，規則與打牌階段相同，出牌較大的玩家取走翻開的牌，出牌較小的玩家抽取牌堆中的下一張牌，下一輪由取走翻開牌的玩家先出，換得的牌也能夠再打出去，直到中央牌堆26張牌全數換完為止。

換牌階段會從不完全資訊對局慢慢轉變為完全資訊對局，隨著棄牌堆愈來愈多，對方手牌的資訊就愈多，直到13輪換牌結束就會變成完全資訊對局，因為透過打出的26張加上自己手上的13張最終手牌，就能夠知道對方的最終手牌了。

打牌階段

換牌階段結束後就是打牌階段，如果過程中有記牌的話，其實就可以知道對方的所有手牌，這時候的策略就變得很單純，只要用Minimax Algorithm把所有可能展開就可以得到最佳的打牌方式。
在Day5的時候有提到，像是蜜月橋牌這種先後手順序會發生改變的遊戲，你的max層的子節點有可能也是max層，那該怎麼處理呢？

在使用Minimax algorithm展開的時候子節點回傳的分數都是指先手玩家所得的分數(磴數)。
利用蜜月橋牌的規則特性，當子節點仍為我方先手時，則代表這回合(磴)是獲勝的，所以子節點在回傳分數時要加1才是真正的分數。若子節點為對方先手，則代表輸掉了這回合，所以這個就是對方的分數，那回傳的分數則是當前回合數減去對方得分，在這樣的架構下，不管是輪到哪一邊，都是取最大值，如下圖，level為回合數。

打牌階段共有13個回合，比起其他遊戲的對局樹深度算是很淺的了，雖然要窮舉完還是要花不久的時間，但是我們可以透過建立殘局庫的方式來加速，試著把打牌階段給破解。

殘局庫

蜜月橋牌有王的所有可能數量如下，n為回合數，以下稱為level。

其中除以2的部分是前後重複的情況，乘以2的部分是先後手交換的情況，同樣的牌型，在橋牌中先後手的不同也會造成不同的結果，乘以4是代表分別以四種花色為王牌的情況。

比如 level13(n = 13) 就是雙方各有13張牌的初始狀態，所有可能的組合數為：

要設計一個一發完牌馬上查表就能知道結果的殘局庫，得存下這麼多的牌型，就算每個牌型都只用1個byte來存，大概是17.4ZB的大小。
ZB是什麼概念呢？
就是目前最常見的1TB硬碟，你得買170億個才裝得下。

看起來是不太現實，那我們將n給降一降。
level8所有可能的組合數為：

看起來還是非常的龐大，所以當然不可能直接展開所有的牌型，得進行壓縮，像是昨天說到的暗棋會有盤面等價的情況，蜜月橋牌當然也會有。

牌型壓縮

在蜜月橋牌中用A贏下2跟用3贏下2效果都是一樣的，都是得到一磴，不會因為數字更大而得到更多的分數，所以這裡使用依大小排列的二元序列來表示雙方手牌，1表示為先手方手牌，0表示為後手方手牌，如下圖所示，這副牌表示為1101101 1010010 010010 000111。

我們完全不需要管牌的點數到底是多少，只需要知道各花色牌的大小關係。
這樣我們只需要用26個bit就能表示雙方的手牌了，而且很多牌型都可以視為同一種，比如下圖，先手方有A、2與先手方有Q、5，紀錄方式都為1001。

這些大小關係相同的牌型都為等價牌型。

這樣可以非常有效的減少大量重複的牌型。level8中任意的16張牌就為8個0與8個1的排列組合，組合數為 共12870種；再來就是把這些牌切成四個花色，為 共969種。level8的所有牌型就為12870 × 969共12471030種，比起本來少了非常多。

花色壓縮

我們可以看到下圖中的兩副牌，假設最左邊的花色為王牌，那王牌的張數與排列是一模一樣的，非王牌花色僅僅只是不同花色間的先後順序不同而已，重新排列後還是視為相同牌型。

所以可以將花色由張數少的排到張數多的，由少到多排列，王牌依舊放置於序列的最前面。
花色組合數為下列方程式的整數解個數(KF為王牌花色)。

這樣level8的組合數就從 共969種減少為193種了。

這邊當然是寫程式解的，要我手算應該是有點困難。

def count_flower(level):
    count = 0
    for KF in range(14):  # KF 從 0 到 13
        for F1 in range(14):  # F1 從 0 到 13
            for F2 in range(F1, 14):  # F2 >= F1
                for F3 in range(F2, 14):  # F3 >= F2
                    if KF + F1 + F2 + F3 == level * 2:
                        count += 1
    return count

level8的所有可能牌型就更進一步壓縮為12870 × 193 = 2483910種。

所有牌型可能數

結論

通過牌型的資料結構設計，成功壓縮大量的等價牌型，將 的牌型壓縮到了 ，讓展開所有變化不再是天方夜譚。
東西太多只好拆成兩篇，明天繼續介紹如何儲存殘局庫。

Reference

• 蜜月橋牌程式開發及殘局庫的建立
• 蜜月橋牌程式叫牌與換牌階段的策略改進