search.c

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

            Tree[i].flags = 0;
            Tree[i].reply = 0;
            Tree[i].score = (beta == -20000) ? score : alpha; 
            TrPnt[ply+1] = i+1;
                                if (abs (score) > 9000) Tree[i].flags |= exact; 
            if (beta == -20000) return (score); 
                                    else return (alpha); 
               }

         }
        }
      /* ok try the transition file if its there */
      else if (hashfile && (depth > HashDepth) && (GameCnt < HashMoveLimit)
          && (ProbeFTable (side, depth, ply, &alpha, &beta, &score) == true))
        {
            if (beta == -20000 || alpha > beta)
         {
             bstline[ply] = PV;
             bstline[ply + 1] = 0;
             /*
              * make sure the move is in the
              * MoveList
              */
             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;
                  }
                     PutInTTable (side, score, depth, ply, alpha, beta, PV);
                     if (beta == -20000) return (score);
                     else return (alpha);
                 }
                }
                } else {
                                register int i = TrPnt[ply];
                                Tree[i].t = PV & 0x3f;
                                Tree[i].f = PV>>8;
                                Tree[i].score = (beta == -20000) ? score : alpha;
            TrPnt[ply+1] = i+1;
                                if (abs (score) > 9000) Tree[i].flags |= exact;
                                if (beta == -20000) return (score);
                                    else return (alpha);
                              }
 

         }
        }
     }
#endif /* ttblsz */

  if ((depth > 0) || InChk || (background && ply < Sdepth + 2)) 
    {
      if (ply >1)
   MoveList (side, ply);
   quiescent = false;
    }
  else
    {
      CaptureList (side, ply);
      quiescent = true;
    }

  /* no moves return what we have */

  /*
   * normally a search will continue til past goal and no more capture
   * moves exist
   */
  /* unless it hits DepthBeyond */
  if (TrPnt[ply] == TrPnt[ply + 1]) 
    return (!InChk ? score : -10000+ply);


  /* if not at goal set best = -inf else current score */
  best = (depth > 0) ? -12000 : score;
#ifdef NULLMOVE

  PVarisave = PVari;
  if (!didnull &&    /* no previous null-move */
      !PVari &&         /* no null-move during the PV */
      (ply > 1) &&      /* not at ply 1 */
      (depth > 1) &&
      !InChk &&         /* no check */
      (emtl[side] > valueQ))
    /* enough material such that zugzwang is unlike but who knows which value
       is suitable? */
    {

      /* ok, we make a null move, i.e.  this means we have nothing to do
    but we have to keep the some arrays up to date otherwise gnuchess
    gets confused.  Maybe somebody knows exactly which informations are
    important and which not.

    Another idea is that we try the null-move first and generate the
    moves later.  This may save time but we have to take care that
    PV and other variables contain the right value so that the move
    ordering works right.
    */
      register struct GameRec *g;
      SHORT rdepth;

      nxtline[ply + 1] = 0;
      CptrFlag[ply] = 0;
      PawnThreat[ply] = 0;
      Tscore[ply] = score;
      PVsave = PV;
      PV = 0;
      null = 1;
      g = &GameList[++GameCnt];
      g->hashkey = hashkey;
      g->hashbd = hashbd;
      epsquare = -1;
      TOsquare = -1;
      g->Game50 = Game50;
      g->gmove = 0;
      g->flags = 0;
      g->piece = 0;
      g->color = neutral;
      rdepth = (depth-3 < 0 ? 0 : depth-3);
      nmscore = -search (xside, ply + 1, rdepth, ext, -beta, -beta+1, nxtline, &rcnt,false,1);
      null = 0;
      PV = PVsave;
      GameCnt--;
      if (nmscore > beta)
        {
     DepthBeyond -= extdb;
     return (nmscore);
   }
      if (depth <= 3 && score > beta && nmscore < -9000)
          depth++;
    }
