search.c   [plain text]

/*
    Sjeng - a chess variants playing program
    Copyright (C) 2000-2001 Gian-Carlo Pascutto

    This program 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 of the License, or
    (at your option) any later version.

    This program 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 this program; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

    File: search.c                                        
    Purpose: contains functions related to the recursive search

*/

#include "sjeng.h"
#include "extvars.h"
#include "protos.h"
#include "limits.h"

unsigned long FH, FHF;
unsigned long razor_drop, razor_material, drop_cuts, ext_recap, ext_onerep;

char true_i_depth;

int bestmovenum;

int ugly_ep_hack;

char postpv[STR_BUFF];

char searching_move[20];
int moveleft;
int movetotal;

int legals;

int failed;
int extendedtime;

int tradefreely;

int s_threat;

unsigned long rootnodecount[MOVE_BUFF];

bool checks[PV_BUFF];

#define KINGCAP 50000
#define NONE    0
#define SINGLE  1


void order_moves (move_s moves[], long int move_ordering[], long int see_values[], int num_moves, int best) {

  int promoted, captured;
  int i, from, target, seev;
  /* fill the move ordering array: */

  /* if searching the pv, give it the highest move ordering, and if not, rely
     on the other heuristics: */
  if (searching_pv) {
    searching_pv = FALSE;
    for (i = 0; i < num_moves; i++) {
      from = moves[i].from;
      target = moves[i].target;
      promoted = moves[i].promoted;
      captured = moves[i].captured;
      
      /* give captures precedence in move ordering, and order captures by
	 material gain */
      if (captured != npiece)
	{
	  seev = see(ToMove, target, from);

	  if (seev >= -50)
	    move_ordering[i] = 50000 + seev;
	  else
	    move_ordering[i] = seev;
	  
	  see_values[i] = seev;
	  
	}      
      else
	move_ordering[i] = 0;
      
      /* make the pv have highest move ordering: */
      if (from == pv[1][ply].from 
	  && target == pv[1][ply].target
	  && promoted == pv[1][ply].promoted) {
	searching_pv = TRUE;
	move_ordering[i] = INF;

	if (captured != npiece)
	  see_values[i] = see(ToMove, target, from);
      } 
      else if ((best != -1) && (best != -2) && (i == best))
	{
	  move_ordering[i] = INF;

	  if (captured != npiece)
	    see_values[i] = see(ToMove, target, from);
	}
      else if (best == -2)
	{
	  /* we have an iterative deepening move */
	  if (from == pv[ply+1][ply+1].from 
	      && target == pv[ply+1][ply+1].target 
	      && promoted == pv[ply+1][ply+1].promoted)
	    {
	      move_ordering[i] = INF;
	    }
	}
      
      /* heuristics other than pv (no need to use them on the pv move - it is
	 already ordered highest) */
      else 
	{

	  if (ply != 1 || i_depth < 2)
	    {
	      /* add the history heuristic bonus: */
	      move_ordering[i] += (history_h[from][target]>>i_depth);

	      /* add the killer move heuristic bonuses: */
	      if (from == killer1[ply].from && target == killer1[ply].target
		  && promoted == killer1[ply].promoted)
		move_ordering[i] += 10000;
	      else if (from == killer2[ply].from && target == killer2[ply].target
		       && promoted == killer2[ply].promoted)
		move_ordering[i] += 5000;
	      else if (from == killer3[ply].from && target == killer3[ply].target
		       && promoted == killer3[ply].promoted)
		move_ordering[i] += 2500;
	    }
	  else
	    {
	      if ((nodes / 100) > INF)
		{
		  move_ordering[i] = rootnodecount[i] / 1000;
		}
	      else
		{
		  move_ordering[i] = rootnodecount[i] / 100;
		}
	    }
	}
    }
  }

  /* if not searching the pv: */
  else {
    for (i = 0; i < num_moves; i++) {
      from = moves[i].from;
      target = moves[i].target;
      promoted = moves[i].promoted;
      captured = moves[i].captured;
      
      /* give captures precedence in move ordering, and order captures by
	 material gain */
      if ((best != -1) && (i == best))
	{
	  move_ordering[i] = INF;

	  /* make sure we have SEE data */
	  if (captured != npiece)
	    see_values[i] = see(ToMove, target, from);
	  
	}
      else if (best == -2)
	{
	  /* we have an iterative deepening move */
	  if (from == pv[ply+1][ply+1].from 
	      && target == pv[ply+1][ply+1].target 
	      && promoted == pv[ply+1][ply+1].promoted)
	    {
	      move_ordering[i] = INF;
	     
	      if (captured != npiece)
	    	see_values[i] = see(ToMove, target, from);
	    }
	}
      else if (captured != npiece)
	{	  
	  seev = see(ToMove, target, from);

	  if (seev >= -50)
	    move_ordering[i] = 50000 + seev;	    
	  else
	    move_ordering[i] = seev;	    

	  see_values[i] = seev;
	  
	}      
      else
	move_ordering[i] = 0;
      
      /* heuristics other than pv */
      
      /* add the history heuristic bonus: */
      move_ordering[i] += (history_h[from][target]>>i_depth);

      /* add the killer move heuristic bonuses: */
      if (from == killer1[ply].from && target == killer1[ply].target
	  && promoted == killer1[ply].promoted)
	move_ordering[i] += 10000;
      else if (from == killer2[ply].from && target == killer2[ply].target
	       && promoted == killer2[ply].promoted)
	move_ordering[i] += 5000;
      else if (from == killer3[ply].from && target == killer3[ply].target
	       && promoted == killer3[ply].promoted)
	move_ordering[i] += 2500;
    }
  }

}

void perft (int depth) {

  move_s moves[MOVE_BUFF];
  int num_moves, i;
  int ic;

  //ep_temp = ep_square;
  num_moves = 0;

  /* return if we are at the maximum depth: */
  if (!depth) {
    raw_nodes++;
    return;
  }

  /* generate the move list: */
  gen (&moves[0]);
  num_moves = numb_moves;

  ic = in_check();

  /* loop through the moves at the current depth: */
  for (i = 0; i < num_moves; i++) {
    make (&moves[0], i);

    /* check to see if our move is legal: */
    if (check_legal (&moves[0], i, ic)) {
      /* go deeper into the tree recursively, increasing the indent to
	 create the "tree" effect: */
      perft (depth-1);
    }

    /* unmake the move to go onto the next: */
    unmake (&moves[0], i);
  }

  //ep_square = ep_temp;

}

