聲明：本程式設計參考象棋巫師源碼（開發工具dephi 11，建議用delphi 10.3以上版本）。
這一章主要介紹置換表。本章目标：
實作置換表；
采用置換表走法、殺手走法等多種啟發方式。
5.1 置換表
沒有置換表，就稱不上是完整的計算機博弈程式。在搜尋過程中，某個搜尋結果可能會出現這麼多次，這浪費了很多時間。為避免重複搜尋，儲存搜尋結果的表，就是置換表。由于哈希表的讀寫速度很快，通常置換表就由哈希表來實作。
置換表非常簡單，以局面的 Zobrist Key mod HASH_SIZE 作為索引值。每個置換表項存儲的内容無非就是：A. 深度，B. 标志，C. 分值，D. 最佳走法，E. Zobrist Lock 校驗碼。置換表結構：
置換表的處理函數也很傳統——一個 ProbeHash 和一個 RecordHash 就足夠了。
先說 RecordHash，即便采用深度優先的替換政策，RecordHash 也非常簡單，在判斷深度後，将 Hash 表項中的每個值填上就是了。
再看看 ProbeHash 是如何利用置換表資訊的：
(1) 檢查局面所對應的置換表項，如果 Zobrist Lock 校驗碼比對，那麼我們就認為命中(Hit)了；
(2) 是否能直接利用置換表中的結果，取決于兩個因素：A. 深度是否達到要求，B. 非PV節點還需要考慮邊界。
第二種情況是最好的(完全利用)，ProbeHash 傳回一個非 -MATE_VALUE 的值，這樣就能不對該節點進行展開了。
如果僅僅符合第一種情況，那麼該置換表項的資訊仍舊是有意義的——它的最佳走法給了我們一定的啟發(部分利用)。
5.2 殺棋分數調整
增加了置換表以後，殺棋分數要進行調整——置換表中的分值不能是距離根節點的殺棋分值，而是距離目前(置換表項)節點的分值。是以當分值接近殺棋分數時，ProbeHash 和 RecordHash 都要做細微的調整：
(1) 對于RecordHash：置換表項記錄的殺棋步數 = 實際殺棋步數 - 置換表項距離根節點的步數；
(2) 對于ProbeHash：實際殺棋步數 = 置換表項記錄的殺棋步數 + 置換表項距離根節點的步數。
5.3 殺手(Killer)走法
殺手走法就是兄弟節點中産生Beta截斷的走法。根據國際象棋的經驗，殺手走法産生截斷的可能性極大。很顯然，兄弟節點中的走法未必在目前節點下能走，是以在嘗試殺手走法以前先要對它進行走法合理性的判斷。在第二章裡寫過CanMove（走法是否合理）這個函數，這裡它将大顯身手。如果殺手走法确實産生截斷了，那麼後面耗時更多的 GenerateMove （生成所有走法）就可以不用執行了。
如何儲存和擷取“兄弟節點中産生截斷的走法”呢？我們可以把這個問題簡單化——距離根節點步數(nDistance)同樣多的節點，彼此都稱為“兄弟”節點，換句話說，親兄弟、堂表兄弟以及關系更疏遠的兄弟都稱為“兄弟”。
我們可以把距離根節點的步數(nDistance)作為索引值，構造一個殺手走法表。每個殺手走法表項存有兩個殺手走法，走法一比走法二優先：存一個走法時，走法二被走法一替換，走法一被新走法替換；取走法時，先取走法一，後取走法二。
5.4 優化走法順序
利用各種資訊管道(如置換表、殺手走法、曆史表等)來優化走法順序的手段稱為“啟發”。第五章以前，我們隻用曆史表作啟發，但從這個版本開始，我們采用了多種啟發方式：
(1) 如果置換表中有過該局面的資料，但無法完全利用，那麼多數情況下它是淺一層搜尋中産生截斷的走法，我們可以首先嘗試它；
(2) 然後是兩個殺手走法(如果其中某個殺手走法與置換表走法一樣，那麼可以跳過)；
(3) 然後生成全部走法，按曆史表排序，再依次搜尋(可以排除置換表走法和兩個殺手走法)。
這樣，我們就可以構造一個狀态機，來描述走法順序的若幹階段：
首先要定義走法結構：
其中Next方法就是狀态機的實作：
提取置換表和儲存置換表的代碼如下：
SearchFull函數中生成所有走法，并逐一走這些走法被Next方法所替代：
以上程式未經充分測試，發現問題請及時回報。
下一章将實作以下目标：
實作開局庫；
實作PVS(主要變例搜尋)；
把根節點的搜尋單獨處理，增加搜尋的随機性；
克服由長将引起的置換表的不穩定性。
其他未說明的内容請參閱源碼注釋，如有問題，敬請指出。
本章節源碼百度雲盤：
連結：中國象棋程式設計（五）置換表
提取碼：1234