/* 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 <math.h>
#include "util.h"
#include "eval.h"
#include "bitboard.h"
#include "move.h"
#include "movelist.h"
#include "option.h"
#include "timer.h"
#include "ttable.h"
#include "search.h"
#include "moveseq.h"
#include "log.h"
#include "square.h"
#include "piece.h"
#include "input.h"
#include "searchparams.h"
#include "searchdata.h"
#include "searchstats.h"
#include "sort.h"
#include "null.h"
#include "cmd.h"
#include "moveseq.h"
#include "quiesce.h"
#include "history.h"
#include "iterate.h"

#define TIMECHECK 	0xFFF       // 4095


#define FUTSCORE(board,fdel)     (MATERIAL(board,side)+(fdel))

int8_t LMRReductionMatrix[2][64][64]; // [(pv=1,nonpv=0)][depth][movecount]
int FutilityMoveCountArray[16];

search_t search;

static inline int LMRReduction(int nodetype, int depth, int movecount){
    ASSERT(depth>=1);
    ASSERT(movecount>=1);
    if(nodetype==PV){
	return LMRReductionMatrix[1/*PV*/][MIN(depth,63)][MIN(movecount,63)];
    }else{
	return LMRReductionMatrix[0/*nonPV*/][MIN(depth,63)][MIN(movecount,63)];
    }
}

static inline int FutilityMoveCount(int depth){
    return depth<16 ? FutilityMoveCountArray[depth]:512;
}

static void SearchDumpLine(board_t *board, 
			   searchparams_t *searchparams,
			   searchdata_t *searchdata,
			   searchstats_t *searchstats,
			   int ply,
			   int depth,
			   int alpha,
			   int beta,
			   int best,
			   int best_move,
			   int nodecnt,
			   int reason);


int Search (board_t *board, 
	    searchparams_t *searchparams, 
	    searchdata_t *searchdata, 
	    searchstats_t *searchstats,
	    uint8_t ply, 
	    short depth, 
	    int alpha, 
	    int beta, 
	    short nodetype, 
	    int *best_move,
	    moveseq_t *pv_out);

void SearchCheckTime(searchparams_t *searchparams,
		     searchdata_t *searchdata,
		     searchstats_t *searchstats);

void SearchInit(option_list_t *options){
    int depth;
    int movecount;
    search.UseNull=OptionGetBool(options,"NullMovePruning");
    search.UseNullVer=OptionGetBool(options,"NullMoveVerification");
    search.UseTT=OptionGetBool(options,"UseTT");
    search.UseMateScores=OptionGetBool(options,"UseMateScores");
    search.UseTTinPV=OptionGetBool(options,"UseTTinPV");
    search.UseMateScoresinPV=OptionGetBool(options,"UseMateScoresinPV");
    search.UseLMR=OptionGetBool(options,"LMR");
    search.AggressiveLMR=OptionGetBool(options,"AggressiveLMR");
    search.UseFut=OptionGetBool(options,"FutilityPruning");
    search.LateMovePruning=OptionGetBool(options,"LateMovePruning");
    search.UseAspiration=OptionGetBool(options,"AspirationSearch");
    search.AspirationWindow=OptionGetInt(options,"AspirationWindow");
    search.UseMateDistancePruning=OptionGetBool(options,"MateDistancePruning");
    search.LazyEvalMargin1=OptionGetInt(options,"LazyEvalMargin1");
    search.LazyEvalMargin2=OptionGetInt(options,"LazyEvalMargin2");
    search.DeltaMargin=OptionGetInt(options,"DeltaMargin");
    search.UseHistory=OptionGetBool(options,"UseHistory");
    search.Razoring=OptionGetBool(options,"Razoring");
    search.DumpTree=OptionGetBool(options,"DumpTree");
    search.PanickTimeFactor=OptionGetInt(options,"PanickTimeFactor");
    if(!search.AggressiveLMR){
	for (depth = 1; depth < 64; depth++) {
	    for (movecount = 1; movecount < 64; movecount++) {
		LMRReductionMatrix[1/*PV*/][depth][movecount]    
		    = movecount>=6?1:0;
		LMRReductionMatrix[0/*nonPV*/][depth][movecount] 
		    = movecount>=3?1:0;
	    }
	}
    }else{
	// Stockfish!
	for (depth = 1; depth < 64; depth++) {
	    for (movecount = 1; movecount < 64; movecount++) {
		double    pvRed = log((double)depth) * log((double)movecount) / 3.0;
		double nonPVRed = log((double)depth) * log((double)movecount) / 1.5;
		LMRReductionMatrix[1/*PV*/][depth][movecount]    
		    = (int8_t) (   pvRed >= 1.0 ? floor(pvRed) : 0);
		LMRReductionMatrix[0/*nonPV*/][depth][movecount] 
		    = (int8_t) (nonPVRed >= 1.0 ? floor(nonPVRed) : 0);
	    }
	}
    }
    if(!search.LateMovePruning){
	for (depth = 0; depth < 16; depth++){
	    FutilityMoveCountArray[depth] = 512;
	}
    }else{
	// Stockfish!
	for (depth = 0; depth < 16; depth++){
	    FutilityMoveCountArray[depth] = 3 + (1 << (3 * depth / 4));
	}
    }
}

void MoveMakeEx(board_t *board, 
		searchdata_t *searchdata, 
		int ply, 
		int *move, 
		undo_t *undo){
    searchdata->moveseq->gencnt=ply+1;
    MoveMakeS(board,move,undo);
    // Put this after MoveMake to make sure capture information is updated
    searchdata->moveseq->moves[ply]=*move;
}

