基本介紹
- 中文名：置換表
- 外文名：Transposition Tables
基本原理,算法流程,Zobrist 哈希方法,置換策略分析,單置換表,雙置換表,
基本原理
置換表（Translation Table，TT）的原理是採用哈希表技術將已搜尋的結點的局面特徵、估值和其他相關信息記錄下來，如果待搜尋的結點的局面特徵在哈希表中已經有記錄，在滿足相關條件時，就可以直接利用置換表中的結果。
對一個結點進行估值時，應先查找置換表，置換表命中失敗，再對該結點進行搜尋。置換表在使用時要及時更新，當計算出一個結點的估值時，應立即將這個結點的相關信息保存到置換表。為了加快處理速度，一般不採用再散列技術，一旦在寫入置換表的時候發生衝突，直接覆蓋相關的數據項，只要保證在讀取操作時避免讀取到錯誤數據即可，因此置換表的設計應使得發生衝突的機率很小。
置換表一般容量很大，以儘量保存龐大的博弈樹各結點信息，並且應實現快速訪問，因此多用哈希表技術來具體實現。與一般哈希表不同的是，這裡的哈希表一般不使用再散列技術，在哈希衝突很少時，不去進行再散列，能有效加快處理速度，如果出現寫衝突，直接覆蓋，只要在讀訪問時不使用錯誤數據即可。
置換表中的一個數據項應包含詳細信息說明對應博弈樹的何種結點，該結點的搜尋評估值，以及評估值對應的搜尋深度等。其中評估值一般還可以分成兩部分，分別保存該結點的上限值和下限值，比如渴望搜尋和空窗探測等，多數時候是得到一個結點的上限值或下限值就剪枝返回，這種值同樣有利用價值。如果得到了某結點的準確評估值，可以將上限值和下限值保存成一樣來表示。置換表在使用時一般要及時更新。置換表技術在當今機器博弈領域已經是廣為使用的技術，對搜尋速度有明顯的提高。機器博弈中的博弈樹往往是非常龐大的，alpha-beta 搜尋由於一般情況下是邊生成結點邊搜尋，並不需要保存整個博弈樹，記憶體開銷並不大。如果置換表用來保存博弈樹已經搜尋過的全部結點信息，記憶體開銷將是巨大的。從剪枝效率的角度考慮，由於博弈樹頂層的剪枝對剪枝效率具有決定性的影響，因此，即使置換表只保存較頂層的博弈樹結點信息，仍然能夠明顯地提高剪枝效率。
對於置換表的使用，還有一種情況需要特別指出，博弈樹最末層結點在很多情況下保存到置換表中，並沒有作用，這一點容易被很多人所忽視，導致置換表使用上的浪費，也降低了搜尋速度。置換表不僅僅是提高重複搜尋的效率，還能有效地解決博弈圖的搜尋。
算法流程
首先，確定哈希函式，將結點對應局面映射為一個哈希值，這個哈希值通常為一個 32 位的整數，根據這個值計算出哈希地址。一種快速而簡單的方法就是將這個哈希值對置換表的長度取餘數，作為待訪問的哈希表元素的地址。
其次，哈希函式可能產生地址衝突，即不同的哈希值映射到了同一地址，上述 32 位的哈希值是不安全的。置換表中的數據項，還應必須包含一個唯一標識局面特徵的校驗值，這個校驗值通常是一個 64 位的整數，從理論上來說，64 位整數也有可能發生衝突，但這個機率極小，在實際中可以忽略不計。使用哈希函式通過哈希值找到置換表數據項的地址之後，再驗證該數據項的校驗值和待搜尋結點對應的局面的特徵值是否一致，只有二者一致，才認為查找命中。
再次，對於 PV 結點、All 結點和 Cut 結點，後兩種情況並非對應結點的精確估值。因此置換表置換表中的數據項，不僅要記錄對應結點的估值結果，還應同時記錄這個估值的類型，究竟是一個精確值，還是一個上界值或者下界值。
最後，結點的估值結果與搜尋深度有關，搜尋深度越深，估值越準確。故置換表中的數據項，還應記錄結點對應的搜尋深度。如果下次搜尋到的局面 A，在置換表中找到了同樣的局面 A'，如果 A 對應的搜尋深度為Depth，置換表中 A'對應的搜尋深度為 Depth'，顯然只有當 Depth' ≥ Depth 時，才能直接使用置換表中 A'的估值信息，但如果 Depth > Depth'，則置換表中對應結點的估值信息就沒有意義了，因為需要再向前搜尋幾步才能得到一個更準確的值。
因此，置換表中的一個數據項至少應包含如下數據：結點局面的 64 位校驗值、搜尋深度、估值以及估值的類型。置換表的數據結構可用類 C/C++偽代碼定義如下：
struct HashItem
{
unsigned long long checksum; //表示棋盤局面的 64 位校驗值
ENTRYTYPE type;/*估值的類型，EXACT 表示精確值，LOWERBOUND表示下界值，UPPERBOUND 表示上界值*/
int depth; //結點對應的搜尋深度
int value; //結點的估值
}HashTable[HashTableSize];
Zobrist 哈希方法
一種高效的生成一個特定局面下的 32 位哈希值和 64 位校驗值方法就是Zobrist 哈希方法：創建一個 64 位數組 Z[type][pos]，其值為 type 類型的棋子在棋盤坐標 pos 的一個 64 位隨機整數。對棋盤上存在的所有的棋子的隨機數求異或，結果保存在 64 位變數 BoardKey 內，就得到了該局面的一個校驗值。這樣，類型為 type1 的棋子從 pos1 移動到 pos2 時，只要將當前的 BoardKey 值作如下操作：
（1）將要移動的棋子從棋盤上去除，BoardKey = BoardKey ^ Z[type1][pos1]，(“^”表示按位異或運算，下同)；
（2）如果目的位置有對方類型為 type2 的棋子被吃掉，也將其去除，BoardKey= BoardKey ^ Z[type2][pos2]；
（3）將移動後的棋子置入目的坐標，BoardKey = BoardKey ^ Z[type1][pos2]。
使用 Zobrist 哈希方法構造一個局面下的 32 位哈希值的方法與構造 64 位校驗值的方法是一樣的，只需將 64 位的整型變數改為 32 位即可。Zobrist 哈希方法使結點哈希值的產生可以隨著著法的執行或撤銷逐步進行。結合了置換表的 α-β 搜尋/剪枝算法可用類 C/C++偽代碼表示如下：
int AlphaBeta_TT(board, depth, alpha, beta)
{
value = SearchTT(HashKey, alpha, beta, depth);
if(置換表命中) return value;
if(GameOver(board) || depth == 0)
{
value = Evaluation(board);
if(depth == 0) InsertHashTable(HashKey, EXACT, value, depth);
return value;
}
best = -∞; ValueIsExact = 0;
w = CreateSuccessors(board, p); /*生成 board 下的 w 種著法 P0...Pw1*/
for(i = 0; i < w; i++)
{
HashKey = MakeMoveWithTT(board, pi);
value = -AlphaBeta_TT(board, depth - 1, -beta, -alpha);
HashKey = RestoreMoveWithTT(board, pi);
if(value >= beta)
{
InsertHashTable(HashKey, LOWERBOUND, value, depth);
return value; //β 剪枝
}
if(value > best)
{
best = value;
if(value > alpha)
{
alpha = value; ValueIsExact = 1;
InsertHashTable(HashKey, EXACT, value, depth);
}
}
}
if(ValueIsExact) InsertHashTable(HashKey, EXACT, value, depth);
else InsertHashTable(HashKey, UPPERBOUND, value, depth);
return best;
}
置換表的長度（所包含的數據項數量）也是需要考慮的因素。置換表越長，發生地址衝突的機率越小，從而能保存更多的局面信息，置換表命中率越高，算法性能越好。在西洋棋計算機博弈中，置換表的長度每增加 1 倍，命中率約提高 7%。但置換表的長度也並非越大越好，一旦置換表的長度超過物理記憶體的承受能力，導致使用了硬碟中的虛擬記憶體，性能反而下降的很快。
置換表數據的更新有兩種策略，即深度優先和隨時替換。深度優先策略不比較校驗值，寫入置換表的數據對應的搜尋深度大於置換表相應數據項的深度，才能替換原有數據；始終替換策略注重實時性，對新估值的局面信息不作任何判斷，立即更新置換表中對應的數據項。
置換策略分析
單置換表
由於幾步以前搜尋的結果對本步搜尋來說依然具有一定的可信度，因此不必在每次搜尋之前都清空置換表，而是保持這些數據作為以後搜尋的信息!但數據的可信程度隨著棋局的演變不斷降低，而置換表的容量是有限的，相對於幾近無窮的棋局，當出現重複局面時，需要確定究竟哪些局面該存入置換表中。目前對於單置換表策略，主要有深度優先和隨時替換兩種。
深度優先
該策略的基本思想：置換表中原有數據距離葉子節點越遠，即深度越深，說明置換表的可信程度越高。在寫入哈希表時，如果置換表中已經有了該存儲項，且寫入數據的搜尋深度大於哈希表內已存儲數據的深度，則替換掉原有數據；否則說明可信度不高，不進行任何操作。讀出時也做相同處理，只有存儲數據的深度大於當前搜尋深度時，數據才是可信的!由於該策略著重於原有數據的利用，導致了一些最新的信息因為搜尋深度的問題而無法保留。
隨時替換
該策略的基本思想：置換表中原有數據一般都只有較小的搜尋子樹，並且原有的搜尋深度一般小於後來產生的搜尋深度，因而用新產生的棋局信息不做任何判斷立即更換置換表中原有數據。該策略具有很好的實時性，但卻導致了表中具有較高深度的數據大量丟失。
雙置換表
雙置換表策略結合了以上兩種策略的優勢，即採用兩個置換表分別進行深度優先替換和隨時替換策略的搜尋。其基本思想：首先基於深度優先的考慮，一般來說深度越深其子樹的節點數越多，就更容易顯示雙置換表的優勢，減少搜尋節點數，並且數據的可靠性越高，因而將深度優先策略作為雙置換表的第一層；其次，依據局部性原理，最近訪問的內容往往在不遠的將來會被再次訪問的可能性非常大，因而一旦遇到與表中以前所存局面相同時就立即替換，隨時替換置換表策略在寫入和讀出時都不用做深度判斷，只要可以剪枝就執行，因此將隨時替換策略作為雙置換表的第二層。然而雙置換表並不是兩個表的簡單羅列，其最大的難點在於如何使這兩個表有機配合工作，確定什麼時候該剪枝及以哪個表中的數據為準進行剪枝。如果配合不好其效率將會大大降低，甚至導致誤剪枝等嚴重後果。另外，兩個置換表的同時使用必然增加存儲量，從而加大了置換表查找和寫入的時間和空間難度等。基於以上問題，置換策略設計如下：
（1）如果待置入節點的深度大於等於雙置換表第 1 層節點存儲的深度，則將當前第 1 層存儲內容移至第 2 層，第 1層存儲寫入待置入節點信息；
（2）如果待置入節點的深度小於雙置換表第 1 層節點存儲的深度，則將待置入節點信息寫入第 2 層存儲中。
基於以上置換策略，在套用雙置換表時，只要其中有一個置換表可以剪枝，則進行剪枝處理。
