宣告：本程式設計參考象棋巫師原始碼（開發工具dephi 11，建議用delphi 10.3以上版本），
這一章主要完善演算法，本章目標：
- 實作開局庫；
- 實作PVS(主要變例搜索)；
- 把根節點的搜索單獨處理，增加搜索的隨機性；
- 克服由長將引起的置換表的不穩定性，
6.1 實作開局庫
開局庫幾乎是每個象棋程式必備的部件，它的好處是：
(1) 即使再笨的程式，開局庫能使得它們在開局階段看上去不那么業余；
(2) 通過隨機選擇走法，讓開局靈活多變，增加對弈的趣味性，
我們程式使用開源象棋程式 ElephantEye 的開局庫Book.dat檔案，開局庫檔案的結構：
type BookItem=record dwLock:Cardinal; wmv, wvl:Word; end;
其中，dwLock 記錄了局面 Zobrist 校驗碼中的 dwLock1，wmv 是走法，wvl 是權重(隨機選擇走法的幾率，僅當兩個相同的 dwLock 有不同的 wmv 時，wvl 的值才有意義)，
搜索一個局面時，首先不做Alpha-Beta搜索，而是查找開局庫中有沒有對應的項，有的話就取出所有相同項，從中隨機選擇一個 wmv，ElephantEye 為了壓縮開局庫的容量，所有對稱的局面只用一項，所以當一個局面在開局庫中找不到時，還應該試一下它的對稱局面是否在 BookTable 中，在這里我們將最新的Book.dat檔案轉化成了SQLite資料庫檔案，這樣就不需要BookItem，在這里說明下，由于我們程式局面記錄使用的是10X9的二維資料，起始是（0,0），象棋巫師使用的是長度256的一維陣列記錄局面，轉換成二維陣列時，縱向、橫向均平移了3個單位，在我們程式中相當于從（3,3）點為起始，為了使用象棋巫師的開局庫，我們必須與之兼容，也要轉換成一維陣列，開局庫在制作時，wmv 走法也要還原成我們程式的走法，這里我們已經處理好了，直接用就可以，以下函式要做變化(csCommon單元)：
function PtToInteger(p:TPoint):Byte; begin Result:=P.X +P.Y shl 4+51;//加51是為了與象棋巫師對應，相當于將起點定為（3,3） end;
以下為開局庫搜索代碼（我們程式使用了SQLiteTable開源檔案，需要附帶SQLite.dll檔案，不想附帶DLL檔案，可以將其改為FireDAC）：
{加載開局庫}
procedure LoadBook;
begin
BookDB:=TSQLiteDatabase.Create('book.db3');
BookDB.ExecSQL('create temp table TBook as select * from Books');//創建記憶體表
Randomize;
end;
{查找開局}
function SearchBook:Integer;
var
i, vl, nBookMoves,mv:Integer;
mvs,vls:array[Byte]of Integer;
bMirror:Boolean;
dwLock:Cardinal;
posMirror:TPieceMove;
s,d:TPoint;
begin
// 搜索開局庫的程序有以下幾個步驟
// 1. 搜索當前局面
bMirror:= FALSE;
dwLock:= pcMove.zobr.dwLock1;
BookTB:=BookDB.GetTable('select * from TBook where dwLock='+Inttostr(dwLock));
// 2. 如果沒有找到，那么搜索當前局面的鏡像局面
if BookTB.RowCount =0 then
begin
bMirror:=TRUE;
pcMove.Mirror(posMirror);
dwLock:=posMirror.zobr.dwLock1;
BookTB:=BookDB.GetTable('select * from TBook where dwlock='+Inttostr(dwLock));
end;
// 3. 如果鏡像局面也沒找到，則立即回傳
if BookTB.RowCount =0 then
Exit(0);
// 4. 把走法和分值寫入到"mvs"和"vls"陣列中
vl:=0;nBookMoves:= 0;
for i:=0 to BookTB.RowCount-1 do
begin
if bMirror then
mv:=MIRROR_MOVE(BookTB.FI(1))//走法
else
mv:=BookTB.FI(1);
s:=GetSrc(mv);
d:=GetDest(mv);
if pcMove.canMove(s,d) then
begin
mvs[nBookMoves]:= mv;
vls[nBookMoves]:= BookTB.FI(2);//權重
vl:=vl+vls[nBookMoves];
Inc(nBookMoves);
if nBookMoves= 256 then // 防止"book.db3"中含有例外資料
break;
end;
BookTB.Next;
end;
if vl = 0 then
Exit(0); // 防止"BOOK.db3"中含有例外資料
// 5. 根據權重隨機選擇一個走法
vl:= Random(vl);//這樣權重也是隨機的，有什么區別？
for i:= 0 to nBookMoves-1 do
begin
vl:=vl-vls[i];
if vl < 0 then
break;
end;
Result:= mvs[i];
end;
6.2 根節點的特殊處理
現在我們的程式一開局不會總是跳正馬了，根據 ElephantEye 提供的開局庫，它大部分時候走中炮，有時也走仙人指路(進兵)或飛相，可是當它脫離開局庫時，仍然擺脫不了思維的單一性，例如我們第一步走邊兵(開局庫中當然沒有這個局面)，它仍舊只會跳同一邊的正馬，
一個解決辦法是：在根節點處，讓一個不是最好的走法也能在一定的幾率取代前一個走法，
我們把根節點的搜索函式單獨分離，這樣做有很多好處：
(1) 處理思考的隨機性；
(2) 沒有必要嘗試 Beta 截斷(根節點處 Beta 始終是 +MATE_VALUE)；
(3) 省略了檢查重復局面、獲取置換表、空步裁剪等步驟，
代碼如下：
// 根節點的Alpha-Beta搜索程序
function SearchRoot(nDepth:Integer):Integer;
var
vl, vlBest, mv, nNewDepth:Integer;
Sort:SortStruct;
s,d:TPoint;
begin
vlBest:= -MATE_VALUE;
Sort.Init(Search.mvResult);
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
nNewDepth:= InCheck.ToInteger+nDepth- 1;// 如果老將被攻擊，就多搜索一層
if vlBest = -MATE_VALUE then// 主要變例搜索
vl:= -SearchFull(-MATE_VALUE, MATE_VALUE, nNewDepth, True)
else
begin
vl:= -SearchFull(-vlBest - 1, -vlBest, nNewDepth);
if vl > vlBest then
vl:= -SearchFull(-MATE_VALUE, -vlBest, nNewDepth, True);
end;
UndoMakeMove;
if vl > vlBest then
begin
vlBest:= vl;
Search.mvResult:= mv;
if (vlBest >-WIN_VALUE)and(vlBest < WIN_VALUE) then
begin
//// 增加電腦走棋的隨機性
vlBest:=vlBest + random(RANDOM_MASK) - random(RANDOM_MASK);
if vlBest=DrawValue then
vlBest:=vlBest - 1;
end;
end;
end;
end;
RecordHash(HASH_PV, vlBest, nDepth, Search.mvResult);
SetBestMove(Search.mvResult, nDepth);
Result:=vlBest;
end;
6.3 PVS主要變例搜索
經過前面的作業，走法已經得到了很好的排序，好的走法會先被搜索，這是PVS的基礎，
圖a 圖b
假設第一個走法是最好的走法，沒有引發剪枝，A點的搜索區間為(0, 100)，走法1得到估值30，由于30 > 0，所以A點的alpha變為30，以后的搜索區間變為(30, 100)，所以B2點的搜索區間為(-100, -30)，
可以進一步大膽地考慮，假設第1個走法就是最好的走法，那么后面走法得到的估值不會落在區間(30, 100)，所以從A點的第2個走法開始，要做的就是驗證這種假設，搜索區間為(30, 31)，由于搜索區間很小，搜索速度會很快，回傳值vl有3種情況，
（1）vl <= 30，說明走法不比第1個走法好，假設成立，
（2）vl >= 100，回傳值比A點的原有搜索邊界beta還大，應該剪枝，假設成立，
（3）30 < vl < 100，走法比第1個走法好，假設不成立，
第3種情況時，走法不成立，應該對該走法重新以(30, 100)區間進行搜索，如果得到40，則該走法就是最好的走法，后續搜索又對該走法進行假設驗證，區間為(40, 41)，
6.4 長將判負策略
由于單方面長將不變作負的規則，以前的版本如果發生這種情況，想當然地給予-MATE_VALUE的值，再根據殺棋步數作調整，但是由于長將判負并不是對某個單純局面的評分，而是跟路線有關的，所以使用置換表時就會產生非常嚴重的后果——某個局面的資訊可能來自另一條不同的路線，
解決辦法就是：獲取置換表時把“利用長將判負策略搜索到的局面”過濾掉，為此這個版本中我們把長將判負的局面定為BAN_VALUE(MATE_VALUE - 100)，如果某個局面分值在WIN_VALUE(MATE_VALUE - 200)和BAN_VALUE之間，那么這個局面就是“利用長將判負策略搜索到的局面”，
我們仍舊把部分“利用長將判負策略搜索到的局面”記錄到置換表，因為這些局面提供的最佳走法是有啟發價值的，反過來說，如果“利用長將判負策略搜索到的局面”沒有最佳走法，那么這種局面就沒有必要記錄到置換表了，經經過這種處理，我們的程式在殺棋階段不再會走出莫名其妙的走法了，
以上程式未經充分測驗，發現問題請及時反饋，
本章節原始碼百度云盤（測驗程式打包在里面）：
鏈接：中國象棋程式設計（六）置換表
提取碼：1234
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/390204.html
標籤：Delphi