声明：本程序设计参考象棋巫师源码（开发工具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
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
