
#define VALUE_MATE				32700
#define VALUE_INF				(VALUE_MATE+1)
#define VALUE_NONE				(-VALUE_INF)
#define MATE					(-VALUE_MATE + ply) 
#define DRAW					(0)
#define VALUE_IS_MATE(val)		(ABS(val) >= VALUE_MATE - MAX_DEPTH)

#define SLOW_RATE_OF_PLAY		0
#define NORMAL_RATE_OF_PLAY		1
#define FAST_RATE_OF_PLAY		2

#define IDLE					0   //	(0)	// no search
#define SEARCHING		    (1<<0)	//	(1)	// search in progress
#define INFINITE_MODE	    (1<<1)  //	(2)	// infinite , ponder , limited 
									//(movetime, nodes, depth, mate) mode // hack: all in one
#define ALLOW_NULL_MOVE			1
#define PREVENT_NULL_MOVE		0
#define TRANS_RETRIEVED			1

#define FUTILITY_MARGIN(d)		((int)(100.0+(140.0*log(MAX(d,1.0)))))

// SearchTimer

class SearchTimer{
private:
	int last_info, last_time, start;
	static const int			info_interval = 1024,	  // was 256
								currmove_interval = 512; // was 512
	int GetTime()				{return (int)GetTickCount()														;}									
public:		
	void Restart()				{start = last_time = last_info = GetTime()										;}
	bool TimeToSendCurrmove()	{return (last_time - start > currmove_interval)									;}
	int  SearchTime()			{last_time = GetTime();		return (last_time  - start)							;}	
	bool TimeToSendInfo()		{if(last_time - last_info > info_interval) {last_info = last_time; return true	;}
								 return false																	;}	
};

// SearchData

class SearchData{
public:	
	// root moves
	Move pv[MAX_MULTIPV][MAX_DEPTH];
	uint64 pv_nodes[MAX_MULTIPV];
	uint pv_size[MAX_MULTIPV];
	int pv_time[MAX_MULTIPV];		
	int score[MAX_MULTIPV];
	int index[MAX_MULTIPV]; // we can replace score[] elements but dont replace pv[]... so we need extra index easy to sort		
	uint legal_moves;
	uint multipv;
		
	// time
	int rate_of_play,
		warning_time,
		danger_time,
		overtime;	// if we have problems in search 
					//e.g. if the best move has changed	
	// limits
	int depth_limit,
		node_limit,
		time_limit;

	// request
	int request_interval,
		nodes_to_request;

	// other
	int depth,
		status;
	uint64 nodes;
	bool bad_move;
	bool fail_high;	
	int mate_in_root;
	int root_seldepth;
	int last_scores[2];
	Move bench_move[1];
	bool root_zero_window;
	int bestmove_changes[MAX_DEPTH];	
			
	// functions	
	
	void Init() {		
		overtime = 0;			
		for(int i = 0; i < MAX_MULTIPV; i++) {
			score[i] = VALUE_NONE;
			index[i] = i; // number of pv[]
		}
	}
	SearchData() {
		Init(); 		
		status = IDLE; 
		bench_move->Clear();
		multipv = DEFAULT_MULTIPV; 
		rate_of_play = NORMAL_RATE_OF_PLAY;		
		depth_limit = node_limit = time_limit = 0;
	}	
};

// SearchOptions
// information from OptionInit() & ResetSearchOptions()
// plus some special search heuristics

