treesearch.cpp

《C++Builder程序设计范例--中国象棋》配书盘自述文件

#include <stdio.h>
#include "MainForm1.h"
#include "CDefines.h"
#include "Chess.h"
#include "Global.h"

#undef max
#undef min
#define max(a, b)  (((a) > (b)) ? (a) : (b))
#define min(a, b)  (((a) < (b)) ? (a) : (b))

bool ComputerThinking = false;
bool GotValidMove = false;

int LegalMoves;
extern bool OnlyKnOrPa;

extern double WantedTime;
WORD MessageToPost;
bool NoComputerMove = false;


static MOVETYPE MoveTemp[MAXPLY - BACK + 2];

MOVETYPE *MoveTable = &MoveTemp[-BACK];

#define     TOLERANCE       8
#define     IF_EQMOVE(a, b)     if ((a.movpiece == b.movpiece) && (a.newpos1 \
== b.newpos1) && (a.oldpos == b.oldpos) && (a.content == b.content) \
&& (a.spe == b.spe))

typedef struct
    {
        short principvar;  /*  搜索树的主要变化  */
        MAXTYPE value,     /*  静态局面估值 */
            evaluation;    /*  位置估值 */
    } INFTYPE;
typedef enum {mane, specialcap, norml} MOVGENTYPE;  /*  移动类型  */
typedef struct
    {
        PATHTYPE path;        /*  下一个回合的最好路线 */
        short capturesearch;  /*  吃子搜索  */
        MAXTYPE maxval;       /*  搜索树中返回的最大值 */
        int nextply;          /*  下一个回合的搜索深度 */
        INFTYPE next;         /* 下一个回合的信息 */
        short zerowindow;     /*  宽度为零的α~β窗口  */
        MOVGENTYPE movgentype;
    } SEARCHTYPE;

typedef struct
    {
        MAXTYPE alpha, beta;
        int ply;
        INFTYPE *inf;
        MOVETYPE *bestpath;
        SEARCHTYPE *S;
    } PARAMTYPE;


short ChckTab[MAXPLY+3];
short *CheckTable = &ChckTab[1];
bool SkipSearch;


static INFTYPE startinf;     /*  一个回合的信息  */
static MAXTYPE alphawindow;  /*  α窗口值  */
static MAXTYPE repeatevalu;  /*  一个回合中的最大值 */

static MAXTYPE search(MAXTYPE alpha, MAXTYPE beta, int ply, INFTYPE *inf,
        MOVETYPE *bestpath);


/*
在信息窗体中打印深度值和着法
*/
inline void PrintMove()
{
   if (!Depth)
      {
      sprintf(buffer, "%-7d%7s", MaxDepth, MoveStr(&MoveTable[0]));
      InfoForm->SetDepthText(buffer);
      }
}

/*
 *  初始化将军表
 */

static void RemoveKillMove(void)
{
    CheckTable[-1] = 0;
}


static DEPTHTYPE searchstatedepth;

/*
 *  备份搜索且设置对话环境
 */

static void getprogramstate(void)
{
    COLORTYPE oldplayer;

    searchstatedepth = Depth;
    while (Depth > 0)
{
        Depth--;
        oldplayer = Opponent;
        Opponent = Player;
        Player = oldplayer;
        Perform(&MoveTable[Depth], 1);   //回退一步
    }
    Depth--;
    if (Opan) TakeBackMove(&MoveTable[Depth]);
}


/*
 *  恢复搜索环境
 */

static void getsearchstate(void)
{
    COLORTYPE oldplayer;

    if (Opan) MakeMove(&MoveTable[Depth+1]);
    Depth++;
    while (Depth < searchstatedepth)
    {
        Perform(&MoveTable[Depth], 0);  //向前看一步
        oldplayer = Player;
        Player = Opponent;
        Opponent = oldplayer;
        Depth++;
    }
}

inline bool UsableMessage(MSG msg)
{
  if (msg.hwnd != Application->MainForm->Handle || msg.message != WM_COMMAND)
      return false;
   return true;
}
static void MessageScan()
{
   MSG msg;

   if (!::PeekMessage(&msg, Application->MainForm->Handle, 0, 0, PM_REMOVE))
      return;

   if (Analysis)
      {
      switch (msg.message)
         {
         case WM_SETCURSOR :
            ::DispatchMessage(&msg);
            break;
         case WM_COMMAND :
            if ((msg.wParam -(MainForm->Stop->Command))==0)
               {
               SkipSearch = true;
               AutoPlay = false;
               }
           break;
         default:
            ::TranslateMessage(&msg);
            ::DispatchMessage(&msg);
            break;
         }
      }
   else
      {
      switch (msg.message)
         {
         case WM_LBUTTONDOWN :
            getprogramstate();
            NoComputerMove = true;
            GotValidMove = false;
            ::DispatchMessage(&msg);
            NoComputerMove = false;
            if (Opan && !MultiMove && GotValidMove)
               {
               IF_EQMOVE(KeyMove, MoveTable[Depth + 1])
                  {
                      SkipSearch = false;
                      GotValidMove = false;
                      EnterKeyMove();
                      StartAnalysis();
                      PrintBestMove(&MainPath[0], MainEvaluat);
                      MainForm->Menu=MainForm->TChessThinkMenu; //动态设置主窗体主菜单
                      Screen->Cursor=TCursor(crWaitCursor);
                  }
               else
                  SkipSearch = true;
               }
            getsearchstate();
            break;
         default:
            if (UsableMessage(msg))
               {
               SkipSearch = true;
              if (msg.message != WM_PAINT)
                 ::PostMessage(Application->MainForm->Handle, msg.message, msg.wParam, msg.lParam);

               }
            else
               {
              ::TranslateMessage(&msg);
              ::DispatchMessage(&msg);
               }
            break;
         }
      }
}


