Day22 Transposition Table
===

在Day4的時候有提到，對局樹會有很多重複的盤面出現，造成效能的浪費，未來會介紹到Transposition Table就能夠來處理這個問題。
奇異博士看到了上百萬個我棄賽的未來，沒看到的就是今天，我自己都沒想到。

## Transposition Table
### 以空間換取時間
**Transposition Table（同形表）** 是用來儲存歷史盤面跟相關資訊的，避免在搜尋過程中重複計算已經評估過的棋局狀態。通過儲存已經搜索過的盤面及其相關資訊，當搜索中遇到相同的盤面時，直接從使用之前的結果，從而節省計算資源和時間。
### 重複盤面
再看一次上下兩條分支，雖然過程不同，但結果相同的情況。


再來就是這種旋轉跟鏡像對稱的盤面，其實都可以視為同一種。


在搜索的過程中，如果先把分支的結果給存下來，只要遇到重複的盤面就直接使用之前搜索過的結果，這樣就可以省去不必要的重複計算。
如下圖，本來 X 下在中間後，O 有8種下法，但實際上我們只需要搜索其中的2種，剩下的盤面都可以直接查詢歷史盤面，不用再重新搜索了。


初始盤面也是只需要搜索其中的3種，比前面介紹的所有剪枝都還要強大。

### 循環走步
Transposition Table也可以用來處理循環走步的問題。