class SearchOptions{
public:
	int hash,
		multipv,
		rate_of_play;
	bool chess_960,
		clear_hash,		
		ponder,
		show_curr_line;
	// "constants"
	// search	
	static const int  BAD_VALUE_TIME_MARGIN	 	= 36;	// cp (was 50)
	static const int  DEFAULT_DYNAMIC_WINDOW	= 25;
	static const int  EASY_THRESHOLD			= 150;
	static const int  LAZY_EVAL_MARGIN			= 170;	
	static const bool USE_MATE_DISTANCE_PRUNING = true;
	static const bool USE_DELTA_PRUNING			= true;
	static const bool USE_NULL_MOVE				= true; 
	static const bool DETECT_ZUGZWANG			= true;
	static const bool USE_IID					= true;
	static const bool USE_RAZORING				= true;	
	static const bool USE_FUTILITY				= true; 
	static const bool USE_LMR					= true;
	static const bool USE_LMR_RE_SEARCH			= true;
	static const bool USE_HISTORY_PRUNING		= true;
	static const bool USE_TRANS					= true;
	static const bool DISPLAY_STATISTICS		= true;
	static const bool USE_LAZY_EVAL				= false;
	static const bool USE_EVAL_PRUNING			= true;
	static const bool USE_VICTIM_DELTA_PRUNING	= true;
	static const bool USE_SECOND_HISTORY		= true;
	// killers
	static const int  KILLER_BRANCH_PLY			= 4;	// [UPPER_STACK_KILLER_NB , +INF)
	static const int  UPPER_STACK_KILLER_NB		= 2;	// how many killers we can get from ply-2 [0,KILLER_SIZE]
	static const bool USE_MATE_KILLER			= true;
	static const bool USE_KILLER				= true;
		  
	int qsearch_delta_pawn,
		qsearch_delta_minor, // knight + bishop
		qsearch_delta_rook,
		qsearch_delta_queen,
		lmr_move_count[2],
		null_move_margin,
		razor_margin;
	
	// other
	float lmr,
		lmr_depth,
		iid_depth, 
		razor_depth,		
		iid_reduction,				
		null_move_depth,
		futility_threshold,
		null_move_reduction[2],
		qsearch_check_depth[2],		
		zugzwang_verification_reduction;

	// extensions, margins
	float recapture_extension[2],
		  move_is_check_extension[2],
		  single_evasion_extension[2],		  
		  passed_pawn_advance_extension[2],	
		  tactical_move_extension[2],
		  qsearch_in_check_extension;

	SearchOptions() {
		single_evasion_extension[PV_NODE]			= 1.0;
		single_evasion_extension[NON_PV_NODE]		= 1.0;
		passed_pawn_advance_extension[PV_NODE]		= 1.0;
		passed_pawn_advance_extension[NON_PV_NODE]	= 0.0;
		recapture_extension[PV_NODE]				= 1.0;
		recapture_extension[NON_PV_NODE]			= 0.0;
		move_is_check_extension[PV_NODE]			= 1.0;
		move_is_check_extension[NON_PV_NODE]		= 0.5; 
		tactical_move_extension[PV_NODE]			= 1.0;
		tactical_move_extension[NON_PV_NODE]		= 0.0; 
		qsearch_in_check_extension					= 1.0;

		lmr											= 1.0;	
		lmr_depth									= 2.0;		
		qsearch_check_depth[PV_NODE]				= 2.0;
		qsearch_check_depth[NON_PV_NODE]			= 1.0;
		
		qsearch_delta_pawn = 220;
		qsearch_delta_minor = 450;
		qsearch_delta_rook = 650;
		qsearch_delta_queen = 1050;
		null_move_margin = 300;
		razor_margin = 300;
		lmr_move_count[NON_PV_NODE] = 4;
		lmr_move_count[PV_NODE] = 15;
		
		iid_depth = 3.0;
		razor_depth = 3.0;
		iid_reduction = 2.0;		
		null_move_depth = 3.0;
		futility_threshold = 2.0;
		null_move_reduction[0] = 3.0;
		null_move_reduction[1] = 4.0;
		hash = 0; //TRANS_DEFAULT_SIZE;
		zugzwang_verification_reduction = 4.0;		
	}
};

// SearchStack

class SearchStack{
private:	
public:	
	// eval
	EvalInfo ev_info[1];

	// search
	Move move[1];
	uint pv_size;
	int reduction;
	Move pv[MAX_DEPTH];

	// sort
	Move trans_move[1],
		mate_killer[1],
		killer[KILLER_SIZE];
	Sort sort[1];
			
	// functions	

	void PrintPV() {		
		for(int i = 0; i < pv_size; i++) {
			printf(" ");
			pv[i].Print();			
		}	printf("\n");
	}	
};

// Searcher

class Searcher {
private:
	SearchStack      (*stack)[1];
public:	
	Personality      (*person)[1];
	SearchData		 data[1];	
	SearchTimer		 timer[1];
	SearchOptions    options[1];
	History			 history[1];
	Trans            trans[1];
	
	int active_person;
	bool locked_view;
	bool view;

	// functions
	