long int qsearch (int alpha, int beta, int depth) {

  /* perform a quiscense search on the current node using alpha-beta with
     negamax search */

  move_s moves[MOVE_BUFF];
  int num_moves, i, j;
  long int score = -INF, standpat, 
    move_ordering[MOVE_BUFF],
    see_values[MOVE_BUFF];
  bool legal_move, no_moves = TRUE;
  int sbest, best_score, best, delta, bound;
  int originalalpha;
  int oldtime;
  int seev;
  
  pv_length[ply] = ply;
  
  /* before we do anything, see if we're out of time: */
  if (!(nodes & 8191)) 
    {
      if (interrupt()) 
	{
	  time_exit = TRUE;
	  return 0;
	}
      else if (((rdifftime (rtime (), start_time) >= time_for_move)) && (i_depth > 1))
	{
	  if (failed == 1 && !extendedtime 
	      && !fixed_time
	      && !go_fast
	      && Variant != Bughouse
	      && (time_left > max(time_for_move*4, 1000)))
	    {
	      extendedtime = 1;
	      oldtime = time_for_move;
	      time_for_move += allocate_time();
	      printf("Extended from %d to %d, time left %d\n", oldtime,
		     time_for_move, 
		     time_left);
	    }
	  else
	    {
	      time_exit = TRUE;
	      return 0;
	    }
	}
    }
  
  /* return our score if we're at a leaf node: */
  if (depth <= 0 || ply > maxdepth) 
  {
    /* remove leafcounting effect */
    qnodes--;
    nodes--;
    score = eval ();
    return score;
  }

  originalalpha = alpha;
 
  switch (QProbeTT(&bound, alpha, beta, &best))
    {
    case EXACT:
      return bound;
      break;
    case UPPER:
      if (bound <= alpha)
	return bound;
      if (bound < beta)
      	beta = bound;
      break;
    case LOWER:
      if (bound >= beta)
	return bound;
      if (bound > alpha)
      	alpha = bound;
      break;
    case DUMMY:
      break;
    case HMISS:
      best = -1;;
      break;
    };
  
  standpat = eval ();
  
  if (standpat >= beta) {
    /* rem check this */
    QStoreTT(standpat, originalalpha, beta, 500);
    return standpat;
  }
  else if (standpat > alpha) {
    alpha = standpat;
  }
  
  sbest = -1;
  best_score = -INF;
  num_moves = 0;
  
  delta = alpha-150-standpat;
 
  /* generate and order moves: */
  gen (&moves[0]);
  num_moves = numb_moves;

  if (kingcap) return KINGCAP;

  order_moves (&moves[0], &move_ordering[0], &see_values[0], num_moves, best);

  /* loop through the moves at the current node: */
  while (remove_one (&i, &move_ordering[0], num_moves)) {

    legal_move = FALSE;
    
    seev = see_values[i];
 
    if (((seev < delta) || (seev < 0)) && !moves[i].promoted)
	continue;
  
    make (&moves[0], i);
 
    score = -qsearch (-beta, -alpha, depth-1);
	
    if (score != -KINGCAP) 
      {
	nodes++;
	qnodes++;
		
	legal_move = TRUE;
	no_moves = FALSE;
      };

    unmake (&moves[0], i);

    if(score > best_score && legal_move)
      {
	best_score = score;
      };

    /* check our current score vs. alpha: */
    if (score > alpha && legal_move) 
      {

	/* don't update the history heuristic scores here, since depth is messed
	   up when qsearch is called */
	best = i;
	
	/* try for an early cutoff: */
	if (score >= beta) 
	  {
	    QStoreTT(score, originalalpha, beta, i);
	    return score;
	  }
	
	alpha = score;
	
	/* update the pv: */
	pv[ply][ply] = moves[i];;
	for (j = ply+1; j < pv_length[ply+1]; j++)
	  pv[ply][j] = pv[ply+1][j];
	pv_length[ply] = pv_length[ply+1];
      }
    
  }

  /* we don't check for mate / stalemate here, because without generating all
     of the moves leading up to it, we don't know if the position could have
     been avoided by one side or not */

  if (no_moves)
    {
      /* we tried all moves and none were good...sack to alpha */
      	return standpat;
    }
  else
    {
      QStoreTT(alpha, originalalpha, beta, best);
      return alpha;
    }  
}

bool remove_one (int *marker, long int move_ordering[], int num_moves) {

  /* a function to give pick the top move order, one at a time on each call.
     Will return TRUE while there are still moves left, FALSE after all moves
     have been used */

  int i, best = -INF;

  *marker = -INF;

  for (i = 0; i < num_moves; i++) {
    if (move_ordering[i] > best) {
      *marker = i;
      best = move_ordering[i];
    }
  }

  if (*marker > -INF) {
    move_ordering[*marker] = -INF;
    return TRUE;
  }
  else {
    return FALSE;
  }

}

