search.c

GNU国际象棋C++源代码Windows版的

/*
 * search.c - C source for GNU CHESS
 *
 * Copyright (c) 1988,1989,1990 John Stanback
 * Copyright (c) 1992 Free Software Foundation
 * Modified by Conor McCarthy for the Windows environment
 *
 * This file is part of GNU CHESS.
 *
 * GNU Chess is free software; you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free
 * Software Foundation; either version 2, or (at your option) any later
 * version.
 *
 * GNU Chess is distributed in the hope that it will be useful, but WITHOUT ANY
 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 * FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
 * details.
 *
 * You should have received a copy of the GNU General Public License along with
 * GNU Chess; see the file COPYING.  If not, write to the Free Software
 * Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
 */
#include "gnuchess.h"
#include "ttable.h"
#include "ttable.c" /* inline doesn't work with separate compilation!! */
#ifdef NULLMOVE
#undef DEEPNULL
#endif
#if !defined OLDTIME && defined HAVE_GETTIMEOFDAY
double pow ();
#endif
SHORT background = 0;
static SHORT DepthBeyond;
UTSHORT PrVar[MAXDEPTH+1];
SHORT notime = true;
#ifdef IGNUAN
extern SHORT GNUANtop;
extern SHORT GNUANmv;
#endif
#if defined NULLMOVE || defined DEEPNULL
SHORT null;       /* Null-move already made or not */
SHORT no_null;
SHORT PVari;      /* Is this the PV */
#endif
#ifdef DEBUG40
extern int whichway;
#endif
#ifdef IGNUAN
extern GNUANadj();
#endif
#ifdef DEBUG
  int tracetmp;
  UTSHORT DBLINE[MAXDEPTH+1];
  struct leaf *dbptr;
#endif
SHORT zwndw;
SHORT start_stage;
SHORT terminal;
extern SHORT origbrd[64],origcol[64];
extern SHORT OrigGameCnt;
int repetition (void);

#define interval 15

#include "ataks.h"

/* ............    MOVE GENERATION & SEARCH ROUTINES    .............. */
inline
int
repetition ()

/*  Check for draw by threefold repetition.  */

{
  register SHORT i, c, cnt;
  register SHORT f, t;
  SHORT b[64];

  cnt = c = 0;
  /* try to avoid work */
  memset ((CHAR *) b, 0, sizeof (b));
  for (i = GameCnt; i > Game50; i--)
    {
      f = GameList[i].gmove >> 8;
      t = GameList[i].gmove & 0x3f;

      if (b[f]) c--;
      if (b[t]) c--;
      b[f] = (board[f] + (color[f] << 8))
        - (board[t] + (color[t] << 8)) + b[t];
      b[t] = (board[t] + (color[t] << 8)) - (no_piece + (neutral << 8));
      if (b[f]) c++;
      if (b[t]) c++;
      if (c == 0)
        if (((i ^ GameCnt) & 1))
     cnt++;
    }
  return (cnt);
}

int
pick (SHORT p1, SHORT p2)

/*
 * Find the best move in the tree between indexes p1 and p2. Swap the best
 * move into the p1 element.
 *
 */
{
  register struct leaf *p, *q, *r, *k;
  register s0;
  struct leaf temp;

  k = p = &Tree[p1];
  q = &Tree[p2];
  s0 = p->score;
  for (r = p + 1; r <= q; r++)
    if (r->score != 9999 && (r->score) > s0)
      {
   s0 = (r->score);
   p = r;
      }
  if (p != k)
    {
      temp = *p;
      *p = *k;
      *k = temp;
      return true;
    }
  return false;
}

void
SaveBoard (void)
{
  SHORT sq;
  for (sq=0;sq<64;sq++)
   {
    origbrd[sq]=board[sq];
    origcol[sq]=color[sq];
   }
  OrigGameCnt=GameCnt;
}

#ifdef DEBUG
UTSHORT trace[MAXDEPTH+1];
CHAR traceline[256];
UTSHORT tracelog[MAXDEPTH+1];
int tracen = 0;
int traceflag = 0;
int traceply = 0;
#endif
int bookflag = false;
int Jscore = 0;

static int TCcount, TCleft;
void
SelectMove (SHORT side, SHORT iop)