* **圍棋**
黑棋可以在A點將白棋給吃掉。
但就在黑棋提過去之後 A 點的棋子也只剩下一氣，白棋如果下在 B 點也可以把黑棋吃掉。
這樣雙方只要開始提來提去那這盤棋就沒完沒了了，所以圍棋有個規則是，當對方提過來時，我方必須隔一手之後才能提回去，這就是[打劫](https://zh.wikipedia.org/zh-tw/%E5%8A%AB_(%E5%9B%B4%E6%A3%8B))。
這邊就可以檢查歷史盤面，來檢查是否有違規情況，比如上圖中黑棋下在 A 點將白棋吃掉後，白棋不能夠馬上於 B 點吃回去，必須先在其他地方落子，下一個回合後才能夠吃回來，如果白棋馬上吃回去，那就會跟歷史盤面有重複，所以只要有重複盤面就可以判定是違規。
(三劫、四劫、長生劫等複雜循環行為這裡暫時不去探討)

* **象棋**
長將、長捉、長殺([棋例](https://zh.wikipedia.org/zh-tw/%E9%95%B7%E6%89%93_(%E8%B1%A1%E6%A3%8B)#%E6%A3%8B%E4%BE%8B))
* **西洋棋**
[三次重複](https://zh.wikipedia.org/wiki/%E4%B8%89%E6%AC%A1%E9%87%8D%E8%A4%87)

其他還有像是跳棋、Surakarta，都是很容易發生循環走步的遊戲，設計一個好的Transposition Table就會變得非常重要。

## Zobrist Hashing
一開始在看井字遊戲大家可能不會有感覺，但是看一下象棋、西洋棋或是圍棋，要如何存下過往盤面資訊？
如果是用Array來表示棋盤資料結構的話，然後將每個盤面的Array都儲存下來，就算不考慮比對Array的效能。
圍棋隨便都能達到上百手，你在每個盤面展開的時候都得去比對前面一百個盤面，這樣線性搜索效能肯定是非常差的，這時候我們就會用到Hash。


圖片擷取自[how programmers overprepare for job interviews](https://youtu.be/5bId3N7QZec?si=6CSqwLQchxah9DRb)，這影片太好笑了一定要點進去看!

而Zobrist Hashing應該是目前最常見的建同形表的方式，Day16也有提到過一個Zobrist's Model，沒錯！這兩個Zobrist是同一位，就是[Albert Zobrist](https://www.chessprogramming.org/Albert_Zobrist)。

Zobrist Hashing 通過給每個棋子在每個位置上分配一個隨機的二進制數字（hash值），來表示盤面。當棋子移動時，可以使用位元運算快速更新整個棋盤的hash值，而不必重新計算整個盤面的hash值。
正常情況你得給新的盤面一個新的hash值，但Zobrist Hashing只針對移動的棋子做XOR，效率會高非常多。

### 步驟
以西洋棋為例，步驟如下：

1. **初始化隨機數表**
為每個棋子的每個可能位置分配一個隨機的 64 位整數，西洋棋的隨機數表的大小約為：
12 種棋種 × 64 個棋盤位置 = 768 個隨機數
2. **盤面hash值的生成**
遍歷棋盤上的每個位置，根據當前該位置的棋子類型和位置，查詢對應的隨機數，並通過XOR運算將這些隨機數組合成一個唯一的hash值，來表示當前盤面。
3. **更新hash值**
每當一個棋子移動時：
將棋子移動前的位置與其對應的隨機數進行XOR，表示移開該棋子。
將棋子移動後的新位置與對應的隨機數進行XOR，表示棋子已到新位置。

步驟1可以一開始就產生好，不用每次遊戲都產生一個新的隨機數表，比如在[Deep Learning and the Game of Go](https://github.com/maxpumperla/deep_learning_and_the_game_of_go)這個開源程式中，他已經先建立好一個[HASH_CODE](https://github.com/maxpumperla/deep_learning_and_the_game_of_go/blob/master/code/dlgo/zobrist.py)，實際的操作範例可以看[goboard_fast.py](https://github.com/maxpumperla/deep_learning_and_the_game_of_go/blob/master/code/dlgo/goboard_fast.py)。

### XOR(exclusive or)的特性
詳細XOR的特性與證明請至[邏輯互斥或](https://zh.wikipedia.org/zh-tw/%E9%80%BB%E8%BE%91%E5%BC%82%E6%88%96)查看。
* 交換律：
$a \oplus b = b \oplus a$
* 結合律：
$(a \oplus b) \oplus c = a \oplus (b \oplus c)$

因為這兩個特性，XOR不會被順序影響，無論棋子移動順序如何，結果hash值一致。
* 運算元的單位值：
$x \oplus x = 0$
$x \oplus 0 = x$
這樣放置棋子與移除棋子相當方便，如果是移動的話就等同於先移除再放置，操作順序一樣不影響。

### 優點

- **快速局面更新**：只需針對少數位置進行XOR操作，更新速度非常快。
- **減少重複搜索**：能識別不同手順導致的相同盤面，避免重複計算。
- **空間效率高**：hash值用固定大小（64 位整數）表示，不必存整個棋盤狀態。

### 缺點

- **碰撞問題**：不同盤面會生成相同hash值，但在實際應用中，這種機率非常低，可以忽略。
使用64位元的hash值若搜尋 $2^{32}$ (約42億)個節點數，碰撞機率為 $10^{-10}$ ，比中樂透機率還低。
(這個數據引用自電腦對局導論，書中有詳細推導過程，歡迎大家去買書，這裡就不展開了。)

## 結論
Transposition Table對於對局樹的搜索來說相當重要，可能你費盡心思做了一大堆剪枝，都不如實作一個Transposition Table，對效能的影響非常的大。使用Zobrist Hashing可以用相對小的空間儲存各種棋盤狀態，並且能利用位元運算XOR快速更新，現在就為你的程式實作一個吧！
本來還想寫一點當Transposition Table滿了之後的一些置換策略，但想到現在的記憶體隨便都16G、32G，還非常便宜，就不用考慮Transposition Table的大小了吧。

## Reference
* 電腦對局導論
* [Transposition Table](https://www.chessprogramming.org/Transposition_Table)
* [Zobrist Hashing](https://www.chessprogramming.org/Zobrist_Hashing)
* [BCH Hashing](https://www.chessprogramming.org/BCH_Hashing)
* [Deep Learning and the Game of Go](https://github.com/maxpumperla/deep_learning_and_the_game_of_go)