
int Searcher::Search(Board *b, int alpha, int beta, float depth, int ply, int nullmove, int trans_retrieved) {
																		 
	// init	
	int value,
		in_check,
		null_value,		
		generated = 0,
		value_type = 0,
		eval = VALUE_NONE,
		old_alpha = alpha,
		best_value = VALUE_NONE,
		optimistic_value = VALUE_NONE;
	bool pv_node = (beta - alpha) > 1, prune,
		lmr_used, extension, zero_window, test_history;		
	SearchStack *ss = stack[ply];
	Move best_move[1], m[1];		
	MoveList played[1];	
	float new_depth;
	undo_t undo[1];
	
	Sort *sort = ss->sort;
	sort->Init();

	if (depth <= 0)		return QSearch(b, alpha, beta, options->qsearch_check_depth[pv_node], ply);		
		
	if(SearchStopped())				return 0;
	if(b->Draw())					return DRAW;
	if(ply >= MAX_DEPTH-1)			return ss->ev_info->value;
	if(ply >= data->root_seldepth)	data->root_seldepth = ply;
	ClearPV(ply);
	NewNode();	

	// checks and pinned pieces
	in_check = ss->ev_info->in_check;
	sort->checkers = ss->ev_info->checkers;
	sort->pinned_rooks = ss->ev_info->pinned_rooks;
	sort->pinned_bishops = ss->ev_info->pinned_bishops;

	// mate distance pruning
	if(options->USE_MATE_DISTANCE_PRUNING) {
		int lower_bound = MATE + 2;
		int upper_bound = -MATE - 1;

		if(alpha < lower_bound
		&& b->IsMate(in_check, sort->checkers, sort->pinned_rooks, sort->pinned_bishops))
			lower_bound = MATE;
		if(lower_bound >= beta)		return lower_bound;
		if(alpha < lower_bound)		alpha = lower_bound;
		if(upper_bound <= alpha)	return upper_bound;
		if(beta > upper_bound)      beta = upper_bound;		
	}

	// transposition table
	stack[ply]->trans_move->Clear(); 

	if(options->USE_TRANS) {
		int	trans_value;
		uint8 trans_type;		
		float trans_depth;
		if(trans->Retrieve(b->key, stack[ply]->trans_move, &trans_value, &trans_depth, &trans_type))
			if(!pv_node && trans_depth >= depth) {
				if(trans_type == LOWER_BOUND && trans_value >= beta)		return trans_value;
				if(trans_type == UPPER_BOUND && trans_value <= alpha)		return trans_value;
				if(trans_type == EXACT_BOUND)								return trans_value;
			}		
	}

	eval = ss->ev_info->value;
	
	// null move pruning
	if(options->USE_NULL_MOVE
	&& nullmove == ALLOW_NULL_MOVE
	&& depth >= options->null_move_depth	
	&& !pv_node 
	&& !in_check
	&& b->CanUseNullMove()
	&& eval + options->null_move_margin >= beta) {

		// null move search
		new_depth = depth - options->null_move_reduction[depth >= options->null_move_depth + 3.0];
		b->MakeNullMove(undo);		
		b->Eval((ss+1)->ev_info, person[active_person], &pawn_info[active_person]);
		null_value = -Search(b, -beta, -beta + 1, new_depth, ply+1, PREVENT_NULL_MOVE);
		b->UnmakeNullMove(undo);

		// zugzwang verification search
		if(options->DETECT_ZUGZWANG		
		&& null_value >= beta
		&& (depth-1.0) >= options->zugzwang_verification_reduction) {
			new_depth = depth - options->zugzwang_verification_reduction;			 
			value = Search(b, alpha, beta, new_depth, ply, PREVENT_NULL_MOVE, TRANS_RETRIEVED); // use stack trans move; 
			if(value >= beta) 				return beta;			
		}
		// pruning
		if(null_value >= beta)				return beta;		

	// razoring
	} else if(options->USE_RAZORING
	&& !pv_node
	&& depth <= options->razor_depth) {
		 
		if(eval + options->razor_margin < beta) {
			float check_depth = 0.0;
			value = QSearch(b, beta-1, beta, check_depth, ply);			
			if(value < beta) 	return value;			
		}
	}	

	// Internal Iterative Deepening
	if(options->USE_IID
	&& pv_node == true
	&& !ss->trans_move->IsReal()	
	&& depth >= options->iid_depth) {

		new_depth = MIN(depth / 2.0, depth - options->iid_reduction);
		value = Search(b, alpha, beta, new_depth, ply, PREVENT_NULL_MOVE);
		if(VALUE_IS_MATE(value))	return value;
		*ss->trans_move = ss->pv[0];
	}

	best_move->Clear();	
	InitSort(sort, ply, in_check);
	sort->FindDiscovered(b);
	
	if(!in_check) {
		sort->sections  = BIT(SORT_TRANS);
		sort->sections |= BIT(SORT_MATE);
		sort->sections |= BIT(SORT_CAPTURE);
		sort->sections |= BIT(SORT_KILLER);
		sort->sections |= BIT(SORT_QUIET);
	} else {
		sort->sections  = BIT(SORT_EVASION);
	}

	while(m->Copy(sort->GetMove(b, history))) {
		generated++;
		played->Add(m);
		*ss->move = *m;
		
		// extensions
		new_depth = NewDepth(b, depth, ply, m, pv_node, in_check, sort);
		extension = (new_depth > depth - 1.0);

		// futility pruning
		if(options->USE_FUTILITY		
		&& !pv_node		
		&& !extension
		&& depth <= 6.0		
		&& !m->IsCapProm()) {

			optimistic_value = eval + FUTILITY_MARGIN(depth);			
			if(optimistic_value <= alpha) {
				best_value = MAX(optimistic_value, best_value);
				continue;
			}			
		}

		// history pruning
		test_history = false;
		if(options->USE_HISTORY_PRUNING
		&& generated >= MAX(2*depth, 2)
		&& !pv_node		
		&& !in_check
		&& !extension
		&& !m->IsCastle()
		&& !m->IsCapProm()
		&& !b->MoveIsPassedPawnAdvance(m)		
		&& history->CanPrune(m, b->stm, depth)) {
			if(generated >= 2*depth + 3)			continue;
			test_history = true;
		}

		// LMR
		lmr_used = false;
		if(options->USE_LMR
		&& depth >= options->lmr_depth
		&& generated >= options->lmr_move_count[pv_node]		
		&& !(sort->sections & BIT(SORT_KILLER))
		&& !extension
		&& !m->IsCastle()		
		&& !b->MoveIsPassedPawnAdvance(m)
		&& history->CanReduce(m, b->stm)) {
			new_depth -= options->lmr;
			lmr_used = true;
		}
			
		prune = false;
		b->MakeMove(m, undo);	
		InitLazyEval(ss, alpha, beta);		
		b->Eval((ss+1)->ev_info, person[active_person], &pawn_info[active_person]);	

		// second (victim) history pruning // TUNE ME
		if(options->USE_SECOND_HISTORY
		&& test_history) {
			int pvd_old, pvd_new, vd_old, vd_new;
			vd_old = ss->ev_info->pure_victim_delta;
			pvd_old = ss->ev_info->pawn_victim_delta;
			vd_new = (ss+1)->ev_info->pure_victim_delta;
			pvd_new = (ss+1)->ev_info->pawn_victim_delta;

			// mover does not attack any new opponent's piece (all pieces & pawns separated)
			if(!((vd_new - vd_old) * sign[b->stm^1] >= 1)
			&& !((pvd_new - pvd_old) * sign[b->stm^1] >= 1))
				prune = true;			
		}

		// eval pruning
		int eval_delta = (ss+1)->ev_info->value + best_value;
		if(options->USE_EVAL_PRUNING
		&& !pv_node		
		&& !in_check
		&& !extension
		&& depth <= 4.0
		&& !m->IsCapProm()
		&& generated >= depth + 2
		&& !b->MoveIsPassedPawnAdvance(m)) {
			if(m->Piece() == KING) {
				if(eval_delta >= 90)	prune = true;
			} else if(m->Piece() == PAWN) {
				if(eval_delta >= 150)	prune = true;
			} else {
				if(eval_delta >= 110)	prune = true;
			}			
		}
		
		// victim delta pruning		
		if(options->USE_VICTIM_DELTA_PRUNING
		&& !prune
		&& !pv_node		
		&& !in_check
		&& !extension
		&& depth <= 3.0
		&& !m->IsCapProm()
		&& generated >= depth
		&& !ss->ev_info->lazy_used
		&& !(ss+1)->ev_info->lazy_used
		&& !b->MoveIsPassedPawnAdvance(m)) {
			// initialize victims block
			int pvd_old, pvd_new, vd_old, vd_new;
			vd_old = ss->ev_info->pure_victim_delta;
			pvd_old = ss->ev_info->pawn_victim_delta;
			vd_new = (ss+1)->ev_info->pure_victim_delta;
			pvd_new = (ss+1)->ev_info->pawn_victim_delta;			
			// we put our piece under attack
			if((vd_new - vd_old) * sign[b->stm^1] < 0)											prune = true;
			// we put our pawn under attack (we don't have attacked pieces)
			else if(((pvd_new - pvd_old) * sign[b->stm^1] < 0) 
				 && !(ss->ev_info->victims[b->stm] & ~b->piece[PAWN]) && depth <= 2)			prune = true;
		}

		if(prune) {
			b->UnmakeMove(m, undo);			
			continue;
		}

		zero_window = pv_node && (generated > 1);
		if(zero_window) {
			value = -Search(b, -alpha-1, -alpha, new_depth, ply+1, ALLOW_NULL_MOVE);
			if(value > alpha && value < beta)	zero_window = false;
		}
		if(zero_window == false) {
			value = -Search(b, -beta, -alpha, new_depth, ply+1, ALLOW_NULL_MOVE);
		}

		// LMR re-search
		if(options->USE_LMR_RE_SEARCH
		&& options->USE_LMR
		&& lmr_used
		&& value > alpha)
			value = -Search(b, -beta, -alpha, new_depth + options->lmr, ply+1, ALLOW_NULL_MOVE);

		b->UnmakeMove(m, undo);
		
		if (value > best_value) {
			best_value = value;
			*best_move = *m;
			UpdatePV(ply, m);
			if (value > alpha) {				
				alpha = value;					
				if (value >= beta) 
					break;
            }
        }
	}

	if(SearchStopped())	return 0;
	if(!generated) {
		if(in_check)	return MATE;
		else			return DRAW;
	}
		
	if(best_value >= beta) {
		UpdateKillers(ply, m);
		value_type = LOWER_BOUND;		
		UpdateMateKiller(ply, value, m);
		history->GoodMove(m, b->stm, depth);
		for(int i = 0; i < played->Size()-1; i++)
			history->BadMove(played->move[i], b->stm);		
	}
	else if(best_value <= old_alpha)	value_type = UPPER_BOUND;
	else if(pv_node)					value_type = EXACT_BOUND;
	else ASSERT(false);

	if(options->USE_TRANS) 
		trans->Store(b->key, best_move, best_value, depth, value_type);	

	return alpha;	
}