/*
 *  检查以前是否生成过棋子移动
 */

short generatedbefore(PARAMTYPE *P)
{

    if (P->S->movgentype != mane)
    {
        IF_EQMOVE(MoveTable[Depth], P->bestpath[Depth]) return 1;
    }
    return 0;
}


/*
 *  测试剪枝。剪枝值包含最大可能估值
 */

inline short cut(MAXTYPE cutval, PARAMTYPE *P)
{
    short ct = 0;

    if (cutval <= P->alpha)
    {
	ct = 1;
        if (P->S->maxval < cutval) P->S->maxval = cutval;
    }
    return ct;
}


/*
  执行移动，计算估值，测试剪枝等。
 */

static short update(PARAMTYPE *P)
{
    short selection;

    AddNode(&Nodes);
    P->S->nextply = P->ply - 1;      /*  计算下一个回合  */
    if (Level == matesearch)  /*  将死搜索  */
    {
        Perform(&MoveTable[Depth], 0);  /*  向前看一步 */
        /*  检查移动是否合法  */

       if (Attacks(Opponent, PieceTable[Player][0].isquare)
          || (Repetition(0) >= 2))
           goto TAKEBACKMOVE;

            if (!Depth) LegalMoves++;
        CheckTable[Depth] = 0;
        P->S->next.value = P->S->next.evaluation = 0;
        if (P->S->nextply <= 0)  /* 计算将军并执行剪枝 */
        {
	    if (!P->S->nextply)
                CheckTable[Depth] = Attacks(Player,
                    PieceTable[Opponent][0].isquare);
	    if (!CheckTable[Depth])
                if (cut(P->S->next.value, P)) goto TAKEBACKMOVE;
        }
        goto ACCEPTMOVE;
    }
    /*  在第一轮中保证有限的特殊吃子优先得到搜索 */
    if (MaxDepth <= 1)
        if (P->S->capturesearch && Depth >= 2)
            if (!((MoveTable[Depth].content < MoveTable[Depth].movpiece)
                || (P->S->movgentype == specialcap) || (MoveTable[Depth].oldpos
                == MoveTable[Depth-2].newpos1)))
                goto CUTMOVE;
            /*  计算下一步静态增量估值  */
    P->S->next.value = -P->inf->value + StatEvalu(&MoveTable[Depth]);
    /* 计算将军表（只计算能将军的移动）不能算是一个回合 */
    CheckTable[Depth] = PieceAttacks(MoveTable[Depth].movpiece, Player,
        MoveTable[Depth].newpos1, PieceTable[Opponent][0].isquare);
    if (CheckTable[Depth]) P->S->nextply = P->ply;
        /*  在最后的吃子搜索中进行选择  */
    selection = ((P->S->nextply <= 0) && !CheckTable[Depth] && (Depth > 0));
    if (selection)   /*  检查估值  */
	if (cut(P->S->next.value + 0, P)) goto CUTMOVE;
    Perform(&MoveTable[Depth], 0);  /*  向前看一步  */
    /*  检查移动是否合法  */
       if (Attacks(Opponent, PieceTable[Player][0].isquare)
          || (Repetition(0) >= 2))
           goto TAKEBACKMOVE;
    if (!Depth)
    {
        LegalMoves++;
        P->S->next.value += random(4);
    }
    P->S->next.evaluation = P->S->next.value;
ACCEPTMOVE:
    if (Analysis)
      PrintMove();
    return 0;
TAKEBACKMOVE:
    Perform(&MoveTable[Depth], 1);  //回退一步
CUTMOVE:
    if (Analysis)
       PrintMove();
    return 1;
}


/*
给予和棋加分或罚分，如果无法取胜的话就定为和棋
 */