void MoveUnMakeEx(board_t *board, 
		searchdata_t *searchdata, 
		undo_t *undo){
    searchdata->moveseq->gencnt--;
    MoveUnMakeS(board,undo);
}

static void NullMoveMakeEx(board_t *board, 
			   searchdata_t *searchdata, 
			   int ply, 
			   undo_t *undo){
    searchdata->moveseq->moves[ply]=NULLMOVE;
    searchdata->moveseq->gencnt=ply+1;
    NullMoveMakeS(board,undo);
}

static void NullMoveUnMakeEx(board_t *board, 
			   searchdata_t *searchdata, 
			   undo_t *undo){
    searchdata->moveseq->gencnt--;
    NullMoveUnMakeS(board,undo);
}


void ShowBestMove(searchstats_t *searchstats){
    char LANmv[SANSZ];
    MoveToLAN(searchstats->RootPVSeq->moves[0],LANmv);
    Output("bestmove %s", LANmv);
    if(searchstats->RootPVSeq->gencnt>=2){
	MoveToLAN(searchstats->RootPVSeq->moves[1],LANmv);
	Output(" ponder %s\n", LANmv);
    }else{
	Output("\n", LANmv);
    }
}

// [VdB] Periodic updates.

static void ShowUpdate(searchparams_t *searchparams, 
		       searchdata_t *searchdata,
		       searchstats_t *searchstats)
{
    Output("stat01: %d %d %d %d %d %s\n", 
	   (int)(100*TimerElapsed (searchdata->timer)),
	   searchstats->NodeCnt+searchstats->QuiesCnt,
	   searchdata->RootDepth,
	   searchdata->RootMovesRemaining,
	   searchdata->RootMoves,
	   searchdata->RootMoveCurrent
	   );
}

static void ShowUpdateUci(searchparams_t *searchparams, 
			  searchdata_t *searchdata,
			  searchstats_t *searchstats){
    searchstats->ElapsedTime=TimerElapsed(searchdata->timer);
    if(searchstats->ElapsedTime<1.0){
	Log("info currmove %s currmovenumber %d\n",
	       searchdata->RootMoveCurrentLAN,
	       searchdata->RootMoves-searchdata->RootMovesRemaining
	       );
	return;
    }
    Output("info currmove %s currmovenumber %d\n",
	   searchdata->RootMoveCurrentLAN,
	   searchdata->RootMoves-searchdata->RootMovesRemaining
	   );
}

/* 
 * Look at input during searching.
 * We assume that the availability of input has already been checked.
 *
 */


void inline SearchParseInput(board_t *board,
			     searchparams_t *searchparams, 
			     searchdata_t *searchdata, 
			     searchstats_t *searchstats){
    char *input_cmd;
    input_cmd=InputLook();
    split_input(input_cmd);
    if(searchparams->protocol==PROTOCOL_UCI){
	if(tokeneq(token[0],"stop") || tokeneq(token[0],"quit")){
	    //	    ShowBestMove(searchparams);
	    longjmp(searchdata->rootpointer,1);
	}else if(tokeneq(token[0],"ponderhit")){
	    searchparams->infinite=false;
	    IterateSetTime(board,searchparams,searchdata,searchstats);
	    // ElapsedTime should have been set in the previous call...but never mind
	    searchstats->ElapsedTime = TimerElapsed(searchdata->timer);
	    searchparams->maxtime+=searchstats->ElapsedTime;
	    Log("Increasing maxtime to %f\n",searchparams->maxtime);
	    InputWakeup();
	    SearchCheckTime(searchparams,
			    searchdata,
			    searchstats);
	}else{
	    InputWakeup(); // ignore
	}
	return;
    }
    if(false){
    }else if (searchparams->infinite && 
	      !(tokeneq(token[0],".")) && 
	      !(tokeneq(token[0],"+"))) {
	longjmp(searchdata->rootpointer,1);
    }else if(tokeneq(token[0],"?")||
	     tokeneq(token[0],"force")||
	     tokeneq(token[0],"ping")||
	     tokeneq(token[0],"stop")||
	     tokeneq(token[0],"result")||
	     tokeneq(token[0],"new")||
	     tokeneq(token[0],"quit")){   
	longjmp(searchdata->rootpointer,1);
    }else{ // We also process some command during search
	if(tokeneq(token[0],"post")){
	    cmd_post();
	}else if(tokeneq(token[0],"nopost")){
	    cmd_nopost();
	}else if(tokeneq(token[0],"easy")){
	    cmd_easy();
	}else if(tokeneq(token[0],"hard")){
	    cmd_hard();
	}else if(tokeneq(token[0],"isready")){
	    cmd_isready();
	}else if(tokeneq(token[0],"option")){
	    cmd_option();
	}else if (tokeneq(token[0],".")){ /* periodic updates */
	    ShowUpdate(searchparams,searchdata,searchstats);
	}else if (tokeneq(token[0],"+")){
	    MoveSeqShow(searchdata->RootBoard,searchdata->moveseq);
	}
	// For unrecognized commands or commands that have been 
	// processed here we discard the input.
	InputWakeup();
    }
}

void SearchCheckTime(searchparams_t *searchparams,
		     searchdata_t *searchdata,
		     searchstats_t *searchstats){
    searchstats->ElapsedTime = TimerElapsed(searchdata->timer);
    if(searchstats->ElapsedTime >= searchparams->maxtime){ /* Hard timeout */
	longjmp(searchdata->rootpointer,1);	
    }
    if(searchstats->ElapsedTime >= searchparams->SearchTime  && 
       searchdata->RootScore>searchdata->RootAlpha && searchdata->RootState!=SCORE_FAIL_LOW
       ){ /* Do not timeout while failing low, or while resolving a fail low.
	     Currently this also means we cannot timeout
	     while searching the first root move. Is this a good idea?
	  */
	longjmp(searchdata->rootpointer,1);	
    }
}




