//   GreKo chess engine
//   (c) 2002-2021 Vladimir Medvedev <vrm@bk.ru>
//   http://greko.su

#include "eval.h"
#include "learn.h"
#include "moves.h"
#include "notation.h"
#include "search.h"
#include "utils.h"

extern Position g_pos;
extern deque<string> g_queue;
extern bool g_console;
extern bool g_xboard;
extern bool g_uci;

SearchParams g_searchParams;
SearchResults g_searchResults;
SearchContext g_searchContext;

int NUM_THREADS = 1;
SearchThread g_threads[MAX_NUM_THREADS];

static HashEntry* g_hash = NULL;
static size_t g_hashSize = 0;
static U64 g_hashMask = 0;

enum
{
	SORT_HASH        = 6000000,
	SORT_CAPTURE     = 5000000,
	SORT_MATE_KILLER = 4000000,
	SORT_KILLER      = 3000000,
	SORT_REFUTATION  = 2000000,
	SORT_MAX_HISTORY = 1000000,
	SORT_OTHER       = 0
};

enum
{
	NODE_PV = 0,
	NODE_NON_PV = 1
};

const EVAL WINDOW_ROOT = 100;

const int USE_FUTILITY[]                = { 0, 1 };
const int USE_NULLMOVE[]                = { 0, 1 };
const int USE_LMR[]                     = { 0, 1 };
const int USE_PAWN_7TH_EXTENSIONS[]     = { 1, 1 };
const int USE_RECAPTURE_EXTENSIONS[]    = { 1, 1 };
const int USE_SINGLE_REPLY_EXTENSIONS[] = { 1, 1 };
const int USE_IID[]                     = { 1, 1 };
const int USE_SEE_PRUNING[]             = { 1, 1 };
const int USE_MATE_PRUNING[]            = { 1, 1 };
const int USE_HASH_EXACT_EVAL[]         = { 1, 1 };
const int USE_HASH_PRUNING[]            = { 1, 1 };
const int USE_QCHECKS[]                 = { 1, 1 };

const EVAL FUTILITY_MARGIN_ALPHA[] = { 0, 50, 350, 550 };
const EVAL FUTILITY_MARGIN_BETA[]  = { 0, 50, 350, 550 };

const int NULLMOVE_MIN_DEPTH = 2;
const int NULLMOVE_BASE_R = 3;
const FP_TYPE NULLMOVE_DEPTH_DIVISOR = 6.0;
const FP_TYPE NULLMOVE_EVAL_DIVISOR = 120.0;

const int LMR_MIN_DEPTH = 4;
const int LMR_MIN_MOVE = 3;
const FP_TYPE LMR_DEPTH_DIVISOR = 10.0;
const FP_TYPE LMR_MOVE_DIVISOR = 10.0;
const int LMR_MAX_SUCCESS_RATE = 50;

const int SEE_PRUNING_MIN_QPLY = 0;

U64        CurrentSearchTime();
HashEntry* ProbeHash(const Position& pos);
void       RecordHash(const Position& pos, Move mv, EVAL score, int depth, int ply, U8 hashType);

void SearchThread::Start(int depth)
{
#ifndef SINGLE_THREAD
	m_run = true;
	m_thread = std::thread(&SearchThread::HelperProc, this, depth);
#endif
}
////////////////////////////////////////////////////////////////////////////////

void SearchThread::HelperProc(int startDepth)
{
	for (int depth = startDepth; depth < MAX_PLY; ++depth)
	{
		AlphaBeta(-INFINITY_SCORE, INFINITY_SCORE, depth, 0);
		if (!m_run)
			break;
	}
}
////////////////////////////////////////////////////////////////////////////////

void SearchThread::Stop()
{
#ifndef SINGLE_THREAD
	m_run = false;
	if (m_thread.joinable())
		m_thread.join();
#endif
}
////////////////////////////////////////////////////////////////////////////////

bool SearchThread::IsTerminated() const
{
	if (g_searchContext.terminated)
		return true;
	else if (m_id != 0 && !m_run)
		return true;
	else
		return false;
}
////////////////////////////////////////////////////////////////////////////////