static short drawgame(SEARCHTYPE *S)
{
    int drawcount;
    REPEATTYPE searchrepeat;
    SIXTYTYPE searchsixty;

    if (Depth == 1)
    {
        searchsixty = SixtyMoveCnt();
        searchrepeat = Repetition(0);
       	if (searchrepeat >= 3)
        {
            S->next.evaluation = 0;
	    return 1;
	}

        drawcount = 0;
        if (searchsixty >= 116)  /*  58次移动中没有吃子 */
            drawcount = 3;
        else
        {
            if (searchrepeat >= 2)  /*  第二次重复  */
                drawcount = 2;
            else if (searchsixty >= 20)  /*  10次移动中没有吃子  */
               drawcount = 1;
        }
        S->next.value += (repeatevalu / 4) * drawcount;
	S->next.evaluation += (repeatevalu / 4 ) * drawcount;
    }
    if (Depth >= 3)
    {
        searchrepeat = Repetition(1);
        if (searchrepeat >= 2)       /*  连续重复算平局  */
        {
            S->next.evaluation = 0;
	    return 1;
        }
    }
    return 0;  //能赢就要赢
}


/*
根据计算出的路线和最大值更改最好路线和最大估值
 */

inline void updatebestpath(PARAMTYPE *P)
{
    memcpy(P->bestpath, &P->S->path[0], sizeof(PATHTYPE));
    /* *bestpath = P->S->path; */
    P->bestpath[Depth] = MoveTable[Depth];
    if (!Depth)
    {
        MainEvaluat = P->S->maxval;
        if (Level == matesearch)
            P->S->maxval = alphawindow;
        if (Analysis) PrintBestMove(&MainPath[0], MainEvaluat);
    }
}


/*
棋路树搜索程序的内部循环。MoveTable[Depth]表包含了移动。
 */

static short loopbody(PARAMTYPE *P)
{
    COLORTYPE oldplayer;
    short lastanalysis;

    if (generatedbefore(P)) return 0;
    if (Depth < MAXPLY)
    {
        P->S->path[Depth + 1] = ZeroMove;
        if (P->S->movgentype == mane)
            memmove(&P->S->path[0], P->bestpath, sizeof(PATHTYPE));
            /* P->S->path = *bestpath; */
    }
    /*  Principvar 意味着主要变着的搜索 */
    /*  零窗口意味着宽度为0的α~β窗口  */
    P->S->next.principvar = 0;
    P->S->zerowindow = 0;
    if (P->inf->principvar)
        if (P->S->movgentype == mane)
            P->S->next.principvar = (P->bestpath[Depth+1].movpiece != empty);
        else
            P->S->zerowindow = (P->S->maxval >= P->alpha);
REPEATSEARCH:
    if (update(P)) return 0;
    if (Level == matesearch)  /*  无子可动、将死时停止搜索  */
        if ((P->S->nextply <= 0) && !CheckTable[Depth]) goto NOTSEARCH;
    if (drawgame(P->S)) goto NOTSEARCH;
    if (Depth >= MAXPLY)
        goto NOTSEARCH;
    /*  使用递归调用搜索分析下一个回合 */
    oldplayer = Player;
    Player = Opponent;
    Opponent = oldplayer;
    Depth++;
    if (P->S->zerowindow)
        P->S->next.evaluation = -search(-P->alpha - 1, -P->alpha, P->S->nextply,
                &P->S->next, &P->S->path[0]);
    else
        P->S->next.evaluation = -search(-P->beta, -P->alpha, P->S->nextply,
                &P->S->next, &P->S->path[0]);
    Depth--;
    oldplayer = Opponent;
    Opponent = Player;
    Player = oldplayer;
NOTSEARCH:
    Perform(&MoveTable[Depth], 1);  /*  退回一步  */
    if (SkipSearch)
        return 1;
    lastanalysis = Analysis;  /*  扫描消息并检查是否设置 SkipSearch  */
    MessageScan();
    if (!SkipSearch)
        if (Analysis && !SingleStep && ((!Depth) || !lastanalysis))
        {
            StopTime(&ChessClock);
            if (MainEvaluat > alphawindow)
                SkipSearch = ChessClock.totaltime >= (WantedTime * 1.5);
        }
    if (Analysis && (MaxDepth <= 1))
        SkipSearch = 0;
    P->S->maxval = max(P->S->maxval, P->S->next.evaluation);  /*  更改最大值 */
    IF_EQMOVE(P->bestpath[Depth], MoveTable[Depth])  /*  走子没有变化的话，更改最好路线 */
        updatebestpath(P);
    if (P->alpha < P->S->maxval)      /*  更改α窗口并检查剪枝 */
    {
        updatebestpath(P);
        if (P->S->maxval >= P->beta)
            return 1;
        /*  调整最大值，在原来最大值的基础上加上一个容忍常数  */
        if (P->ply >= 2  && P->inf->principvar && !P->S->zerowindow)
            P->S->maxval = min(P->S->maxval + TOLERANCE, P->beta - 1);
        P->alpha = P->S->maxval;
        if (P->S->zerowindow && ! SkipSearch)
        {
            /*  全宽度搜索（一个不漏） */
            P->S->zerowindow = 0;
            goto REPEATSEARCH;
        }
    }
    return SkipSearch;
}


/*
 *  在新的位置生成吃子移动
 */