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

  // 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;

//检测重复局面
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;

{历史走法信息}
type TMoveStruct=record
  wmv:Word ;//历史走示
  pcCaptured, ucbCheck:Byte;//是否吃子，是否将军
  dwKey:LongWord;//当前棋局
  procedure SetValue(mv:Word;pc:Byte;bCheck:Boolean;dwKey_:Cardinal);
end;

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;

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;

// 静态(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;