EVAL SearchThread::AlphaBeta(
	const EVAL alpha,
	const EVAL beta,
	const int depth,
	const int ply)
{
	if (ply > MAX_PLY)
		return alpha;

	m_pvs[ply].clear();

	CheckLimits();
	CheckInput();

	if (IsTerminated())
		return alpha;

	if (ply > 0 && m_pos.Repetitions() >= 2)
		return DRAW_SCORE;

	int nodeType = (beta - alpha > 1)? NODE_PV : NODE_NON_PV;
	if (USE_MATE_PRUNING[nodeType])
	{
		if (alpha >= CHECKMATE_SCORE - ply)
			return alpha;
	}

	//
	//   PROBING HASH
	//

	Move hashMove;
	HashEntry* pEntry = ProbeHash(m_pos);

	if (pEntry != NULL)
	{
		hashMove = pEntry->GetMove();
		if (pEntry->GetDepth() >= depth && ply > 0)
		{
			EVAL hashScore = pEntry->GetScore(ply);
			if (USE_HASH_EXACT_EVAL[nodeType] && pEntry->GetType() == HASH_EXACT)
				return hashScore;
			if (USE_HASH_PRUNING[nodeType])
			{
				if (pEntry->GetType() == HASH_ALPHA && hashScore <= alpha)
					return alpha;
				if (pEntry->GetType() == HASH_BETA && hashScore >= beta)
					return beta;
			}
		}
	}

	COLOR side = m_pos.Side();
	Move lastMove = m_pos.LastMove();
	bool inCheck = m_pos.InCheck();
	bool isNull = lastMove.IsNull();
	Move bestMove;
	EVAL score = alpha;
	U8 hashType = HASH_ALPHA;

	//
	//   QSEARCH
	//

	if (!inCheck && depth <= 0)
		return AlphaBetaQ(alpha, beta, ply, 0);

	//
	//   FUTILITY
	//

	EVAL staticScore = Evaluate(m_pos);

	if (USE_FUTILITY[nodeType] &&
		!inCheck &&
		!isNull &&
		depth >= 1 &&
		depth <= 3)
	{
		if (staticScore <= alpha - FUTILITY_MARGIN_ALPHA[depth])
			return AlphaBetaQ(alpha, beta, ply, 0);
		if (staticScore >= beta + FUTILITY_MARGIN_BETA[depth])
			return beta;
	}

	//
	//   NULLMOVE
	//

	if (USE_NULLMOVE[nodeType] &&
		!inCheck &&
		!isNull &&
		m_pos.MatIndex(side) > 0 &&
		depth >= NULLMOVE_MIN_DEPTH)
	{
		int R = static_cast<int>(
			NULLMOVE_BASE_R +
			(depth - NULLMOVE_MIN_DEPTH) / NULLMOVE_DEPTH_DIVISOR +
			std::max(0, staticScore - beta) / NULLMOVE_EVAL_DIVISOR);

		m_pos.MakeNullMove();
		EVAL nullScore = -AlphaBeta(-beta, -score, depth - 1 - R, ply + 1);
		m_pos.UnmakeNullMove();

		if (IsTerminated())
			return alpha;

		if (nullScore >= beta)
			return beta;
	}

	//
	//   IID
	//

	if (USE_IID[nodeType] && hashMove.IsNull() && depth > 4)
	{
		AlphaBeta(alpha, beta, depth - 4, ply);
		if (!m_pvs[ply].empty())
			hashMove = m_pvs[ply][0];
	}

	MoveList& mvlist = m_mvlists[ply];
	if (inCheck)
		GenMovesInCheck(m_pos, mvlist);
	else
		GenAllMoves(m_pos, mvlist);
	UpdateSortScores(mvlist, hashMove, ply, lastMove);

	bool singleReply = false;
	if (USE_SINGLE_REPLY_EXTENSIONS[nodeType])
	{
		int numReplies = 0;
		for (size_t i = 0; i < mvlist.Size(); ++i)
		{
			Move mv = mvlist[i].m_mv;
			if (m_pos.MakeMove(mv))
			{
				m_pos.UnmakeMove();
				if (++numReplies > 1)
					break;
			}
		}
		singleReply = (numReplies == 1);
	}

	int legalMoves = 0;
	int quietMoves = 0;
	int deltaHist = 1;

	for (size_t i = 0; i < mvlist.Size(); ++i)
	{
		Move mv = GetNextBest(mvlist, i);
		if (m_pos.MakeMove(mv))
		{
			++m_nodes;
			++legalMoves;

			m_histTry[mv.To()][mv.Piece()] += deltaHist;

			if (m_id == 0 && ply == 0 && g_uci && CurrentSearchTime() > 1000)
				cout << "info currmove " << MoveToStrLong(mv) << " currmovenumber " << legalMoves << endl;

			int newDepth = depth - 1;

			//
			//   EXTENSIONS
			//

			if (inCheck)
				++newDepth;

			if (ply + depth <= 2 * g_searchContext.currentIteration)
			{
				if (USE_PAWN_7TH_EXTENSIONS[nodeType])
				{
					if (mv.Piece() == PW && Row(mv.To()) == 1)
						++newDepth;
					else if (mv.Piece() == PB && Row(mv.To()) == 6)
						++newDepth;
				}
				else if (USE_RECAPTURE_EXTENSIONS[nodeType])
				{
					if (mv.To() == lastMove.To() &&
						mv.Captured() != NOPIECE &&
						lastMove.Captured() != NOPIECE)
					{
						++newDepth;
					}
				}
				else if (USE_SINGLE_REPLY_EXTENSIONS[nodeType])
				{
					if (singleReply)
						++newDepth;
				}
			}

			//
			//   LMR
			//

			int reduction = 0;
			if (USE_LMR[nodeType] &&
				depth >= LMR_MIN_DEPTH &&
				!isNull &&
				!inCheck &&
				!m_pos.InCheck() &&
				!mv.Captured() &&
				!mv.Promotion() &&
				SuccessRate(mv) <= LMR_MAX_SUCCESS_RATE)
			{
				++quietMoves;
				if (quietMoves >= LMR_MIN_MOVE)
				{
					reduction = static_cast<int>(
						1 +
						(depth - LMR_MIN_DEPTH) / LMR_DEPTH_DIVISOR +
						(quietMoves - LMR_MIN_MOVE) / LMR_MOVE_DIVISOR);
				}
			}

			EVAL e;
			if (legalMoves == 1)
				e = -AlphaBeta(-beta, -score, newDepth, ply + 1);
			else
			{
				e = -AlphaBeta(-score - 1, -score, newDepth - reduction, ply + 1);
				if (e > score && reduction > 0)
					e = -AlphaBeta(-score - 1, -score, newDepth, ply + 1);
				if (e > score && e < beta)
					e = -AlphaBeta(-beta, -score, newDepth, ply + 1);
			}

			m_pos.UnmakeMove();

			if (IsTerminated())
				return alpha;

			if (ply == 0 && legalMoves == 1)
				UpdatePV(mv, ply);

			if (e > score)
			{
				score = e;
				bestMove = mv;
				UpdatePV(mv, ply);
				hashType = HASH_EXACT;
			}

			if (score >= beta)
			{
				if (!mv.Captured() && !mv.Promotion())
				{
					if (score > CHECKMATE_SCORE - 50 && score < CHECKMATE_SCORE)
						m_mateKillers[ply] = mv;
					else
						m_killers[ply] = mv;

					m_refutations[ply][lastMove.To()][lastMove.Piece()] = mv;
					m_histSuccess[mv.To()][mv.Piece()] += deltaHist;
				}
				hashType = HASH_BETA;
				break;
			}
		}
	}

	if (legalMoves == 0)
	{
		if (inCheck)
			score = -CHECKMATE_SCORE + ply;
		else
			score = DRAW_SCORE;
	}
	else
	{
		if (m_pos.Fifty() >= 100)
			score = DRAW_SCORE;
	}

	if (!IsTerminated())
		RecordHash(m_pos, bestMove, score, depth, ply, hashType);

	return score;
}
////////////////////////////////////////////////////////////////////////////////

