search.c

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

   }
#ifdef notdef
      if (score > (Jscore - zwndw) && score > (Tree[1].score + 250))
   ExtraTime = 0;
#endif
      if (score > plyscore + 250)
   ExtraTime = 0;
      ElapsedTime (2);
      if (root->flags & exact || rpt > 1) flag.timeout = true;
#if defined OLDTIME || !defined HAVE_GETTIMEOFDAY
      else if (!(Sdepth < MINDEPTH) && TCflag && ((4 * et) > (2 * ResponseTime + ExtraTime)))
   flag.timeout = true;
#else
      else if (!(Sdepth < MINDEPTH) && TCflag && !flag.onemove &&
          ((int) ((double)1.93913099 * (pow ((double) et, (double)1.12446928l))) > (ResponseTime + ExtraTime)))
          { flag.timeout = true;}
#endif
      /************************ time control ***********************************/

      /* save PV as killer */
      for (i = 1; PrVar[i] != 0; i++) killr0[i] = PrVar[i];
      if (!flag.timeout) start_score= Tscore[0] = score;
      /* if done or nothing good to look at quit */
      if ((root->flags & exact) || (score < -9000)) flag.timeout = true;
      /* find the next best move put below root */
      if (!flag.timeout)
   {
     /* */
#if !defined NODYNALPHA
     Jscore = (plyscore + score) >> 1;
#endif
     zwndw = 20 + abs (Jscore / 12);
     plyscore = score;
     /* recompute search window */
     beta = score + ((computer == black) ? BBwindow : WBwindow);
#if !defined NODYNALPHA
     alpha = ((Jscore < score) ? Jscore : score) - ((computer == black) ? BAwindow : WAwindow) - zwndw;
#else
     alpha = score - ((computer == black) ? BAwindow : WAwindow);
#endif
   }
#ifndef BAREBONES
#ifdef QUIETBACKGROUND
      if (!background)
#endif /* QUIETBACKGROUND */
   ShowResults (score, PrVar, '.');
#ifdef DEBUG41
      debug41 (score, PrVar, '.');
#endif
#endif
    }
  /******************************* end of main loop ***********************************/
  /* background mode */
  if (iop == 2 || flag.abort)
    return;
    /* if no moves and not in check then draw */
  if ((score == -9999) && !(SqAtakd (PieceList[side][0], xside)))
    {
      root->flags |= draw;
      DRAW = CP[31];    /* No moves */
    }
  else if (GameCnt == MAXMOVES)
    {
      root->flags |= draw;
      DRAW = CP[28];    /* Max Moves */
    }
  /* not in book so set hint to guessed move for other side */
  if (!bookflag)
    hint = ((PrVar[1]) ? PrVar[2] : 0);

   algbr (root->f, root->t, (SHORT) root->flags);
  /* if not mate or draw make move and output it */
  if (((score != -9999) && (rpt <= 1)) || (root->flags & draw))
    {
      MakeMove (side, &Tree[0], &tempb, &tempc, &tempsf, &tempst);
#if !defined NOMATERIAL
      if (flag.material && !pmtl[black] && !pmtl[white] && (mtl[white] < (valueR + valueK)) && (mtl[black] < (valueR + valueK)))
   {
     root->flags |= draw;
     DRAW = CP[57];  /* No pieces */
   }
      else
#endif
      if (!PieceCnt[black] && !PieceCnt[white])
   {
     root->flags |= draw;
     DRAW = CP[32];  /* No pieces */
   }
    }
  else
    { root->score = score; /* When mate, ignore distinctions! * --SMC */
    }
  rpt = repetition ();
  g = &GameList[GameCnt];
  if (g->flags & capture && g->piece == king) { flag.mate = flag.illegal = true; }
  /* If Time Control get the elapsed time */
  if (TCflag) ElapsedTime (1);
  if (rpt > 1) root->flags |= (draw | exact);
  if (score == -9999 /*|| rpt > 1 */)
    mvstr[0][0] = mvstr[1][0] = mvstr[2][0] = mvstr[3][0] = mvstr[4][0] = '\0';
  /* if mate set flag */
  if ((score == -9999) || (score == 9998)) {flag.mate = true; }
  OutputMove (score);
  /* if mate clear hint */
  if (flag.mate) hint = 0;
  /* if pawn move or capture or castle or promote zero repitition array */
  if ((board[root->t] == pawn) || (root->flags & (capture | cstlmask | promote)))
    {
      Game50 = GameCnt;
      ZeroRPT ();
    }
  /* add move to game list */
#ifdef IGNUAN
  GNUANmv = g->gmove;