int Searcher::QSearch(Board *b, int alpha, int beta, float check_depth, int ply) {

	SearchStack *ss = stack[ply];
	int search_checks,
		best_value,
		in_check,
		value;
	Move m[1];	
	undo_t undo[1];		
	uint generated;
	ClearPV(ply);
	NewNode();

	Sort *sort = ss->sort;
	sort->Init();
	
	if(SearchStopped())		return 0;
	if(b->Draw())			return DRAW;
	if(ply >= MAX_DEPTH-1)	return ss->ev_info->value;
	if(ply >= data->root_seldepth) data->root_seldepth = ply;

	// checks and pinned pieces
	in_check = ss->ev_info->in_check;
	sort->checkers = ss->ev_info->checkers;
	sort->pinned_rooks = ss->ev_info->pinned_rooks;
	sort->pinned_bishops = ss->ev_info->pinned_bishops;

	if(options->USE_MATE_DISTANCE_PRUNING) {
		int lower_bound = MATE + 2;
		int upper_bound = -MATE - 1;

		if(alpha < lower_bound
		&& b->IsMate(in_check, sort->checkers, sort->pinned_rooks, sort->pinned_bishops))
			lower_bound = MATE;
		if(lower_bound >= beta)		return lower_bound;
		if(alpha < lower_bound)		alpha = lower_bound;
		if(upper_bound <= alpha)    return upper_bound;
		if(beta > upper_bound)      beta = upper_bound;		
	}

	value = ss->ev_info->value;
					
	if(!in_check) {
		if(value >= beta) return value;
		if(value > alpha) alpha = value;

		// delta pruning
		if(options->USE_DELTA_PRUNING) {
			if(options->qsearch_delta_pawn <= alpha - value) {
				sort->capture_mask ^= (b->piece[PAWN] & PromoteSafeSquares[b->stm]); // except promotions and their threat
				if(options->qsearch_delta_minor <= alpha - value) {
					sort->capture_mask ^= (b->piece[KNIGHT]|b->piece[BISHOP]);
					if(options->qsearch_delta_rook <= alpha - value) {
						sort->capture_mask ^= b->piece[ROOK];
						if(options->qsearch_delta_queen <= alpha - value) {
							sort->capture_mask ^= b->piece[QUEEN];
						}
					}
				}
			}
		}
		best_value = value;
	} else {
		check_depth += options->qsearch_in_check_extension;
		best_value = VALUE_NONE;
	}
	search_checks = (check_depth >= 1.0) && !in_check;
	generated = 0; // we have no generated moves

	// sort init	
	if(!in_check) {		
		sort->sections = BIT(SORT_CAPTURE);
		if(search_checks)	sort->sections |= BIT(SORT_CHECK);		
	} else {
		sort->sections = BIT(SORT_EVASION);
		sort->in_check = in_check;
	}	
			
	while(m->Copy(sort->GetMoveQs(b, history))) {
		generated++;						

		b->MakeMove(m, undo);
		InitLazyEval(ss, alpha, beta);
		b->Eval((ss+1)->ev_info, person[active_person], &pawn_info[active_person]);
		value =  -QSearch(b, -beta, -alpha, check_depth - 1.0, ply+1);		
		b->UnmakeMove(m, undo);
		
		if (value > best_value) {
			best_value = value;	
			UpdatePV(ply, m);
			if (value > alpha) {				
				alpha = value;						
				if (value >= beta)    return beta; 			
            }
        }
	}

	if(!generated && in_check) 		return MATE;	
	return alpha;
}

