Day24 Endgame Database
===
之前介紹不同對局類型時有提到，不管是收斂型對局或是終盤時才開始收斂的對局，都有機會將其破解，跟昨天一樣可以將這些破解的殘局事先儲存起來。

## Endgame Database
Endgame Database (殘局庫)就是用來儲存殘局的結果，跟開局庫不同的地方是，開局庫儲存的只是「較好」的開局，甚至有些只是儲存各種常見的開局，而**殘局庫儲存的都是「正解」**。

### 適合的棋類
不是所有的遊戲都適合製作殘局庫，前面提到需要是收斂型對局或是終盤時開始收斂的對局，不然會過於複雜。
有時候也不一定是對局複雜度的問題，還要看遊戲的特性，比如狀態空間複雜度約 $10^{28}$ 的黑白棋，跟約 $10^{47}$ 的西洋棋，反而是西洋棋更適合一些，看出這兩種遊戲的區別了嗎？
沒錯！**黑白棋是愈下愈多顆，而西洋棋則是愈下愈少**，所以要看的不是整體複雜度而是**殘局時的複雜度**，適合的遊戲：西洋棋、象棋、暗棋、橋牌等。

### 殘局庫的類型
殘局庫根據儲存的資訊可以分為以下幾類：
* **WLD (Win Loss Draw)**
只儲存盤面的結果(勝/敗/和)的殘局庫就稱為WLD殘局庫。
* **DTM (Distance to Mate)**
儲存距離「將死」(遊戲結束)的步數。
* **DTC (Distance to Conversion)**
將局勢轉換為其他類型殘局的步數，有點像是一個轉換法，比如發生了一些不可逆的行為時，像是吃子、暗棋的翻子、西洋棋的[升變](https://zh.wikipedia.org/zh-tw/%E5%8D%87%E8%AE%8A)，比如下圖象棋的殘局：海底撈月(紅先)。
經過數手後發生了吃子行為，會變成下圖，從本來的5子殘局變成4子殘局，獲勝的過程中會發生狀態的轉換。
[圖片來源](https://www.xiangqiqipu.com/Article/View-15039.html)
* **DTC (Distance to Capture)**
電腦對局導論中的DTC是Distance to Capture，指的是吃子後最後能贏棋的距離，我在[暗棋殘局庫對審局函數之改良](https://hdl.handle.net/11296/w3xct6)中看到的定義為距離吃子的距離，一個DTC就有三種解釋(看了三篇論文解釋也都不太一樣...)，使用前要記得看清楚定義。

### 建立殘局庫的方式
**Retrograde Analysis (回溯分析法)** 是建殘局庫最常被使用的方法，其實就是一種暴力窮舉，只是他是反向的，**從終局開始逆向推導**，回溯到前一個可能將死之前的盤面，窮舉出所有可能的盤面，並計算他的結果，接著再由這些已知勝負結果的盤面往回推一手，每回推一層可能的盤面就會多非常多，比如[線上西洋棋殘局庫](https://www.shredderchess.com/online/endgame-database.html)中，最多到六子的殘局，已經有3787154440416種盤面了，上面的6子西洋棋殘局庫總容量達1153GB，而且這明顯還是壓縮過的，平均每個盤面資訊用不到3bit來儲存。

### 殘局庫的壓縮
以下表格擷取自[Endgame Tablebase](https://en.wikipedia.org/wiki/Endgame_tablebase)，我們可以看到每多一子的殘局，殘局庫都會變大非常多，勢必得想辦法壓縮才有辦法建得更大，而且這麼大的殘局庫你根本也沒辦法將其載入至記憶體，使用上也有很多細節需要注意。
| Number of pieces | Number of positions | Database name | Metric | Completed in | Size |
|------------------|--------------------------|---------------|--------|--------------|---------------|
| 5 or fewer | 26,038,209,193 | Syzygy | DTZ | 2013 | 939 MB |
| 5 or fewer | 26,038,209,193 | Nalimov | DTM | 2005 | 7.05 GB |
| 6 | 3,787,154,440,416 | Syzygy | DTZ | 2013 | 150.2 GB |
| 6 | 3,787,154,440,416 | Nalimov | DTM | 2005 | 1.2 TB |
| 7 | 423,836,835,667,331 | Syzygy | DTZ | 2018 | 18.4 TB |
| 7 | 423,836,835,667,331 | Lomonosov | DTM | 2012 | 140 TB |
| 8 | 38,176,306,877,748,245 | — | — | — | ~2 PB (estimated for Syzygy) |

針對不同的遊戲也有不同的壓縮策略，比如要注意循環走步，或是暗棋中考慮**棋種組合等價**的問題，像是除了砲以外，在暗棋中剩餘棋子都能吃掉鄰近一格比自己小的棋子，就會造成很多等價的盤面，當然還有前面一直用的老招，hash map！I'll use hash map！
這邊因為~~來不及寫~~剩下幾天要進入實作環節，就會來實作殘局庫了，到時候再來詳細解釋，Talk is cheap！一邊動手做大家會更有感覺。

## 結論
殘局庫的建立比起開局庫稍微複雜了些，其中有很多壓縮的知識，雖然殘局庫通常比起開局庫來得大、盤面更多，還都是正解，理論上應該也能大幅提升程式棋力才對，但其實對程式棋力影響大部分還不如開局庫，一樣要看遊戲特性，比如上面的西洋棋六子殘局，**真正西洋棋比賽要吃到剩下6子以下才分出勝負的其實並不多，所以進到殘局庫的機會就比開局庫小得多**，導致英雄無用武之地，相當可惜。

## Reference
* 電腦對局導論
* [Endgame Tablebase](https://en.wikipedia.org/wiki/Endgame_tablebase)
* [Design and implementation aspects of a Surakarta program](https://www.researchgate.net/publication/329160216_Design_and_implementation_aspects_of_a_Surakarta_program)
* [Equivalence Classes in Chinese Dark Chess Endgames](https://ieeexplore.ieee.org/document/6799248)
* [Compressing Chinese Dark Chess Endgame Databases by Deep Learning](https://ieeexplore.ieee.org/document/8281641)
* [線上象棋殘局庫](https://www.chessdb.cn/query/)
* [線上西洋棋殘局庫](https://www.shredderchess.com/online/endgame-database.html)
* [暗棋殘局庫的壓縮與實做](https://etds.lib.ntnu.edu.tw/thesis/detail/57e6238b5c6b71b6b7de753a3bc0c183/)
* [象棋殘局庫之研究](https://hdl.handle.net/11296/25usj5)
* [利用深度學習技法的暗棋殘局庫壓縮及檢索研究](https://hdl.handle.net/11296/tfswjd)
* [暗棋殘局庫對審局函數之改良](https://hdl.handle.net/11296/w3xct6)