宣告：本程式設計參考象棋巫師原始碼（開發工具dephi 11，建議用delphi 10.3以上版本），
這一章主要介紹置換表，本章目標：
- 實作置換表；
- 采用置換表走法、殺手走法等多種啟發方式，
5.1 置換表
沒有置換表，就稱不上是完整的計算機博弈程式，在搜索程序中，某個搜索結果可能會出現這么多次，這浪費了很多時間，為避免重復搜索，保存搜索結果的表，就是置換表，由于哈希表的讀寫速度很快，通常置換表就由哈希表來實作，
置換表非常簡單，以局面的 Zobrist Key mod HASH_SIZE 作為索引值，每個置換表項存盤的內容無非就是：A. 深度，B. 標志，C. 分值，D. 最佳走法，E. Zobrist Lock 校驗碼，置換表結構：
{置換表結構}
type HashItem=record
ucDepth, ucFlag:Byte;//深度、標志
svl:SmallInt; //分值
wmv, wReserved:Word; //最佳走法
dwLock0, dwLock1:Cardinal; //Zobrist檢驗碼
end;
置換表的處理函式也很傳統——一個 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) 然后生成全部走法，按歷史表排序，再依次搜索(可以排除置換表走法和兩個殺手走法)，
這樣，我們就可以構造一個狀態機，來描述走法順序的若干階段：
首先要定義走法結構：
{走法排序結構}
type SortStruct=record
mvHash, mvKiller1, mvKiller2:Integer; // 置換表走法和兩個殺手走法
nPhase, nIndex, nGenMoves:Integer; // 當前階段，當前采用第幾個走法，總共有幾個走法
mvs:TArray<Integer>; // 所有的走法
procedure Init(mvHash_:Integer);// 初始化，設定置換表走法和兩個殺手走法
function Next:Integer; // 得到下一個走法
end;
其中Next方法就是狀態機的實作：
function SortStruct.Next:Integer;
var
mv:Integer;
Comparer: IComparer<Integer>;
s,d:TPoint;
begin
// "nPhase"表示著法啟發的若干階段，依次為：
// 0. 置換表著法啟發，完成后立即進入下一階段；
if nPhase=PHASE_HASH then
begin
nPhase:= PHASE_KILLER_1;
if (mvHash<>0) then
Exit(mvHash);
end;
// 1. 殺手著法啟發(第一個殺手著法)，完成后立即進入下一階段；
if nPhase=PHASE_KILLER_1 then
begin
nPhase:= PHASE_KILLER_2;
s:=GetSrc(mvKiller1);d:=GetDest(mvKiller1);
if (mvKiller1<> mvHash)and(mvKiller1<>0) and pcMove.CanMove(s,d) then
Exit(mvKiller1);
end;
// 2. 殺手著法啟發(第二個殺手著法)，完成后立即進入下一階段；
if nPhase=PHASE_KILLER_2 then
begin
nPhase:= PHASE_GEN_MOVES;
s:=GetSrc(mvKiller2);d:=GetDest(mvKiller2);
if (mvKiller2 <>mvHash)and(mvKiller2<>0)and pcMove.canMove(s,d) then
Exit(mvKiller2);
end;
// 3. 生成所有著法，完成后立即進入下一階段；
if nPhase=PHASE_GEN_MOVES then
begin
nPhase:= PHASE_REST;
mvs:= pcMove.GenerateMoves;
nGenMoves:=Length(mvs);
Comparer := TComparer<Integer>.Construct(CompareHistory);
TArray.Sort<Integer>(mvs,Comparer);
nIndex:= 0;
end;
// 4. 對剩余著法做歷史表啟發；
if nPhase=PHASE_REST then
begin
while (nIndex < nGenMoves) do
begin
mv:= mvs[nIndex];
Inc(nIndex);
if (mv<>mvHash)and(mv<>mvKiller1)and(mv<>mvKiller2) then
Exit(mv);
end;
end;
// 5. 沒有著法了，回傳零，
Result:=0;
end;
提取置換表和保存置換表的代碼如下：
// 提取置換表項
function ProbeHash(vlAlpha,vlBeta,nDepth:Integer;var mv:Integer):Integer;
var
bMate:Boolean; // 殺棋標志：如果是殺棋，那么不需要滿足深度條件
hsh:HashItem;
begin
// 查詢置換表分為以下幾步：
// 1.獲取當前局面的置換表表項
hsh:= Search.HashTable[pcMove.zobr.dwKey and (HASH_SIZE - 1)];
// 2.判斷置換表中的zobristLock校驗碼與當前局面是否一致
if (hsh.dwLock0 <> pcMove.zobr.dwLock0) or(hsh.dwLock1 <> pcMove.zobr.dwLock1) then
begin
mv:= 0;
Exit(-MATE_VALUE);
end;
mv:= hsh.wmv;
bMate:= False;
//3.如果是殺棋，回傳與深度相關的殺棋分數，如果是長將或者和棋，回傳-MATE_VALUE，
if hsh.svl > WIN_VALUE then
begin
hsh.svl:=hsh.svl - pcMove.nDistance;
bMate:= True;
end
else if hsh.svl < -WIN_VALUE then
begin
hsh.svl:=hsh.svl+ pcMove.nDistance;
bMate:= True;
end;
//4.如果置換表中節點的搜索深度小于當前節點，查詢失敗
if (hsh.ucDepth>= nDepth)or(bMate) then
begin
// 5.遇到一個beta節點，只能說明當前節點的值不小于hash.vl，
// 如果正好hash.vl >= vlBeta，說明當前節點會產生beta階段，否則，置換表查詢失敗，需要重新對該局面進行搜索，
if hsh.ucFlag=HASH_BETA then
begin
if hsh.svl >=vlBeta then Exit(hsh.svl) else Exit(-MATE_VALUE);
end
// 6.遇到一個alpha節點，只能說明當前節點的值不大于hash.vl，
// 如果正好hash.vl <= vlAlpha，說明當前節點又是一個alpha節點，并且值不大于hash.vl，否則，置換表查詢失敗，需要重新對該局面進行搜索，
else if hsh.ucFlag=HASH_ALPHA then
begin
if hsh.svl <= vlAlpha then Exit(hsh.svl) else Exit(-MATE_VALUE);
end;
Exit(hsh.svl);
end;
Result:=-MATE_VALUE;
end;
// 保存置換表項
procedure RecordHash(nFlag,vl,nDepth,mv:Integer);
var
hsh:HashItem;
begin
hsh:= Search.HashTable[pcMove.zobr.dwKey and (HASH_SIZE - 1)];// 獲取當前局面的置換表表項
if hsh.ucDepth > nDepth then Exit; // 深度優先覆寫原則
hsh.ucFlag:= nFlag; // 節點型別
hsh.ucDepth:= nDepth; // 搜索深度
// 如果是殺棋，需要將分值轉換為與深度無關的分值，如果是長將或者和棋，又沒有最佳走法，就不記入置換表，
if vl > WIN_VALUE then
begin
hsh.svl:= vl + pcMove.nDistance;
end
else if vl < -WIN_VALUE then
begin
hsh.svl:= vl - pcMove.nDistance;
end
else
hsh.svl:= vl;
hsh.wmv:= mv;
hsh.dwLock0:= pcMove.zobr.dwLock0;
hsh.dwLock1:= pcMove.zobr.dwLock1;
Search.HashTable[pcMove.zobr.dwKey and (HASH_SIZE - 1)]:= hsh;
end;
SearchFull函式中生成所有走法，并逐一走這些走法被Next方法所替代：
{超出邊界(Fail-Soft)的Alpha-Beta搜索程序}
function SearchFull(vlAlpha,vlBeta,nDepth:Integer;bNoNull:Boolean=False):Integer;
var
vl, vlBest,mvBest,mvHash,nHashFlag,mv:Integer;
s,d:TPoint;
Sort:SortStruct;
begin
// 一個Alpha-Beta完全搜索分為以下幾個階段
// 1. 到達水平線，則呼叫靜態搜索(注意：由于空步裁剪，深度可能小于零)
if pcMove.nDistance>0 then
begin
if (nDepth <= 0)then
Exit(SearchQuiesc(vlAlpha, vlBeta));
// 1-1. 檢查重復局面(注意：不要在根節點檢查，否則就沒有走法了)
vl:= pcMove.RepStatus;
if vl <> 0 then
Exit(pcMove.RepValue(vl));
// 1-2. 到達極限深度就回傳局面評價
if pcMove.nDistance = LIMIT_DEPTH then
Exit(pcMove.Evaluate);
// 1-3. 嘗試置換表裁剪，并得到置換表走法
vl:= ProbeHash(vlAlpha, vlBeta, nDepth, mvHash);
if vl > -MATE_VALUE then
Exit(vl);
// 1-3. 嘗試空步裁剪(根節點的Beta值是"MATE_VALUE"，所以不可能發生空步裁剪)
if (not bNoNull)and(pcMove.InCheck=False)and pcMove.NullOkay then
begin
pcMove.NullMove;
vl:= -SearchFull(-vlBeta, 1 - vlBeta, nDepth - NULL_DEPTH - 1, True);//NO_NULL=True
pcMove.UndoNullMove;
if vl >= vlBeta then
Exit(vl);
end;
end
else
mvHash:=0;
// 2. 初始化最佳值和最佳走法
nHashFlag:= HASH_ALPHA;
vlBest:= -MATE_VALUE; // 這樣可以知道，是否一個走法都沒走過(殺棋)
mvBest:=0; // 這樣可以知道，是否搜索到了Beta走法或PV走法，以便保存到歷史表
// 3. 初始化走法排序結構
Sort.Init(mvHash);
// 4. 逐一走這些走法，并進行遞回
with pcMove do
while True do
begin
mv:=Sort.Next;
if mv=0 then Break;
s:=GetSrc(mv);d:=GetDest(mv);
if MakeMove(s,d) then
begin
vl:= -SearchFull(-vlBeta, -vlAlpha, nDepth+InCheck.ToInteger-1);
// 將軍延伸（如果局面處于被將軍的狀態，或者只有一種回棋，多向下搜索一層）
// 將軍延伸或者只有一種走法也要延伸
UndoMakeMove;
// 5. 進行Alpha-Beta大小判斷和截斷
if (vl > vlBest) then // 找到最佳值(但不能確定是Alpha、PV還是Beta走法)
begin
vlBest:= vl; // "vlBest"就是目前要回傳的最佳值，可能超出Alpha-Beta邊界
if (vl >= vlBeta) then // 找到一個Beta走法
begin
nHashFlag:= HASH_BETA;// 節點型別
mvBest:= mv; // Beta走法要保存到歷史表
break; // Beta截斷
end;
if (vl > vlAlpha) then // 找到一個PV走法
begin
nHashFlag:= HASH_PV; // 節點型別
mvBest := mv; // PV走法要保存到歷史表
vlAlpha:= vl; // 縮小Alpha-Beta邊界
end;
end;
end;
end;
// 5. 所有走法都搜索完了，把最佳走法(不能是Alpha走法)保存到歷史表，回傳最佳值
if vlBest =-MATE_VALUE then
Exit(pcMove.nDistance - MATE_VALUE); // 如果是殺棋，就根據殺棋步數給出評價
// 記錄到置換表
RecordHash(nHashFlag, vlBest, nDepth, mvBest);
if mvBest<>0 then
begin
// 如果不是Alpha走法，就將最佳走法保存到歷史表
SetBestMove(mvBest, nDepth);
if pcMove.nDistance = 0 then // 搜索根節點時，總是有一個最佳走法(因為全視窗搜索不會超出邊界)，將這個走法保存下來
Search.mvResult:=mvBest;
end;
Result:=vlBest;
end;
以上程式未經充分測驗，發現問題請及時反饋，
下一章將實作以下目標：
- 實作開局庫；
- 實作PVS(主要變例搜索)；
- 把根節點的搜索單獨處理，增加搜索的隨機性；
- 克服由長將引起的置換表的不穩定性，
其他未說明的內容請參閱原始碼注釋，如有問題，敬請指出，
本章節原始碼百度云盤：
鏈接：中國象棋程式設計（五）置換表
提取碼：1234
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/387679.html
標籤：Delphi