long int search (int alpha, int beta, int depth, int is_null) {

  /* search the current node using alpha-beta with negamax search */

  move_s moves[MOVE_BUFF];
  int num_moves, i, j;
  long int score = -INF, move_ordering[MOVE_BUFF], see_values[MOVE_BUFF];
  bool no_moves, legal_move;
  int bound, threat, donull, best, sbest, best_score, old_ep;
  bool incheck, first;
  int extend, fscore, fmax, selective;
  move_s kswap;
  int ksswap;
  int originalalpha;
  int afterincheck;
  int legalmoves;
  int dropcut;
  int oldtime;
  int egscore;
  static const int rc_index[14] = {0,1,1,2,2,5,5,3,3,4,4,2,2,0};
  
  /* before we do anything, see if we're out of time: */
  if (!(nodes & 8191)) {
    if (interrupt()) 
      {
	time_exit = TRUE;
	return 0;
      }
    else if (((rdifftime (rtime (), start_time) >= time_for_move)) && (i_depth > 1))
      {
	if (failed == 1 && !extendedtime 
	    && !fixed_time
	    && !go_fast
	    && Variant != Bughouse
	    && (time_left > max(time_for_move*4, 1000)))
	  {
	    extendedtime = 1;
	    oldtime = time_for_move;
	    time_for_move += allocate_time();
	    printf("Extended from %d to %d, time left %d\n", oldtime,
		   time_for_move, 
		   time_left);
	  }
	else
	  {
	    time_exit = TRUE;
	    return 0;
	  }
      }
  }
  
  originalalpha = alpha;
  fmax = -INF;
  
  threat = 0;
  extend = 0;
  
  pv_length[ply] = ply;
  
  if (is_draw ()) 
    {
      return 0;
    }
  
  if ((path[ply-1].captured != npiece || ply == 2))
  {
    if (piece_count <= EGTBPieces && (Variant == Normal))
    {
      egscore = probe_egtb();
      if (egscore != KINGCAP)
	return egscore;
    }
    else if (piece_count <= 3 && (Variant == Suicide) && SEGTB)
    {
      EGTBProbes++;
      
      egscore = egtb(white_to_move);
      if (egscore != -128)
      {
	EGTBHits++;
	if (egscore < 0)
	{
	  return -INF+(129+egscore);
	}
	else if (egscore > 0)
	{
	  return INF-(129-egscore);
	}
	else if (egscore == 0)
	  return 0;
      }
    }
  }

  incheck = checks[ply];

  /* perform check extensions if we haven't gone past maxdepth: */
  if (ply < maxdepth+1 && incheck && ((ply <= i_depth*2) || (depth == 0))) 
    {
      depth++;
      ext_check++;
      extend++;
    } 
  else if ((ply < maxdepth+1) && (ply > 2) && (ply < (i_depth*2))
	   && (depth <= 2)
	   && cfg_recap
	   && (path[ply-1].captured != 13)
	   && (rc_index[path[ply-1].captured] == rc_index[path[ply-2].captured]))
    {
      depth++;
      ext_recap++;
      extend++;
    }

  /* try to find a stable position before passing the position to eval (): */
  if (depth <= 0 || ply >= maxdepth)
    {

      if (Variant != Suicide && Variant != Losers)
	{
	      captures = TRUE;
	      score = qsearch (alpha, beta, maxdepth);   
	      captures = FALSE;
	      return score; 
	}
      else
	{
	  if (Variant == Suicide)
	    {
	      return suicide_eval();

	    }
	  else if (Variant == Losers)
	    {		 
	      i = losers_eval();
	      
	      if (abs(i) == INF)
		{
		  return ((i > 0) ? INF-ply : -INF+ply);
		}
	      else
		{		
		  return i;		  
		}
	    }
	}
    }
  
  num_moves = 0;
  no_moves = TRUE;
 
  switch (ProbeTT(&bound, alpha, beta, &best, &threat, &donull, depth))
    {
    case EXACT:
      return bound;
      break;
    case UPPER:
      if (bound <= alpha)
	return bound;
      if (bound < beta)
      	beta = bound;
      best = -1;
      break;
    case LOWER:
      if (bound >= beta)
	return bound;
      if (bound > alpha)
      	alpha = bound;
      break;
    case DUMMY:
      break;
    case HMISS:
      best = -1;
      threat = FALSE;
      break;
    };
  
  if (best == 500) best = -1;
 
  sbest = -1;
  best_score = -INF;

  old_ep = ep_square;
  
  legalmoves = 0;
  
  if (Variant == Losers)
    {
      i = losers_eval();
      
      if (abs(i) == INF)
      {
	return (i > 0) ? i-ply : i+ply;
      }
      
      captures = TRUE;
      gen (&moves[0]);
      num_moves = numb_moves;
      captures = FALSE; 
									               
      if (num_moves)
	{
	  for (i = 0; i < num_moves; i++)
	    {
	      make(&moves[0], i);
	      if (check_legal(&moves[0], i, incheck))
		{
		  legalmoves++;
		}
	      unmake(&moves[0], i);
	    }
	}       
      if (!legalmoves) 
	{
	  captures = FALSE;
	  gen(&moves[0]);
	  num_moves = numb_moves;
	};          

      legalmoves = 0;
    } 

  if ((is_null == NONE)
      && ((phase != Endgame) || ((phase == Endgame) && (depth <= 6)))
      && !incheck && donull && !searching_pv
      && (threat == FALSE)
      && (((Variant != Suicide) && (Variant != Losers)) 
	  || (Variant == Losers && moves[0].captured == npiece)))
    {

        ep_square = 0;      
        white_to_move ^= 1;
        ply++;
        fifty++;
        hash ^= 0xDEADBEEF;
      
      	/* use R=1 cos R=2 is too dangerous for our ply depths */
      	if (Variant != Normal && Variant != Losers)
		score = -search(-beta, -beta+1, ((depth > 3) ? depth-2-1 : depth-1-1), SINGLE);
     	 else
	{
	  if (depth > 11)
	    score = -search(-beta, -beta+1, depth-4-1, SINGLE);
	  else if (depth > 6)
	    score = -search(-beta, -beta+1, depth-3-1, SINGLE);
	  else
	    score = -search(-beta, -beta+1, depth-2-1, SINGLE);

	 };
      
      hash ^= 0xDEADBEEF;
      fifty--;
      ply--;
      white_to_move ^= 1;
      ep_square = old_ep;

      if (time_exit) return 0;

      NTries++;

      if (score >= beta)
	{
	  
	  NCuts++;
	  
          StoreTT(score, alpha, beta, 500, 0, depth);
	  
	  return score;
	}
      else if (score < -INF+100)
	{
	  threat = TRUE;
	  TExt++;
	  depth++;
	  extend++;
	  ext_onerep++;
	}
    }
  else if (threat == TRUE)
    {
      TExt++;
      depth++;
      extend++;
      ext_onerep++;
    }
  
  score = -INF;
  
  first = TRUE;
  selective = 0;

  if (phase != Endgame && (Variant != Suicide) && cfg_futprune)
    {

      fscore = (white_to_move ? Material : -Material) + 900;
    
      if (!extend && depth == 3 && fscore <= alpha)
	depth = 2;
    
      fscore = (white_to_move ? Material : -Material) + 500;
    
      if (!extend && depth == 2 && fscore <= alpha)
	{
	  selective = 1;
	  best_score = fmax = fscore;
	}
    
      fscore = (white_to_move ? Material : -Material) + ((Variant == Normal) ? 150 : 200);
    
      if (!extend && depth == 1 && fscore <= alpha)
	{
	  selective = 1;
	  best_score = fmax = fscore;
	}
    }

    if (Variant != Losers)
    {
      /* generate and order moves: */
      gen (&moves[0]);
      num_moves = numb_moves;
    }
    
  
  if ((Variant == Suicide) && num_moves == 1) depth++;
  else if ((Variant == Losers) && legalmoves == 1) depth++;
  
  if (num_moves > 0)
    {
      
      order_moves (&moves[0], &move_ordering[0], &see_values[0], num_moves, best);
      
      /* loop through the moves at the current node: */
      while (remove_one (&i, &move_ordering[0], num_moves)) {
      
	make (&moves[0], i);
    
	legal_move = FALSE;
      
	hash_history[move_number+ply-1] = hash;
	path[ply-1] = moves[i];
      
	//old_ep = ep_square;
	
	extend = 0; /* dont extend twice */
      
	/* go deeper if it's a legal move: */
      
	if (check_legal (&moves[0], i, incheck)) {
      
	  afterincheck = f_in_check(&moves[0], i);
	  checks[ply] = afterincheck;
	
	  if (!afterincheck && ((Variant == Normal) 
		             || (Variant == Suicide) 
			     || (Variant == Losers)) && (depth < 3) &&
	      (((board[moves[i].target] == wpawn) && (rank(moves[i].target) >= 6)
		|| ((board[moves[i].target] == bpawn) && (rank(moves[i].target) <= 3)))))
	    {
	      extend++;
	    };
	
	  dropcut = 0;
	
	  /* Razoring of uninteresting drops */
	  if ((moves[i].from == 0)
	      && (depth > 1)           /* more than pre-frontier nodes */
	      && (afterincheck == 0)   /* not a contact checking move */
	      && (incheck == 0)        /* not a check evasion */
	      && !searching_pv
	      && cfg_razordrop
	      )
	    { razor_drop++; extend--;}
	  else
	    {
	      if ((moves[i].from == 0) && (depth == 1) && (incheck == 0) && cfg_cutdrop) 
		{
		  if (white_to_move)
		    {
		      dropcut = (calc_attackers(moves[i].target, 1) 
				 - calc_attackers(moves[i].target, 0)) > 0;
		      if (dropcut) drop_cuts++;
		    }
		  else
		    {
		      dropcut = (calc_attackers(moves[i].target, 0)
				 - calc_attackers(moves[i].target, 1)) > 0;
		      if (dropcut) drop_cuts++;
		    }
		}

	    }
	
	  if (!dropcut && (!selective || (afterincheck != 0) 
			   || (fmax + ((abs(material[moves[i].captured]) * 
				 ((Variant == Normal || Variant == Losers)?1:2)
				 )) > alpha) 
			   || (moves[i].promoted))) 
	    {
	    
	      /* we only count the nodes we actually examine */  
	    
	      nodes++;
	    
	      if (first == TRUE)
		{ 
		  score = -search (-beta, -alpha, depth+extend-1, NONE);
		  FULL++;
		}
	      else
		{
		  score = -search (-alpha-1, -alpha, depth+extend-1, NONE);
		  PVS++;
		    
		  if (score > best_score && !time_exit && score != -KINGCAP)
		    {
		      if ((score > alpha) && (score < beta))
			{
			  score = -search(-beta, -score, depth+extend-1, NONE);
			  //	    ep_square = old_ep;
			  PVSF++;
			    
			  if (score > best_score) best_score = score;
			}
		      else	
			best_score = score;
		    }
		}

	      legal_move = TRUE;
	    
	    }
	  else
	    razor_material++;
	
	
	  legalmoves++;
	  no_moves = FALSE;
	}

	if (score > best_score && legal_move)
	  {
	    best_score = score;
	  };
      
	unmake (&moves[0], i);
      
	/* return if we've run out of time: */
	if (time_exit) return 0;
      
	/* check our current score vs. alpha: */
	if (score > alpha && legal_move) {
	
	  /* try for an early cutoff: */
	  if (score >= beta) {
	  
	    /* update the history heuristic since we have a cutoff: */
	    history_h[moves[i].from][moves[i].target] += depth * depth;
	  
	    if (moves[i].captured == npiece)
	      {
		/* we have a cutoff, so update our killers: */
		/* first, check whether it matches one of the known killers */
		if (moves[i].from == killer1[ply].from && moves[i].target ==
		    killer1[ply].target && moves[i].promoted == killer1[ply].promoted)
		  {
		    killer_scores[ply]++;
		  }
		else if (moves[i].from == killer2[ply].from && moves[i].target ==
			 killer2[ply].target && moves[i].promoted == killer2[ply].promoted)
		  {
		    killer_scores2[ply]++;
		    
		    if (killer_scores2[ply] > killer_scores[ply])
		      {
			kswap = killer1[ply];
			killer1[ply] = killer2[ply];
			killer2[ply] = kswap;		
			ksswap = killer_scores[ply];
			killer_scores[ply] = killer_scores2[ply];
			killer_scores2[ply] = ksswap;
		      }
		  }
		
		else if (moves[i].from == killer3[ply].from && moves[i].target ==
			 killer3[ply].target && moves[i].promoted == killer3[ply].promoted)
		  {
		    
		    killer_scores3[ply]++;
		    
		    if (killer_scores3[ply] > killer_scores2[ply])
		      {
			kswap = killer2[ply];
			killer2[ply] = killer3[ply];
			killer3[ply] = kswap;		
			ksswap = killer_scores2[ply];
			killer_scores2[ply] = killer_scores3[ply];
			killer_scores3[ply] = ksswap;
		      }
		  }
		/* if not, replace killer3 */
		else
		  {
		    killer_scores3[ply] = 1;
		    killer3[ply] = moves[i];
		  }
	      }
	  
	    if (first == TRUE) FHF++;
	  
	    FH++;
	  
	    StoreTT(score, originalalpha, beta, i, threat, depth);
	  
	    return score;
	  }
	
	  alpha = score;
	
	  sbest = i;

	  /* update the pv: */
	  pv[ply][ply] = moves[i];
	  for (j = ply+1; j < pv_length[ply+1]; j++)
	    pv[ply][j] = pv[ply+1][j];
	  pv_length[ply] = pv_length[ply+1];
	}
      
	if (legal_move)
	  first = FALSE;
      
      }

      if (legalmoves <= 1 && (Variant != Suicide) && cfg_onerep) threat = TRUE;
    }
  else
    {
      /* no generated moves..only happens in suicide */
      StoreTT(INF-ply, originalalpha, beta, 0, threat, depth);
      return INF-ply;
    }

  /* check for mate / stalemate: */
  if (no_moves) 
    {
      if (Variant != Losers && Variant != Suicide)
      {
      	if (in_check ()) 
	{
	  StoreTT(-INF+ply, originalalpha, beta, 0, threat, depth);
	  return (-INF+ply);
	}
      else 
	{
	  StoreTT(0, originalalpha, beta, 0, threat, depth);
	  return 0;
	}
      }
      else
      {
	  StoreTT(INF-ply, originalalpha, beta, 0, threat, depth);
	  return (INF-ply);
      }
    }
  else
    {
      if (fifty > 100) 
	{
	  return 0;
	}	
    };
  
  /* doesnt seem to have any effect */ 
  if (sbest == -1) sbest = 500;

  if (best_score <= originalalpha)
    {
      if (!selective)
	StoreTT(best_score, originalalpha, beta, sbest, threat, depth);
    }
  else 
    {
      if (!selective)
	StoreTT(best_score, originalalpha, beta, sbest, threat, depth);
      else
	StoreTT(best_score, -INF, -INF, sbest, threat, depth);/*store lowbound*/
    }
 
  return best_score;

}


