FireMonkey3D之中国象棋程序设计（六）完善算法

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

FireMonkey3D之中国象棋程序设计（六）完善算法

相关

标签