中国象棋程序设计(五)置换表

中国象棋程序设计(五)置换表

声明:本程序设计参考象棋巫师源码(开发工具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;

以上程序未经充分测试,发现问题请及时反馈。

下一章将实现以下目标:

  1. 实现开局库;
  2. 实现PVS(主要变例搜索);
  3. 把根节点的搜索单独处理,增加搜索的随机性;
  4. 克服由长将引起的置换表的不稳定性。

其他未说明的内容请参阅源码注释,如有问题,敬请指出。

本章节源码百度云盘:

链接:中国象棋程序设计(五)置换表

提取码:1234