
// RootSearch()

void Searcher::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 *rml) {
																						// root move list
	// init
	const int ASP_WINDOW_NB = 4;
	int alpha, beta, value,	i, k,
		dynamic_window, ext;	
	Move *current_move;
	Move easy_move[1];	
	undo_t undo[1];
	
	timer->Restart();
	history->Clear();
	trans->NewSearch();
	
    // work with strings
	RootSetData(wtime, btime, depth_limit, nodes, mate, movetime, ponder, infinite);
	RootSetTime(b, wtime, btime, winc, binc, movestogo, ponder);

	if(rml->Size() == 0)
		b->GenLegalMoves(rml);
	data->legal_moves = rml->Size();
	if(!data->depth_limit)	
		data->depth_limit = MAX_DEPTH;

	stack[0]->ev_info->beta = VALUE_INF;
	stack[0]->ev_info->alpha = VALUE_NONE;
	b->Eval(stack[0]->ev_info, person[active_person], &pawn_info[active_person]);

	// iterative deepening

	for(data->depth = 1; data->depth < data->depth_limit; data->depth++) {	
		data->Init();
		beta = VALUE_INF;
		alpha = -VALUE_INF; 		
		rml->InsertSort(SORT_ALL);
		ControlEasyMove(rml, easy_move);
				
		if(CanViewInfo() && !locked_view)	view = true;

		if(view) {
			printf("info depth %d\n", data->depth);		
			printf("info seldepth %d\n", data->root_seldepth);
			printf("info time %d\n", timer->SearchTime());
		}
		for(i = 0; i < data->legal_moves; i++) {

			current_move = *rml->move + i;

			ext = 0; // extension
			if(b->MoveIsCheck(current_move))				ext = 1;
			else if(b->MoveIsTactical(current_move))		ext = 1;

			b->MakeMove(current_move, undo);
			InitLazyEval(stack[0], alpha, beta);	
			b->Eval(stack[1]->ev_info, person[active_person], &pawn_info[active_person]);
						
			if((timer->TimeToSendCurrmove() || DEBUG) && view) {
				printf("info currmove ");
				current_move->Print();
				printf("currmovenumber %d\n", i+1);
			}
			
			data->fail_high = false;
			data->root_zero_window = false;	  // [alpha, beta]
			if((data->depth > 1) && (i >= data->multipv))	data->root_zero_window = true;
			
			if(!data->root_zero_window) { // pv_moves				
				if(CanUseDynamic()) {
					dynamic_window = 3 * ABS(data->last_scores[1] - data->last_scores[0]);
					dynamic_window = MAX(dynamic_window, options->DEFAULT_DYNAMIC_WINDOW);
				} else {
					dynamic_window = 2*VALUE_INF;
				}				
				for(k = 0; k <= ASP_WINDOW_NB; k++, dynamic_window *= 2) {
					ASSERT(dynamic_window >= options->DEFAULT_DYNAMIC_WINDOW);					
					if(k == 1 && !VALUE_IS_MATE(value) && !SearchStopped() && view) {	// output
						printf("info depth %d score cp %d %s pv ", data->depth, value, value <= alpha ? "upperbound" : "lowerbound");
						current_move->PrintN();
						ASSERT(value <= alpha || value >= beta);
					}
					if(k >= ASP_WINDOW_NB)										{dynamic_window = 2*VALUE_INF ;}
					if(k >= ASP_WINDOW_NB/2
					&& !(b->piece[BISHOP]|b->piece[ROOK]|b->piece[QUEEN]))		{dynamic_window = 2*VALUE_INF ;}
					if(value <= alpha || k == 0 || k >= ASP_WINDOW_NB)			alpha = MAX(-VALUE_INF, data->last_scores[1] - dynamic_window);	
					if(value >= beta  || k == 0 || k >= ASP_WINDOW_NB)			beta = MIN(VALUE_INF, data->last_scores[1] + dynamic_window);
					
					value = -Search(b, -beta, -alpha, float(data->depth + ext - 1), 1, ALLOW_NULL_MOVE);
					if((value > alpha) && (value < beta))		break;
					ASSERT(k < ASP_WINDOW_NB);
				}
				ASSERT((value > alpha) && (value < beta));
				rml->value[i] = RootMoveValue(value);
			} else {
				value = -Search(b, -alpha-1, -alpha, float(data->depth + ext - 1), 1, ALLOW_NULL_MOVE);
				if(value > alpha && value < beta) {
					data->fail_high = true;										
					value = -Search(b, -beta, -alpha, float(data->depth + ext - 1), 1, ALLOW_NULL_MOVE);
					rml->value[i] = RootMoveValue(value);
				} else 
					value = VALUE_NONE; // hack	: don`t update multipv
			}						
			b->UnmakeMove(current_move, undo);			
			
			if(UpdateRootMultipv(value, current_move) && view)		PrintMultiPV();	
			if(value > alpha)										alpha = value;
			if(CanFinalize())										CheckInput();
			if(SearchStopped())										return;			
		}
		if(VALUE_IS_MATE(RootBestValue()))	data->mate_in_root += data->depth;

		// Store PV to trans:
		if(options->USE_TRANS)				StorePV(b);
		
		// overtime
		data->last_scores[0] = data->last_scores[1];
		data->last_scores[1] = RootBestValue();
		if(CanAddTime()) {
			data->overtime = data->overtime * 30/100;
			data->overtime += data->bestmove_changes[data->depth] * data->warning_time * 30/100 ;

			if(data->last_scores[1] + options->BAD_VALUE_TIME_MARGIN < data->last_scores[0]) {
				data->overtime += data->warning_time * 200/100 ;
				data->bad_move = true;
			} else {
				data->bad_move = false;
			}
		}	
		
		//	Stop search if:

		if(data->status == (SEARCHING | !INFINITE_MODE) && CanFinalize()) {
			// we found mate
			if(data->mate_in_root > 6)	return;
			// only one legal move
			if(data->legal_moves == 1)  return;	
			// we have no time to start new iteration
			if(timer->SearchTime() > (data->warning_time + data->overtime) * 60/100)	 return;
			// first move so easy
			if(easy_move->IsReal() && timer->SearchTime() > data->warning_time * 10/100) return;
		// special case: benchmark mode
		} else if(CanStopBench() && stack[0]->pv[0].Equal(data->bench_move))			 return;
			
		// debug
		// ASSERT(data->bestmove_changes[data->depth] >= 0);	
		ASSERT(stack[0]->pv[0].IsReal());
	}
	// special cases
	if(data->depth >= MAX_DEPTH
	&& data->status & INFINITE_MODE
	&& !data->node_limit) {	
		const int string_size = 65536;
		char string[string_size];
		for(EVER) {
			if(!fgets(string, string_size, stdin))		{return				;}
			else if(strstr(string, "ponderhit"))		{return				;}		    
	        else if(strstr(string, "stop"))				{return				;}
			else if(strstr(string, "quit"))				{exit(EXIT_SUCCESS) ;}
		}
	}		
}

void Searcher::RootPerft(position_t *position) {

	int i,
		time;		
	Board b[1];
	uint64 nodes;	
	position_t *pos;
	int full_time = 0;
		
	for(pos = &position[0]; pos->fen != 0; pos++) {
		b->FromFEN(pos->fen);

		printf(" %s\n", pos->fen);
		for(i = 1; i <= pos->depth; i++) {
			timer->Restart();
			nodes = Perft(b, i);
			time = timer->SearchTime();			
			if(time < 1)	time = 1;
			printf("%2d %8d   ", i, time);
			printf("%8.2f    ", (double)nodes / (double)time);
			printf(UINT64_FORMAT"\n", nodes);		
		}	
		printf("\n");
		full_time += time;
	}	
	printf(" time: %d\n", full_time);
}