int SearchPVS(board_t *board, 
	      searchparams_t *searchparams, 
	      searchdata_t *searchdata, 
	      searchstats_t *searchstats,
	      uint8_t ply, 
	      short depth, 
	      int alpha, 
	      int beta, 
	      short nodetype, 
	      int *best_move,
	      moveseq_t *pv)
/* Search at a node with open window which is expected to fail high. */
{
    int score,savebeta;


    savebeta=beta;
    

    /* First search with zero window around beta hoping to 
       get a cutoff. 
    */	

    score = Search (board, 
		    searchparams, 
		    searchdata, 
		    searchstats,
		    ply, 
		    depth, 
		    beta-1, 
		    beta, 
		    CUT, /* nodetype */
		    best_move,
		    pv);

    ASSERT(MoveSeqValidate(board,pv));
    if(score < beta){
	searchstats->PVSFailCnt++;
    }
    if (alpha < score && score < beta) { 
	/* We did not fail high and also not low...
	   We now we see if our score is strictly smaller than
	   the above returned upper bound.
	*/
	beta=score+1;  // +1 to get exact tt entries.
	score = Search (board, 
			searchparams, 
			searchdata, 
			searchstats,
			ply, 
			depth, 
			alpha, 
			beta, 
			PV, /* nodetype */
			best_move,
			pv);

	ASSERT(search.UseTTinPV|| MATESCORE(score)|| score==DRAWSCORE || score<=alpha || score>=beta || beta<=alpha+1 || pv->gencnt>=depth);
	ASSERT(MoveSeqValidate(board,pv));
	
    }
    if(score >=beta/*+1*/ && score<savebeta){
	/* Hmm, we have a case of search instability here... 
	   Research with fully open window.
	*/
	searchstats->SearchInconsistencyCnt++;
	beta=savebeta;

	score = Search (board, 
			searchparams, 
			searchdata, 
			searchstats,
			ply, 
			depth, 
			alpha, 
			beta, 
			PV,  /* nodetype */
			best_move,
			pv);
	ASSERT(search.UseTTinPV|| MATESCORE(score)|| score==DRAWSCORE || score<=alpha || score>=beta || beta<=alpha+1 || pv->gencnt>=depth);
	
	ASSERT(MoveSeqValidate(board,pv));
	
    }
    
    ASSERT(search.UseTTinPV|| MATESCORE(score)|| score==DRAWSCORE || score<=alpha || score>=savebeta || savebeta<=alpha+1 || pv->gencnt>=depth);


    return score;
    
}

void SearchRoot (board_t *board, 
		 searchparams_t *searchparams, 
		 searchdata_t *searchdata,
		 searchstats_t *searchstats,
		 movelist_t *movelist)

/**************************************************************************
 *
 *  This perform searches at ply=0.  For ply>0, it calls the more generic
 *  search() routine. 
 *
 *  This routine returns both a score (searchdata->RootScore) which is reset
 *  at every invokation, and a move (searchstats->RootPV) which is only
 *  set if searchdata->RootScore > searchdata->RootAlpha.
 *
 **************************************************************************/


