宣告：本程式設計參考象棋巫師原始碼（開發工具dephi 11，建議用delphi 10.3以上版本），
上一章我們的程式終于會走棋了，不過很多時候它很低能，由于水平線效應，任何變化都只搜索固定的深度，還有，有時它會長將，我們能做哪些改進呢？
本章的目標：
- 用Zobrist校驗碼技術實作重復局面判定；
- 實作靜態(Quiescence)搜索和MVV/LVA啟發；
- 實作將軍延伸和空步(Null-Move)裁剪，
4.1 克服水平線效應
什么是水平線效應？（以下參考自其他博客）
之前搜索到葉子節點，都是呼叫評估函式，并回傳估值，但有時葉子節點是一個吃子走法，這可能得到一個很好的評分，但如果是一個換子，即下一步對手又吃回來，可能局面是一個平手，在葉子節點，局面可能產生劇烈動蕩，除非評估函式能非常精確的反映這一點，那么回傳值不能很好的反映局面真實情況，這種現象稱為水平效應，
克服水平線效應，一般可采取對葉子節點再向下搜索，但是，向下搜索多少步呢？無論多深總有回傳的時候，回傳的又是葉子節點，為了避免不必要的更深搜索，在葉子節點以下，只搜索吃子走法，因為吃子走法是導致局面劇烈動蕩的主要原因，通常把這種思想稱為靜態（Quiescence）搜索，棋子是有限的，吃子走法不會無限膨脹，靜態搜索與Alpha-Beta搜索很相似，主要有以下區別：
（1）靜態搜索沒有深度引數，結束遞回呼叫有兩種情況，一是分值大于beta產生剪枝，二是局面不再有吃子走法，
（2）如果是被將軍的局面，生成所有走法，不是被將軍的局面，只生成吃子走法，
（3）在上一節，生成全部走法后，會使用歷史表的資料對著法排序，以便提高搜索效率，這叫歷史表啟發，如果只生成吃子走法，使用的是MVV/LVA啟發，MVV/LVA的意思是“最有價值的受害者/最沒價值的攻擊者”，這個技術假設最好的吃子是吃到最大的子，如果不止一個棋子能吃到最大的子，那么假設用最小的子去吃是最好的，排序之后，會最先搜索最好的吃子走法，中國象棋棋子價值這樣排列“帥>車>馬（炮）>兵>士（相）”，象棋巫師的價值表是一個23個元素的一維陣列，因為象棋巫師的棋子是這樣定義的：8--14為紅棋，16-22為黑棋，所以這個一維數長度為23，有棋子的區域定義棋子價值，沒有棋子的區域定義為零，為了兼容，我們程式這樣定義：
// MVV/LVA每種子力的價值
cucMvvLva:array[0..32]of Byte =(
4,3,1,1,5,1,1,3,4,3,3,2,2,2,2,2,
4,3,1,1,5,1,1,3,4,3,3,2,2,2,2,2,0);
//排序演算法
function MvvLva(mv:Word):Integer;
var
s,d:TPoint;
begin
s:=GetSrc(mv);
d:=GetDest(mv);
Result:= cucMvvLva[pcMove.chessbd[d.Y,d.X]] shl 3 - cucMvvLva[pcMove.chessbd[s.Y,s.X]]; //計算棋子的權重
end;
{按MVV/LVA值排序的比較函式}
function CompareMvvLva(const lpmv1,lpmv2:Integer):Integer;
begin
Result:=MvvLva(lpmv2) - MvvLva(lpmv1);
end;
此外，我們還通過“將軍延伸”的手段來客服水平線效應，也就是說，在Alpha-Beta搜索的程序中，如果遇到被將軍的局面，就多向下搜索一層，
克服水平線效應的方法有以下幾種：
(1) 靜態(Quiescence)搜索，進入靜態搜索時，要考慮兩種情況，一是不被將軍的情況，首先嘗試不走是否能夠截斷，然后搜索所有吃子的走法(可以按照MVV/LVA排序)；二是被將軍的情況，這時就必須生成所有的走法了(可以按照歷史表排序)，
(2) 空步(Null-Move)裁剪，空步裁剪的代碼非常簡單，但某些條件下并不適用，一是被將軍的情況下，二是進入殘局時(自己一方的子力總價值小于某個閾值)，三是不要連續做兩次空步裁剪，否則會導致搜索的退化，
(3) 將軍延伸，
4.2 檢查重復局面
在之前的程式中，重復局面判斷不是必須的，因為任何變化都只搜索固定的深度，但是靜態搜索和將軍延伸會帶來一個問題——遇到“解將還將”的局面，搜索就會無止境地進行下去，直到程式崩潰，
有兩個辦法可以解決這個問題：
(1) 限制實際搜索深度(通過 nDistance 來限制)；
(2) 自動識別重復局面，遇到這樣的局面就根據規則回傳和棋或殺棋的分數，
前者實作起來非常簡單，我們的程式也這樣做了，但仍舊使程式做了很多無用的搜索，在這個版本中，我們重點把力氣花在檢查重復局面上了，
檢查重復局面的辦法很簡單，每走一個走法就把當前局面的校驗碼記錄下來，再看看前幾個局面的校驗碼是否與當前值相等，當重復局面發生時，就要根據雙方的將軍情況來判定勝負——單方面長將者判負(回傳殺棋分數而不必要繼續搜索了)，雙長將或雙方都存在非將走法則判和(回傳和棋分數)，
我們用了一個 RepStatus 函式來檢查重復，如果局面存在重復，那么它的回傳值將很有意思：
//檢測重復局面
function TPieceMove.RepStatus(nRecur:Integer):Integer;
var
bSelfSide, bPerpCheck, bOppPerpCheck:Boolean;
lpmvs:TMoveStruct;
i:Integer;
begin
bSelfSide:= False;
bPerpCheck:=True;bOppPerpCheck:=True;
i:=nMoveNum-1;
lpmvs:=mvsList[i];
while (lpmvs.wmv<>0)and(lpmvs.pcCaptured= 32) do
begin
if bSelfSide then
begin
bPerpCheck:= bPerpCheck and Boolean(lpmvs.ucbCheck);
if (lpmvs.dwKey=zobr.dwKey) then
begin
Dec(nRecur);
if nRecur= 0 then
begin
Exit(1 + bPerpCheck.ToInteger*2+ bOppPerpCheck.ToInteger*4);
end;
end;
end
else
bOppPerpCheck:= bOppPerpCheck and Boolean(lpmvs.ucbCheck);
bSelfSide:= not bSelfSide;
Dec(i);
lpmvs:=mvsList[i];
end;
Result:=0;
end;
// 重復局面分值
function TPieceMove.RepValue(nRepStatus:Integer):Integer;
var
vlReturn,i,j:Integer;
begin
i:=0;j:=0;
if (nRepStatus and 2)<>0 then i:=nDistance - MATE_VALUE;
if (nRepStatus and 4)<>0 then j:=MATE_VALUE - nDistance;
vlReturn:=i+j;
if vlReturn=0 then Result:=-DRAW_VALUE//和棋分值
else
Result:=vlReturn;
end;
起初bPerpCheck(本方長將)和bOppPerpCheck(對方長將)都設為TRUE，當一方存在非將走法時就改為FALSE，這樣 RepStatus 的回傳值有有這幾種可能：
A. 回傳0，表示沒有重復局面；
B. 回傳1，表示存在重復局面，但雙方都無長將(判和)；
C. 回傳3(=1+2)，表示存在重復局面，本方單方面長將(判本方負)；
D. 回傳5(=1+4)，表示存在重復局面，對方單方面長將(判對方負)；
E. 回傳7(=1+2+4)，表示存在重復局面，雙方長將(判和)，
4.3 Zobrist校驗碼
我們把Zobrist值作為局面的校驗碼，好處在于計算迅速，除了檢查重復局面外，校驗碼還有以下作用：
(1) 作為置換表(Hash表)的鍵值；
(2) 作為開局庫的查找依據，
我們程式Zobrist校驗碼跟開源象棋程式 ElephantEye 是一致的(以空密鑰的RC4密碼流作為隨機序列)，這樣就可以使用 ElephantEye 的開局庫了，Zobrist值總共96位，放在 dwKey、dwLock0 和 dwLock1 中，其中 dwKey 在檢查重復局面時用，也作為置換表的鍵值，dwLock0 和 dwLock1 用作置換表的校驗值，另外，dwLock1 還是查找開局庫的依據(后面會提到)，RC4的演算法比較簡單，就是異或操作，就不在這里貼出來，Zobrist校驗碼的操作放在了AddPiece和DelPiece這兩個函式里，隨著走法進行異或操作，這樣每次棋局發生變化時，dwKey、dwLock0、dwLock1隨之而變，重復局面的判斷依據：dwKey如果與之前的重復了 ，那么就是重復局面，按中國象棋規則“長將作負、不變作和”，重復3次就可以判定了，
程式里定義了歷史走法資訊，這個表記錄了走法、這步棋是否吃子、是否將軍，以及dwKey當前棋局：
{歷史走法資訊}
type TMoveStruct=record
wmv:Word ;//歷史走示
pcCaptured, ucbCheck:Byte;//是否吃子，是否將軍
dwKey:LongWord;//當前棋局
procedure SetValue(mv:Word;pc:Byte;bCheck:Boolean;dwKey_:Cardinal);
end;
這個歷史走法資訊僅是用來判定重復局面，因為吃子之后（吃子自然就不會是重復局面）就會被清零，因此不能用來悔棋，
靜態搜索要生成吃子走法，因此GenerateMoves這個函式要稍作變化，添加引數：bCapture:Boolean=False；函式內僅需將判斷條件更改：
procedure AddMV;
begin
if (Sameside(destPt,srcPt)=False) and ((bCapture and (chessbd[destPt.Y,destPt.X]<32))or(bCapture=False)) then
begin
Result:=Result+[SDToInteger(srcPt,destPt)];
end;
end;
靜態演算法與Alpha-Beta搜索相似，空步裁剪相當簡單：
procedure TPieceMove.NullMove;// 走一步空步
var
dwKey:Cardinal;
begin
dwKey:=zobr.dwKey;
ChangeSide;
mvsList[nMoveNum].SetValue(0, 32, False, dwKey);
inc(nMoveNum);
Inc(nDistance);
end;
procedure TPieceMove.UndoNullMove;// 撤消走一步空步
begin
Dec(nDistance);
Dec(nMoveNum );
ChangeSide;
end;
function TPieceMove.NullOkay:Boolean; // 判斷是否允許空步裁剪
begin
if Player=0 then
Result:=vlRed> NULL_MARGIN
else
Result:=vlBlack> NULL_MARGIN;
end;
Alpha-Beta搜索演算法添加了靜態搜索演算法、檢查重復局面以及空步裁剪，經測驗增加這些演算法后，智能有了大幅提升，居然能走出屏風馬的招式，
代碼如下：
// 靜態(Quiescence)搜索程序
function SearchQuiesc(vlAlpha,vlBeta:Integer):Integer;
var
i, nGenMoves,vl, vlBest:Integer;
mvs:TArray<Integer>;
Comparer: IComparer<Integer>;
s,d:TPoint;
begin
// 一個靜態搜索分為以下幾個階段
// 1. 檢查重復局面
vl:= pcMove.RepStatus;
if (vl <> 0) then
Exit(pcMove.RepValue(vl));
// 2. 到達極限深度就回傳局面評價
if pcMove.nDistance=LIMIT_DEPTH then
Exit(pcMove.Evaluate);
// 3. 初始化最佳值
vlBest:= -MATE_VALUE; // 這樣可以知道，是否一個走法都沒走過(殺棋)
if pcMove.InCheck then
begin
// 4. 如果被將軍，則生成全部走法
mvs:=pcMove.GenerateMoves;
Comparer := TComparer<Integer>.Construct(CompareHistory);
TArray.Sort<Integer>(mvs,Comparer);
end
else
begin
// 5. 如果不被將軍，先做局面評價
vl:= pcMove.Evaluate();
if (vl > vlBest)then
begin
if (vl >= vlBeta) then
Exit(vl);
vlBest:= vl;
if (vl > vlAlpha) then
vlAlpha:= vl;
end;
// 6. 如果局面評價沒有截斷，再生成吃子走法
mvs:=pcMove.GenerateMoves(True);
Comparer := TComparer<Integer>.Construct(CompareMvvLva);
TArray.Sort<Integer>(mvs,Comparer);
end;
nGenMoves:=Length(mvs);
// 7. 逐一走這些走法，并進行遞回
for i:= 0 to nGenMoves-1 do
begin
s:=GetSrc(mvs[i]);
d:=GetDest(mvs[i]);
if pcMove.MakeMove(s,d) then
begin
vl:= -SearchQuiesc(-vlBeta, -vlAlpha);
pcMove.UndoMakeMove;
// 8. 進行Alpha-Beta大小判斷和截斷
if vl > vlBest then // 找到最佳值(但不能確定是Alpha、PV還是Beta走法)
begin
if vl >=vlBeta then // 找到一個Beta走法
Exit(vl); // Beta截斷
vlBest:= vl; // "vlBest"就是目前要回傳的最佳值，可能超出Alpha-Beta邊界
if vl > vlAlpha then// 找到一個PV走法
vlAlpha:= vl; // 縮小Alpha-Beta邊界
end;
end;
end;
// 9. 所有走法都搜索完了，回傳最佳值
if vlBest = -MATE_VALUE then
Result:=pcMove.nDistance - MATE_VALUE
else
Result:=vlBest;
end;
{超出邊界(Fail-Soft)的Alpha-Beta搜索程序}
function SearchFull(vlAlpha,vlBeta,nDepth:Integer;bNoNull:Boolean=False):Integer;
var
i,vl, vlBest,mvBest:Integer;
pc:Byte;
MVS:TArray<Integer>;
Comparer: IComparer<Integer>;
s,d:TPoint;
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. 嘗試空步裁剪(根節點的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;
// 2. 初始化最佳值和最佳走法
vlBest:= -MATE_VALUE; // 這樣可以知道，是否一個走法都沒走過(殺棋)
mvBest:=0; // 這樣可以知道，是否搜索到了Beta走法或PV走法，以便保存到歷史表
// 3. 生成全部走法，并根據歷史表排序
MVS:=pcMove.GenerateMoves;
Comparer := TComparer<Integer>.Construct(CompareHistory);
TArray.Sort<Integer>(MVS,Comparer);
// 4. 逐一走這些走法，并進行遞回
with pcMove do
for i:= 0 to High(MVS) do
begin
s:=GetSrc(MVS[i]);
d:=GetDest(MVS[i]);
if pcMove.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
mvBest:=MVS[i]; // Beta走法要保存到歷史表
break; // Beta截斷
end;
if vl > vlAlpha then // 找到一個PV走法，即vlBate>vl>vlAlpha
begin
mvBest:=MVS[i]; // PV走法要保存到歷史表
vlAlpha:= vl; // 縮小Alpha-Beta邊界
end;
end;
end;
end;
// 5. 所有走法都搜索完了，把最佳走法(不能是Alpha走法)保存到歷史表，回傳最佳值
if vlBest =-MATE_VALUE then
Exit(pcMove.nDistance - MATE_VALUE); // 如果是殺棋，就根據殺棋步數給出評價
if mvBest<>0 then
begin
Inc(Search.nHistoryTable[mvBest], nDepth * nDepth);// 如果不是Alpha走法，就將最佳走法保存到歷史表
if pcMove.nDistance = 0 then // 搜索根節點時，總是有一個最佳走法(因為全視窗搜索不會超出邊界)，將這個走法保存下來
Search.mvResult:=mvBest;
end;
Result:=vlBest;
end;
下一章將實作置換表、采用置換表走法、殺手走法等多種啟發方式，
其他未說明的內容請參閱原始碼注釋，如有問題，敬請指出，
本章節原始碼百度云盤：
鏈接：中國象棋程式設計（四）制定規則
提取碼：1234
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/383000.html
標籤：Delphi