search.c

一款运行在linux上的象棋游戏。用GTK/GNOME环境下用GLADE开发。

/* GNU Chess 5.0 - search.c - tree-search code
   Copyright (c) 1999-2002 Free Software Foundation, Inc.

   GNU Chess is based on the two research programs 
   Cobalt by Chua Kong-Sian and Gazebo by Stuart Cracraft.

   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, Inc., 59 Temple Place - Suite 330,
   Boston, MA 02111-1307, USA.

   Contact Info: 
     [e-mail]
     [e-mail], [e-mail], [e-mail]
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "common.h"

#define TIMECHECK 	1023
#define HISTSCORE(d)	((d)*(d))

#define FUTSCORE        (MATERIAL+fdel)
#define GETNEXTMOVE  (InChk[ply] ? PhasePick1 (&p, ply) : PhasePick (&p, ply))

static inline void ShowThinking (leaf *p, uint8_t ply)
{
   if (flags & XBOARD)
      return;
   if (!(flags & POST))
      return;
   if (NodeCnt < 500000 && (flags & SOLVE)) {
      return;
   }
   SANMove (p->move, ply);
   printf ("\r%2d.         %2d/%2d%10s    ", Idepth, 
      (int) (p-TreePtr[ply]+1), (int) (TreePtr[ply+1]-TreePtr[ply]), SANmv);
   fflush (stdout);
}

static int ply1score;

int SearchRoot (short depth, int alpha, int beta)
/**************************************************************************
 *
 *  This perform searches at ply=1.  For ply>1, it calls the more generic
 *  search() routine.  The rationale for splitting these is because at
 *  ply==1, things are done slightly differently than from the other plies,
 *  e.g. print PVs, not testing null move etc.
 *
 **************************************************************************/
{
   int best, score, savealpha;
   uint8_t side, xside, ply;
   short nodetype;
   leaf *p, *pbest;

   ply = 1; 
   side = board.side;
   xside = 1^side;
   ChkCnt[2] = ChkCnt[1];
   ThrtCnt[2] = ThrtCnt[1];
   KingThrt[white][ply] = MateScan (white);
   KingThrt[black][ply] = MateScan (black);
   InChk[ply] = SqAtakd (board.king[side], xside);
   if (InChk[ply] && ChkCnt[ply] < 3*Idepth)
   {
      ChkExtCnt++;
      ChkCnt[ply+1]++;
      depth += 1;
   }
   best = -INFINITY;
   savealpha = alpha;
   nodetype = PV;
   pbest = NULL;

   for (p = TreePtr[1]; p < TreePtr[2]; p++)
   {
      pick (p, 1); 
      ShowThinking (p, ply);
      MakeMove (side, &p->move);
      NodeCnt++;
      
      /*  If first move, search against full alpha-beta window  */
      if (p == TreePtr[1])
      {
         score = -Search (2, depth-1, -beta, -alpha, nodetype);
         /*
	    The following occurs when we are re-searching a fail high move
            and now it has fail low.  This can be disastrous, so immediately
	    adjust alpha and research.
          */
	 if (beta == INFINITY && score <= alpha)
	 {
	    alpha = -INFINITY;
            score = -Search (2, depth-1, -beta, -alpha, nodetype);
         }
      }

      /*  Else search against zero window  */
      else
      {
	 nodetype = CUT;
         alpha = MAX (best, alpha);            
         score = -Search (2, depth-1, -alpha-1, -alpha, nodetype);
         if (score > best)
         {
            if (alpha < score && score < beta)
	    {
	       nodetype = PV;
               score = -Search (2, depth-1, -beta, -score, nodetype);
	    }
         }
      }
      UnmakeMove (xside, &p->move);

      ply1score = p->score = score;
      if (score > best)
      {
         best = score;
	 pbest = p;
         if (best > alpha)
         {
            rootscore = best;
            RootPV = p->move;
	    if (best >= beta)
	       goto done;
            ShowLine (RootPV, best, '&');
         }
      }

      if (flags & TIMEOUT)
      {
	/* ply == 1 always at this point, but code
	 * copied from Search
	 */
         best = (ply & 1 ? rootscore : -rootscore );
	 return (best);
      }

      if (((flags & PONDER) || SearchDepth == 0) && (NodeCnt & TIMECHECK) == 0)
      {
	 if (flags & PONDER) {
	    if (input_status != INPUT_NONE)
	       SET(flags, TIMEOUT);
	 } else {
	    ElapsedTime = GetElapsed (StartTime);
	    if ((ElapsedTime >= SearchTime && (
		    rootscore == -INFINITY-1 
		    || ply1score > lastrootscore - 25 
		    || flags & SOLVE))
		|| ElapsedTime >= maxtime)
	       SET (flags, TIMEOUT);
	 }
      }

      if (MATE+1 == best+1)
         return (best);
   }

/*  If none of the move is good, we still want to try the same first move */
   if (best <= savealpha)
      TreePtr[1]->score = savealpha;

/*****************************************************************************
 *
 *  Out of main search loop.
 *
 *****************************************************************************/
done:

   /*  Update history  */
   if (best > savealpha)
      history[side][pbest->move & 0x0FFF] += HISTSCORE(depth);

   rootscore = best;
   return (best);
}