{
    int score, alpha,beta,savealpha,savebeta,savedepth;
    short depth;
    uint8_t side, xside;
    leaf *p;
    undo_t undo[1];
    moveseq_t pv[1];
    unsigned long nodecnt;
    int movecount=0;
    int best_move;


    beta=searchdata->RootBeta;
    alpha=searchdata->RootAlpha;
    depth=searchdata->RootDepth;

    searchdata->RootScore=-INFIN-1;
    savealpha = alpha;
    savebeta=beta;
    savedepth=depth;

    

    searchstats->NodeCnt++;
    searchdata->DumpId++;
    
    side = board->side;
    xside = 1^side;

    searchdata->ChkCnt[0]=0;
    searchdata->ChkCnt[1]=0;
    searchdata->InChk[0]=board->in_check;
    if(board->in_check){
	searchstats->ChkExtCnt++;
	searchdata->ChkCnt[1]=1;
	depth += 1;
    }
    for (p = movelist->moves; p < movelist->moves+movelist->gencnt; p++) {
	
	MoveListPickSel(movelist,p); 

	nodecnt=searchstats->NodeCnt+searchstats->QuiesCnt;
	
	/* periodic updates */
	MoveToSAN (board, p->move, searchdata->RootMoveCurrent);
	MoveToLAN (p->move, searchdata->RootMoveCurrentLAN);
	searchdata->RootMoves=movelist->gencnt;
	searchdata->RootMovesRemaining=movelist->moves+movelist->gencnt-p-1;
	if(searchparams->protocol==PROTOCOL_UCI){
	     ShowUpdateUci(searchparams, 
			   searchdata,
			   searchstats);
	}
	/* end periodic updates */
	
	MoveMakeEx(board,searchdata,0,&p->move,undo);
	movecount++;
	
	/*  If first move, search against full alpha-beta window  */
		
	if (p == movelist->moves){
	    score = -Search (board, 
			     searchparams, 
			     searchdata,
			     searchstats,
			     1, 
			     depth-1, 
			     -beta, 
			     -alpha, 
			     PV, /*  nodetype */
			     &best_move,
			     pv);

	    ASSERT(MoveSeqValidate(board,pv));

	} else { /*  we expect to fail low at other nodes */
	    alpha = MAX (searchdata->RootScore, alpha);  
	    score=-SearchPVS(board, 
			     searchparams, 
			     searchdata, 
			     searchstats,
			     1, 
			     depth-1, 
			     -beta, 
			     -alpha, 
			     CUT, 
			     &best_move,
			     pv);

	}
	

	MoveUnMakeEx (board, searchdata, undo);

	/* this is for sorting the movelist at the root */
	p->score = (searchstats->NodeCnt+searchstats->QuiesCnt-nodecnt);  

	if (score > searchdata->RootScore) {
	    /* Since RootScore is initialized as -INFIN-1
	       this branch will be taken at least once
	       (if there is no timeout).
	    */
	    searchdata->RootScore = score;  
	    if (searchdata->RootScore > alpha){  /* new PV */
		
		searchstats->RootPV = p->move;
		MoveSeqPrependMove(searchstats->RootPVSeq,pv,searchstats->RootPV);
		ASSERT(MoveSeqValidate(board,searchstats->RootPVSeq));
		searchstats->RootPVScore=searchdata->RootScore;
		if (searchdata->RootScore >= beta){  /* fail high at root */

		    ShowLine (board, 
			      searchparams, 
			      searchdata, 
			      searchstats,
			      SCORE_FAIL_HIGH);
		    goto done;
		}

		ShowLine (board, 
			  searchparams, 
			  searchdata, 
			  searchstats,
			  SCORE_EXACT);
	    }
	}
	
       
	if(InputLook()){
	    SearchParseInput(board,searchparams,searchdata,searchstats);
	}
       
	if(!searchparams->infinite && (searchstats->NodeCnt & TIMECHECK)==0){
	    SearchCheckTime(searchparams,searchdata,searchstats);
	}
	

    }
    
    
   

    /* We always get here if there is not timeout.
       This happens either by searching all rootmoves,
       or by a having a move with a score above beta.
    */

 done:

    // hack: to put best move in front
    
    {
	int max_score;
	leaf *q;
	max_score=-INFIN;
	for(p=movelist->moves; p < movelist->moves+movelist->gencnt; p++){
	    if(p->score>max_score){
		max_score=p->score;
	    }
	    if((p->move & MOVEMASK)== (searchstats->RootPV & MOVEMASK)){
		q=p;
	    }
	}
	q->score=max_score+1;
    }
    

    if (searchdata->RootScore <= savealpha){

	/* Fail low at root */
	ShowLine (board, 
		  searchparams, 
		  searchdata, 
		  searchstats,
		  SCORE_FAIL_LOW);

	/*  If none of the moves is good, we still want to try the same first move */
	movelist->moves->score = savealpha;

	
    }else{   /* searchdata->RootScore>savealpha */

	/* no fail low: update history */
	if(search.UseHistory){
	    HistoryGood(searchdata->history,board,searchstats->RootPV,depth);
	}

        /* this is useful for analysis */
        if (search.UseTT){
            TTablePut (TTable,board, depth, 0, savealpha, beta, false /* move_connected */, searchdata->RootScore, searchstats->RootPV);
        }

    }
    
    
}




int Extension(board_t *board,
	      searchparams_t *searchparams, 
	      searchdata_t *searchdata, 
	      searchstats_t *searchstats,
	      int nodetype,
	      int ply,
	      int depth,
	      unsigned int move_class,
	      int *dangerous){
    int ext=0;
    int side,xside;
    side=board->side;
    xside=1^side;
    *dangerous=false;
    if(board->in_check){
	*dangerous=true;
	if(ply+1 <= 2* searchdata->RootDepth){
	    ext+=1;
	    searchstats->ChkExtCnt++;
	}
    }
    if(/*(move_class & CLASSCAPTURE) && */
       board->pmaterial[side]==0 && board->pmaterial[xside]==0){
	*dangerous=true; 
	if((move_class & CLASSCAPTURE) && !ext){
	    ext+=1;
	}
    }
    if (depth <= 1 && (move_class & (CLASS6RANK | CLASS7RANK))){
	*dangerous=true;
	if(!ext && nodetype==PV){
	    //	    ext+=1;
	}
    }
    if ((move_class & CLASSPROMOTION)){
	searchstats->PawnExtCnt++;
	*dangerous=true;
	if(!ext && nodetype==PV){
	    //	    ext+=1;
	}
    }
    if(move_class & CLASSPASSEDPAWN){
	*dangerous = true;
    }
    if(move_class & CLASSPOSITIVESWAPOFF){
    	*dangerous = true;
    }
    return ext;
}



#define REASON_NORMAL 0
#define REASON_FUT 1
#define REASON_QUIESCE 2
#define REASON_TRANS_EXACT 3
#define REASON_RECOG 4
#define REASON_BAILOUT 5
#define REASON_DRAW_3 6
#define REASON_MATE 7
#define REASON_TRANS_BOUNDS 8
#define REASON_NULL 9
#define REASON_NULL_VER 10
#define REASON_BETA_CUTOFF 11
#define REASON_MATE_DISTANCE_PRUNING 12
#define REASON_DRAW_50 13
#define REASON_NULL_FAIL_LOW 14
#define REASON_STALEMATE 15
#define REASON_RAZORING 16
#define REASON_THREAT_RESEARCH 17

char * ReasonAsci[18]={"nor","fut","qui","tre","rec","bai","re3","mat","trb","nul","nuv","bet","mdp","d50","nfl","stm","raz","thr"};

