宣告：本程式設計參考象棋巫師原始碼（開發工具dephi 11，建議用delphi 10.3以上版本），
這一章計劃初步實作搜索演算法，前兩章基本上按照我自己對中國象棋的理解來設計程式，從這章開始參照象棋巫師演算法，
3.1、局面評價
中國象棋共有7種棋子：將（帥）、士、相、馬、車、炮、兵，局面評價中最關鍵的因素是每種棋子的價值，子力價值是跟它的絕對位置相關的，比如兵(卒)，過河前基本上沒有什么威脅，子力價值就很低，過河后分數大漲，越接近九宮分數就越高，九宮中心甚至接近一個馬或炮的值，再比如馬，在臥槽的位置和在掛角的位置對將（帥）的影響非常大，在此位置子力評分很高，如此一來，每個兵種就都會有一個與絕對位置相關的價值，因此我們定義一個三維常量陣列：vlPc:array [0..6,0..9,0..8] of Byte（從“象眼”中照搬過來的），這個子力價值表水平左右對稱，以紅方為基準，黑方使用時只須顛倒縱向資料即可，
我們在TPieceMove內定義兩個常量：vlRed, vlBlack:Integer; 用來記錄紅、黑雙方的子力價值；定義Evaluate函式來評價局面分，即紅黑雙方的子力價值差，先走棋再加3分，我們可以每次走棋后，全盤搜索每個棋子的位置來計算局面分，但是這樣做太浪費時間了，因為根本沒有必要每次都把棋盤掃描一遍，我們定義了兩個函式來實作每步走棋計算分值：呼叫 AddPiece (放一枚棋子)和 DelPiece (取走一枚棋子)，可以趁這個機會更新 Evaluate，這樣的局面評價函式已經足夠了，
3.2、極大極小搜索演算法
以上均為準備作業，現在我們先從最簡單的搜索演算法學起：極大極小搜索演算法，這個演算法這樣首先這樣評價局面：
如果黑方被將死了，那么評價函式回傳一個充分大的正數；如果紅方被將死了，那么回傳一個充分大的負數，如果紅方是贏棋或者很有希望贏，那么函式通常會回傳正數；如果黑方是贏棋或者很有希望贏，那么回傳負數；如果棋局是均勢或者是和棋，那么回傳在零左右的數值，
按照搜索演算法的思路，我們先定義常量：MATE_VALUE = https://www.cnblogs.com/zhangxiny/p/10000; 最高分值，即將死的分值，極大搜索時，初始化始最優值為負無窮，即—MATE_VALUE；極小搜索時，為正MATE_VALUE，這樣定義的好處是可以確定沒有走過任何棋，
簡要描述一下這個函式是如何運作的，假設根局面(棋盤上當前局面)是紅方走，先生成紅方所有合理走法，逐一走這些走法，呼叫“maxSearch”函式，生成黑方所有合理著法，在每個后續局面中，呼叫的是“MinSearch”函式，它對局面作出評價并回傳，由于現在是紅方走，因此紅方需要讓評價盡可能地大，能得到最大值的那個著法被認為是最好的，因此回傳這個著法的評價，“minSearch”函式正好相反，當黑方走時呼叫“Min”函式，而黑方需要盡可能地小，因此選擇能得到最小值的那個著法，這兩個函式是互相遞回的，即它們互相呼叫，直到達到所需要的深度為止，當函式到達最底層時，它們就回傳“Evaluate”函式的值，如果在深度為1時呼叫“MinMax”函式，那么“Evaluate”函式在走完每個合理著法之后就呼叫，選擇一個能達到最佳值的那個著法導致的局面，如果層數大于1，那么另一方有權選擇局面，并找一個最好的，
舉個例子，電腦為A，人類為B，A在走棋之前需要思考，A走了某一步后，看看B有哪些走法，B又不傻，所以B肯定是要選擇讓A得分最少的走法走棋，而A會選擇在所有走法中B認為得分最少的走法中分值最高的走法，也就是說Ａ的走法取決于Ｂ，反之亦然，聽起來大概會比較抽象比較繞吧，試著多讀幾遍，多理解理解，
通過極大極小搜索演算法，電腦就可以初步自動回應走棋了，極大極小搜索演算法可以合成負極大搜索，搜索程序如下圖：
紅色數字是當前節點的分值，藍色數字是父節點對子節點回傳值取負后的值，
搜索進行到C1、C2、C3時，要做評估，得到的估值是12、15、13，由于此時輪到紅方走棋，表示紅方在三個局面分別有12、15、13的優勢，在極大極小搜索中，要在B1求這三個局面估值的最小值，現在我們可以這樣來看，黑方在C1、C2、C3的優勢分別為-12、-15、-13，黑方顯然在B1點需要對三個局面做一個選擇，選擇的目標當然是優勢最大化，可以這樣表示：max(-12, -15, -13)；
在極大極小搜索中，B1是黑方走棋，是極小點，應該求最小值，現在由于多加了一個負號，也變成求極大值了，B1點也成了極大點，
黑方在B1、B2、B3分別取得了-12、-5、-14的優勢，對于紅方來講，則在這三個點分別有12、5、14的優勢，所以在A點，輪到紅方走棋，它會在B1、B2、B3中選擇最大值，即：max(12, 5, 14)，這里看出A的選擇了嗎？
代碼如下：
function negaMaxSearch (depth:Integer):Integer;
var
vlBest,i,value:Integer;
mvs:TArray<TMoves>;
s,d:TPoint;
id:Byte;
begin
// 深度為0，呼叫評估函式并回傳分值
if depth = 0 then
Exit(pcMove.evaluate);
vlBest:=-MATE_VALUE; // 初始最優值為負無窮
mvs:= pcmove.generateMoves; // 生成當前局面的所有走法
value:= 0;
for i:= 0 to Length(mvs)-1 do
begin
s:=mvs[i].src;
d:=mvs[i].dest;
if not pcMove.makeMove(s,d,id) then Continue;
value:=-negaMaxSearch(depth - 1);
PcMove.undoMakeMove(s,d,id);
if value > vlBest then
vlBest:= value;
if depth = MINMAXDEPTH then
Search.mvResult:= mvs[i];
end;
Result:=vlBest;// 回傳當前節點的最優值
end;
這個函式有一個常量：MINMAXDEPTH＝３，呼叫時，引數depth必須也等于3，通過測驗，我們會發現這個搜索演算法運行時要檢查整個博弈樹，然后盡可能選擇最好的線路,但因為分枝因子太大導致效率非常低，無法做到很深的搜索，搜索５層基本卡死，
3.3、Alpha-Beta搜索
這是本章的重點，要把這個演算法搞明白得費一番功夫，Alpha-Beta搜索好處在于裁剪了不必要的分枝因子，簡單來講就是這個搜索演算法就是在負極大搜索演算法的基礎上加上范圍[Alpha-Beta]，在這個范圍內的演算法可以考慮，同時不斷縮小Alpha的范圍，超過Beta就要截斷，最開始，Alpha、Beta的值也是“負MATE_VALUE”和“正MATE_VALUE”，當函式遞回時，Alpha和Beta不但取負數而且位置交換了，這樣縮小了搜索范圍，從而減少搜索數量，
- 演算法思路：這個演算法思想是在搜索中傳遞兩個值，第一個值是Alpha，即搜索到的最好值，任何比它更小的值就沒用了，因為策略就是任何小于或等于Alpha的值都要舍棄，第二個值是Beta，即對于對手來說最壞的值，對中國象棋來說，這是對手不能承受的最壞的結果，因為對手達到這個值就等于輸棋，我們知道在對手看來，他總是要找到一個對策比Beta好的著法，走棋的一方沒有機會使用這種策略，在搜索著法時，每個搜索過的著法都回傳跟Alpha和Beta有關的值，它們之間的關系非常重要，或許意味著搜索可以停止并回傳，如果某個著法的結果小于或等于Alpha，那么它就是很差的著法，可以拋棄，因為在這個策略中，局面對走棋的一方來說是以Alpha為評價的，如果某個著法的結果大于或等于Beta，那么整個結點就作廢了，因為對手不希望走到這個局面，而它有別的著法可以避免到達這個局面，因此如果我們找到的評價大于或等于Beta，就證明了這個結點是不會發生的，剩下的合理著法沒有必要再搜索，如果某個著法的結果大于Alpha但小于Beta，那么這個著法就是走棋一方可以考慮走的，除非以后有所變化，因此Alpha會不斷增加以反映新的情況，有時候可能一個合理著法也不超過Alpha，這在實戰中是經常發生的，此時這種局面是不予考慮的，為了避免這樣的局面，我們必須在博弈樹的上一個層局面選擇另外一個著法，Alpha-Beta搜索裁剪因子如下圖演示：
從圖示上看，Alpha剪掉比自己的小的分枝，Beta減掉比自己大的分枝，關鍵點在于Alpha-Beta搜索必須進行排序，
- 演算法實作：我們根據以上思路寫出一個Alpha-Beta搜索函式，偽代碼（以下來自象棋巫師）：
function AlphaBeta(var vlAlpha, vlBeta, nDepth:integer):Integer; var vl:integer; begin if nDepth=0 then Exit(局面評價函式); 生成全部走法; 排序全部走法; for (每個生成的走法) do begin 走這個走法; vl =:-AlphaBeta(-vlBeta, -vlAlpha, nDepth - 1); 撤消這個走法; if vl >= vlBet then Exit(vlBeta); if vl > vlAlpha then vlAlpha = vl; end; Result:= vlAlpha; end;
但是，這樣的程式根本走不出棋來，因為它回傳的是一個分數而不是一個走法，另外，我們還發現幾個問題：
(1) 排序的依據是什么？
(2) 是不是每個生成的走法都可以走？
(3) 如果什么走法都走不出來，那么回傳vlAlpha合理嗎？
針對以上幾個問題，我們對程式做如下改進：
(0) 如果函式在根節點處被呼叫，就把最佳走法作為電腦要走的棋；
(1) 國際象棋程式的經驗證明，歷史表是很好的走法排序依據；
(2) 由于我們的走法生成器并沒有考慮自殺(被將軍)的情況，因此走完一步后要檢查是否被將軍了，被將軍時應立即退回來；
(3) 如果沒有走出過任何走法，說明當前局面是殺棋或困斃局面，應該回傳殺棋的分數，
下面是改進過的程式，改進的地方已標出：
function AlphaBeta(vlAlpha,vlBeta,nDepth:Integer):Integer;
var
vl:integer;
begin
if nDepth = 0 then
Exit(局面評價函式);
生成全部走法;
按歷史表排序全部走法;{--添加---}
for (每個生成的走法) do
begin
走這個走法;
if (被將軍) then {--添加---}
撤消這個走法 {--添加---}
else {--添加---}
begin
int vl:= -AlphaBeta(-vlBeta, -vlAlpha, nDepth - 1);
撤消這個走法;
if vl >= vlBeta then
begin
將這個走法記錄到歷史表中;{--添加---}
Exit(vlBeta);
end;
if vl > vlAlpha then
begin
設定最佳走法;{--添加---}
vlAlpha = vl;
end;
end;
end;
if (沒有走過任何走法) then {--添加---}
Exit(殺棋的分數); {--添加---}
將最佳走法記錄到歷史表中; {--添加---}
if (根節點) then {--添加---}
最佳走法就是電腦要走的棋; {--添加---}
Resutl:= vlAlpha;
end;
- 殺棋的分數：遇到將死或困斃的局面時，應該回傳 nDistance - MATE_VALUE，這樣程式就能找到最短的搜索路線，nDistance 是當前節點距離根節點的步數，每走一個走法，nDistance 就增加1，每撤消一個走法，nDistance 就減少1，如果程式中使用了置換表，這個問題將變得更加復雜，我們以后再討論，
- 歷史表：國際象棋程式的經驗證明，歷史表是很好的走法排序依據，那么，什么樣的走法要記錄到歷史表中去呢？象棋小巫師選擇了以下兩類走法：
A. 產生Beta截斷的走法；
B. 不能產生Beta截斷，但它是所有PV走法(vl > vlAlpha)中最好的走法，
Delphi實作演算法需要這樣：
- 首先，我們必須建立一個走法歷史表，象棋巫師里把走法定義為一個16位無符號整數（Word），結構如下（每個XY各占4位）：
| Dest | Src | ||
| Y | X | Y | X |
我們之前的代碼也必須做出調整，將生成所有走法的函式更改為回傳整數陣列，以兼容象棋巫師的演算法，定義走法歷史表：nHistoryTable:array [Word] of Integer; 象棋巫師的歷史表是一個大小為65536的陣列，正好能將走法的數值(mv)作為指標，因此根據走法取得歷史表的值非常容易，即nHistoryTable[mv]，那么，一個走法記錄到歷史表，究竟該給 nHistoryTable 中的這個元素加多少分的值呢？沿用國際的經驗——深度的平方，所以，更新歷史表的代碼非常簡單： Inc（nHistoryTable[mv], nDepth * nDepth);
- 其次，對這個歷史表按進行排序nDepth的平方從大到小排序，采用了快速排序法，Delphi泛型自帶快速排序法，代碼如下：
uses System.Generics.Collections,System.Generics.Defaults;//泛型排序必須參考單元 function CompareHistory(const mv1,mv2:Integer):Integer;//定義從大到小的排序函式，mv即為走法 begin Result:=Search.nHistoryTable[mv2] -Search.nHistoryTable[mv1];//按深度的平方進行比較 end; function SortMVS:TArray<Integer>; var Comparer: IComparer<Integer>; begin MVS:=pcMove.GenerateMoves; Comparer := TComparer<Integer>.Construct(CompareHistory); TArray.Sort<Integer>(MVS,Comparer); Result:=MVS; end;
- 最后，實作Alpha-Beta搜索演算法：
{超出邊界(Fail-Soft)的Alpha-Beta搜索程序}
function SearchFull(vlAlpha,vlBeta,nDepth:Integer):Integer;
var
i,vl, vlBest:Integer;
pc:Byte;
MVS:TArray<Integer>;
Comparer: IComparer<Integer>;
s,d:TPoint;
mvBest:Integer;
begin
// 一個Alpha-Beta完全搜索分為以下幾個階段
// 1. 到達水平線，則回傳局面評價值
if nDepth = 0 then
Exit(pcMove.Evaluate);
// 2. 初始化最佳值和最佳走法
vlBest:= -MATE_VALUE; // 這樣可以知道，是否一個走法都沒走過(殺棋)
mvBest:=0; // 這樣可以知道，是否搜索到了Beta走法或PV走法，以便保存到歷史表
// 3. 生成全部走法，并根據歷史表排序
MVS:=pcMove.GenerateMoves;
Comparer := TComparer<Integer>.Construct(CompareHistory);
TArray.Sort<Integer>(MVS,Comparer);
// 4. 逐一走這些走法，并進行遞回
for i:= 0 to High(MVS) do
begin
s:=GetSrc(MVS[i]);
d:=GetDest(MVS[i]);
if pcMove.MakeMove(s,d, pc) then{新增函式，在移動棋子的基礎上，添加了判斷被將軍和nDistance++}
begin
vl:= -SearchFull(-vlBeta, -vlAlpha, nDepth - 1);
pcMove.UndoMakeMove(s,d, pc);
// 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邊界
if pcMove.nDistance = 0 then // 搜索根節點時，總是有一個最佳走法(因為全視窗搜索不會超出邊界)，將這個走法保存下來
Search.mvResult:=mvBest;
end;
end;
end;
end;
// 5. 所有走法都搜索完了，把最佳走法(不能是Alpha走法)保存到歷史表，回傳最佳值
if vlBest =-MATE_VALUE then
Exit(pcMove.nDistance - MATE_VALUE); // 如果是殺棋，就根據殺棋步數給出評價
if mvBest>0 then
Inc(Search.nHistoryTable[mvBest], nDepth * nDepth);// 如果不是Alpha走法，就將最佳走法保存到歷史表
Result:=vlBest;
end;
以上代碼即實作了Alpha-Beta搜索演算法，電腦開始有一點點智能，可以走一些合理的棋了，
3.4、核心代碼改動說明：
這一章有較多的改動，有必要說明一下，
TPieceMove中新增或修改的主要屬性和方法：
（1）vlRed屬性：紅方所有棋子的價值
（2）vlBlack屬性：黑方所有棋子的價值
（3）addPiece、DelPiece方法：此方法增加了一項功能，就是在增減棋子時，更新vlRed和vlBlack，
（4）MakeMove方法：改方法做了一些改進，如果移動棋子后，發現老將被對方攻擊，也就是說這步棋是去送死的，那么就要撤銷對棋子的移動，并回傳false，
（5）UndoMakeMove方法：撤銷對棋子的移動，
新增csSearch單元：
（1）負極大搜索演算法：negaMaxSearch，
（2）Alpha-Beta搜索演算法：SearchFull(vlAlpha,vlBeta,nDepth:Integer):Integer;
csCommn單元中新增內容：
（1）vlPc三維陣列常量：棋子在棋盤每個位置的子力價值，
（2）定義了一些常量：
ADVANCED_VALUE = https://www.cnblogs.com/zhangxiny/p/3; // 先行權分值
MATE_VALUE = https://www.cnblogs.com/zhangxiny/p/10000; // 最高分值，即將死的分值
WIN_VALUE = https://www.cnblogs.com/zhangxiny/p/MATE_VALUE - 200; // 搜索出勝負的分值界限，超出此值就說明已經搜索出殺棋了
MINMAXDEPTH=3;//用于負極大搜索演算法的搜索層次
（2）定義TSearch記錄，其成員有：
mvResult：//這是搜索演算法找到的最佳走法，隨后電腦就會執行這步棋，
nHistoryTable:array [Word] of Integer; //歷史表
（3）去掉TMoves走法記錄
Chess_Unit單元：
（1）添加悔棋功能
（2）添加電腦回應走棋
其他未說明的函式請參閱原始碼注釋，
本章節原始碼百度云盤：
鏈接：中國象棋程式設計（三）制定規則
提取碼：1234
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/380809.html
標籤：Delphi