EVAL SearchThread::AlphaBetaQ(
	const EVAL alpha,
	const EVAL beta,
	const int ply,
	const int qply)
{
	if (ply > MAX_PLY)
		return alpha;

	m_pvs[ply].clear();

	CheckLimits();
	CheckInput();

	if (IsTerminated())
		return alpha;

	int nodeType = (beta - alpha > 1)? NODE_PV : NODE_NON_PV;
	bool inCheck = m_pos.InCheck();
	Move lastMove = m_pos.LastMove();
	EVAL score = alpha;
	EVAL staticScore = Evaluate(m_pos, alpha, beta);

	if (!inCheck)
	{
		if (staticScore > alpha)
			score = staticScore;
		if (score >= beta)
			return beta;
	}

	MoveList& mvlist = m_mvlists[ply];
	if (inCheck)
		GenMovesInCheck(m_pos, mvlist);
	else
	{
		GenCapturesAndPromotions(m_pos, mvlist, score - staticScore);
		if (qply < USE_QCHECKS[nodeType])
			AddSimpleChecks(m_pos, mvlist);
	}
	UpdateSortScores(mvlist, Move(0), ply, lastMove);

	int legalMoves = 0;
	for (size_t i = 0; i < mvlist.Size(); ++i)
	{
		Move mv = GetNextBest(mvlist, i);

		if (USE_SEE_PRUNING[nodeType] &&
			!inCheck &&
			qply >= SEE_PRUNING_MIN_QPLY)
		{
			if (SEE(m_pos, mv) < 0)
				continue;
		}

		if (m_pos.MakeMove(mv))
		{
			++m_nodes;
			++legalMoves;

			EVAL e = -AlphaBetaQ(-beta, -score, ply + 1, qply + 1);
			m_pos.UnmakeMove();

			if (IsTerminated())
				return alpha;

			if (e > score)
			{
				score = e;
				UpdatePV(mv, ply);
			}
			if (score >= beta)
				break;
		}
	}

	if (legalMoves == 0)
	{
		if (inCheck)
			score = -CHECKMATE_SCORE + ply;
	}

	return score;
}
////////////////////////////////////////////////////////////////////////////////