	void RootSetData(int wtime, int btime, int depth_limit, int nodes,
				 int mate, int movetime, int ponder, int infinite);
	void RootSetTime(Board *b, int wtime, int btime, int winc,
					int binc, int movestogo, int ponder);
	void RootSearch(Board *b, int wtime, int btime, int winc, int binc, int depth_limit, int nodes,
				    int mate, int movestogo, int movetime, int ponder, int infinite, MoveList *sm);	
	int Search(Board *b, int alpha, int beta, float depth, int ply, int nullmove, int trans_retrieved = 0);	
	int QSearch(Board *b, int alpha, int beta, float check_depth, int ply);
	float NewDepth(Board *b, float depth, int ply, Move *m, bool pv_node, bool in_check, Sort *sort);
	void InitSort(Sort *sort, int ply, int in_check); 
	void UpdateKillers(int ply, Move *m);
	void UpdateMateKiller(int ply, int value, Move *m);
	void NewNode();
	int BiosKey();	
	void CheckTime();
	void CheckInput();
	void PrintMultiPV();
	void StorePV(Board *b);
	uint64 Perft(Board *b, int depth);
	void RootPerft(position_t *position);	
	bool CanUseDeltaPruning(Board *b, Move *m, int in_check, int move_is_check);
	void Benchmark(position_t *position, bool view);
			
	Searcher() {
		person = new Personality[MAX_PERSONS][1];
		stack = new SearchStack[MAX_DEPTH][1];
		for(int i = 0; i < MAX_DEPTH; i++) 
			stack[i]->pv_size = 0;
		locked_view = false;
		active_person = 0;		
#ifdef PST_TXT
		person[active_person]->ParseFile("Parameters.txt");	
#else
		person[active_person]->ParseParams();
#endif
	}	
	bool SearchStopped()  {return !data->status;} // hack: IDLE can`t be when searching
	bool CanTerminate()	  {return data->depth>1;} // else we have no bestmove to send
	bool CanFinalize()	  {return data->depth>3;} // safely than CanStop()
	bool CanUseNodes()	  {return data->depth>2;} // min depth = 3
	bool CanAddTime()	  {return data->depth>3;} // can we increase overtime?
	bool CanViewInfo()	  {return data->depth>2;} // can we print PV & currmove?
	bool CanStopBench()	  {return data->depth>8;} // best move was found in benchmark
	bool CanUseDynamic()  {return data->depth>5 
						   && data->multipv == 1;}
	sint32 RootMoveValue(int value) {return 2 * VALUE_INF * data->depth + value;}
	int RootBestValue()   {return data->score[0];}// current best root value
	void ClearPV(uint ply){stack[ply]->pv_size = 0;}
	void UpdatePV(uint ply, Move * current_move) {
		SearchStack *sl = stack[ply];			  // Stack at this Level
		SearchStack *sd = stack[ply+1];			  // Stack Deeper on 1 PLY
		sl->pv[0] = *current_move;				  // copy current move to PV	
		sl->pv_size = sd->pv_size + 1;			  // copy some pv_moves from ds		
		for(int i = 0; i < sd->pv_size; i++)   sl->pv[i+1] = sd->pv[i];		
	}
	bool UpdateRootMultipv(int value, Move * current_move) {		
		int i = data->multipv - 1;		
		if(value <= data->score[i])	return false; // move is too bad	
		if(SearchStopped() &&					  // don`t update wrong result
			data->legal_moves > 1)	return false; // exclude single move in root 
		int replace = data->index[i];			  // index of pv[] to replace
		SearchStack *sd = stack[1];				  // Stack Deeper on 1 PLY
		data->pv_nodes[replace] = data->nodes;	  // update pv_nodes[]
		data->pv_time[replace] = timer->SearchTime();// update pv_time[]
		Move *mpv = data->pv[replace];	
		mpv[0] = *current_move;					  // copy current move to multipv
		data->pv_size[replace] = sd->pv_size + 1; // set pv length
		while(i && value > data->score[i-1]) {    // hack	
			data->score[i] = data->score[i-1];    // shift elements 
			data->index[i] = data->index[i-1];
			i--;
		}
		data->score[i] = value;                   // insert our value
		data->index[i] = replace;				  // and index of pv[]
		if(i == 0) {
			UpdatePV(0, current_move);			  // update pv of stack[0] 
			data->bestmove_changes[data->depth]++;
		}										  // copy some pv_moves from sd to root PV
		for(i = 0; i < sd->pv_size; i++)  mpv[i+1] = sd->pv[i];				
		return true;
	}
	void ControlEasyMove(MoveList *rml, Move *easy_move) {
		if(data->depth - 1 == 1) {
			if(rml->value[0] - rml->value[1] >= options->EASY_THRESHOLD) 
				*easy_move = stack[0]->pv[0];
			else easy_move->Clear();
		} else if(data->depth - 1 > 1) {
			if(!easy_move->Equal(stack[0]->pv[0]))
				 easy_move->Clear();
		} else if(data->depth - 1 < 1)	easy_move->Clear();
	}
	void PrintBestMove() {		
		printf("bestmove ");
		stack[0]->pv[0].Print();				  // print bestmove and											 
		if(stack[0]->pv_size >= 2) {			  // now ponder move
			printf(" ponder ");
			stack[0]->pv[1].Print();	
		}
		printf("\n");
	}
	void InitLazyEval(SearchStack *ss, int alpha, int beta) {
		if(options->USE_LAZY_EVAL) {
			(ss+1)->ev_info->alpha = -beta - options->LAZY_EVAL_MARGIN;
			(ss+1)->ev_info->beta = -alpha + options->LAZY_EVAL_MARGIN;
		} else {
			(ss+1)->ev_info->alpha = VALUE_NONE;
			(ss+1)->ev_info->beta = VALUE_INF;
		}		
	}
	Move RootBestMove()			{return stack[0]->pv[0]			;}
	Personality *ActivePerson() {return person[active_person]	;}
};

