/* 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: 
     bug-gnu-chess@gnu.org
     cracraft@ai.mit.edu, cracraft@stanfordalumni.org, cracraft@earthlink.net
*/

#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.
 *  2.  At the frontier (depth == 1)
 *  3.  At a PV node.
 *  4.  If side to move is in check.
 *  5.  If the material score + pawn value is still below beta.
 *  6.  If we are being mated at next ply.
 *  7.  If hash table indicate the real score is below beta (UPPERBOUND).
 *  8.  If side to move has less than or equal to a bishop in value.
 *  9.  If Idepth <= 3.  This allows us to find mate-in 2 problems quickly.
 *  10. We are looking for a null threat.
 *
 *****************************************************************************/
   if (ply > 4 && InChk[ply-2] && InChk[ply-4])
      donull = false;
   if (flags & USENULL && g0 != NULLMOVE && depth > 1 && nodetype != PV &&
       !InChk[ply] && MATERIAL+ValueP > beta && beta > -MATE+ply && donull &&
	board.pmaterial[side] > ValueB )
   {
      TreePtr[ply+1] = TreePtr[ply];
      MakeNullMove (side);
      nullscore = -Search (ply+1, depth-3, -beta, -beta+1, nodetype);
      UnmakeNullMove (xside); 
      if (nullscore >= beta)
      {
         NullCutCnt++;
         return (nullscore);
      }
      if ( depth-3 >= 1 && MATERIAL > beta && nullscore <= -MATE+256)
      {
         depth += 1;
	 extend = true;
      }
   }

   if (InChk[ply] && TreePtr[ply]+1 < TreePtr[ply+1])
      SortMoves (ply);

   pickphase[ply] = PICKHASH;
   GETNEXTMOVE;

/*************************************************************************
 *
 *  Razoring + Futility.
 *  At depth 3, if there is no extensions and we are really bad, decrease
 *  the search depth by 1.
 *  At depth 2, if there is no extensions and we are quite bad, then we
 *  prune all non checking moves and capturing moves that don't bring us up
 *  back to alpha.
 *  Caveat: Skip all this if we are in the ending.
 *
 *************************************************************************/
   fcut = false;
   fdel = MAX (ValueQ, maxposnscore[side]);
   if (!extend && nodetype != PV && depth == 3 && FUTSCORE <= alpha)
   {
      depth = 2;
      RazrCutCnt++;
   }
   fdel = MAX (ValueR, maxposnscore[side]);
   fcut = (!extend && nodetype != PV && depth == 2 && FUTSCORE <= alpha);
   if (!fcut)
   {
      fdel = MAX (3*ValueP, maxposnscore[side]);
      fcut = (nodetype != PV && depth == 1 && FUTSCORE <= alpha);
   }

   MakeMove (side, &p->move);
   NodeCnt++;
   g0 = g1 = 0;
   while ((g0 = SqAtakd (board.king[side], xside)) > 0 ||
      	 (fcut && FUTSCORE < alpha && !SqAtakd (board.king[xside], side) &&
	  !MateScan (xside)))
   {
      if (g0 == 0) g1++;
      UnmakeMove (xside, &p->move);
      if (GETNEXTMOVE == false)
         return (g1 ? Evaluate(alpha,beta) : DRAWSCORE);
      MakeMove (side, &p->move);
      NodeCnt++;
   }
   firstmove = true;
   pbest = p;
   best = -INFINITY;
   savealpha = alpha;
   nullscore = INFINITY;
   savenode = nodetype;
   if (nodetype != PV)
      nodetype = (nodetype == CUT) ? ALL : CUT;

   while (1)
   {
      /* We have already made the move before the loop. */
      if (firstmove)
      {
         firstmove = false;
         score = -Search (ply+1, depth-1, -beta, -alpha, nodetype);
      }

      /* Zero window search for rest of moves */
      else
      {
	 if (GETNEXTMOVE == false)
	    break;

         MakeMove (side, &p->move);
         NodeCnt++;
         if (SqAtakd (board.king[side], xside)) 
         {
            UnmakeMove (xside, &p->move);
            continue;
         }

/*****************************************************************************
 *
 *  Futility pruning.  The idea is that at the frontier node (depth == 1),
 *  if the side on the move is materially bad, then if the move doesn't win
 *  back material or the move isn't a check or doesn't threatened the king, 
 *  then there is no point in searching this move.  So skip it.  
 *  Caveat:  However if the node is a PV, we skip this test.
 *
 *****************************************************************************/
      	 if (fcut && FUTSCORE <= alpha && !SqAtakd (board.king[xside], side) &&
		!MateScan (xside))
		
         {
            UnmakeMove (xside, &p->move);
	    FutlCutCnt++;
	    NodeCnt--;
            continue;
         }
         NodeCnt++;

         if (nodetype == PV)
            nodetype = CUT;
         alpha = MAX (best, alpha);                /* fail-soft condition */
         score = -Search (ply+1, depth-1, -alpha-1, -alpha, nodetype);
         if (score > best)
         {
	    if (savenode == PV)
	       nodetype = PV;
            if (alpha < score && score < beta)
	    {
               score = -Search (ply+1, depth-1, -beta, -score, nodetype);
	    } 
	    if (nodetype == PV && score <= alpha &&
		Game[GameCnt+1].move == NULLMOVE)
	    {
               score = -Search (ply+1, depth-1, -alpha, INFINITY, nodetype);
	    }
         }
      }

      UnmakeMove (xside, &p->move);

      if (score > best)
      {
         best = score;
         pbest = p;
	 if (best >= beta)
	    goto done;
      }

      if (flags & TIMEOUT)
      {
         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);        
	 }
      }