uint64 Searcher::Perft(Board *b, int depth) {

	int new_depth = depth - 1;
	uint64 move_nb = 0;	
	MoveList ml[1];
	undo_t undo[1];
	int i;

	b->GenLegalMoves(ml);	
	for(i = ml->Size()-1; i >= 0; i--) {
		b->MakeMove(ml->move[i], undo);
		
		if(new_depth == 0)	move_nb += 1;
		else move_nb += Perft(b, new_depth);

		b->UnmakeMove(ml->move[i], undo);
	}	
	return move_nb;
}

void Searcher::NewNode() {
	data->nodes++;
	if(data->nodes_to_request-- <= 0) {
		data->nodes_to_request = data->request_interval;
		CheckInput();
		CheckTime();
	}
}

bool Searcher::CanUseDeltaPruning(Board *b, Move *m, int in_check, int move_is_check) {	
	if(move_is_check)								return false;
	if(in_check)									return false;
	
	// init
	BitBoard pawn_can_prom_co[] = {Rank_6 | Rank_7, Rank_2 | Rank_3};
	uint8 stm = b->stm;
	BitBoard to = BIT(m->To());

	if(m->Piece() == PAWN) {
		if(m->IsPromote())							return false;		
		if(to & pawn_can_prom_co[stm])				return false;
	}	
	switch(m->Capture()) {
		case PAWN: if(to & pawn_can_prom_co[stm^1]) return false;
		case QUEEN:									return false;	
		case ROOK: if(m->Piece() == PAWN)			return false;		
	}
	if(CountBits(b->occupied_by[stm]) <= 3)			return false; //  = 1 (king) + 2
	if(CountBits(b->occupied_by[stm^1]) <= 3)		return false;

	return true;
}