void SearchThread::CheckInput(bool force)
{
	if (m_id != 0)
		return;

	if (g_searchContext.terminated)
		return;
	if (g_searchResults.depth < 1)
		return;

	if (force || (m_nodes % 8192 == 0))
	{
		if (InputAvailable())
		{
			string s;
			getline(cin, s);
			Log("> " + s);
			ProcessInput(s);
		}
	}
}
////////////////////////////////////////////////////////////////////////////////

void SearchThread::CheckLimits()
{
	if (m_id != 0)
		return;

	if (g_searchContext.terminated)
		return;
	if (g_searchResults.depth < 1)
		return;

	if (g_searchParams.analysis == false)
	{
		if (g_searchParams.limitTime)
		{
			if (CurrentSearchTime() >= g_searchParams.maxTimeHard)
			{
				g_searchContext.terminated = true;

				stringstream ss;
				ss << "Search stopped by stHard, dt = " << CurrentSearchTime();
				Log(ss.str());
			}
		}

		if (g_searchParams.limitNodes &&
			m_nodes >= g_searchParams.maxNodes)
		{
			g_searchContext.terminated = true;
		}
	}
}
////////////////////////////////////////////////////////////////////////////////

void ClearHash()
{
	assert(g_hash != NULL);
	assert(g_hashSize > 0);
	memset((char*)g_hash, 0, g_hashSize * sizeof(HashEntry));
}
////////////////////////////////////////////////////////////////////////////////

void SearchThread::ClearHistory()
{
	memset(m_histTry, 0, 64 * 14 * sizeof(int));
	memset(m_histSuccess, 0, 64 * 14 * sizeof(int));
}
////////////////////////////////////////////////////////////////////////////////

void SearchThread::ClearKillersAndRefutations()
{
	memset(m_killers, 0, (MAX_PLY + 1) * sizeof(Move));
	memset(m_mateKillers, 0, (MAX_PLY + 1) * sizeof(Move));
	memset(m_refutations, 0, (MAX_PLY + 1) * 64 * 14 * sizeof(Move));
}
////////////////////////////////////////////////////////////////////////////////

U64 CurrentSearchTime()
{
	return GetProcTime() - g_searchContext.startTime;
}
////////////////////////////////////////////////////////////////////////////////

Move FirstLegalMove(Position& pos)
{
	MoveList mvlist;
	GenAllMoves(pos, mvlist);
	for (size_t i = 0; i < mvlist.Size(); ++i)
	{
		Move mv = mvlist[i].m_mv;
		if (pos.MakeMove(mv))
		{
			pos.UnmakeMove();
			return mv;
		}
	}
	return Move(0);
}
////////////////////////////////////////////////////////////////////////////////

Move SearchThread::GetNextBest(MoveList& mvlist, size_t i)
{
	for (size_t j = i + 1; j < mvlist.Size(); ++j)
	{
		if (mvlist[j].m_score > mvlist[i].m_score)
			swap(mvlist[i], mvlist[j]);
	}
	return mvlist[i].m_mv;
}
////////////////////////////////////////////////////////////////////////////////

Move GetRandomMove(Position& pos)
{
	g_threads[0].SetPosition(pos);
	EVAL e0 = g_threads[0].AlphaBeta(-INFINITY_SCORE, INFINITY_SCORE, 1, 0);

	MoveList mvlist;
	GenAllMoves(pos, mvlist);
	vector<Move> cand_moves;

	for (size_t i = 0; i < mvlist.Size(); ++i)
	{
		Move mv = mvlist[i].m_mv;
		if (pos.MakeMove(mv))
		{
			g_threads[0].SetPosition(pos);
			EVAL e = -g_threads[0].AlphaBetaQ(-INFINITY_SCORE, INFINITY_SCORE, 0, 0);
			pos.UnmakeMove();

			if (e >= e0 - 100)
				cand_moves.push_back(mv);
		}
	}

	if (cand_moves.empty())
		return Move(0);
	else
	{
		size_t ind = Rand32() % cand_moves.size();
		return cand_moves[ind];
	}
}
////////////////////////////////////////////////////////////////////////////////