int FutMargins[4]={0,200,300,400};
int RazorMargins[4]={0,200,250,300};

int Search (board_t *board, 
	    searchparams_t *searchparams, 
	    searchdata_t *searchdata, 
	    searchstats_t *searchstats,
	    uint8_t ply, 
	    short depth, 
	    int alpha, 
	    int beta, 
	    short nodetype, 
	    int *best_move_out,
	    moveseq_t *pv_out)
/**************************************************************************
 *
 *  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, savebeta, savedepth, savenodecnt, reason;
    int threat_move;
    int side, xside;
    int legal_moves=0;
    unsigned int move_class;
    int rc, firstmove;
    int fdel, donull;
    leaf *p;
    int pbest_move;
    int g0, g1;
    int upperbound;
    int movecount=0;
    pickstate_t pickstate[1];
    undo_t undo[1];
    int i;
    int R;
    int ret;
    moveseq_t pv[1];
    int doLMR;
    int savedumpid;
    short savenode;
    int best_move=NOMOVE;
    int dangerous;
    int ext;
    movelist_t moves_played[1];
    int move_connected, move_avoid_threat;
    int local_eval;
    uint8_t flag;

#ifdef DEBUG
	board_t board_copy[1];
	BoardCopy(board_copy,board);
#endif 
    ASSERT((nodetype==PV && alpha+1<beta)|| (nodetype!=PV && alpha+1>=beta));
    ASSERT(!board_copy->xin_check);

    

    *best_move_out=NOMOVE;

    side = board->side;
    xside = 1^side;


    reason=REASON_NORMAL;
    savenode = nodetype;
    
    pv->gencnt=0;
    pv_out->gencnt=0;
    moves_played->gencnt=0;

    savedepth=depth;
    savealpha = alpha;
    savebeta = beta;
    savenodecnt=searchstats->NodeCnt;
    savedumpid=searchdata->DumpId;
    searchstats->NodeCnt++;
    searchdata->DumpId++;

    // Set posdiff/lazydiff to sensible initial values 
    searchdata->posdiff[side]=searchdata->posdiff[xside]=search.LazyEvalMargin1;
    searchdata->lazydiff[side]=searchdata->lazydiff[xside]=search.LazyEvalMargin2;

    searchdata->reduction[ply]=0;

    // emergency exit

    if(ply>=MAXPLYDEPTH){
	best=board->in_check?alpha:Evaluate(board, 
					    searchparams,
					    searchdata, 
					    searchstats, 
					    -INFIN,
					    INFIN);
	reason=REASON_BAILOUT;
	goto nomove;
	
    }




    if (EvaluateDraw (board)){
	best=DRAWSCORE;
	reason=REASON_RECOG;
	goto nomove;
    }

    if (board->GameCnt >= board->Game50+3 && BoardRepeat(board)) {
	best=DRAWSCORE;
	reason=REASON_DRAW_3;
	goto nomove;
    }

    if (board->GameCnt >= board->Game50+100) {
	best=DRAWSCORE;
	reason=REASON_DRAW_50;
	goto nomove;
    }


    //local_eval=Evaluate(board,searchparams,searchdata,searchstats,alpha,beta);
    local_eval=MATERIAL(board,board->side);


    PickStateInit(pickstate);
    

    /* End draw check */


    donull = true;


    if (depth <= 0){
	searchstats->NodeCnt--;
	best=Quiesce (board, searchparams, searchdata, searchstats, ply, alpha, beta, 0 /*depth*/, best_move_out); 
	reason=REASON_QUIESCE;
	goto nomove;
    }



    /**************************************************************************** 
     *
     *  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.
     *
     ***************************************************************************/


    searchdata->Hashmv[ply] = NOMOVE;
    upperbound = INFIN;
    if (search.UseTT){ 
	uint8_t tt_depth;
	rc = TTableGet (TTable, board,  ply, &tt_depth, &flag, &score, &g1);
	if(rc && (flag & TTABLE_UNDERTHREAT) && (tt_depth>=depth || MATESCORE(score)) && searchdata->reduction[ply-1]>0){
	    best=alpha; // force full depth research
	    reason=REASON_THREAT_RESEARCH;
	    searchstats->TransThreatCnt++;
	    goto nomove;
	}
	if(rc){
	    searchdata->Hashmv[ply] = g1 & MOVEMASK;
	    if(flag & (TTABLE_EXACTSCORE|TTABLE_QUIESCENT)){
		local_eval=score;
	    }else if(flag & TTABLE_UPPERBOUND){
	    	if(score<local_eval){
	    	    local_eval=score;
	    	}
	    }else if(flag & TTABLE_LOWERBOUND){
		if(score>local_eval){
		    local_eval=score;
		}
	    }
	}
	if (rc && (tt_depth>=depth || (search.UseMateScores && MATESCORE(score))) &&
	    (search.UseTTinPV 
	     || (search.UseMateScoresinPV && MATESCORE(score))
	     ||  savenode!=PV) 
	    ){
	    if(flag & TTABLE_EXACTSCORE){
		best=score;
		*best_move_out=searchdata->Hashmv[ply];
		TTableRefresh(TTable,board);
		reason=REASON_TRANS_EXACT;
		goto nomove;
	    }else if(flag & TTABLE_UPPERBOUND){
		beta = MIN (beta, score);
		upperbound = score;
		donull = false;
	    }else if(flag & TTABLE_LOWERBOUND){
		alpha = MAX (alpha, score);
	    }
	    if (alpha >= beta){
		best=score;
		TTableRefresh(TTable,board);
		*best_move_out=searchdata->Hashmv[ply];
		reason=REASON_TRANS_BOUNDS;
		goto nomove;
	    }
	}
    }
    
    
    

    /*****************************************************************************
     *
     *  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 RootDepth <= 3.  This allows us to find mate-in 2 problems quickly.
     *  10. We are looking for a null threat.
     *
     *****************************************************************************/

    ASSERT(ply>=1);
    g0=searchdata->moveseq->moves[ply-1];

    // a la Stockfish!
    R=depth>=5?4:3;
    if(local_eval>beta+2*ValueP){
        R++;
    }
    //    R=3;
    int donenull=false;
    threat_move=NOMOVE;
    move_connected=false;
    if (search.UseNull && g0 != NULLMOVE  &&  depth > 1 /*&& savenode != PV*/ &&  
	  !board->in_check && local_eval+ValueP >= beta 
	&& beta > -MATE+(ply+1) && donull &&
	board->pmaterial[side] > ValueB){
	donenull=true;
	    NullMoveMakeEx(board,searchdata,ply,undo);
	    nullscore = -Search (board, 
				 searchparams, 
				 searchdata, 
				 searchstats,
				 ply+1, 
				 depth-R, 
				 -beta, 
				 -beta+1, 
				 ALL, 
				 &best_move,
				 pv);
	    ASSERT(MoveSeqValidate(board,pv));
	    if(nullscore<=alpha ){
		threat_move=best_move;
		move_connected=(threat_move!=NOMOVE && MoveConnected(g0,threat_move));
	    }
	    if(nullscore<=alpha && ply>=1 && searchdata->reduction[ply-1]>0){
		if(MATESCORE(nullscore) || move_connected){
		    NullMoveUnMakeEx(board,searchdata,undo);
		    best=nullscore;
		    searchstats->NullFailLowCnt++;
		    reason=REASON_NULL_FAIL_LOW;
		    goto nomove;
		}
	    }

	    NullMoveUnMakeEx(board,searchdata,undo);
	    if (savenode!=PV && nullscore >= beta){
		if(depth<6 || !search.UseNullVer){
		    searchstats->NullCutCnt++;
		    best=nullscore /* beta*/;
		    *best_move_out=NULLMOVE;
		    reason=REASON_NULL;
		    goto nomove;
		}else{ /* verification */
		    int nullscore_ver;
		    int old_flags;
		    old_flags=search.UseNull; 
		    search.UseNull=false; // temporary hack
		    nullscore_ver=Search (board, 
					  searchparams, 
					  searchdata, 
					  searchstats,
					  ply, 
					  depth-5,  
					  beta-1, 
					  beta, 
					  nodetype, 
					  &best_move,
					  pv);
		    ASSERT(MoveSeqValidate(board,pv));

		    search.UseNull=old_flags;
		    if(nullscore_ver>=beta){
			searchstats->NullCutCnt++;
			*best_move_out=NULLMOVE;
			best=nullscore /* beta */;
			reason=REASON_NULL_VER;
			goto nomove; 
		    }
		}
	    }
	}

    if(search.Razoring && savenode != PV && 
       depth <= 3 && 
       !MATESCORE(beta) && 
       !board->in_check && 
       local_eval < beta - RazorMargins[depth] && 
       searchdata->moveseq->moves[ply-1]!=NULLMOVE
        ){
    	score=Quiesce (board, searchparams, searchdata, searchstats, ply, alpha, beta, 0 /*depth*/, &best_move); 
    	if(score <= alpha){
    	    best=score;
    	    *best_move_out=best_move;
    	    searchstats->RazrCutCnt++;
	    reason=REASON_RAZORING;
    	    goto nomove;
    	}
    }

    firstmove = true;
    best = -INFIN;


    while(true){

	if(board->in_check){
	    ret=PhasePick1(board,searchdata,pickstate,&p,ply,depth);
	}else{
	    ret=PhasePick(board,searchdata,pickstate,&p,ply,depth);
	}

	if(!ret){
	    break;
	}

	move_class=MoveClassifier(board,p->move);
	// TODO Take ep into account
	fdel=Value[board->cboard[TOSQ(p->move)]];


	MoveMakeEx (board, searchdata, ply,  &p->move, undo);

	if(board->xin_check){
	    MoveUnMakeEx (board, searchdata, undo);
	    continue;
	}
	legal_moves++;

	if (savenode != PV){
	    nodetype = (savenode == CUT) ? ALL : CUT;
	}else if(firstmove){
	    nodetype = PV;
	}else{
	    nodetype = CUT;
	}

	ext=Extension(board,
		      searchparams,
		      searchdata,
		      searchstats,
		      nodetype,
		      ply,
		      depth,
		      move_class,
		      &dangerous);

	if(dangerous){
	    searchstats->DangerousNodeCnt++;
	}


	movecount++;
	moves_played->moves[moves_played->gencnt++].move=p->move;

	// Futility pruning
	move_avoid_threat=threat_move && MoveAvoidThreat(threat_move,p->move);

	if(savenode!=PV && search.UseFut && !dangerous && !move_avoid_threat && best>=-MATE+256){
	    if(depth<=3 && local_eval+fdel+FutMargins[depth] < alpha){
		searchstats->FutlCutCnt++;
		best=MAX(best,local_eval+fdel+FutMargins[depth]/2);
		MoveUnMakeEx (board, searchdata, undo);
		continue;
	    }else if(movecount>=FutilityMoveCount(depth) && ((pickstate->phase==PICKREST)|| (pickstate->phase==PICKBADCAPT))){
		searchstats->FutlCutCnt++;
		MoveUnMakeEx (board, searchdata, undo);
		continue;
	    }
	}


	if (firstmove){
	    firstmove = false;
	    ASSERT(search.UseTT || (alpha==savealpha));
	    score = -Search (board, 
			     searchparams, 
			     searchdata, 
			     searchstats,
			     ply+1, 
			     depth-1+ext, 
			     -beta, 
			     -alpha, 
			     nodetype, 
			     &best_move,
			     pv);

	    ASSERT(MoveSeqValidate(board,pv));
	} else {  /* Zero window search for rest of moves */


	    alpha = MAX (best, alpha);                /* fail-soft condition */
	    doLMR=search.UseLMR &&  !dangerous && !(move_class&CLASSCAPTURE) && !move_avoid_threat;
	    /* First try to dismiss this node at reduced depth
	     */
	    searchdata->reduction[ply]=LMRReduction(savenode,depth,movecount);
	    doLMR=doLMR && (searchdata->reduction[ply]>=1);
	    if(doLMR){
		searchstats->LMRRedCnt++;
		score = -SearchPVS (board, 
				    searchparams, 
				    searchdata, 
				    searchstats,
				    ply+1, 
				    depth-1-searchdata->reduction[ply], 
				    -alpha-1, 
				    -alpha, 
				    CUT, /* nodetype */
				    &best_move,
				    pv);
	    }
	    if(!doLMR || (doLMR && score > best)){
		/* If we raise alpha do ordinary PVS search
		 */
		searchdata->reduction[ply]=0;
		if(doLMR){
		    searchstats->LMRRedCnt--;
		    searchstats->LMRFailHighCnt++;
		}
		score=-SearchPVS(board, 
				 searchparams, 
				 searchdata, 
				 searchstats,
				 ply+1, 
				 depth-1+ext, 
				 -beta, 
				 -alpha, 
				 nodetype, 
				 &best_move,
				 pv);

		ASSERT(search.UseTTinPV|| MATESCORE(score)|| score==DRAWSCORE || score<=alpha || score>=beta || beta<=alpha+1 || pv->gencnt>=depth-1);
	    }
	    
	}
	
	MoveUnMakeEx(board,searchdata,undo);
	if (score > best){
	    // this assertion appears to fail sometimes...why?
	    ASSERT(searchdata->reduction[ply]==0);
	    best = score;
	    // pbest is historical artifact.
	    pbest_move = p->move;
	    if(score<=alpha && ply==1){
		//		MoveSeqPrependMove(pv_out,pv,p->move);
		// To have a ponder move even if we fail high at root
		pv_out->moves[0]=p->move;
		pv_out->gencnt=1;
	    }
	    if (best >= beta){
		searchstats->BetaCutCnt++;
		searchstats->BetaCutMoveCnt+=movecount;
		reason=REASON_BETA_CUTOFF;
		goto done;
	    }
	    if(best>alpha){
		MoveSeqPrependMove(pv_out,pv,p->move);
		ASSERT(search.UseTTinPV|| MATESCORE(best)|| best==DRAWSCORE || best<=savealpha || best>=beta || beta<=savealpha+1 || pv_out->gencnt>=savedepth);
	    }
	}

	if(InputLook()){
	    SearchParseInput(board,searchparams,searchdata,searchstats);
	}
	
	if(!searchparams->infinite && (searchstats->NodeCnt & TIMECHECK)==0){
	    SearchCheckTime(searchparams,searchdata,searchstats);
	}

	/*  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 (search.UseMateDistancePruning && (MATE+1 == best+(ply+1))){
	    reason=REASON_MATE_DISTANCE_PRUNING;
	    goto done;
	}
    }

#ifdef DEBUG
    ret=BoardState(board_copy);
#endif 

    if(legal_moves==0){
	if(board->in_check){
	    best=-MATE+(ply+1)-2;
	    ASSERT((side==white && ret==BOARD_BLACK_WINS)||(side==black && ret==BOARD_WHITE_WINS));
	    reason=REASON_MATE;
	    goto nomove;
	}else{
	    best=DRAWSCORE;
	    reason=REASON_STALEMATE;
	    goto nomove;
	}
    }

    if(movecount==0){
	best=Evaluate(board,
		      searchparams,
		      searchdata,
		      searchstats,
		      alpha,
		      beta);
	reason=REASON_FUT;
	goto nomove;
	
    }

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

    

    /*  Save a cutoff move inside the transposition table or else preserve the hash move  */


    if (search.UseTT){
	TTablePut (TTable, 
		   board, 
		   depth, 
		   ply, 
		   savealpha, 
		   beta, 
		   move_connected,
		   best, 
		   (best>savealpha)?pbest_move:searchdata->Hashmv[ply]); 
    }

    /*  Update history  */
    if (best > savealpha && search.UseHistory){
	HistoryGood(searchdata->history,board,pbest_move,depth);
	for(i=0;i<moves_played->gencnt;i++){
	    int move=moves_played->moves[i].move;
	    if((move & MOVEMASK) != (pbest_move & MOVEMASK)){
		HistoryBad(searchdata->history,board,move,depth);
	    }
	}
    }

    /*  Don't store captures as killers as they are tried before killers */


    if (!(pbest_move & (CAPTURE | PROMOTION)) && best > savealpha){
	if (searchdata->killer1[ply] == 0){
	    searchdata->killer1[ply] = pbest_move & MOVEMASK;
	    ASSERT(board->cboard[TOSQ(searchdata->killer1[ply])]==0);
	} else if ((pbest_move & MOVEMASK) != searchdata->killer1[ply]){
	    searchdata->killer2[ply] = pbest_move & MOVEMASK;
	    ASSERT(board->cboard[TOSQ(searchdata->killer2[ply])]==0);
	}
    }

    ASSERT(MoveIsPseudoLegal(board,pbest_move));
    *best_move_out=pbest_move;

 nomove:
    
    ASSERT(search.UseTTinPV|| MATESCORE(best)|| best==DRAWSCORE || best<=savealpha || best>=beta || beta<=savealpha+1 || pv_out->gencnt>=savedepth);
    ASSERT(best>=-MATE-1);
    ASSERT(best<=MATE+1);

    if(search.DumpTree){
	SearchDumpLine(board,searchparams,searchdata,searchstats,ply,savedepth,savealpha,savebeta,best,*best_move_out, savedumpid,reason);
    }

    
    return (best);
}