#elif defined DEEPNULL

  /*
   * The deepnull algoritm is taken from the article by
   * Christian Donninger in ICCA journal Vol 16, No. 3.  TomV
   */
  PVarisave = PVari;
  if ((flag.deepnull ? !didnull : !null) &&  /* no previous null-move */
      !flag.nonull &&
      !no_null &&
      !PVari &&         /* no null-move during the PV */
      (ply > (flag.deepnull ? 1: 2)) &&      /* not at ply 1 */
      (score > alpha - 150 || !flag.deepnull) &&
      (ply <= Sdepth || flag.deepnull) &&
      (depth > (flag.deepnull ? (flag.verydeep ? 1: 2): 3)) &&
      !InChk &&         /* no check */
      /* enough material such that zugzwang is unlikely: */
      ! (emtl[xside] == 0 || emtl[side] <= valueB))
    {

      /* ok, we make a null move, i.e.  this means we have nothing to do
    but we have to keep the some arrays up to date otherwise gnuchess
    gets confused.

    Another idea is that we try the null-move first and generate the
    moves later.  This may save time but we have to take care that
    PV and other variables contain the right value so that the move
    ordering works right.
    */
      CptrFlag[ply] = 0;
      PawnThreat[ply] = 0;
      Tscore[ply] = score;
      PVsave = PV;
      PV = 0;
      epsquare = -1;
      TOsquare = -1;
      if (!null)
        null= ply;
      if (flag.deepnull) {
        nmscore = -search (xside, ply + 1, (depth >= 3 ? depth - 3: 0), ext, -beta, -alpha, nxtline, &rcnt,false,1);
        if (ply == null)
          null = 0;
        PV = PVsave;
   if (nmscore > beta) {
     DepthBeyond-= extdb;
     return nmscore;
        }
   if (nmscore > alpha)
     alpha= nmscore;
        if (depth <= 3 && ply < DepthBeyond-depth-4
            && score >= beta && nmscore < score - 350)
              depth++;
      } else {
        best = -search (xside, ply + 1, depth - 2, ext, -beta - 1, -beta, nxtline, &rcnt, false, 1);
        null = 0;
        PV = PVsave;
        if (best < alpha) best = -12000;
        else if (best > beta) {
      DepthBeyond-= extdb;
           return (best);
        }  else best = -12000;
      }
    }