move_s search_root (int originalalpha, int originalbeta, int depth) {

  /* search the root node using alpha-beta with negamax search */

  move_s moves[MOVE_BUFF], best_move = dummy;
  int num_moves, i, j;
  long int root_score = -INF, move_ordering[MOVE_BUFF], see_values[MOVE_BUFF];
  bool no_moves, legal_move, first;
  int alpha, beta;
  move_s kswap;
  move_s oldbest;
  int oldbestnum;
  int ksswap;
  int incheck;
  int mc = 0;
  int oldnodecount;
  
  alpha = originalalpha;
  beta = originalbeta;

  num_moves = 0;
  no_moves = TRUE;
  ply = 1;
  searching_pv = TRUE;
  time_exit = FALSE;
  time_failure = FALSE;
  first = TRUE;
  cur_score = -INF;
  
  /* check for a draw by 3 fold repetition: */
  if (is_draw ()) 
    {
      result = draw_by_rep;
      cur_score = 0;
      pv_length[ply] = 0;
      return (dummy);
    };
  
  pv_length[ply] = ply;
  // GCP
  hash_history[move_number+ply-1] = hash; 
  
  /*check extensions: */
 
  incheck = in_check ();
  
  if (incheck) 
  {
    ext_check++;
    depth++;
  };

  checks[ply] = incheck;
  
  if (Variant == Losers)
    { 
      legals = 0;
      captures = TRUE;
      gen (&moves[0]);
      num_moves = numb_moves;
      captures = FALSE; 
									               
      if (num_moves)
	{
	  for (i = 0; i < num_moves; i++)
	    {
	      make(&moves[0], i);
	      if (check_legal(&moves[0], i, incheck))
		{
		  legals++;
		}
	      unmake(&moves[0], i);
	    }
	}  
      
      if (!legals) 
	{
	  captures = FALSE;
	  gen(&moves[0]);
	  num_moves = numb_moves;

	  for (i = 0; i < num_moves; i++)
	    {
	      make(&moves[0], i);
	      if (check_legal(&moves[0], i, incheck))
		{
		  legals++;
		}
	      unmake(&moves[0], i);					               
	    }
	};                 
    }   
  else
    {
      /* generate and order moves: */
      
      gen (&moves[0]);
      num_moves = numb_moves;
    }
  
  movetotal = legals;

  order_moves (&moves[0], &move_ordering[0], &see_values[0], num_moves, -1);
  
  /* loop through the moves at the root: */
  while (remove_one (&i, &move_ordering[0], num_moves)) {
  
    if (!alllosers && rootlosers[i] && ((Variant == Losers) || (Variant == Suicide))) continue;
    
    make (&moves[0], i);
    legal_move = FALSE;

    hash_history[move_number+ply-1] = hash;
    path[ply-1] = moves[i];
    
    oldnodecount = nodes;
    
    //old_ep = ep_square;

    /* go deeper if it's a legal move: */
    if (check_legal (&moves[0], i, incheck)) {
  
      unmake(&moves[0], i);
      mc++;
      moveleft = movetotal - mc;
      comp_to_san(moves[i], searching_move);
      make(&moves[0], i);
      
      nodes++;

      checks[ply] = f_in_check(&moves[0], i);

      if ((first == TRUE) || (i_depth < 2))
	{
	  root_score = -search (-beta, -alpha, depth-1, NONE);
	  //ep_square = old_ep;	

	  if (!time_exit && (post || !xb_mode) && i_depth >= mindepth) 
	    {
	      if (root_score >= beta)
		{
		  /* update the pv: */
		  pv[ply-1][ply-1] = moves[i];
		  for (j = ply; j < pv_length[ply]; j++)
		    pv[ply-1][j] = pv[ply][j];
		  pv_length[ply-1] = pv_length[ply];

		  post_fh_thinking(root_score, &moves[i]);
		}
	      else if (root_score <= alpha)
		{
		  /* update the pv: */
		  /* maybe not..fail low yields nonsense */
	//	   pv[ply-1][ply-1] = moves[i];
	//	   for (j = ply; j < pv_length[ply]; j++)
	//	     pv[ply-1][j] = pv[ply][j];
	//	   pv_length[ply-1] = pv_length[ply];

		  failed = 1;

		  post_fl_thinking(root_score, &moves[i]);
		}
	      else
		{
		  /* update the pv: */
		  pv[ply-1][ply-1] = moves[i];
		  for (j = ply; j < pv_length[ply]; j++)
		    pv[ply-1][j] = pv[ply][j];
		  pv_length[ply-1] = pv_length[ply];

		  post_thinking(root_score);
		}
	      
	       if (root_score > cur_score && !time_exit)
	       {
	          cur_score = root_score;
		  bestmovenum = i;
		  best_move = moves[i];
	       }
			    
	    }
	}
      else
	{
	  root_score = -search (-alpha-1, -alpha, depth-1, NONE);
	  //ep_square = old_ep;

	  if ((root_score > alpha) && (root_score < beta) && !time_exit)
	    {
              post_fail_thinking(root_score, &moves[i]); 

	      oldbest = best_move;
	      oldbestnum = bestmovenum;
	      
	      if (root_score > cur_score && !time_exit) 
	      {
	      	  cur_score = root_score;
	          bestmovenum = i;
	          best_move = moves[i];
	      }
	
	      root_score = -search(-beta, -root_score, depth-1, NONE);
	      //ep_square = old_ep;
	      
	      if (root_score > alpha && !time_exit)
	      {
		  failed = 0;
		
		  cur_score = root_score;
		  bestmovenum = i;
		  best_move = moves[i];
	          
		  if (i_depth >= mindepth)
	      	  {
		      /* update the pv: */
		      pv[ply-1][ply-1] = moves[i];
		      for (j = ply; j < pv_length[ply]; j++)
		        pv[ply-1][j] = pv[ply][j];
		      pv_length[ply-1] = pv_length[ply];
		  }
	      }
	      else {best_move = oldbest; bestmovenum = oldbestnum; };
	   }

	  if (root_score >= beta && !time_exit) 
	    post_fh_thinking(root_score, &moves[i]);
	}

    if (root_score > cur_score && !time_exit) 
	{
	  cur_score = root_score;
	  bestmovenum = i;
	  best_move = moves[i];
	}
      
      /* check to see if we've aborted this search before we found a move: 
       * or a failed search <- removed 2000-5-28
       * we should use the fail-highs
       * and the fail-lows are handled in think */   
    if (time_exit && (cur_score == -INF))
      {
	if (no_moves)
	  time_failure = TRUE;
      }
    
    no_moves = FALSE;
    legal_move = TRUE;
    
    }
    
    unmake (&moves[0], i);

    /* if we've run out of time, return the best we have so far: */
    if (time_exit)
      return best_move;

    /* check our current score vs. alpha: */
    if (root_score > alpha && legal_move) {

       /* we have a cutoff, so update our killers: */
      /* first, check whether it matches one of the known killers */
      if (moves[i].from == killer1[ply].from && moves[i].target ==
	 killer1[ply].target && moves[i].promoted == killer1[ply].promoted)
	{
	  killer_scores[ply]++;
	}
      else if (moves[i].from == killer2[ply].from && moves[i].target ==
	killer2[ply].target && moves[i].promoted == killer2[ply].promoted)
	{
	  killer_scores2[ply]++;
		
	  if (killer_scores2[ply] > killer_scores[ply])
	    {
	      kswap = killer1[ply];
	      killer1[ply] = killer2[ply];
	      killer2[ply] = kswap;		
	      ksswap = killer_scores[ply];
	      killer_scores[ply] = killer_scores2[ply];
	      killer_scores2[ply] = ksswap;
	    }
	}
      else if (moves[i].from == killer3[ply].from && moves[i].target ==
	       killer3[ply].target && moves[i].promoted == killer3[ply].promoted)
	{
	  killer_scores3[ply]++;
	  
	  if (killer_scores3[ply] > killer_scores2[ply])
	    {
	      kswap = killer2[ply];
	      killer2[ply] = killer3[ply];
	      killer3[ply] = kswap;		
	      ksswap = killer_scores2[ply];
	      killer_scores2[ply] = killer_scores3[ply];
	      killer_scores3[ply] = ksswap;
	    }
	}
	/* if not, replace killer3 */
	else
	{
	  killer_scores3[ply] = 1;
	  killer3[ply] = moves[i];
	}

      /* update the history heuristic since we have a cutoff: */
      /* PGC square it */
      history_h[moves[i].from][moves[i].target] += depth * depth;

      alpha = root_score;
      best_move = moves[i];
      bestmovenum = i;
      cur_score = alpha;
      
      /* update the pv: */
      pv[ply][ply] = moves[i];
      for (j = ply+1; j < pv_length[ply+1]; j++)
	pv[ply][j] = pv[ply+1][j];
      pv_length[ply] = pv_length[ply+1];
      
      if (cur_score >= beta) return best_move;

      /* print out thinking information: */
      if (post && i_depth >= mindepth) {
	post_thinking (alpha);
      }
    }
    if (legal_move)
      first = FALSE;

    rootnodecount[i] = nodes - oldnodecount;
  }

  /* check to see if we are mated / stalemated: */
  if (no_moves && !is_pondering) 
  {
    if (Variant != Suicide && Variant != Losers)
      {
	if (in_check ()) {
	  if (white_to_move == 1) {
	    result = white_is_mated;
	  }
	  else {
	    result = black_is_mated;
	  }
	}
	else {
	  result = stalemate;
	}
      }
    else
      {
	if (white_to_move == 1) {
	  result = black_is_mated;
	}
	else {
	  result = white_is_mated;
	}
      }
  }
  else if (!is_pondering)
  {
    /* check for draw by the 50 move rule: */
    if (fifty > 100) 
    {
    	result = draw_by_fifty;
	cur_score = 0;
	pv_length[ply] = 0;
	return dummy;
    }
  }

  return best_move;

}