void SearchDumpLine(board_t *board, 
		    searchparams_t *searchparams,
		    searchdata_t *searchdata,
		    searchstats_t *searchstats,
		    int ply,
		    int depth,
		    int alpha,
		    int beta,
		    int best,
		    int best_move_out,
		    int dumpid,
		    int reason){
    char pv[MAXPLYDEPTH*(SANSZ+1)+1];
    char LANmv[SANSZ];    MoveToLAN(best_move_out,LANmv);
    MoveSeqToSAN(searchdata->RootBoard,searchdata->moveseq,pv);
    LogString(LogDump,"%8d (%8d) ["U64_FORMAT"] p:%2d d:%2d a:%4d b:%4d s:%5d [%3s]     %s (%s)    \n",
	      dumpid, 
	      searchdata->DumpId-dumpid,
	      board->HashKey,
	      ply,
	      depth,	      alpha,
	      beta,
	      best,
	      ReasonAsci[reason],
	      pv,
	      LANmv);
}
		    

void ShowLineUci(board_t *board, 
	    searchparams_t *searchparams, 
	    searchdata_t *searchdata, 
	    searchstats_t *searchstats,
	    int c){
    char pv[MAXPLYDEPTH*(SANSZ+1)+1];
    int nodecnt;
    int nps;
    // TODO: Mate scores
    ASSERT(MoveSeqValidate(board,searchstats->RootPVSeq));
    nodecnt=searchstats->NodeCnt+searchstats->QuiesCnt;
    searchstats->ElapsedTime=TimerElapsed(searchdata->timer);
    nps=((int)nodecnt/searchstats->ElapsedTime);
    if(c==SCORE_FAIL_LOW){
	Output("info depth %d time %d nodes %d nps %d score cp %d upperbound\n",
	       searchdata->RootDepth, 
	       (int)(1000*searchstats->ElapsedTime),
	       nodecnt,
	       nps,
	       searchstats->RootPVScore);
    }else if(c==SCORE_FAIL_HIGH){
	MoveToLAN(searchstats->RootPVSeq->moves[0],pv);
	Output("info depth %d time %d nodes %d nps %d score cp %d lowerbound pv %s\n",
	       searchdata->RootDepth, 
	       (int)(1000*searchstats->ElapsedTime),
	       nodecnt,
	       nps,
	       searchstats->RootPVScore,
	       pv);
    }else{
	MoveSeqToLAN(searchstats->RootPVSeq,pv);
	Output("info depth %d time %d nodes %d nps %d score cp %d pv %s\n",
	       searchdata->RootDepth, 
	       (int)(1000*searchstats->ElapsedTime),
	       nodecnt,
	       nps,
	       searchstats->RootPVScore,
	       pv);
    }
	   
		 
}