#endif
  g->score = score;
  g->nodes = NodeCnt;
  g->time = (et + 50) / 100;
  g->depth = Sdepth;
  /* update time comtrol info */
  if (TCflag)
    {
#if defined CHESSTOOL || defined XBOARD
      TimeControl.clock[side] -= (et + OperatorTime + 45);
      timecomp[compptr] = (et + OperatorTime + 45);
#else
      TimeControl.clock[side] -= (et + OperatorTime);
      timecomp[compptr] = (et + OperatorTime);
#endif
      if(notime)TimeControl.clock[side] += TCadd;
      notime = true;
      /* finished our required moves - setup the next set */
      --TimeControl.moves[side];
    }
  /* check for end conditions */
  if ((root->flags & draw) && rpt < 2)
#if !defined CLIENT
    flag.mate = true;
#else
    ;
#endif
  else if (GameCnt == MAXMOVES)
    {
      flag.mate = true;
    }
  /* out of move store, you loose */
  else
    /* switch to other side */
    player = xside;
  Sdepth = 0;
}


int
search (SHORT side,
   register SHORT ply,
   register SHORT depth,
        SHORT ext,
   SHORT alpha,
   SHORT beta,
   UTSHORT *bstline,
   SHORT *rpt,
   SHORT quiescent,
   SHORT didnull)

/*
 * Perform an alpha-beta search to determine the score for the current board
 * position. If depth <= 0 only capturing moves, pawn promotions and
 * responses to check are generated and searched, otherwise all moves are
 * processed. The search depth is modified for check evasions, certain
 * re-captures and threats. Extensions may continue for up to 11 ply beyond
 * the nominal search depth.
 */