bool IsGameOver(Position& pos, string& result, string& comment)
{
	if (pos.Bits(PW) == 0 &&
		pos.Bits(PB) == 0 &&
		pos.MatIndex(WHITE) < 5 &&
		pos.MatIndex(BLACK) < 5)
	{
		result = "1/2-1/2";
		comment = "{Insufficient material}";
		return true;
	}

	Move mv = FirstLegalMove(pos);
	if (mv.IsNull())
	{
		if (pos.InCheck())
		{
			if (pos.Side() == WHITE)
			{
				result = "0-1";
				comment = "{Black mates}";
			}
			else
			{
				result = "1-0";
				comment = "{White mates}";
			}
		}
		else
		{
			result = "1/2-1/2";
			comment = "{Stalemate}";
		}
		return true;
	}

	if (pos.Fifty() >= 100)
	{
		result = "1/2-1/2";
		comment = "{Fifty moves rule}";
		return true;
	}

	if (pos.Repetitions() >= 3)
	{
		result = "1/2-1/2";
		comment = "{Threefold repetition}";
		return true;
	}

	return false;
}
////////////////////////////////////////////////////////////////////////////////

NODES Perft(Position& pos, int depth, int ply)
{
	if (depth <= 0)
		return 1;

	NODES total = 0;

	MoveList mvlist;
	GenAllMoves(pos, mvlist);

	for (size_t i = 0; i < mvlist.Size(); ++i)
	{
		Move mv = mvlist[i].m_mv;
		if (pos.MakeMove(mv))
		{
			total += Perft(pos, depth - 1, ply + 1);
			pos.UnmakeMove();
		}
	}

	return total;
}
////////////////////////////////////////////////////////////////////////////////

void PrintPV(const Position& pos,
	EVAL alpha,
	EVAL beta,
	int depth,
	EVAL score,
	U64 time,
	NODES nodes,
	const vector<Move>& pv)
{
	if (pv.empty())
		return;

	stringstream ss;
	if (!g_uci)
	{
		ss <<
			setw(2) << depth <<
			setw(8) << score <<
			setw(10) << time / 10 <<
			setw(12) << nodes;
		ss << "   ";
		Position tmp = pos;
		int plyCount = tmp.Ply();

		if (tmp.Side() == BLACK)
		{
			if (plyCount == 0)
				++plyCount;
			ss << plyCount / 2 + 1 << ". ... ";
		}

		for (size_t m = 0; m < pv.size(); ++m)
		{
			Move mv = pv[m];
			MoveList mvlist;
			GenAllMoves(tmp, mvlist);
			if (tmp.Side() == WHITE)
				ss << plyCount / 2 + 1 << ". ";
			++plyCount;
			ss << MoveToStrShort(mv, tmp, mvlist);
			if (!tmp.MakeMove(mv))
				break;
			if (tmp.InCheck())
			{
				if (score + m + 1 == CHECKMATE_SCORE)
					ss << "#";
				else if (score - (int)m + 1 == -CHECKMATE_SCORE)
					ss << "#";
				else
					ss << "+";
			}
			if (m == 0)
			{
				if (score >= beta)
				{
					ss << "!";
					break;
				}
				else if (score <= alpha)
					ss << "?";
			}
			if (m < pv.size() - 1)
				ss << " ";
		}
	}
	else
	{
		ss << "info depth " << depth;
		ss << " score cp " << score;
		ss << " time " << time;
		ss << " nodes " << nodes;

		if (!pv.empty())
		{
			ss << " pv";
			for (size_t i = 0; i < pv.size(); ++i)
				ss << " " << MoveToStrLong(pv[i]);
		}
	}

	out(ss.str());
}
////////////////////////////////////////////////////////////////////////////////