//

void Searcher::RootSetData(int wtime, int btime, int depth_limit, int nodes,
						   int mate, int movetime, int ponder, int infinite) {
	// limits
	data->node_limit  = nodes;
	data->time_limit  = movetime;
	data->depth_limit = MAX(depth_limit, 2*mate - 1);

	// request data
	data->request_interval = nodes ? MIN(nodes, 1000) : 10000; 	
	if(DEBUG)	data->request_interval /= 10;
	data->nodes_to_request = data->request_interval;

	// infinite search
	infinite |= (ponder | data->depth_limit |  data->time_limit | data->node_limit);	
	data->status = SEARCHING | (infinite ? INFINITE_MODE : 0); 

	// other
	view = false;	
	data->nodes = 0;	
	data->mate_in_root = 0;
	data->root_seldepth = 0;
	data->last_scores[0] = 0;
	data->last_scores[1] = 0;
	data->bad_move = false;
		
	for(int i = 0; i < MAX_DEPTH; i++)	
		data->bestmove_changes[i] = -1; // hack : see UpdateMultiPV()
	stack[1]->ev_info->beta = VALUE_INF;
	stack[1]->ev_info->alpha = VALUE_NONE;	
}

//

void Searcher::RootSetTime(Board *b, int wtime, int btime, int winc, 
						   int binc, int movestogo, int ponder) {
	// init 
    double time = 0.0, inc = 0.0, reserve = 100.0,
		   danger_ratio = 8.0, ponder_ratio = 1.30,
		   danger_time, warning_time, maximum, add, tmp,		
		   rate_of_play[] = {0.043, 0.033, 0.024},	// [slow normal fast] 
		   rate_ratio = rate_of_play[data->rate_of_play],	
		   mtg = (double)movestogo;				// mtg - MovesToGo
	
	if(b->stm == WHITE) {	time += (double)wtime;	inc += (double)winc;	}
	if(b->stm == BLACK) {	time += (double)btime;	inc += (double)binc;	}

	if(mtg <= 0.0  ||  mtg > (1/rate_ratio))	  mtg = (1/rate_ratio);
	add = inc * (mtg - 1.0);
	tmp = danger_ratio * rate_ratio; // ratio 'a' in Y = aX + b 
	tmp = tmp * mtg + (1 - tmp);	 // we must have X = 1 => Y = 1

	ASSERT(add >= 0);
	ASSERT(tmp >= 1);

	warning_time = DEC_IF_RES_IS_POSITIVE((time + add) / mtg , reserve);	
	danger_time  = DEC_IF_RES_IS_POSITIVE((time + add) / tmp , reserve);
	maximum      = DEC_IF_RES_IS_POSITIVE(time * 0.90		 , reserve);

	if(ponder)							warning_time *= ponder_ratio;
	if(warning_time > maximum)			warning_time = maximum;
	if(danger_time > maximum)			danger_time = maximum;
	if(warning_time > danger_time)		warning_time = danger_time;
	if(danger_time < 8*reserve) 		data->nodes_to_request /=2;	
	if(danger_time < 4*reserve) 		data->nodes_to_request /=2;

	data->warning_time = warning_time;
	data->danger_time = danger_time;

}
//go wtime 100 btime 100 winc 0 binc 0

