FireMonkey3D之中国象棋程序设计(六)完善算法

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 校验码中的 dwLock1wmv 是走法,wvl 是权重(随机选择走法的几率,仅当两个相同的 dwLock 有不同的 wmv 时,wvl 的值才有意义)

  搜索一个局面时,首先不做Alpha-Beta搜索,而是查找开局库中有没有对应的项,有的话就取出所有相同项,从中随机选择一个 wmvElephantEye 为了压缩开局库的容量,所有对称的局面只用一项,所以当一个局面在开局库中找不到时,还应该试一下它的对称局面是否在 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