void SearchThread::ProcessInput(const string& s)
{
	vector<string> tokens;
	Split(s, tokens);
	if (tokens.empty())
		return;

	string cmd = tokens[0];

	if (g_searchParams.analysis)
	{
		if (CanBeMove(cmd))
		{
			Move mv = StrToMove(cmd, g_pos);
			if (!mv.IsNull())
			{
				g_pos.MakeMove(mv);
				g_queue.push_back("analyze");
				g_searchContext.terminated = true;
			}
		}
		else if (Is(cmd, "undo", 1) && g_searchParams.analysis)
		{
			g_pos.UnmakeMove();
			g_queue.push_back("analyze");
			g_searchContext.terminated = true;
		}
	}

	if (g_searchParams.analysis == false)
	{
		if (cmd == "?")
			g_searchContext.terminated = true;
		else if (Is(cmd, "result", 1))
		{
			m_pvs[0].clear();
			g_searchContext.terminated = true;
		}
	}

	if (Is(cmd, "board", 1))
		g_pos.Print();
	else if (Is(cmd, "exit", 1))
		g_searchContext.terminated = true;
	else if (Is(cmd, "isready", 1))
		out("readyok");
	else if (Is(cmd, "quit", 1))
	{
		for (int i = 1; i < NUM_THREADS; ++i)
			g_threads[i].Stop();
		exit(0);
	}
	else if (Is(cmd, "stop", 1))
		g_searchContext.terminated = true;
}
////////////////////////////////////////////////////////////////////////////////

HashEntry* ProbeHash(const Position& pos)
{
	assert(g_hash != NULL);
	assert(g_hashSize > 0);

	U64 hash = pos.Hash();

	int index = static_cast<int>(hash & g_hashMask);
	HashEntry* pEntry = g_hash + index;

	if (pEntry->Fits(hash))
		return pEntry;
	else
		return NULL;
}
////////////////////////////////////////////////////////////////////////////////

void RecordHash(const Position& pos, Move mv, EVAL score, int depth, int ply, U8 hashType)
{
	assert(g_hash != NULL);
	assert(g_hashSize > 0);

	U64 hash = pos.Hash();
	int index = static_cast<int>(hash & g_hashMask);
	HashEntry& entry = g_hash[index];

	entry.SetMove(mv);
	entry.SetScore(score, ply);
	entry.SetDepth(depth);
	entry.SetType(hashType);

	entry.LockHash(hash);
}
////////////////////////////////////////////////////////////////////////////////

static const EVAL SEE_VALUE[14] =
{
	0, 0, 100, 100, 300, 300, 300, 300, 500, 500, 900, 900, 20000, 20000
};

EVAL SEE_Exchange(const Position& pos, FLD f, COLOR side, EVAL score, EVAL target, U64 occ)
{
	U64 x;
	FLD from = NF;
	EVAL newTarget = 0;

	// find least attacker
	do
	{
		// pawns
		x = BB_PAWN_ATTACKS[f][side ^ 1] & pos.Bits(PAWN | side) & occ;
		if (x)
		{
			from = LSB(x);
			newTarget = SEE_VALUE[PAWN | side];
			break;
		}

		// knights
		x = BB_KNIGHT_ATTACKS[f] & pos.Bits(KNIGHT | side) & occ;
		if (x)
		{
			from = LSB(x);
			newTarget = SEE_VALUE[KNIGHT | side];
			break;
		}

		// bishops
		x = BishopAttacks(f, occ) & pos.Bits(BISHOP | side) & occ;
		if (x)
		{
			from = LSB(x);
			newTarget = SEE_VALUE[BISHOP | side];
			break;
		}

		// rooks
		x = RookAttacks(f, occ) & pos.Bits(ROOK | side) & occ;
		if (x)
		{
			from = LSB(x);
			newTarget = SEE_VALUE[ROOK | side];
			break;
		}

		// queens
		x = QueenAttacks(f, occ) & pos.Bits(QUEEN | side) & occ;
		if (x)
		{
			from = LSB(x);
			newTarget = SEE_VALUE[QUEEN | side];
			break;
		}

		// kings
		x = BB_KING_ATTACKS[f] & pos.Bits(KING | side) & occ;
		if (x)
		{
			from = LSB(x);
			newTarget = SEE_VALUE[KING | side];
			break;
		}

		return score;
	}
	while (0);

	EVAL exchangeScore = -SEE_Exchange(pos, f, side ^ 1,
		-(score + target), newTarget,
		occ & ~BB_SINGLE[from]);

	return std::max(score, exchangeScore);
}
////////////////////////////////////////////////////////////////////////////////

EVAL SEE(const Position& pos, Move mv)
{
	COLOR side = GetColor(mv.Piece());
	EVAL score = SEE_VALUE[mv.Captured()];
	EVAL target = SEE_VALUE[mv.Piece()];
	U64 occ = pos.BitsAll() & ~BB_SINGLE[mv.From()];

	return -SEE_Exchange(pos, mv.To(), side ^ 1, -score, target, occ);
}
////////////////////////////////////////////////////////////////////////////////