int Search (uint8_t ply, short depth, int alpha, int beta, short nodetype)
/**************************************************************************
 *
 *  The basic algorithm for this search routine came from Anthony 
 *  Marsland.  It is a PVS (Principal Variation Search) algorithm.
 *  The fail-soft alpha-beta technique is also used for improved
 *  pruning.
 *
 **************************************************************************/
{
   int best, score, nullscore, savealpha;
   int side, xside;
   int rc, t0, t1, firstmove;
   int fcut, fdel, donull, savenode, extend;
   leaf *p, *pbest;
   int g0, g1;
   int upperbound;

   /* Check if this position is a known draw */
   if (EvaluateDraw ())
      return (DRAWSCORE);
   if (GameCnt >= Game50+3 && Repeat())
   {
      RepeatCnt++;
      return (DRAWSCORE); 
   }

   side = board.side;
   xside = 1^side;
   donull = true;

/*************************************************************************
 *
 *  Perform some basic search extensions.
 *  1.  One reply extensions.  
 *  2.  If in check, extend (maximum of Idepth-1).
 *  3.  If there is a threat to the King, extend (not beyond 2*Idepth)
 *  4.  If recapture to same square and not beyond Idepth+2
 *  5.  If pawn move to 7th rank at the leaf node, extend.
 *
 *************************************************************************/
   extend = false;
   InChk[ply] = SqAtakd (board.king[side], xside);
   if (InChk[ply])
   {
      TreePtr[ply+1] = TreePtr[ply];
      GenCheckEscapes (ply);
      if (TreePtr[ply] == TreePtr[ply+1])
         return (-MATE+ply-2);
      if (TreePtr[ply]+1 == TreePtr[ply+1])
      {
         depth += 1;
	 extend = true;
         OneRepCnt++;
      }
   }

/*
   We've already found a mate at the next ply.  If we aren't being mated by 
   a shorter line, so just return the current material value.
*/
   if (rootscore + ply >= MATE)
      return (MATERIAL);

   g0 = Game[GameCnt].move;
   g1 = GameCnt > 0 ? Game[GameCnt-1].move : 0;
   t0 = TOSQ(g0); 
   t1 = TOSQ(g1);
   ChkCnt[ply+1] = ChkCnt[ply];
   ThrtCnt[ply+1] = ThrtCnt[ply];
   KingThrt[white][ply] = MateScan (white);
   KingThrt[black][ply] = MateScan (black);
   if (InChk[ply]  && /* ChkCnt[ply] < Idepth-1*/ ply <= 2*Idepth)
   {
      ChkExtCnt++;
      ChkCnt[ply+1]++;
      depth += 1;
      extend = true;
   }
   else if (!KingThrt[side][ply-1] && KingThrt[side][ply] && ply <= 2*Idepth)
   {
      KingExtCnt++;
      extend = true;
      depth += 1;
      extend = true;
      donull = false;
   }
   /* Promotion extension */
   else if (g0 & PROMOTION)
   {
      PawnExtCnt++;
      depth += 1; /* Not reached, but why?! */
      extend = true;
   }
   /* Recapture extension */
   else if ((g0 & CAPTURE) && (board.material[computer] - 
	board.material[1^computer] == RootMaterial))
   {
      RcpExtCnt++;
      depth += 1;
      extend = true;
   }
   /* 6th or 7th rank extension */
   else if (depth <= 1 && cboard[t0] == pawn && (RANK(t0) == rank7[xside] || RANK(t0) == rank6[xside]))
   {
      PawnExtCnt++;
      depth += 1;
      extend = true;
   }

/**************************************************************************** 
 *
 *  The following extension is to handle cases when the opposing side is 
 *  delaying the mate by useless interposing moves. 
 *
 ****************************************************************************/
   if (ply > 2 && InChk[ply-1] && cboard[t0] != king && t0 != t1 && 
	 !SqAtakd (t0, xside))
   {
      HorzExtCnt++;
      depth += 1;
      extend = true;
   }

/***************************************************************************
 *
 *  This is a new code to perform search reductiion.  We introduce some
 *  form of selectivity here.
 *
 **************************************************************************/

   if (depth <= 0)
      return (Quiesce (ply, alpha, beta)); 

/**************************************************************************** 
 *
 *  Probe the transposition table for a score and a move.
 *  If the score is an upperbound, then we can use it to improve the value
 *  of beta.  If a lowerbound, we improve alpha.  If it is an exact score,
 *  if we now get a cut-off due to the new alpha/beta, return the score.
 *
 ***************************************************************************/
   Hashmv[ply] = 0;
   upperbound = INFINITY;
   if (flags & USEHASH)
   {
      rc = TTGet (side, depth, ply, &score, &g1);
      if (rc)
      {
         Hashmv[ply] = g1 & MOVEMASK;
         switch (rc)
         {
	 case POORDRAFT  :  /* Not reached */ break;
	 case EXACTSCORE :  /* Not reached */ return (score);
            case UPPERBOUND :  beta = MIN (beta, score);
			       upperbound = score;
			       donull = false;
	                       break;
            case LOWERBOUND :  /*alpha = MAX (alpha, score);*/
			       alpha = score;
	                       break;
	    case QUIESCENT  :  Hashmv[ply] = 0;
	                       break;
	    default : break;
         }
	 if (alpha >= beta)
	    return (score);
      }
   }

/*****************************************************************************
 *
 *  Perform the null move here.  There are certain cases when null move
 *  is not done.  
 *  1.  When the previous move is a null move.