{
  register SHORT j, pnt;
  SHORT tempb, tempc, tempsf, tempst;
  SHORT xside, pbst, score, rcnt, InChk;
  UTSHORT mv, nxtline[MAXDEPTH+1];
  struct leaf *node, tmp;
  SHORT best = -12000;
  SHORT bestwidth = 0;
#if defined NULLMOVE || defined DEEPNULL
  SHORT PVsave;
  SHORT PVarisave;
  SHORT nmscore;
#endif
  SHORT extdb= 0;
  SHORT threat= 0;      /* [e-mail] */
  SHORT threat2= 0;     /* [e-mail] */
#ifdef DEBUG
  int xxxtmp;
#endif

  /* look every ZNODE nodes for a timeout */
#if defined NULLMOVE || defined DEEPNULL
  if (!null)
    {
#endif
      if (NodeCnt > ETnodes)
   {
     ElapsedTime (2);
     if (flag.back)
       {
         flag.back = false;
         flag.timeout = true;
         flag.musttimeout = false;
       }
     else if (TCflag || MaxResponseTime)
       {
         if ((et >= (ResponseTime + ExtraTime)) && Sdepth > MINDEPTH )
      {     /* try to extend to finish ply */
        if (!flag.onemove && (flag.back || (TCflag && TCcount < MAXTCCOUNTX)))
          {
            flag.back = false;
            flag.musttimeout = true;
            TCcount += 1;
            ExtraTime += TCleft;
          }
        else
          {
            flag.back = false;
            flag.timeout = true;
            flag.musttimeout = false;
          }
      }
       }
     else if (flag.back)
       {
         flag.back = false;
         flag.timeout = true;
         flag.musttimeout = false;
       }

   }
      else if (!TCflag && flag.musttimeout && Sdepth > MINDEPTH)
   {
     flag.timeout = true;
     flag.musttimeout = false;
   }
#if defined NULLMOVE || defined DEEPNULL
    }
#endif

  xside = side ^ 1;
  if (ply == 1) INCscore= 0;
  score = evaluate (side, ply, depth, ext, alpha, beta, &terminal, &InChk);
  if (ply > 1 && terminal == true)
    return (0);

  /* score > 9000 its a draw or mate */
  if (score > 9000) 
    { 
      bstline[ply] = 0; 
      *rpt = 0;
      return (score); 
    }
  if (ply >= MAXDEPTH-1) return (score);

  /*  No point searching deeper than the ply where a mate was found  */
  if (root->score + ply > 9998)  
      return (score);  

  /*
   * check for possible repetition if so call repetition - rpt is
   * repeat count
   */
  if ((GameCnt >= (Game50 + 3)) && ProbeRPThash(side,hashkey))
    {
      *rpt = repetition ();
      if (*rpt == 1) 
   score = -contempt;
      else if (*rpt > 1 && ply > 1) 
   {
          bstline[ply] = 0;
          return (-contempt);
        }
    }
  else
    *rpt = 0;


  /* Do we need to add depth because of special conditions */
  /* if in check or pawn threat or in capture sequence search deeper */
  /*************************************** depth extensions ***********************************/
 
#define DOTHREAT    (start_stage < THRSTAGE)
#define DOCHECK     (start_stage < 6 /*CHECKSTAGE*/)
#define INRANGE       (ply + depth < DepthBeyond - DEPTHMARGIN)
 
  Threat[ply]= 0;
  if (depth > 0)
    {
      /* Allow opponent a chance to check again */
      if (InChk) 
        {
          if (flag.threat)
            depth= (DOCHECK && INRANGE) ? depth+1: depth;
          else
            depth= (depth < 2) ? 2 : depth;
        }
      else if ((ply>1 && PawnThreat[ply - 1] && INRANGE) ||            
              (flag.rcptr && ply>2 && CptrFlag[ply - 1] && CptrFlag[ply - 2] && 
          ply<Sdepth+2 && CptrFlag[ply-1]==CptrFlag[ply-2]))
          ++depth;
    }
  else
    {
      int tripple_check = 0;
      if (score >= alpha &&
          (InChk || (ply>1 && PawnThreat[ply - 1] && ply<DepthBeyond-4)
          || (hung[side] > 1 && !ext && ply%2==0))) {
        threat2= 1;
        ext++;
        depth= 1;
      }
      else if (score <= alpha &&
               ((ply<Sdepth+4 && ply>4 &&
                ChkFlag[ply-2] && ChkFlag[ply-4] &&
                (ChkFlag[ply-2] != ChkFlag[ply-4] ||
                (flag.threat && DOTHREAT && QueenCheck[ply-2])))
          ||
                (flag.threat && ply<DepthBeyond-DEPTHMARGIN && ply>6
                && ChkFlag[ply-2] && ChkFlag[ply-4] && ChkFlag[ply-6]
                &&  (tripple_check=1)
                && ((ply < Sdepth+4 ?
                  (ChkFlag[ply-2] != ChkFlag[ply-4] || ChkFlag[ply-2] !=
ChkFlag [ply-6])
                  : (ChkFlag[ply-2] != ChkFlag[ply-4] &&
                     ChkFlag[ply-2] != ChkFlag[ply-6] &&
                     ChkFlag[ply-4] != ChkFlag[ply-6]))
                || (DOTHREAT && QueenCheck[ply-2]
                && QueenCheck[ply-4] && QueenCheck[ply-6]
                && QueenCheck[ply-2] != QueenCheck[ply-6]))
                ))) {
          if (tripple_check && DepthBeyond < Sdepth+13+DEPTHMARGIN)
            {
              extdb += 2;
              DepthBeyond += 2;
            }
          depth= 1;
          ext++;
          Threat[ply]= threat= 1;
        }

    }    
  ThreatSave[ply]= ((ply>1 && ThreatSave[ply-1]) || threat);
  /*******************************************************************************************/
  /* Make sure that width test at lower ply gets non random move
     count in case of pruning:  -- TomV
     This test also allows us to delay move generation till the
     null move is done.
   */
  if (ply>1) TrPnt[ply+1]= TrPnt[ply];

  /*
   * if more then DepthBeyond ply past goal depth or at goal depth and
   * score > beta quit - means we are out of the window
   * Changed such that capture are not unlimited.  Kong Sian
   */
#ifdef UNLIMITEDCAPS
  if (depth < 1 && score > beta) return (score);
  if (ply > DepthBeyond) depth = 0;
#else
  if (ply > DepthBeyond || (depth < 1 && score > beta)) { return (score); }
#endif

  /* Lets prune if its likely that we can get a cut.  Kong Sian*/
#ifdef PRUNE
  if ((depth == 1 || depth == 2) && !InChk && score > beta + 50*depth &&
   emtl[side] > valueQ && hung[side]==0)
     return (score);
#endif


/*
 * if below first ply and not at goal depth generate all moves else only
 * capture moves
 */

#if defined ttblsz
     if ( flag.hash && ply > 1 && *rpt == 0)
       {
      if (ProbeTTable (side, depth, ply, &alpha, &beta, &score) == true)
        {
            if (beta == -20000 || alpha > beta)
         {
             bstline[ply] = PV;
             bstline[ply + 1] = 0;
             if (score == -10000+ply) bstline[ply] = 0;
                            /*
                             * make sure the move is in the
                             * MoveList
                             */
#ifdef IGNUAN
                            if (ply == 1)
                              {   
                                  struct leaf tmp;
              register int spnt;
                                  for (spnt = TrPnt[ply]; spnt < TrPnt[ply + 1]; spnt++)
                                    {
                                        if (((Tree[spnt].f << 8) | Tree[spnt].t) == PV)
                                          {
                                              if (ply == 1 && Tree[spnt].score == DONTUSE) {bstline[1] = 0; break;}
                                              Tree[spnt].score = (beta == -20000) ? score : alpha;
                                              if (abs (score) > 9000) Tree[spnt].flags |= exact;
                                              if (spnt != TrPnt[ply])
                                                {
                                                    tmp = Tree[TrPnt[ply]];
                                                    Tree[TrPnt[ply]] = Tree[spnt];
                                                    Tree[spnt] = tmp;
                                                }
                                              if (beta == -20000) return (score);
                                              else return (alpha);
                                          }
                                    }
                              } else 
#endif
            {
            register int i = TrPnt[ply];
            Tree[i].t = PV & 0x3f;
            Tree[i].f = PV>>8;