/*  The following line should be explained as I occasionally forget too :) */
/*  This code means that if at this ply, a mating move has been found,     */
/*  then we can skip the rest of the moves!  				   */
      if (MATE+1 == best+ply)
         goto done;
   } 

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

/*
   if (upperbound < best)
      printf ("Inconsistencies %d %d\n", upperbound, best);
*/

   /*  Save the best move inside the transposition table  */
   if (flags & USEHASH){
/*
 * Nasty temporary hack to try and work around timeout problem
 * If we are pondering and timeout don't save incomplete answers
 * Must look at failure of TIMEOUT condition more carefully!
 */
	if ( !(flags & TIMEOUT))
          TTPut (side, depth, ply, savealpha, beta, best, pbest->move); 
      }

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

   /*  Don't store captures as killers as they are tried before killers */
   if (!(pbest->move & (CAPTURE | PROMOTION)) && best > savealpha)
   {
      if (killer1[ply] == 0)
         killer1[ply] = pbest->move & MOVEMASK;
      else if ((pbest->move & MOVEMASK) != killer1[ply])
         killer2[ply] = pbest->move & MOVEMASK;
   }

   return (best);
}


void ShowLine (int move __attribute__ ((unused)), int score, char c)
/*****************************************************************************
 *
 *  Print out the latest PV found during the search.
 *  The only move we know is the root move.  The rest of the PV is taken
 *  from the hash table.  This strategy avoids all the headaches associated
 *  with returning the PV up from the leaf to the root.
 *
 *****************************************************************************/
{
   int i, len;
   int pvar[MAXPLYDEPTH];

   /* SMC */
   if (!(flags & POST))
     return;
   if (NodeCnt < 500000 && (flags & SOLVE)) {
      /* printf("NodeCnt = %d\n",NodeCnt); getchar(); */
      return;
   }
   if (Idepth == 1 && c == '&')
      return;
   if ((flags & XBOARD) && c == '&')
      return;
   if (rootscore == -INFINITY-1)
      return;
   ElapsedTime = GetElapsed (StartTime);

   /*
    * The different output formats for Xboard and GNU Chess are documented
    * in the engine protocol guide.
    *
    * In particular if the character after ply is not a space, Xboard
    * assume it is talking to a GNU Chess compatible engine and
    * uses time in seconds, not centiseconds.
    *
    * This code should be simplified!
    *
    */
   if (flags & XBOARD) {
     if (score > MATE-255) {
       printf ("%d%c Mat%d %d %ld\t", Idepth, c,
                (int)(MATE+2-abs(score))/2, (int)(ElapsedTime), NodeCnt+QuiesCnt);
       if (ofp != stdout)
	 fprintf (ofp,"%2d%c%7.2f  Mat%02d%10ld\t", Idepth, c, ElapsedTime,
                (MATE+2-abs(score))/2, NodeCnt+QuiesCnt);
     } else if (score < -MATE+255) {
       printf ("%d%c -Mat%2d %d %ld\t", Idepth, c,
                (int)(MATE+2-abs(score))/2, (int)(ElapsedTime), NodeCnt+QuiesCnt);
       if (ofp != stdout)
       fprintf (ofp,"%2d%c%7.2f -Mat%02d%10ld\t", Idepth, c, ElapsedTime,
		 (MATE+2-abs(score))/2, NodeCnt+QuiesCnt);
     } else {
	 printf ("%d%c %d %d %ld\t", Idepth, c, (int)score, 
		 (int)(ElapsedTime), NodeCnt+QuiesCnt);
	 if (ofp != stdout) 
	   fprintf (ofp,"%2d%c%7.2f%7d%10ld\t", Idepth, c, 
		    ElapsedTime, score, NodeCnt+QuiesCnt);	 
       }
   }
   else {              /* Not XBOARD */
      if (score > MATE-255) {
	 printf ("\r%2d%c%7.2f  Mat%02d%10ld\t", Idepth, c, ElapsedTime,
		 (MATE+2-abs(score))/2, NodeCnt+QuiesCnt);
	 if (ofp != stdout)
	    fprintf (ofp,"\r%2d%c%7.2f  Mat%02d%10ld\t", Idepth, c, ElapsedTime,
		     (MATE+2-abs(score))/2, NodeCnt+QuiesCnt);
      } else if (score < -MATE+255) {
	 printf ("\r%2d%c%7.2f -Mat%02d%10ld\t", Idepth, c, ElapsedTime,
		 (MATE+2-abs(score))/2, NodeCnt+QuiesCnt);
	 if (ofp != stdout)
	    fprintf (ofp,"\r%2d%c%7.2f -Mat%02d%10ld\t", Idepth, c, ElapsedTime,
		     (MATE+2-abs(score))/2, NodeCnt+QuiesCnt);
      } else {
	 printf ("\r%2d%c%7.2f%7d%10ld\t", Idepth, c, ElapsedTime,
		 score, NodeCnt+QuiesCnt);
	 if (ofp != stdout) 
	    fprintf (ofp,"\r%2d%c%7.2f%7d%10ld\t", Idepth, c, ElapsedTime,
		    score, NodeCnt+QuiesCnt);	 
      }
   }

   if (c == '-')
   {
      printf ("\n");
      if (ofp != stdout) fprintf(ofp, "\n");
      return;
   }
   else if (c == '+')
   {
      SANMove (RootPV, 1);
      printf (" %s\n", SANmv);
      if (ofp != stdout) fprintf (ofp," %s\n", SANmv);
      return;
   }

   SANMove (RootPV, 1);
   printf (" %s", SANmv);
   if (ofp != stdout) fprintf (ofp," %s", SANmv);
   MakeMove (board.side, &RootPV);
   TreePtr[3] = TreePtr[2];
   GenMoves (2);
   len = strlen (SANmv);
   i = 2;
   pvar[1] = RootPV;

   /*  We fill the rest of the PV with moves from the hash table */
   if ((flags & USEHASH))
   {
      while (TTGetPV (board.side, i, rootscore, &pvar[i]))
      {
         if ((MATESCORE(score) && abs(score) == MATE+2-i) || Repeat ())
            break;
  
         if (len >= 32)
         {
            printf ("\n\t\t\t\t");
	    if (ofp != stdout) fprintf (ofp,"\n\t\t\t\t");
            len = 0;
         }
         SANMove (pvar[i], i);
         printf (" %s", SANmv);
	 if (ofp != stdout) fprintf (ofp," %s", SANmv);
         MakeMove (board.side, &pvar[i]);
         TreePtr[i+2] = TreePtr[i+1];
         GenMoves (++i);
         len += strlen (SANmv);
      }
   }

   printf ("\n");
   if (ofp != stdout) fprintf(ofp,"\n");
   for (--i; i; i--)
      UnmakeMove (board.side, &pvar[i]);
   fflush (stdout);
   if (ofp != stdout) fflush (ofp);
}