#endif
  /* if best so far is better than alpha set alpha to best */
  if (best > alpha) alpha = best;
  /********************** main loop ************************************************************************/
  /* look at each move until no more or beta cutoff */
  for (pnt = pbst = TrPnt[ply]; pnt < TrPnt[ply + 1] && best <= beta && best != 9999-ply; pnt++)
    {
      if ((pnt&interval)==0)
       {
        flag.searching=true;
        CheckMessage();
        flag.searching=false;
       }
      NodeCnt++;
      /* find the most interesting looking of the remaining moves */
      if (ply > 1)
   pick (pnt, TrPnt[ply + 1] - 1);
#if defined NULLMOVE || defined DEEPNULL
      PVari = PVarisave && (pnt == pbst); /* Is this the PV? */
#endif

      node = &Tree[pnt];

      /* is this a forbidden move */
      if (ply == 1 && node->score == DONTUSE) { continue;}
#ifdef DEBUG
      if (debuglevel & (512 | 1024))
   {
     if (!tracen)
       traceflag = ((ply > traceply) ? false : true);
     else if (ply <= tracen && (ply == 1 || traceflag))
       {
         if (trace[ply] == (Tree[pnt].t | (Tree[pnt].f << 8)))
      traceflag = true;
         else
      traceflag = false;
       }
     tracelog[ply] = (Tree[pnt].t | (Tree[pnt].f << 8));
     tracelog[ply + 1] = 0;
   }
#endif
      nxtline[ply + 1] = 0;

#ifndef BAREBONES
      /* if at top level */
      if (ply == 1)
   {        /* at the top update search status */
     if (flag.post)
#ifdef QUIETBACKGROUND
       if (!background)
#endif /* QUIETBACKGROUND */
         ShowCurrentMove (pnt, node->f, node->t);
   }
#endif
#ifdef DEBUG
     xxxtmp = node->score;
     tracetmp = traceflag;
#endif
   if (!(node->flags & exact)) {
     /* make the move and go deeper */
     MakeMove (side, node, &tempb, &tempc, &tempsf, &tempst);
     CptrFlag[ply] = (node->flags & capture) ? TOsquare+1 : 0;
     PawnThreat[ply] = (node->flags & pwnthrt);
     Tscore[ply] = node->score;
     PV = node->reply;
     if (flag.pvs && depth > 0) {
            if (pbst == pnt) {
              node->score= -search (xside, ply + 1,
                                 depth > 0 ? depth - 1 : 0, ext,
                                 -beta, -alpha,
                                 nxtline, &rcnt, quiescent, 0);
            } else {
              node->score= -search(xside, ply + 1,
                              depth > 0 ? depth - 1 : 0, ext,
                              -alpha-1, -alpha,
                              nxtline, &rcnt, quiescent, 0);
              if (node->score >= best && alpha <= node->score
              && node->score <= beta)
                  node->score = -search (xside, ply + 1,
                                 depth > 0 ? depth - 1 : 0, ext,
                                 -beta, -node->score,
                                 nxtline, &rcnt, quiescent, 0);
            }
          } else

     node->score = -search (xside, ply + 1,
             (depth > 0) ? depth - 1 : 0, ext,
             -beta, -alpha,
             nxtline, &rcnt, quiescent, false);
     node->width = (ply % 2 == 1) ? (TrPnt[ply + 2] - TrPnt[ply + 1]) : 0;
     if (abs (node->score) > 9000) node->flags |= exact;
     else if (rcnt == 1) node->score /= 2;
          if (node->score == 9999-ply && !ChkFlag[ply]) 
       {
         node->flags |= draw;
              node->score = (-contempt);
       }
     if ((rcnt >= 2 || GameCnt - Game50 > 99 ))
       {
         node->flags |= (draw | exact);
         DRAW = CP[21]; /* Draw */
         node->score = -contempt;
       }
     node->reply = nxtline[ply + 1];
     /* reset to try next move */
     UnmakeMove (side, node, &tempb, &tempc, &tempsf, &tempst);
        }
      /* if best move so far */
      if (!flag.timeout && ((node->score > best) || ((node->score == best) && (node->width > bestwidth))))
   {
     /*
      * all things being equal pick the denser part of the
      * tree
      */
     bestwidth = node->width;

     /*
      * if not at goal depth and better than alpha and not
      * an exact score increment by depth
      */
     if (depth > 0 && node->score > alpha && !(node->flags & exact)) node->score += depth; 
     best = node->score;
     pbst = pnt;
     if (best > alpha) { alpha = best; }
     /* update best line */
     for (j = ply + 1; nxtline[j] > 0; j++) bstline[j] = nxtline[j]; 
     bstline[j] = 0;
     bstline[ply] = (node->f << 8) | node->t;
     /* if at the top */
     if (ply == 1)
       {
         /*
          * if its better than the root score make it
          * the root
          */
         if ((best > root->score) || ((best == root->score) && (bestwidth > root->width)) || pnt > 0)
      {
        tmp = Tree[pnt];
        for (j = pnt - 1; j >= 0; j--)
          Tree[j + 1] = Tree[j];
        Tree[0] = tmp;
        pbst = 0;
      }
#ifndef BAREBONES
#ifdef QUIETBACKGROUND
         if (!background)
#endif /* QUIETBACKGROUND */
      if (Sdepth > 2)
        if (best > beta)
          {
            ShowResults (best, bstline, '+');
#ifdef DEBUG41
            debug41 (best, bstline, '+');
#endif
          }
        else if (best < alpha)
          {
            ShowResults (best, bstline, '-');
#ifdef DEBUG41
            debug41 (best, bstline, '-');
#endif
          }
        else
          ShowResults (best, bstline, '&');
#ifdef DEBUG41
         debug41 (best, bstline, '&');
#endif
#endif
         ElapsedTime (2);
         TCcount++;
         if (!background && Sdepth > 2)
      {
        if (best < alpha)
          {
            TCcount = 0;
            ExtraTime += Sdepth * TCleft;
            if (ExtraTime > 12 * TCleft)
           ExtraTime = 12 * TCleft;
            if (best > 300)
           ExtraTime = 0;
            return (best);
          }
      }
       }
   }
      if (flag.timeout)
   {
          DepthBeyond-= extdb;
#if defined NULLMOVE || defined DEEPNULL
     PVari = PVarisave;
#endif
         if (best == -12000)
           return (Tscore[ply - 1]);
         else
           return (best);

   }
    }

  /**************************************************************/
 /*************** out of main loop *****************************/

  if (best == -10000+ply) bstline[ply] = 0;
  node = &Tree[pbst];
  mv = (node->f << 8) | node->t;
#if defined NULLMOVE || defined DEEPNULL
  PVari = PVarisave;
#endif

  /*
   * we have a move so put it in local table - if it's already there
   * done else if not there or needs to be updated also put it in
   * hashfile
   */
#if ttblsz
  if (flag.hash && !quiescent && *rpt == 0 && best == alpha)
    {