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

## 蜜月橋牌
蜜月橋牌是一種兩人橋牌遊戲，比起一般[橋牌](https://zh.wikipedia.org/zh-tw/%E6%A9%8B%E7%89%8C)多加入了換牌階段，整體來說還蠻有趣的，湊不滿四人時也是一個很好打發時間的遊戲。

### 初始狀態
雙方各發13張牌，剩餘的26張牌置於桌上。


接著我們把蜜月橋牌按照順序拆成三個階段來看，針對不同的階段使用不同的策略。
### 叫牌階段
這邊同橋牌的叫牌階段，叫牌階段是**不完全資訊對局**，你沒有辦法知道對方的手牌。
唯一的線索就是在跟對方互相叫牌的時候去推測對方的大概牌力，在介紹Monte Carlo Method的時候有提到可以通過模擬的方式來評估。

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


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

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


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


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

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

$C_n^{52} \times C_n^{52-n} \div 2 \times 2\times 4$

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

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

$C_{13}^{52} \times C_{13}^{39} \times 4$

$= 635013559600 \times 8122425444 \times 4$
$= 20631401175120201849600$
$\approx 2 \times 10^{22}$

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

$\text{ZB} = 10^3 \ \text{EB}$
$\text{EB} = 10^3 \ \text{PB}$
$\text{PB} = 10^3 \ \text{TB}$
$\text{TB} = 10^3 \ \text{GB}$

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

${C_8^{52} \times C_8^{44}} \times 4$

$= 752538150 \times 177232627 \times 4$
$= 533497252968880200$
$\approx 5.33 \times 10^{17}$

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

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


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


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

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

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


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

$KF+F_1+F_2+F_3=level\times2$
$13\geq\ F_3\geq F_2\geq F_1\geq0\ \ ,\ 13\geq KF\geq0$
$KF, F_1, F_2, F_3 \in \mathbb{Z}$

這樣level8的組合數就從 $H_{16}^4 = \ C_{16}^{19}$ 共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種。

### 所有牌型可能數

| level | 二元序列數量 | 花色數量 | 牌型總數 |
|-------|--------------|----------|--------------------|
| 1 | 2 | 4 | 8 |
| 2 | 6 | 11 | 66 |
| 3 | 20 | 23 | 460 |
| 4 | 70 | 41 | 2870 |
| 5 | 252 | 67 | 16908 |
| 6 | 924 | 102 | 94248 |
| 7 | 3432 | 145 | 497640 |
| 8 | 12870 | 193 | 2483910 |
| 9 | 48620 | 241 | 11717420 |
| 10 | 184756 | 285 | 52655460 |
| 11 | 705432 | 322 | 227149104 |
| 12 | 2704156 | 347 | 938342132 |
| 13 | 10400600 | 356 | 3702613600 |

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

## Reference
* [蜜月橋牌程式開發及殘局庫的建立](http://doi.org/10.6345/NTNU202001544)
* [蜜月橋牌程式叫牌與換牌階段的策略改進](http://doi.org/10.6345/NTNU202201230)