void SetHashSize(double mb)
{
	if (g_hash)
		delete[] g_hash;

	size_t Nmax = (size_t)(1024 * 1024 * mb / sizeof(HashEntry));

	g_hashSize = 1;
	while (2 * g_hashSize <= Nmax)
		g_hashSize *= 2;

	g_hash = new HashEntry[g_hashSize];
	g_hashMask = g_hashSize - 1;
}
////////////////////////////////////////////////////////////////////////////////

void SetNumThreads(int num)
{
	NUM_THREADS = num;
	stringstream ss;
	ss << "Threads number set to: " << num;
	Log(ss.str());
}
////////////////////////////////////////////////////////////////////////////////

void SetStrength(int level)
{
	level = std::max(0, level);
	level = std::min(100, level);

	if (level == 100)
	{
		g_searchParams.limitKnps = false;
		g_searchParams.maxKnps = 0.0;
		return;
	}

	double minKnps = 0.1;
	double maxKnps = 1000;

	g_searchParams.limitKnps = true;
	double k = pow(maxKnps / minKnps, 0.01);
	g_searchParams.maxKnps = (minKnps * pow(k, level));
}
////////////////////////////////////////////////////////////////////////////////

void StartPerft(Position& pos, int depth)
{
	NODES total = 0;
	U64 t0 = GetProcTime();

	MoveList mvlist;
	GenAllMoves(pos, mvlist);

	cout << endl;
	for (size_t i = 0; i < mvlist.Size(); ++i)
	{
		Move mv = mvlist[i].m_mv;
		if (pos.MakeMove(mv))
		{
			NODES delta = Perft(pos, depth - 1, 1);
			total += delta;
			cout << " " << MoveToStrLong(mv) << " - " << delta << endl;
			pos.UnmakeMove();
		}
	}
	U64 t1 = GetProcTime();
	FP_TYPE dt = static_cast<FP_TYPE>((t1 - t0) / 1000.);

	cout << endl;
	cout << " Nodes: " << total << endl;
	cout << " Time:  " << dt << endl;
	if (dt > 0) cout << " Knps:  " << total / dt / 1000. << endl;
	cout << endl;
}
////////////////////////////////////////////////////////////////////////////////