void ShowLine (board_t *board, 
	       searchparams_t *searchparams, 
	       searchdata_t *searchdata, 
	       searchstats_t *searchstats,
	       int c)
/*****************************************************************************
 *
 *  Print out the latest PV found during the search.
 *
 *****************************************************************************/
{
    int score, post_score;
    char SANmv[SANSZ];
    char pv[MAXPLYDEPTH*(SANSZ+1)+1];
    char *move2;


    if(searchparams->protocol==PROTOCOL_UCI){
	ShowLineUci(board, 
		    searchparams, 
		    searchdata, 
		    searchstats,
		    c);
	return;
    }

    if (!searchparams->post){
	return;
    }

    searchstats->ElapsedTime = TimerElapsed(searchdata->timer);
    MoveToSAN (board, searchstats->RootPV, SANmv);

    if(c==SCORE_PV){
	score=(int)searchstats->RootPVScore;
    }else{
	score=(int)searchdata->RootScore;
    }

    post_score=score;
    if(searchparams->ponder) post_score=-post_score;

        Output ("%d %d %d %d ", 
    	    searchdata->RootDepth, 
    	    post_score, 
    	    (int)(100*searchstats->ElapsedTime), 
    	    searchstats->NodeCnt+searchstats->QuiesCnt);
	 

    if (c == SCORE_FAIL_LOW){
	Output (" :-(\n");
	return;
    } else if (c == SCORE_FAIL_HIGH){

	if(searchparams->ponder){
	    Output (" (%s!)\n", SANmv);
	}else{
	    Output (" %s!\n", SANmv);
	}
	return;
    }

    if(searchparams->ponder){
	Output (" (%s)", SANmv);
    }else{
	Output(" %s", SANmv);
    }
    


    MoveSeqToSAN(board,searchstats->RootPVSeq,pv);
    move2=strchr(pv,' ');
    if(move2){
	Output("%s",move2);
    }

    Output ("\n");
}