void Searcher::PrintMultiPV() {

	// init		
	int i, k, moves, variants, mate, sign;
	variants = MIN(data->multipv, data->legal_moves);
	
	// pv data	
	uint64 nodes;
	int score, index, time;
			
	for(i = 0; i < variants; i++) {
		score = data->score[i];
		index = data->index[i];
		
		if(score == VALUE_NONE) break; // empty pv[]
		time = data->pv_time[ index ];
		moves = data->pv_size[ index ];
		nodes = data->pv_nodes[ index ];
		
		printf("info multipv %d depth %d ", i+1, data->depth);
		if(ABS(score) < VALUE_MATE - MAX_DEPTH) {
			printf("score cp %d time %d nodes "UINT64_FORMAT" nps %d pv " , 
					score, time, nodes, nodes * 1000 / MAX(128, time));
		} else {
			sign = score / ABS(score); 			
			mate = sign * ((VALUE_MATE - ABS(score) + 1) / 2);			
			printf("score mate %d time %d nodes "UINT64_FORMAT" nps %d pv " , 
					mate, time, nodes, nodes * 1000 / MAX(128, time));
		}
		for(k = 0; k < moves; k++) 	data->pv[ index ][ k ].Print();		
		printf("\n");		
	}	
}

void Searcher::CheckInput() {

	if(BiosKey() == 0) return;

	const int string_size = 512;
	char string[string_size];
	*string = '\0';

	if(fgets(string, string_size, stdin) == NULL) 
		goto exit;
	else if(strstr(string, "quit"))
		goto exit;
	else if(strstr(string, "stop") && CanTerminate())
		data->status = IDLE;		
	else if(strstr(string, "ponderhit")) {
		ASSERT(data->status & INFINITE_MODE);
		ASSERT(data->status & SEARCHING);
		data->status = SEARCHING;
	}
	return;
exit:
	exit(EXIT_SUCCESS);
}

void Searcher::CheckTime() {

	int time = timer->SearchTime();
	if(options->DISPLAY_STATISTICS
	&& !DEBUG && view
	&& timer->TimeToSendInfo()) {
		uint64 nodes = data->nodes;
		if(options->USE_TRANS)	trans->SendInfo();
		if(DEBUG)	pawn_info[active_person].SendInfo();
		printf("info time %d nodes "UINT64_FORMAT" nps %d\n", time, nodes, nodes * 1000 / MAX(128, time));		
	}
	if(data->status == (SEARCHING | !INFINITE_MODE)) {
		// not infinite
		if(CanTerminate() && time >= data->danger_time)
			data->status = IDLE;
		if(CanFinalize()
		&& time >= (data->warning_time + data->overtime)
		&& data->root_zero_window == true
		&& data->bad_move == false
		&& data->fail_high == false)
			data->status = IDLE;
								
	} else { // infinite mode
		if(data->time_limit	&& CanTerminate() && time >= data->time_limit)			data->status = IDLE;
		if(data->node_limit && CanUseNodes()  && data->nodes >= data->node_limit)	data->status = IDLE;
	}
}

int Searcher::BiosKey() {

    HANDLE console_handle;
	bool is_console_mode,
		 is_peek_pipe;
	DWORD events_nb,
		  mode;
		  
	console_handle  = GetStdHandle(STD_INPUT_HANDLE);
	is_console_mode = GetConsoleMode(console_handle, &mode);
	if(is_console_mode) {
		mode &= ~(ENABLE_MOUSE_INPUT | ENABLE_WINDOW_INPUT);
		SetConsoleMode(console_handle, mode);
        FlushConsoleInputBuffer(console_handle);
		GetNumberOfConsoleInputEvents(console_handle, &events_nb);
		if(events_nb <= 1)	return 0;
		return events_nb;
	} else {
		is_peek_pipe = PeekNamedPipe(console_handle, NULL, 0, NULL, &mode, NULL);
		if(is_peek_pipe == 0)	return 1;
		return mode;
	}
}