/*
 * Select a move by calling function search() at progressively deeper ply
 * until time is up or a mate or draw is reached. An alpha-beta window of
 * -Awindow to +Bwindow points is set around the score returned from the
 * previous iteration. If Sdepth != 0 then the program has correctly
 * predicted the opponents move and the search will start at a depth of
 * Sdepth+1 rather than a depth of 1.
 */

{
  static SHORT i, tempb, tempc, tempsf, tempst, xside, rpt;
  static SHORT alpha, beta, score;
  static struct GameRec *g;
  SHORT InChkDummy;
  static SHORT start_score;
  static SHORT plyscore;
#ifdef DEBUG

  if (debuglevel & (512 | 1024))
    {
      CHAR b[32];
      SHORT c1, c2, r1, r2;
      tracen = 0;
      traceflag = false;
      traceply = 0;
      tracelog[0] = 0;
      while (true)
   {
     printf ("debug?");
     gets (b);
     if (b[0] == 'p')
       traceply = atoi (&b[1]);
     else if (b[0] == '\0')
       break;
     else
       {
         c1 = b[0] - 'a';
         r1 = b[1] - '1';
         c2 = b[2] - 'a';
         r2 = b[3] - '1';
         trace[++tracen] = (locn (r1, c1) << 8) | locn (r2, c2);
       }
     if (tracen == 0 && traceply > 0)
       traceflag = true;
   }

    }
#endif

  flag.timeout = false;
  flag.back = false;
  flag.musttimeout = false;
  flag.abort=false;
  INCscore = 0;
  xside = side ^ 1;
/* we need to test if recycle will still have an effect -- DanO*/
/*  recycle = (GameCnt % rehash) - rehash;  not used anymore */

  /* if background mode set to infinite */
  if (iop == 2)
    {
      ResponseTime = 9999999;
      background = true;
    }
  else
    {
      player = side;
      if (TCflag)
   {
     TCcount = 0;
     background = false;
     if (TimeControl.moves[side] < 1)
       TimeControl.moves[side] = 1;
     /* special case time per move specified */
     if (flag.onemove)
       {
         ResponseTime = TimeControl.clock[side] - 100;
         TCleft = 0;
       }
     else
       {
         /* calculate avg time per move remaining */

         ResponseTime = TimeControl.clock[side] / TimeControl.moves[side];
         ResponseTime = ResponseTime * 2 / 3;
         ResponseTime += TCadd / 2;
         TCleft = (int) ResponseTime / 5;
         if (TimeControl.moves[side] < 5)
      TCcount = MAXTCCOUNTX - 10;
       }
     if (ResponseTime < 101)
       {
         ResponseTime = 100;
         TCcount = MAXTCCOUNTX - 10;
       }
     else if (ResponseTime < 200)
       {
         TCcount = MAXTCCOUNTX - 10;
       }
   }
      else
   {
     ResponseTime = MaxResponseTime;
     TCleft = 0;
     ElapsedTime (1);
   }
      if (TCleft)
   {
     TCcount = ((int) ((TimeControl.clock[side] - ResponseTime)) / 2) / TCleft;
     if (TCcount > MAXTCCOUNTX)
       TCcount = 0;
     else
       TCcount = MAXTCCOUNTX - TCcount;
   }
      else
   TCcount = MAXTCCOUNTX;
    }

#ifdef QUIETBACKGROUND
  if (!background)
#endif /* QUIETBACKGROUND */
    ShowSidetoMove ();
  ExtraTime = 0;
  if (Sdepth > 0)
      goto inloop;
  else
      ElapsedTime (1);

  ExaminePosition ();
  stage= -1; /* Force init in UpdateWeights() */
  start_score= Tscore[0]= Tscore[1]= score=
    evaluate (side, 1, 1, 0, -9999, 9999, &terminal, &InChkDummy);
  start_stage= stage;
#ifdef HISTORY
  memset ((UCHAR *) history, 0, (unsigned long) sizeof (history));
#endif
  FROMsquare = TOsquare = -1;
  PV = 0;
  if (iop == 1)
    hint = 0;
  for (i = 0; i < MAXDEPTH; i++)
    PrVar[i] = killr0[i] = killr1[i] = killr2[i] = 0;
  /* set initial window for search */
  alpha = score - ((computer == black) ? BAwindow : WAwindow);
  beta = score + ((computer == black) ? BBwindow : WBwindow);
  rpt = 0;
  TrPnt[1] = 0;
  root = &Tree[0];
  VMoveList (side, 1);
  /* can I get a book move? */
#ifndef IGNUAN
  if (flag.regularstart && Book)
    {
      flag.timeout = bookflag = OpeningBook (&hint, side);
      if (TCflag && !flag.onemove && !background)
   ResponseTime += ResponseTime;
    }
#endif
#ifdef IGNUAN
  if (GNUANtop) GNUANadj();
#endif
  /* Are we in stalemate or mated? */
  if (TrPnt[2] == TrPnt[1])
    {
      flag.timeout = true;
      score = -9999;
    }
  if (TrPnt[2] - TrPnt[1] == 1)
      flag.timeout = true;
  if (flag.timeout)
      rpt = repetition ();
  for (i = TrPnt[1]; i < TrPnt[2]; i++) pick (i, TrPnt[2] - 1);
  /* zero stats for hash table */
  reminus = replus = 0;
  GenCnt = NodeCnt = ETnodes = EvalNodes = 0;
#if defined HASHSTATS
  ClearHashStats();
#endif
  plyscore = score;
  Jscore = 0;
  zwndw = 20;
  /********************* main loop ********************************/
  Sdepth = (MaxSearchDepth < (MINDEPTH - 1)) ? MaxSearchDepth : (MINDEPTH - 1);
#if defined NULLMOVE || defined DEEPNULL
  no_null= (emtl[xside] == 0 || emtl[side] == 0);
#endif
inloop:
  while (!flag.timeout)
    {
      /* go down a level at a time */
      Sdepth++;
      TCcount = 0;
#if defined NULLMOVE || defined DEEPNULL
      null = 0;
      PVari = 1;
#endif
      DepthBeyond = Sdepth + ((Sdepth == 1) ? FBEYOND : flag.threat ? SBEYOND: TBEYOND); 

#ifndef BAREBONES
#ifdef QUIETBACKGROUND
      if (!background)
#endif /* QUIETBACKGROUND */
   ShowDepth (0);
#endif
      root->score= Tscore[0]= Tscore[1]= start_score;
      /* search at this level returns score of PV */
      score = search (side, 1, Sdepth, 0, alpha, beta, PrVar, &rpt, QBLOCK, false);
      /* save PV as killer */
      for (i = 1; PrVar[i] != 0; i++) killr0[i] = PrVar[i];

      /* low search failure re-search with (-inf,score) limits  */
      if (score < alpha)
   {
#ifndef BAREBONES
     reminus++;
#ifdef QUIETBACKGROUND
     if (!background)
#endif /* QUIETBACKGROUND */
       ShowDepth ('-');
#endif

#if defined NULLMOVE || defined DEEPNULL
           null = 0;
           PVari = 1;
#endif
          Tscore[0]= Tscore[1]= start_score;
     score = search (side, 1, Sdepth, 0, -9999, 9999, PrVar, &rpt,QBLOCK,false);

          /* save PV as killer */
          for (i = 1; PrVar[i] != 0; i++) killr0[i] = PrVar[i];
   }
      /* high search failure re-search with (score, +inf) limits */
      else if (score > beta && score != 9998)
   {
#ifndef BAREBONES
     replus++;
#ifdef QUIETBACKGROUND
     if (!background)
#endif /* QUIETBACKGROUND */
       ShowDepth ('+');
#endif
#if defined NULLMOVE || defined DEEPNULL
           null = 0;
           PVari = 1;
#endif
          Tscore[0]= Tscore[1]= start_score;
     score = search (side, 1, Sdepth, 0, -9999, 9999, PrVar, &rpt,QBLOCK,false);

          /* save PV as killer */
          for (i = 1; PrVar[i] != 0; i++) killr0[i] = PrVar[i];
   }
      /**************** out of search ********************************************/
      if (flag.musttimeout || Sdepth >= MaxSearchDepth)
   flag.timeout = true;

      else if (TCflag && (Sdepth > (MINDEPTH - 1)) && (TCcount < MAXTCCOUNTR))
   {
     if (plyscore - score > ZDELTA)
       {
         TCcount++;
         ExtraTime += TCleft;
       }