bool Board::CanUseNullMove() {
	BitBoard non_pawn_material = piece[BISHOP] | piece[KNIGHT] | piece[QUEEN] | piece[ROOK];		
	if(non_pawn_material & Occupied(stm))	return true;
	return false;
}

bool Board::IsMate(uint in_check, BitBoard checkers, BitBoard pinned_rooks, BitBoard pinned_bishops) {

	if(!in_check)	return false;
	MoveList eml[1]; // evasions
	GenEvasions(eml, pinned_rooks, pinned_bishops, checkers, in_check);
	return eml->Size() == 0; // in check and no evasions => mate
}

bool Board::MoveIsCheck(Move *m) {

	undo_t undo[1];
	MakeMove(m, undo);
	bool is_check = InCheck();
	UnmakeMove(m, undo);
	
	if(true && DEBUG) {
		BitBoard dr, db;
		FindDiscovered(&dr, &db);
		if(is_check != MoveIsCheck(m, dr, db)) {
			Print();
			m->Print();
			ASSERT(false);
			MoveIsCheck(m, dr, db);
		}
	}

	return is_check;
}

bool Board::MoveIsCheck(Move *m, BitBoard discovered_rooks, BitBoard discovered_bishops) {
	
	uint from = m->From(), to = m->To(), opp_king = ksq[stm^1], pc, tmp=0;
	BitBoard discovered = discovered_rooks | discovered_bishops, to_bit, from_bit, king_bit;
	pc = type[from];
	to_bit = BIT(to);
	from_bit = BIT(from);
	king_bit = BIT(opp_king);
	bool is_check = false;

	ASSERT(Occupied(stm) & BIT(from));

	if(pc == PAWN) {		
		if(Pawn[stm^1][opp_king] & to_bit)		return true;		// direct check
		if((from_bit & discovered_bishops)
		&& !(to_bit & discovered_bishops))		return true;		// discovered check (2nd rank excludes ep captures)
		if((from_bit & discovered_rooks)
		&& !(to_bit & discovered_rooks))		return true;		// discovered check
		if(m->IsPromote()) {										// promotion
			occupied_rl90 ^= BIT_L90(from);
			occupied_rl45 ^= BIT_L45(from);
			occupied_rr45 ^= BIT_R45(from);
			switch(m->Promote()) {
				case PROM_QUEEN:	is_check = (QUEEN_ATT(to) & king_bit) != 0;		break;
				case PROM_KNIGHT:	is_check = (KNIGHT_ATT(to) & king_bit) != 0;	break;
				case PROM_ROOK:		is_check = (ROOK_ATT(to) & king_bit) != 0;		break;
				case PROM_BISHOP:	is_check = (BISHOP_ATT(to) & king_bit) != 0;	break;
			}
			occupied_rl90 ^= BIT_L90(from);
			occupied_rl45 ^= BIT_L45(from);
			occupied_rr45 ^= BIT_R45(from);
			return is_check;
		} else if(m->IsEnPassant()) {
			uint cap_sq = to-8*sign[stm];
			occupied_rl90 ^= BIT_L90(from);
			occupied ^= from_bit | BIT(cap_sq);			
			occupied_rl45 ^= BIT_L45(from) | BIT_L45(to) | BIT_L45(cap_sq);
			occupied_rr45 ^= BIT_R45(from) | BIT_R45(to) | BIT_R45(cap_sq);
			is_check = ((ROOK_ATT(opp_king) & (piece[ROOK]|piece[QUEEN]) & Occupied(stm)) != 0)
					|| ((BISHOP_ATT(opp_king) & (piece[BISHOP]|piece[QUEEN]) & Occupied(stm)) != 0);			
			occupied_rl90 ^= BIT_L90(from);
			occupied ^= from_bit | BIT(cap_sq);			
			occupied_rl45 ^= BIT_L45(from) | BIT_L45(to) | BIT_L45(cap_sq);
			occupied_rr45 ^= BIT_R45(from) | BIT_R45(to) | BIT_R45(cap_sq);			
			return is_check;
		}
	} else if(pc == KNIGHT) {
		if(from_bit & discovered)				return true;
		if(to_bit & KNIGHT_ATT(opp_king))		return true;
	} else if(pc == BISHOP) {
		if(from_bit & discovered_rooks)			return true;		// discovered check
		if(to_bit & BISHOP_ATT(opp_king))		return true;		// direct check		
	} else if(pc == ROOK) {
		if(from_bit & discovered_bishops)		return true;		// discovered check
		if(to_bit & ROOK_ATT(opp_king))			return true;		// direct check		
	} else if(pc == QUEEN) {
		if(to_bit & QUEEN_ATT(opp_king))		return true;
	} else {
		ASSERT(pc == KING);		
		if((from_bit & discovered_rooks)
		&& !(to_bit & discovered_rooks))		return true;		// discovered check
		if((from_bit & discovered_bishops)
		&& !(to_bit & discovered_bishops))		return true;		// discovered check
		if(m->IsCastle()) {
			switch(to) {
				case g1: tmp = f1; king_bit = F1;	break;
				case g8: tmp = f8; king_bit = F8;	break;
				case c1: tmp = d1; king_bit = D1;	break;					
				case c8: tmp = d8; king_bit = D8;	break;					
			}
			if(king_bit & discovered_rooks)		return true;
			return (ATT_FILE(opp_king, occupied_rl90) & BIT(tmp)) != 0;
		}
	}

	return false;	
}