void Searcher::InitSort(Sort *sort, int ply, int in_check) {
	int i;
	SearchStack *sl = stack[ply],   // stack at this level
				*su = stack[ply-2];	// stack upper
	sort->in_check = in_check;
	sort->good_capture = false;
	SearchOptions *opt = options;
	sort->use_killers = opt->USE_KILLER;

	sort->trans_move->Copy(sl->trans_move);
	sort->mate_killer->Clear();
	sort->sml->Clear();	
	if(opt->USE_MATE_KILLER)									sort->mate_killer->Copy(sl->mate_killer);				
		
	for(i = 0; i < SORT_KILLER_SIZE; i++)						sort->killer[i].Clear();		
	for(i = 0; i < KILLER_SIZE; i++)							sort->killer[i].Copy(sl->killer[i]);
	if(ply < opt->KILLER_BRANCH_PLY)							return;		
	for(i = 0; i < opt->UPPER_STACK_KILLER_NB; i++)				sort->killer[i+KILLER_SIZE].Copy(su->killer[i]);											
}

void Searcher::UpdateKillers(int ply, Move *m) {
	int i;
	SearchStack *sl = stack[ply];

	if(m->IsCapProm())	return;
	for(i = 0; i < KILLER_SIZE-1; i++)
		if(m->Equal(sl->killer[i]))
			return;
	// move is unique
	for(i = 0; i < KILLER_SIZE-1; i++)
		sl->killer[i+1] = sl->killer[i];		
	sl->killer[0].Copy(m);
}

void Searcher::UpdateMateKiller(int ply, int value, Move *m) {	
	SearchStack *sl = stack[ply];
	if(options->USE_MATE_KILLER
	&& VALUE_IS_MATE(value))
		sl->mate_killer->Copy(m);
}

void Searcher::StorePV(Board *b) {
	int i;
	Move m[1];
	Board board[1];
	undo_t undo[1];

	*board = *b;	
	const int trans_value = VALUE_NONE;
	const float trans_depth = -127;	
		
	for(i = 0; i < stack[0]->pv_size; i++) {
		*m = stack[0]->pv[i];		
		
		if(!board->MoveIsLegal(m)) {
			//for(int k = 0; k <= i; k++)		stack[0]->pv[k].Print();
			//printf("\n");
			//m->Print();
			//ASSERT(false);
			break; // TODO		
		}
		
		trans->Store(board->key, m, trans_value, trans_depth, PV_BOUND);
		if(i == stack[0]->pv_size - 1)	return;
		board->MakeMove(m, undo);
	}	
}

float Searcher::NewDepth(Board *b, float depth, int ply, Move *m, bool pv_node, bool in_check, Sort *sort) {

	depth -= 1.0;

	// single reply
	if(in_check	&& sort->evasions == 1)		return depth + options->single_evasion_extension[pv_node];	
	// move is check	
	if(b->MoveIsCheck(m, sort->discovered_rooks, sort->discovered_bishops))	{
		ASSERT(b->MoveIsCheck(m));
		return depth + options->move_is_check_extension[pv_node || b->SEE(m) >= -100];
	}
	// passed pawn advance
	if(b->MoveIsPassedPawnAdvance(m)
	&& RANK_COL(m->To(), b->stm) >= RANK_6)	return depth + options->passed_pawn_advance_extension[pv_node];
	// recapture
	Move *previous = stack[ply-1]->move;
	ASSERT(BISHOP_VALUE == KNIGHT_VALUE);
	if(m->Capture()	&& m->To() == previous->To()
	&& PIECE_VALUE(m->Capture()) == PIECE_VALUE(previous->Capture())) {
		return depth + options->recapture_extension[pv_node];
	}
	// most popular tactical moves
	if(b->MoveIsTactical(m))				return depth + options->tactical_move_extension[pv_node];	
	
	return depth;
}
