Day26 蜜月橋牌殘局庫2
===
昨天大部分內容都在探討殘局庫壓縮的問題，這時候就會體會到資料結構設計的重要，今天要來繼續補齊昨天的內容，來探討一下殘局庫的儲存與使用方式。

## 儲存方式
要先思考需要存下哪些資訊，蜜月橋牌的回合數是固定的，所以儲存方式不會是用什麼DTM或DTC，首先當然要有牌型、勝負結果。
這邊牌型注意要記錄花色張數，如果只存下雙方牌大小順序的二元序列，會無法得知各花色的張數，所以存下三種非王牌花色的張數(王牌張數等於總張數扣掉其他三種)。
一樣以level8為例，每一行都代表一種牌型與勝負結果。


31372就是手牌二元序列的十進位，31372轉為二進位數為`111101010001100`不到16位元的話就在前面補0，所以牌的二元序列為`0111101010001100`。
1、2、7分別為三種非王牌花色的張數，王牌則為16-1-2-7 = 6張，這樣就可以把序列切開：
`011110` `1` `01` `0001100`

最後的4為先手方所能獲得的磴數，就是先手方最佳情況可以在8磴中拿到4磴。

比如下圖就是`011110` `1` `01` `0001100`的一種牌型，下面的牌為先手方，上面的是後手方，只要雙方都打到最佳，先手方就能拿到4磴。


大家可以思考一下怎麼打，在思考的過程中就會發現，不對阿！建立殘局庫不就是為了知道正解嗎？
現在知道了勝負結果，但是**根本不知道該打哪張**！
我們將每張牌都展開，這邊只需要展開兩層，比如打出黑桃K，對方只有兩個合法走步，黑桃A跟黑桃4，將二元序列移除掉這兩張牌後得到新的二元序列：
對方出黑桃4：`0111` `1` `01` `0001100`
對方出黑桃A：`0001` `0` `10` `1110011` (先後手會發生改變)
接著就直接查表，查詢level7，根據level7得到的結果就可以知道要打哪張能得到最佳了。
所以需要將所有level的殘局庫都給建出來，每個level都需要查詢。

### 殘局庫大小
| level | 檔案大小 |
|-------|-----------|
| 1 | 88B |
| 2 | 748B |
| 3 | 5.36KB |
| 4 | 35.3KB |
| 5 | 213KB |
| 6 | 1.24MB |
| 7 | 6.87MB |
| 8 | 35.7MB |
| 9 | 177MB |
| 10 | 821MB |
| 11 | 3.65GB |
| 12 | 14.6GB |
| 13 | 58.3GB |
| 1~13 | 77.5GB |

總共77.5GB的殘局庫，這樣就能把蜜月橋牌的打牌階段給破解了。

## Bijective function
當年在讀研究所時，因為殘局庫讀取速度有點慢，建立一個hash table來存也因為碰撞過多導致效率不佳，主要是hash function設計得不是很好，就在我苦思該如何設計好的hash function時，陳彥吉學長就提供了我一篇論文[Design and implementation aspects of a Surakarta program](https://www.researchgate.net/publication/329160216_Design_and_implementation_aspects_of_a_Surakarta_program)，從中得到很大的啟發，論文中Surakarta棋的殘局庫使用了一種Bijective function，將每一種盤面都對應到唯一的index值，如此**完全不會浪費空間，也不會產生碰撞，相當於一個完美的hash function**。
Surakarta使用bitboard來表示棋盤，在Surakarta中盤面0跟1代表的是有沒有棋子，1在的位置則是代表對應到棋盤上的哪個位置。

### 轉換公式
每個盤面的index可以通過以下公式換算：

$\text{bitboard_index} = \sum_{k=1}^{n} C_k^{p_k - 1}$

$F(i, j) = F(i - 1, j) + C_{j-1}^{i-2} = C_j^{i-1}$

詳細推導過程可以看原論文，這邊就直接簡化了，$F(i, j)$ 就是**第j個1在第i個位置**。
在蜜月橋牌中1為先手方的牌，0為後手方的牌，不用管牌的位置，0跟1的位置是按照牌的點數大小排序的。代表的意義不同但表達方式相同，可以視為Surakarta的盤面就是36個bits的二元序列，所以一樣可以將牌型組合的二元序列利用此方法計算出一個唯一的index值。

看公式可能有點抽象，實際來看個範例，首先看一下雙方都剩下一張牌的情況：


再來是雙方都剩下兩張牌的情況：


6種情況都能剛好對應到唯一的index值，最後我想說這麼神的論文一定要來認識一下作者，看了一下發現原來作者就是彥吉學長本人。

### 花色表
搞定了二元序列，蜜月橋牌還需要額外處理花色組合的問題，因為最多的level13也只有356種組合，由於數量不多，我們直接建立一個可以雙向查詢的表格。對於非王牌的花色來說，準確的知道是哪個花色對於搜尋的結果不會有任何影響，只要能區分出任意兩張之間是否為同一個花色就好，我們可以將三個非王牌花色的數量強制設定一個排序，例如就按照張數排序。
因為執行起來非常快，待程式執行時再建花色表即可，不必另外再將花色表的資料存在殘局庫中，可以節省空間。

最後的結構圖如下：


`index = bitboard_index x 花色數量 + 花色index`
要計算牌型對應的index時，只要將二元序列算出來的值乘上356(花色組合數量)加上花色表算出來的值就可以了，這樣每個牌型都能對應到唯一的index值。

另外計算牌型對應的index需要用到的排列組合計算，最大只到 $C_{13}^{26}$ 而已，所以也在程式執行時建組合表，將 $C_0^1$ 到 $C_{13}^{26}$ 的結果都先計算好存在組合表中。

## 最終版本殘局庫
通過上面的方式可以發現，我們只需要在殘局庫中儲存勝負結果就可以了。


因為index就代表著牌型，所以前面的二元序列及花色張數都不必存了，每個牌型都只需要用1個byte來儲存勝負結果即可，再次大幅縮小了殘局庫的大小，最後將殘局庫存成二進位檔`.bin`可以加速讀取。

| level | 檔案大小 |
|-------|-----------|
| 1 | 8B |
| 2 | 66B |
| 3 | 460B |
| 4 | 2.8KB |
| 5 | 16.4KB |
| 6 | 92KB |
| 7 | 485KB |
| 8 | 2.36MB |
| 9 | 11.1MB |
| 10 | 50.2MB |
| 11 | 216MB |
| 12 | 894MB |
| 13 | 3.44GB |
| 1~13 | 4.59GB |

蜜月橋牌初始各13張牌時的可能牌型有 $2 \times 10^{22}$ 種可能，**原先需要17.4ZB，最後壓縮到了3.44GB**，平均每個牌型只用了 0.000000000001 bit。
完整的level1~13殘局庫最終只有4.59GB，已經壓縮到能輕鬆放進記憶體的大小了。

## 結論
殘局庫不止可以通過等價盤面去做壓縮，根據儲存的方式，還可以壓縮儲存的資料，當殘局庫建到可以將所有可能都給儲存下來時，就等同於將其破解了，其中的細節還不少，大家可以嘗試去實作喜歡遊戲的殘局庫，自己動手做會更能體會其中奧妙。

## Reference
* [Design and implementation aspects of a Surakarta program](https://www.researchgate.net/publication/329160216_Design_and_implementation_aspects_of_a_Surakarta_program)
* [蜜月橋牌程式開發及殘局庫的建立](http://doi.org/10.6345/NTNU202001544)
* [蜜月橋牌程式叫牌與換牌階段的策略改進](http://doi.org/10.6345/NTNU202201230)