中国象棋程序设计(四)水平效应、检查重复局面

中国象棋程序设计(四)水平效应、检查重复局面

声明:本程序设计参考象棋巫师源码(开发工具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位,放在 dwKeydwLock0 和 dwLock1 中,其中 dwKey 在检查重复局面时用,也作为置换表的键值,dwLock0 和 dwLock1 用作置换表的校验值,另外,dwLock1 还是查找开局库的依据(后面会提到)。RC4的算法比较简单,就是异或操作,就不在这里贴出来。Zobrist校验码的操作放在了AddPieceDelPiece这两个函数里,随着走法进行异或操作,这样每次棋局发生变化时,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