move_s think (void) {

  /* Perform iterative deepening to go further in the search */
  
  move_s comp_move, temp_move, old_move;
  int i, j, k;
  long int elapsed, temp_score, true_score;
  char postmove[STR_BUFF];
  clock_t cpu_start, cpu_end; 
  float et = 0;
  int alpha, beta;
  int tmptmp;
  int rs;
  move_s moves[MOVE_BUFF];
  int l, lastlegal, ic;
  int pn_restart;
  int num_moves;
  char output[8];
  
  userealholdings = 0;
  pn_restart = 0;
restart:
  nodes = 0;
  qnodes = 0;
  ply = 1;

  EGTBProbes = 0;
  EGTBHits = 0;
  ECacheProbes = 0;
  ECacheHits = 0;
  TTProbes = 0;
  TTHits = 0;
  TTStores = 0;  
  NCuts = 0;
  NTries = 0;
  TExt = 0;
  FH = 0;
  FHF = 0;
  PVS = 0;
  FULL = 0;
  PVSF = 0;
  ext_check = 0;
  ext_recap = 0;
  ext_onerep = 0;
  razor_drop = 0;
  razor_material = 0;
  drop_cuts = 0;
  rs = 0;
  extendedtime = 0;
  forcedwin = 0;
  
  true_i_depth = 0;
  bestmovenum = -1;

  /* Don't do anything if the queue isn't clean */
  /* PGC: only safe if we're not playing...else partner tells screw us up */
  if (interrupt() && (is_analyzing || is_pondering)) return dummy;
  
  //ep_temp = ep_square;
 
  start_time = rtime ();

  // we need to know if we must sit or not in bug
  // 
  legals = 0;

  if (Variant == Losers) captures = TRUE;
  else captures = FALSE;
  gen(&moves[0]);
  num_moves = numb_moves;
  
  ic = in_check();
  
  for (l = 0; l < numb_moves; l++)
    {
      make(&moves[0],l);
      if (check_legal(&moves[0], l, ic))
	{
	  legals++;
	  lastlegal = l;
	}
      unmake(&moves[0],l);
    }

  if (Variant == Losers && legals == 0)
    {
      captures = FALSE;
      num_moves = 0;
      gen(&moves[0]);
      num_moves = numb_moves;

      for (l = 0; l < numb_moves; l++)
	{
	  make(&moves[0],l);
	  if (check_legal(&moves[0], l, ic))
	    {
	      legals++;
	      lastlegal = l;
	    }
	  unmake(&moves[0],l);
	}
    };                       
  
  if (Variant != Bughouse && !is_pondering)
    {
      if (legals == 1)
      {
	time_cushion += (inc*100);
	return moves[lastlegal];
      }
    }

  //ep_square = ep_temp;
  
   /* before we do anything, check to see if we can make a move from book! */
   if (!pn_restart && book_ply < 40 && !is_analyzing && !is_pondering) {
     comp_move = choose_book_move();
     //ep_square = ep_temp;
     /* if choose_book_move() didn't return a junk move indicating that
	no book move was found, play the book move! :) */
     
     if (comp_move.target == 0)
       comp_move = choose_binary_book_move();
     
     //ep_square = ep_temp; 
     
     if (comp_move.target != 0) 
       {
	 comp_to_san (comp_move, postmove);
	 printf("0 0 0 0 %s (Book Move)\n", postmove);
	 cpu_end = clock ();
	 
	 //ep_square = ep_temp;
    
	 time_cushion += (inc*100);
	 
	 return comp_move;
       }
   }
   
   check_phase();

   switch(phase)
     {
     case Opening :
       printf("Opening phase.\n");
       break;
     case Middlegame :
       printf("Middlegame phase.\n");
       break;
     case Endgame :
       printf("Endgame phase.\n");
       break;
     }
   
   /* allocate our time for this move: */

   if (!is_pondering)
     {
       if (!fixed_time)
	 {
	   if (go_fast)
	     {
	       tmptmp = allocate_time();
	       
	       if (tmptmp > 40)
	       {
		 time_for_move = 40;
	       }
	       else
	       {
		 time_for_move = tmptmp;
	       }
	     }
	   else
	     {
	       time_for_move = allocate_time ();
	     }	
	 }
       else
	 {
	   time_for_move = fixed_time;
	 }
     }
   else
     {
       time_for_move = 999999;
     };

   if (pn_restart) time_for_move = (float)time_for_move * (float)2/((float)pn_restart+1.0);
   
   printf("Time for move : %d\n", time_for_move);
   
   if (time_for_move > 50)
     LoadLearn();

   if (!pn_restart)
   {
     clear_dp_tt();
     memset(rootlosers, 0, sizeof(rootlosers));
   }
   
   if (!pn_restart && !is_pondering && ((Variant == Suicide) || (Variant == Losers)) 
       && (piece_count > 3 || (Variant != Suicide)))
     { 
       pn_time = (int)((float)(time_for_move) * 1.0/3.0);
       proofnumberscan();
     }
   else if (!pn_restart)
     pn_move = dummy;
   
  if (result && pn_move.target == dummy.target)
    return pn_move;
  
  if ((forcedwin || result) && (pn_move.target != dummy.target) 
      && !is_analyzing)
    {
      comp_move = pn_move;
    }
  else 
     {
       /* clear the pv before a new search: */
       for (i = 0; i < PV_BUFF; i++)
	 for (j = 0; j < PV_BUFF; j++)
	   pv[i][j] = dummy;
       
       /* clear the history heuristic: */
       memset (history_h, 0, sizeof (history_h));
       
       /* clear the killer moves: */
       for (i = 0; i < PV_BUFF; i++) {
	 killer_scores[i] = 0;
	 killer_scores2[i] = 0;
	 killer_scores3[i] = 0;
	 killer1[i] = dummy;
	 killer2[i] = dummy;
	 killer3[i] = dummy;
       }
       
       memset(rootnodecount, 0, sizeof(rootnodecount));
       
       cpu_start = clock();
       
       temp_score = 0;
       cur_score = 0;
       true_score = 0;
       
       for (i_depth = 1; i_depth <= maxdepth; i_depth++) {
	 
	 /* don't bother going deeper if we've already used 2/3 of our time, and we
	    haven't finished our mindepth search, since we likely won't finsish */
	 elapsed = rdifftime (rtime (), start_time);
	 if (elapsed > time_for_move*2.1/3.0 && i_depth > mindepth)
	   break;
	 
	 failed = 0;
	 
	 alpha = temp_score - (Variant == Normal ? 35 : 100);
	 beta = temp_score + (Variant == Normal ? 35 : 100);

	 //ep_square = ep_temp;
	 temp_move = search_root (alpha, beta, i_depth);

         if (result) break;
	 
	 if (cur_score <= alpha) failed = 1;
	 else failed = 0;
	 
	 if (cur_score <= alpha && !time_exit) /* fail low */
	   {
	     alpha = cur_score - (Variant == Normal ? 350 : 600);
	     beta = cur_score;
	     
	     rs++;
	     
	     //ep_square = ep_temp;
	     temp_move = search_root (alpha, beta, i_depth);	
	     
	     if (cur_score > alpha && !time_exit) failed = 0;
	     
	     if (cur_score <= alpha && !time_exit)
	       {
		 alpha = -(INF+1);
		 beta = cur_score;
		 
		 rs++;
		 
		 //ep_square = ep_temp;
		 temp_move = search_root (alpha, beta, i_depth);	
		 
		 if (cur_score > alpha && !time_exit) failed = 0;
		 
	       }
	     else if (cur_score >= beta && !time_exit)
	       {
		 temp_move = search_root (-INF, +INF, i_depth);
		 if (!time_exit) failed = 0;
	       }
	   }
	 else if (cur_score >= beta && !time_exit) /* fail high */
	   {
	     comp_move = temp_move;
	     temp_score = cur_score;
	     
	     alpha = cur_score - 1;
	     beta = cur_score + (Variant == Normal ? 350 : 600);
	     
	     rs++;
	     
	     //ep_square = ep_temp;
	     temp_move = search_root (alpha, beta, i_depth);
	     
	     if (cur_score >= beta && !time_exit)
	       {
	         comp_move = temp_move;
	         temp_score = cur_score;
		 
		 alpha = cur_score - 1;
		 beta = +(INF+1);
		 
		 rs++;
		 
		 //ep_square = ep_temp;
		 temp_move = search_root (alpha, beta, i_depth);
		 
	       }
	     else if (cur_score <= alpha && !time_exit)
	       {
		 /* fail high then low...do not make it PV */
		 failed = 1;
	       };
	   };
	 
	 //ep_square = ep_temp;
	 
	 if (interrupt() && (i_depth > 1)) 
	   {
	     if (is_pondering)
	       return dummy;
	     else if (!go_fast)
	       break;
	   }
	 
	 /* if we haven't aborted our search on time, set the computer's move
	    and post our thinking: */
	 if (!time_failure && !failed) {
	   /* if our search score suddenly drops, and we ran out of time on the
	      search, just use previous results */
	   /* GCP except when we found a mate...maybe generalise ? */
	   /* enabled 2000-5-28 */
	  // if (time_exit && (cur_score < temp_score-50) && (cur_score > -900000))
	  //   break;

	   /* acidentally pondering if mated */
	   if (cur_score == -INF) return dummy;
	   
	   comp_move = temp_move;
	   temp_score = cur_score;
		  
	   stringize_pv(postpv);
	   
	   if (!time_exit)
	     {
	       true_i_depth = i_depth;
	     }      
	   
	   if (i_depth >= mindepth)
	     post_thinking (cur_score);
	   
	   if (temp_score > 900000 && ((int)(1000000-cur_score) < i_depth))
	     {
	       break;
	     };
	 }

	 if (time_exit) break;

	 /* reset the killer scores (we can keep the moves for move ordering for
	    now, but the scores may not be accurate at higher depths, so we need
	    to reset them): */
	 for (j = 0; j < PV_BUFF; j++) {
	   killer_scores[j] = 0;
	   killer_scores2[j] = 0;
	   killer_scores3[j] = 0;
	 }
	 
       }
     }
       
  //ep_square = ep_temp;

  if (!forcedwin)
  {
    cpu_end = clock();

    et = (cpu_end-cpu_start)/(double) CLOCKS_PER_SEC;

    old_move = comp_move;
    
    if ((Variant == Losers || Variant == Suicide) && !result && !alllosers && !is_pondering)
    {
      s_threat = FALSE;
      
      comp_move = proofnumbercheck(comp_move);

      if ((pn_restart < 10) && (s_threat))
      {
	/* a/b loser */
	pn_restart++;

	/* mark loser */
	for (i = 0; i < num_moves; i++)
	{
	  if (moves[i].from == old_move.from && moves[i].target == old_move.target
	      && moves[i].promoted == old_move.promoted)
	  {
	    rootlosers[i] = TRUE;
	    break;
	  }
	}
	for (j = 0; j < num_moves; j++)
	{
	    if (rootlosers[j]) k++;  
	}

	if (k == legals) alllosers = TRUE;
	
	goto restart;
      }
    }
  };

  if (alllosers) comp_move = old_move;

  if (pn_restart != 0 && xb_mode)
  {
    comp_to_san(comp_move, output);
    printf("tellics whisper %d restart(s), ended up with %s\n", pn_restart, output);
    result = 0;
  }
  elapsed = rdifftime (rtime (), start_time);
  
  printf("Used time : %d\n", elapsed);
  
  /* update our elapsed time_cushion: */
  if (moves_to_tc && !is_pondering) {
    time_cushion += time_for_move-elapsed+inc;
  }
  
  
  if (temp_score == INF-2 && !is_pondering/* && pn_move.target == dummy.target*/) 
    {
      if (white_to_move == 1) 
	{
	  result = black_is_mated;
	}
      else 
	{
	  result = white_is_mated;
	}
  }
  else if (temp_score == -(INF-2) && !is_pondering/* && pn_move.target == dummy.target*/)
    {
      if (white_to_move == 1)
	{
	  result = white_is_mated;
	}
      else
	{
	  result = black_is_mated;
	}
    }
  
  
  if (post && xb_mode && !is_pondering && 
	result != black_is_mated &&
	result != white_is_mated &&
        result != draw_by_fifty && result != draw_by_rep &&
	result != stalemate && !forcedwin)
    {
      if (temp_score > INF-400) 
	{
	  if (Variant != Bughouse)
	  {
	    printf("tellics kibitz Mate in %d\n", (int)((1000000-temp_score)/2));
	  }
	  else
	  {
	    printf("tellics ptell Mate in %d, give him no more pieces.\n", (int)((1000000-temp_score)/2));
	  }
	 }
      
      //comp_to_san (comp_move, postmove);

      if ((et > 0) && (Variant != Bughouse))
	{
	  printf("tellics whisper d%d %+.2f %sn: %ld qp: %.0f%% fh: %.0f%% c-x: %d r-x: %d 1-x: %d egtb: %d time: %.2f nps: %ld\n",
		 true_i_depth, (float)temp_score/100.0, postpv, nodes, 
		 (((float)qnodes*100)/((float)nodes+1)),
		 ((float)FHF*100)/((float)(FH+1)),
//		 ((float)PVS*100)/((float)FULL+1),
//		 ((float)PVSF*100)/((float)PVS+1),
		 ext_check, ext_recap, ext_onerep, EGTBHits,
		 ((float)elapsed/100.), 
		 (long)((float) nodes/(float) (et)));
	}
    }

  
  if ((result != white_is_mated) 
      && (result != black_is_mated)
      && (result != stalemate)
      && (result != draw_by_fifty) && (result != draw_by_rep)
      && (true_i_depth >= 3) 
      && pn_move.target == dummy.target 
      && !is_pondering
      && (Variant != Bughouse))
    {
      if (bestmovenum == -1) DIE;

	Learn(temp_score, bestmovenum, true_i_depth);
    }

  if ((Variant == Bughouse) && temp_score > -999900)
  {
    if (tradefreely == 0 && !userealholdings)
    {
      tradefreely = 1;
      printf("tellics ptell You can trade freely.\n");
    }
  }
  else if ((temp_score < -999900) && (Variant == Bughouse) && pn_move.target == dummy.target)
    {
	if (userealholdings)
	{
            must_sit = TRUE;
	}
	else
	{
	    userealholdings = 1;
	    ProcessHoldings(realholdings);
	    tradefreely = 0;
	    printf("tellics ptell ---trades\n");
	    goto restart;
	}

      
      /* shut up if the mate is already played */
      if (temp_score > -1000000)
	{
	  if (partnerdead)
	    {
	      printf("tellics kibitz Both players dead...resigning...\n");
	      printf("tellics resign\n");
	    }
	  else
	    {
	      printf("tellics ptell I am forcedly mated (dead). Tell me 'go' to start moving into it.\n");
	    }
	}
    }
  else if ((temp_score > -60000) && (temp_score < -40000) && (Variant == Bughouse) && !partnerdead && pn_move.target == dummy.target)
    {
      must_sit = TRUE;
      printf("tellics ptell I'll have to sit...(lose piece that mates you)\n");
    }

  return comp_move;

}


void tree (int depth, int indent, FILE *output, char *disp_b) {

  move_s moves[MOVE_BUFF];
  int num_moves, i, j;
  int ic;

  //
  //ep_temp = ep_square;
  num_moves = 0;

  /* return if we are at the maximum depth: */
  if (!depth) {
    return;
  }

  /* generate the move list: */
  gen (&moves[0]);
  num_moves = numb_moves;

  ic = in_check();

  /* loop through the moves at the current depth: */
  for (i = 0; i < num_moves; i++) {
    make (&moves[0], i);

    /* check to see if our move is legal: */
    if (check_legal (&moves[0], i, ic)) {
      /* indent and print out our line: */
      for (j = 0; j < indent; j++) {
	fputc (' ', output);
      }
      print_move (&moves[0], i, output);
      fprintf (output, "\n");

      /* display board if desired: */
      if (disp_b[0] == 'y')
	display_board (output, 1);

      /* go deeper into the tree recursively, increasing the indent to
	 create the "tree" effect: */
      tree (depth-1, indent+2, output, disp_b);
    }

    /* unmake the move to go onto the next: */
    unmake(&moves[0], i);
  }

  //ep_square = ep_temp;

}