Day22 Transposition Table

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

Transposition Table

以空間換取時間

Transposition Table（同形表） 是用來儲存歷史盤面跟相關資訊的，避免在搜尋過程中重複計算已經評估過的棋局狀態。通過儲存已經搜索過的盤面及其相關資訊，當搜索中遇到相同的盤面時，直接從使用之前的結果，從而節省計算資源和時間。

重複盤面

再看一次上下兩條分支，雖然過程不同，但結果相同的情況。

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

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

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

循環走步

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

• 圍棋
  黑棋可以在A點將白棋給吃掉。
  

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

• 象棋
  長將、長捉、長殺(棋例)

• 西洋棋
  三次重複

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

Zobrist Hashing

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

圖片擷取自how programmers overprepare for job interviews，這影片太好笑了一定要點進去看!

而Zobrist Hashing應該是目前最常見的建同形表的方式，Day16也有提到過一個Zobrist's Model，沒錯！這兩個Zobrist是同一位，就是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這個開源程式中，他已經先建立好一個HASH_CODE，實際的操作範例可以看goboard_fast.py。

XOR(exclusive or)的特性

詳細XOR的特性與證明請至邏輯互斥或查看。

• 交換律：
  
  $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
• Zobrist Hashing
• BCH Hashing
• Deep Learning and the Game of Go