bool Board::MoveIsTactical(Move *m) {

	uint from = m->From(), to = m->To(), cap = m->Capture(), opp_king = ksq[stm^1];	
	uint pc = type[from], mob;

	if(pc == PAWN || pc == KING || pc == QUEEN) {
		// pawn endgame
		if(cap >= KNIGHT
		&& !((piece[KNIGHT]|piece[BISHOP]|piece[ROOK]|piece[QUEEN]) & ~BIT(to)))		return true;
		// queen endgame & open king
		if(cap >= KNIGHT
		&& !((piece[KNIGHT]|piece[BISHOP]|piece[ROOK]) & ~BIT(to))
		&& (piece[QUEEN] & Occupied(stm^1) & ~BIT(to))) {
			mob = CountBits(QUEEN_ATT(ksq[stm]));
			if(mob >= 10)																return true;
		}		
		// pawn storm in middlegame
		if(pc == PAWN		
		&& (piece[KING] & LeftSide)
		&& (piece[KING] & RightSide)
		&& (RANK_COL(to, stm) >= RANK_5)
		&& Pawn[stm][to] & Occupied(stm^1)
		&& piece[QUEEN]	&& piece[ROOK]) {
			if((BIT(to) & (LeftSide & ~FileD))
			&& (piece[KING] & Occupied(stm^1) & LeftSide)
			&& SEE(m) >= 0)																return true; 
			if((BIT(to) & (RightSide & ~FileE))
			&& (piece[KING] & Occupied(stm^1) & RightSide)
			&& SEE(m) >= 0)																return true;
		}
	} 
	if(pc == ROOK || pc == QUEEN) {	
		// two more rooks in a file close to opp's king
		if((FILE_BB(to) & (piece[ROOK]|piece[QUEEN]) & Occupied(stm) & FriendlySide[stm] & ~BIT(from))
		&& File(from) != File(to)
		&& !(FILE_BB(to) & (piece[PAWN]|piece[KNIGHT]|piece[BISHOP]))		
		&& (piece[KING] & Occupied(stm^1) & (CONTACT_FILES_BB(to)|FILE_BB(to)))
		&& SEE(m) >= 0)																	return true;						
	}
	
	return false;
}