void StartSearch(const Position& startpos, int numThreads)
{
	g_searchContext.startTime = GetProcTime();

	g_searchContext.singleReply = false;
	g_searchContext.terminated = false;

	g_searchResults.bestMove = Move(0);
	g_searchResults.depth = 0;
	g_searchResults.pv.clear();
	g_searchResults.score = 0;
	g_searchResults.time = 0;

	for (int i = 0; i < NUM_THREADS; ++i)
	{
		g_threads[i].SetId(i);
		g_threads[i].SetPosition(startpos);
		g_threads[i].ClearKillersAndRefutations();
		g_threads[i].ClearHistory();
		g_threads[i].ClearNodes();
	}

	Log("SEARCH: " + startpos.FEN());
	Position pos = startpos;

	if (FirstLegalMove(pos).IsNull())
		return;

	EVAL alpha = -INFINITY_SCORE;
	EVAL beta = INFINITY_SCORE;

	string result, comment;
	if (IsGameOver(pos, result, comment))
	{
		cout << result << " " << comment << endl << endl;
	}
	else
	{
		if (g_console || g_xboard)
		{
			if (!g_searchParams.silent)
				cout << endl;
		}

		MoveList mvlist;
		GenAllMoves(pos, mvlist);

		int legalMoves = 0;
		for (size_t i = 0; i < mvlist.Size(); ++i)
		{
			Move mv = mvlist[i].m_mv;
			if (pos.MakeMove(mv))
			{
				++legalMoves;
				pos.UnmakeMove();
			}
			if (legalMoves > 1)
				break;
		}
		g_searchContext.singleReply = (legalMoves == 1);

		for (int i = 1; i < numThreads; ++i)
			g_threads[i].Start(i + 1);

		for (int depth = 1; depth < MAX_PLY; ++depth)
		{
			g_searchContext.currentIteration = depth;
			EVAL score = g_threads[0].AlphaBeta(alpha, beta, depth, 0);

			if (g_searchContext.terminated)
				break;

			U64 time = CurrentSearchTime();
			NODES nodes = g_threads[0].GetNodes();

			if (g_searchParams.limitKnps && depth > 1)
			{
				U64 expectedTime = static_cast<U64>(nodes / g_searchParams.maxKnps);
				while (time < expectedTime)
				{
					SleepMillisec(10);
					time = CurrentSearchTime();

					g_threads[0].CheckLimits();
					g_threads[0].CheckInput(true);

					if (g_searchContext.terminated)
						break;
				}
			}

			const vector<Move>& pv = g_threads[0].GetPV();

			if (!g_searchParams.silent)
				PrintPV(pos, alpha, beta, depth, score, time, nodes, pv);

			if (score > alpha && score < beta)
			{
				if (!pv.empty())
				{
					g_searchResults.bestMove = pv[0];
					g_searchResults.depth = depth;
					g_searchResults.nodes = nodes;
					g_searchResults.pv = pv;
					g_searchResults.score = score;
					g_searchResults.time = time;
				}

				if (g_searchParams.analysis == false)
				{
					if (g_searchParams.limitTime &&
						time >= g_searchParams.maxTimeSoft)
					{
						g_searchContext.terminated = true;
						stringstream ss;
						ss << "Search stopped by stSoft, dt = " << time;
						Log(ss.str());
						break;
					}

					if (g_searchContext.singleReply)
					{
						g_searchContext.terminated = true;
						break;
					}

					if (score + depth >= CHECKMATE_SCORE)
					{
						g_searchContext.terminated = true;
						break;
					}

					if (g_searchParams.limitDepth &&
						depth >= g_searchParams.maxDepth)
					{
						g_searchContext.terminated = true;
						break;
					}
				}

				alpha = std::max(score - WINDOW_ROOT / 2, -INFINITY_SCORE);
				beta = std::min(score + WINDOW_ROOT / 2, INFINITY_SCORE);
			}
			else
			{
				alpha = -INFINITY_SCORE;
				beta = INFINITY_SCORE;
				--depth;
			}

			if (g_uci && time > 1000)
			{
				cout << "info time " << time
					<< " nodes " << nodes
					<< " nps " << 1000 * nodes / time
					<< endl;
			}
		}

		if (g_console || g_xboard)
		{
			if (!g_searchParams.silent)
				cout << endl;
		}
	}

	for (int i = 1; i < numThreads; ++i)
		g_threads[i].Stop();

	if (g_searchParams.analysis)
	{
		while (!g_searchContext.terminated)
		{
			string s;
			getline(cin, s);
			g_threads[0].ProcessInput(s);
		}
	}
}
////////////////////////////////////////////////////////////////////////////////

int SearchThread::SuccessRate(Move mv)
{
	if (m_histTry[mv.To()][mv.Piece()] == 0)
		return 0;

	FP_TYPE histTry = static_cast<FP_TYPE>(m_histTry[mv.To()][mv.Piece()]);
	FP_TYPE histSuccess = static_cast<FP_TYPE>(m_histSuccess[mv.To()][mv.Piece()]);
	return int(100 * histSuccess / histTry);
}
////////////////////////////////////////////////////////////////////////////////

void SearchThread::UpdatePV(Move mv, int ply)
{
	if (ply >= MAX_PLY)
		return;

	vector<Move>& pv = m_pvs[ply];
	vector<Move>& child_pv = m_pvs[ply + 1];

	pv.clear();
	pv.push_back(mv);
	pv.insert(pv.end(), child_pv.begin(), child_pv.end());
}
////////////////////////////////////////////////////////////////////////////////

void SearchThread::UpdateSortScores(MoveList& mvlist, Move hashMove, int ply, Move lastMove)
{
	Move killerMove = m_killers[ply];
	Move mateKillerMove = m_mateKillers[ply];
	Move refutationMove = m_refutations[ply][lastMove.To()][lastMove.Piece()];

	for (size_t j = 0; j < mvlist.Size(); ++j)
	{
		Move mv = mvlist[j].m_mv;
		if (mv == hashMove)
			mvlist[j].m_score = SORT_HASH;
		else if (mv.Captured() || mv.Promotion())
		{
			int s_piece = mv.Piece() / 2;
			int s_captured = mv.Captured() / 2;
			int s_promotion = mv.Promotion() / 2;
			mvlist[j].m_score = SORT_CAPTURE + 6 * (s_captured + s_promotion) - s_piece;
		}
		else if (mv == mateKillerMove)
			mvlist[j].m_score = SORT_MATE_KILLER;
		else if (mv == killerMove)
			mvlist[j].m_score = SORT_KILLER;
		else if (mv == refutationMove)
			mvlist[j].m_score = SORT_REFUTATION;
		else
			mvlist[j].m_score = SORT_OTHER + SuccessRate(mv);
	}
}
////////////////////////////////////////////////////////////////////////////////
