WebSVN – Games.Chess Giants – Blame – /engine-texel/search.cpp

Rev	Author	Line No.	Line
99	pmbaty	1	/*
		2	Texel - A UCI chess engine.
		3	Copyright (C) 2012-2014 Peter Österlund, peterosterlund2@gmail.com
		4
		5	This program is free software: you can redistribute it and/or modify
		6	it under the terms of the GNU General Public License as published by
		7	the Free Software Foundation, either version 3 of the License, or
		8	(at your option) any later version.
		9
		10	This program is distributed in the hope that it will be useful,
		11	but WITHOUT ANY WARRANTY; without even the implied warranty of
		12	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
		13	GNU General Public License for more details.
		14
		15	You should have received a copy of the GNU General Public License
		16	along with this program. If not, see <http://www.gnu.org/licenses/>.
		17	*/
		18
		19	/*
		20	* search.cpp
		21	*
		22	* Created on: Feb 25, 2012
		23	* Author: petero
		24	*/
		25
		26	#include "search.hpp"
		27	#include "numa.hpp"
		28	#include "tbprobe.hpp"
		29	#include "treeLogger.hpp"
		30	#include "textio.hpp"
		31	#include "util/logger.hpp"
		32
		33	#include <iostream>
		34	#include <iomanip>
		35	#include <cmath>
		36	#include <limits>
		37
		38	using namespace SearchConst;
		39	using namespace Logger;
		40
		41	Search::Search(const Position& pos0, const std::vector<U64>& posHashList0,
		42	int posHashListSize0, SearchTables& st, ParallelData& pd0,
		43	const std::shared_ptr<SplitPoint>& rootSp,
		44	TreeLogger& logFile0)
		45	: eval(st.et), kt(st.kt), ht(st.ht), tt(st.tt), pd(pd0), threadNo(0),
		46	mainNumaNode(true), logFile(logFile0) {
		47	stopHandler = std::make_shared<DefaultStopHandler>(*this);
		48	spVec.push_back(rootSp);
		49	init(pos0, posHashList0, posHashListSize0);
		50	}
		51
		52	void
		53	Search::init(const Position& pos0, const std::vector<U64>& posHashList0,
		54	int posHashListSize0) {
		55	pos = pos0;
		56	posHashList = posHashList0;
		57	posHashListSize = posHashListSize0;
		58	posHashFirstNew = posHashListSize;
		59	initNodeStats();
		60	minTimeMillis = -1;
		61	maxTimeMillis = -1;
		62	searchNeedMoreTime = false;
		63	maxNodes = -1;
		64	minProbeDepth = 0;
		65	nodesBetweenTimeCheck = 10000;
		66	strength = 1000;
		67	weak = false;
		68	randomSeed = 0;
		69	tLastStats = currentTimeMillis();
		70	totalNodes = 0;
		71	tbHits = 0;
		72	nodesToGo = 0;
		73	verbose = false;
		74	}
		75
		76	void
		77	Search::timeLimit(int minTimeLimit, int maxTimeLimit) {
		78	minTimeMillis = minTimeLimit;
		79	maxTimeMillis = maxTimeLimit;
		80	if ((maxTimeMillis >= 0) && (maxTimeMillis < 1000))
		81	nodesBetweenTimeCheck = 1000;
		82	else
		83	nodesBetweenTimeCheck = 10000;
		84	}
		85
		86	void
		87	Search::setStrength(int strength, U64 randomSeed) {
		88	if (strength < 0) strength = 0;
		89	if (strength > 1000) strength = 1000;
		90	this->strength = strength;
		91	weak = strength < 1000;
		92	this->randomSeed = randomSeed;
		93	}
		94
		95	Move
		96	Search::iterativeDeepening(const MoveList& scMovesIn,
		97	int maxDepth, U64 initialMaxNodes,
		98	bool verbose, int maxPV, bool onlyExact,
		99	int minProbeDepth) {
		100	tStart = currentTimeMillis();
		101	totalNodes = 0;
		102	tbHits = 0;
		103	nodesToGo = 0;
		104	if (scMovesIn.size <= 0)
		105	return Move(); // No moves to search
		106
		107	logFile.open("/home/petero/treelog.dmp", pd, threadNo);
		108	const U64 rootNodeIdx = logFile.logPosition(pos, 0, 0, 0);
		109
		110	kt.clear();
		111	pd.npsInfo.reset();
		112	// pd.wq.resetStat();
		113	const bool smp = pd.numHelperThreads() > 0;
		114	maxNodes = initialMaxNodes;
		115	this->minProbeDepth = (TBProbe::tbEnabled() ? minProbeDepth : MAX_SEARCH_DEPTH) * plyScale;
		116	std::vector<MoveInfo> rootMoves;
		117	getRootMoves(scMovesIn, rootMoves, maxDepth);
		118
		119	Position origPos(pos);
		120	bool firstIteration = true;
		121	Move bestMove = rootMoves[0].move; // bestMove is != rootMoves[0].move when there is an unresolved fail high
		122	Move bestExactMove = rootMoves[0].move; // Only updated when new best move has exact score
		123	this->verbose = verbose;
		124	if ((maxDepth < 0) \|\| (maxDepth > MAX_SEARCH_DEPTH))
		125	maxDepth = MAX_SEARCH_DEPTH;
		126	maxPV = std::min(maxPV, (int)rootMoves.size());
		127	for (size_t i = 0; i < COUNT_OF(searchTreeInfo); i++) {
		128	searchTreeInfo[i].allowNullMove = true;
		129	searchTreeInfo[i].singularMove.setMove(0,0,0,0);
		130	}
		131	ht.reScale();
		132	int posHashFirstNew0 = posHashFirstNew;
		133	try {
		134	for (int depthS = plyScale; ; depthS += plyScale, firstIteration = false) {
		135	initNodeStats();
		136	if (listener) listener->notifyDepth(depthS/plyScale);
		137	int aspirationDelta = 0;
		138	int alpha = 0;
		139	UndoInfo ui;
		140	bool needMoreTime = false;
		141	for (int mi = 0; mi < (int)rootMoves.size(); mi++) {
		142	posHashFirstNew = posHashFirstNew0 + ((mi > 0 && maxPV > 1) ? 1 : 0);
		143	if (mi < maxPV)
		144	aspirationDelta = isWinScore(std::abs(rootMoves[mi].score())) ? 3000 : aspirationWindow;
		145	if (firstIteration)
		146	alpha = -MATE0;
		147	else if (mi < maxPV)
		148	alpha = std::max(rootMoves[mi].score() - aspirationDelta, -MATE0);
		149	else
		150	alpha = rootMoves[maxPV-1].score();
		151
		152	searchNeedMoreTime = (mi > 0);
		153	Move& m = rootMoves[mi].move;
		154	pd.topMove = m;
		155	if (currentTimeMillis() - tStart >= 1000)
		156	if (listener) listener->notifyCurrMove(m, mi + 1);
		157	S64 nodesThisMove = -totalNodes;
		158	posHashList[posHashListSize++] = pos.zobristHash();
		159	bool givesCheck = MoveGen::givesCheck(pos, m);
		160	int beta;
		161	if (firstIteration)
		162	beta = MATE0;
		163	else if (mi < maxPV)
		164	beta = std::min(rootMoves[mi].score() + aspirationDelta, MATE0);
		165	else
		166	beta = alpha + 1;
		167
		168	int lmrS = 0;
		169	bool isCapture = (pos.getPiece(m.to()) != Piece::EMPTY);
		170	bool isPromotion = (m.promoteTo() != Piece::EMPTY);
		171	if ((depthS >= 3*plyScale) && !isCapture && !isPromotion &&
		172	!givesCheck && !passedPawnPush(pos, m) && (mi >= rootLMRMoveCount + maxPV)) {
		173	lmrS = plyScale;
		174	}
		175	pos.makeMove(m, ui);
		176	totalNodes++;
		177	SearchTreeInfo& sti = searchTreeInfo[0];
		178	sti.currentMove = m;
		179	sti.currentMoveNo = mi;
		180	sti.lmr = lmrS;
		181	sti.nodeIdx = rootNodeIdx;
		182	int score = -negaScout(smp, true, -beta, -alpha, 1, depthS - lmrS - plyScale, -1, givesCheck);
		183	if ((lmrS > 0) && (score > alpha)) {
		184	sti.lmr = 0;
		185	score = -negaScout(smp, true, -beta, -alpha, 1, depthS - plyScale, -1, givesCheck);
		186	}
		187	nodesThisMove += totalNodes;
		188	posHashListSize--;
		189	pos.unMakeMove(m, ui);
		190	storeSearchResult(rootMoves, mi, depthS, alpha, beta, score);
		191	if ((verbose && firstIteration) \|\| (mi < maxPV) \|\| (score > rootMoves[maxPV-1].score()))
		192	notifyPV(rootMoves, mi, maxPV);
		193	int betaRetryDelta = aspirationDelta;
		194	int alphaRetryDelta = aspirationDelta;
		195	while ((score >= beta) \|\| ((mi < maxPV) && (score <= alpha))) {
		196	nodesThisMove -= totalNodes;
		197	posHashList[posHashListSize++] = pos.zobristHash();
		198	bool fh = score >= beta;
		199	if (fh) {
		200	if (isWinScore(score))
		201	betaRetryDelta = MATE0; // Don't use aspiration window when searching for faster mate
		202	beta = std::min(score + betaRetryDelta, MATE0);
		203	betaRetryDelta = betaRetryDelta * 3 / 2;
		204	if (mi != 0)
		205	needMoreTime = true;
		206	bestMove = m;
		207	} else { // score <= alpha
		208	if (isLoseScore(score))
		209	alphaRetryDelta = MATE0; // Don't use aspiration window when searching for faster mate
		210	alpha = std::max(score - alphaRetryDelta, -MATE0);
		211	alphaRetryDelta = alphaRetryDelta * 3 / 2;
		212	needMoreTime = searchNeedMoreTime = true;
		213	}
		214	pos.makeMove(m, ui);
		215	totalNodes++;
		216	score = -negaScout(smp, true, -beta, -alpha, 1, depthS - plyScale, -1, givesCheck);
		217	nodesThisMove += totalNodes;
		218	posHashListSize--;
		219	pos.unMakeMove(m, ui);
		220	storeSearchResult(rootMoves, mi, depthS, alpha, beta, score);
		221	notifyPV(rootMoves, mi, maxPV);
		222	}
		223	rootMoves[mi].nodes += nodesThisMove;
		224	if ((mi < maxPV) \|\| (score > rootMoves[maxPV-1].move.score())) {
		225	MoveInfo tmp = rootMoves[mi];
		226	int i = mi;
		227	while ((i > 0) && (rootMoves[i-1].score() < tmp.score())) {
		228	rootMoves[i] = rootMoves[i-1];
		229	i--;
		230	}
		231	rootMoves[i] = tmp;
		232	}
		233	bestMove = rootMoves[0].move;
		234	bestExactMove = bestMove;
		235	if (!firstIteration) {
		236	S64 timeLimit = needMoreTime ? maxTimeMillis : minTimeMillis;
		237	if (timeLimit >= 0) {
		238	U64 tNow = currentTimeMillis();
		239	if (tNow - tStart >= (U64)timeLimit)
		240	break;
		241	}
		242	}
		243	}
		244	S64 tNow = currentTimeMillis();
		245	if (verbose) {
		246	for (int i = nodesByPly.minValue(); i < nodesByPly.maxValue(); i++)
		247	std::cout << std::setw(2) << i
		248	<< ' ' << std::setw(7) << nodesByPly.get(i)
		249	<< ' ' << std::setw(7) << nodesByDepth.get(i)
		250	<< std::endl;
		251	std::stringstream ss;
		252	ss.precision(3);
		253	ss << std::fixed << "Time: " << ((tNow - tStart) * .001);
		254	ss.precision(2);
		255	ss << " depth:" << (depthS/(double)plyScale)
		256	<< " nps:" << ((int)(getTotalNodes() / ((tNow - tStart) * .001)));
		257	std::cout << ss.str() << std::endl;
		258	}
		259	if (maxTimeMillis >= 0)
		260	if (tNow - tStart >= minTimeMillis)
		261	break;
		262	if (depthS >= maxDepth * plyScale)
		263	break;
		264	if (maxNodes >= 0)
		265	if (getTotalNodes() >= maxNodes)
		266	break;
		267	bool enoughDepth = true;
		268	for (int i = 0; i < maxPV; i++) {
		269	int plyToMate = MATE0 - std::abs(rootMoves[i].score());
		270	if (depthS < plyToMate * plyScale)
		271	enoughDepth = false;
		272	}
		273	if (enoughDepth)
		274	break;
		275	if (tNow > tStart)
		276	pd.npsInfo.setBaseNps(getTotalNodesThisThread() * 1000.0 / (tNow - tStart));
		277	if (firstIteration) {
		278	std::stable_sort(rootMoves.begin()+maxPV, rootMoves.end(), MoveInfo::SortByScore());
		279	} else {
		280	// Moves that were hard to search should be searched early in the next iteration
		281	std::stable_sort(rootMoves.begin()+maxPV, rootMoves.end(), MoveInfo::SortByNodes());
		282	}
		283	// std::cout << "fhInfo depth:" << depthS / plyScale << std::endl;
		284	// pd.fhInfo.print(std::cout);
		285	// std::cout << "wqStats depth:" << depthS / plyScale << std::endl;
		286	// pd.wq.printStats(std::cout, pd.numHelperThreads() + 1);
		287	// log([&](std::ostream& os){pd.npsInfo.print(os, depthS / plyScale);});
		288	}
		289	} catch (const StopSearch&) {
		290	pos = origPos;
		291	}
		292	notifyStats();
		293
		294	logFile.close();
		295	return onlyExact ? bestExactMove : bestMove;
		296	}
		297
		298	void
		299	Search::storeSearchResult(std::vector<MoveInfo>& scMoves, int mi, int depth,
		300	int alpha, int beta, int score) {
		301	// std::cout << "d:" << depth/plyScale << " mi:" << mi << " a:" << alpha
		302	// << " b:" << beta << " s:" << score << std::endl;
		303	scMoves[mi].depth = depth;
		304	scMoves[mi].alpha = alpha;
		305	scMoves[mi].beta = beta;
		306	scMoves[mi].move.setScore(score);
		307	scMoves[mi].pv.clear();
		308	tt.extractPVMoves(pos, scMoves[mi].move, scMoves[mi].pv);
		309	if ((maxTimeMillis < 0) && SearchConst::isWinScore(std::abs(score)))
		310	TBProbe::extendPV(pos, scMoves[mi].pv);
		311	}
		312
		313	void
		314	Search::notifyPV(const std::vector<MoveInfo>& moveInfo, int mi, int maxPV) {
		315	bool miNotified = false;
		316	int lastReportedDepth = -1;
		317	for (int i = 0, n = 0; n < maxPV; i++) {
		318	if (!miNotified && (moveInfo[mi].score() > moveInfo[i].score()) &&
		319	(moveInfo[mi].score() > moveInfo[mi].alpha)) {
		320	notifyPV(moveInfo[mi], maxPV > 1 ? n : -1);
		321	lastReportedDepth = moveInfo[mi].depth;
		322	miNotified = true;
		323	n++;
		324	if (n >= maxPV)
		325	break;
		326	}
		327	if (i == mi) {
		328	if (!miNotified) {
		329	notifyPV(moveInfo[mi], maxPV > 1 ? n : -1);
		330	lastReportedDepth = moveInfo[mi].depth;
		331	miNotified = true;
		332	n++;
		333	}
		334	} else {
		335	notifyPV(moveInfo[i], maxPV > 1 ? n : -1);
		336	lastReportedDepth = moveInfo[i].depth;
		337	n++;
		338	}
		339	}
		340	if (listener && (moveInfo[mi].depth != lastReportedDepth))
		341	listener->notifyDepth(moveInfo[mi].depth/plyScale);
		342	}
		343
		344	void
		345	Search::notifyPV(const MoveInfo& info, int multiPVIndex) {
		346	if (info.depth <= 0)
		347	return;
		348	bool uBound = info.score() <= info.alpha;
		349	bool lBound = info.score() >= info.beta;
		350	int score = info.move.score();
		351	if (verbose) {
		352	std::stringstream ss;
		353	ss << std::setw(6) << std::left << TextIO::moveToString(pos, info.move, false)
		354	<< ' ' << std::setw(6) << std::right << score
		355	<< ' ' << std::setw(6) << totalNodes;
		356	if (uBound)
		357	ss << " <=";
		358	else if (lBound)
		359	ss << " >=";
		360	else {
		361	std::string PV = TextIO::moveToString(pos, info.move, false) + " ";
		362	UndoInfo ui;
		363	pos.makeMove(info.move, ui);
		364	PV += tt.extractPV(pos);
		365	pos.unMakeMove(info.move, ui);
		366	ss << ' ' << PV;
		367	}
		368	std::cout << ss.str() << std::endl;
		369	}
		370	if (!listener)
		371	return;
		372	bool isMate = false;
		373	if (isWinScore(score)) {
		374	isMate = true;
		375	score = (MATE0 - score) / 2;
		376	} else if (isLoseScore(score)) {
		377	isMate = true;
		378	score = -((MATE0 + score - 1) / 2);
		379	}
		380	U64 tNow = currentTimeMillis();
		381	int time = (int) (tNow - tStart);
		382	S64 totNodes = getTotalNodes();
		383	S64 tbHits = getTbHits();
		384	int nps = (time > 0) ? (int)(totNodes / (time / 1000.0)) : 0;
		385	listener->notifyPV(info.depth/plyScale, score, time, totNodes, nps, isMate,
		386	uBound, lBound, info.pv, multiPVIndex, tbHits);
		387	}
		388
		389	void
		390	Search::notifyStats() {
		391	S64 tNow = currentTimeMillis();
		392	if (listener) {
		393	int time = (int) (tNow - tStart);
		394	S64 totNodes = getTotalNodes();
		395	int nps = (time > 0) ? (int)(totNodes / (time / 1000.0)) : 0;
		396	S64 tbHits = getTbHits();
		397	listener->notifyStats(totNodes, nps, tbHits, time);
		398	}
		399	tLastStats = tNow;
		400	}
		401
		402	bool
		403	Search::shouldStop() {
		404	S64 tNow = currentTimeMillis();
		405	S64 timeLimit = searchNeedMoreTime ? maxTimeMillis : minTimeMillis;
		406	if ( ((timeLimit >= 0) && (tNow - tStart >= timeLimit)) \|\|
		407	((maxNodes >= 0) && (getTotalNodes() >= maxNodes)))
		408	return true;
		409	if (tNow - tLastStats >= 1000)
		410	notifyStats();
		411	return false;
		412	}
		413
		414	template <bool smp, bool tb>
		415	int
		416	Search::negaScout(int alpha, int beta, int ply, int depth, int recaptureSquare,
		417	const bool inCheck) {
		418	using SplitPointHolder = typename SplitPointTraits<smp>::SpHolder;
		419
		420	// Mate distance pruning
		421	beta = std::min(beta, MATE0-ply-1);
		422	if (alpha >= beta)
		423	return alpha;
		424
		425	if (logFile.isOpened()) {
		426	const SearchTreeInfo& sti = searchTreeInfo[ply-1];
		427	U64 idx = logFile.logNodeStart(sti.nodeIdx, sti.currentMove, alpha, beta, ply, depth);
		428	searchTreeInfo[ply].nodeIdx = idx;
		429	}
		430	if (nodesToGo <= 0) {
		431	nodesToGo = nodesBetweenTimeCheck;
		432	if (stopHandler->shouldStop())
		433	throw StopSearch();
		434	}
		435
		436	// Collect statistics
		437	if (verbose) {
		438	nodesByPly.add(ply);
		439	nodesByDepth.add(depth/plyScale);
		440	}
		441	const U64 hKey = pos.historyHash();
		442	SearchTreeInfo& sti = searchTreeInfo[ply];
		443	sti.currentMove = emptyMove;
		444	sti.currentMoveNo = -1;
		445
		446	// Draw tests
		447	if (canClaimDraw50(pos)) {
		448	if (inCheck) {
		449	MoveList moves;
		450	MoveGen::pseudoLegalMoves(pos, moves);
		451	MoveGen::removeIllegal(pos, moves);
		452	if (moves.size == 0) { // Can't claim draw if already check mated.
		453	int score = -(MATE0-(ply+1));
		454	logFile.logNodeEnd(searchTreeInfo[ply].nodeIdx, score, TType::T_EXACT, UNKNOWN_SCORE, hKey);
		455	return score;
		456	}
		457	}
		458	logFile.logNodeEnd(searchTreeInfo[ply].nodeIdx, 0, TType::T_EXACT, UNKNOWN_SCORE, hKey);
		459	return 0;
		460	}
		461	if (canClaimDrawRep(pos, posHashList, posHashListSize, posHashFirstNew)) {
		462	logFile.logNodeEnd(searchTreeInfo[ply].nodeIdx, 0, TType::T_EXACT, UNKNOWN_SCORE, hKey);
		463	return 0; // No need to test for mate here, since it would have been
		464	// discovered the first time the position came up.
		465	}
		466
		467	// Check transposition table
		468	int evalScore = UNKNOWN_SCORE;
		469	TranspositionTable::TTEntry ent;
		470	ent.clear();
		471	const bool singularSearch = !sti.singularMove.isEmpty();
		472	const bool useTT = (mainNumaNode \|\| (depth >= 1 * plyScale)) && // To reduce memory bandwidth
		473	!singularSearch;
		474	if (useTT) tt.probe(hKey, ent);
		475	Move hashMove;
		476	if (ent.getType() != TType::T_EMPTY) {
		477	int score = ent.getScore(ply);
		478	evalScore = ent.getEvalScore();
		479	ent.getMove(hashMove);
		480	if (((beta == alpha + 1) \|\| (depth <= ply*plyScale)) && ent.isCutOff(alpha, beta, ply, depth)) {
		481	if (score >= beta) {
		482	if (!hashMove.isEmpty())
		483	if (pos.getPiece(hashMove.to()) == Piece::EMPTY)
		484	kt.addKiller(ply, hashMove);
		485	}
		486	sti.bestMove = hashMove;
		487	logFile.logNodeEnd(sti.nodeIdx, score, ent.getType(), evalScore, hKey);
		488	return score;
		489	}
		490	}
		491	if (singularSearch)
		492	hashMove = sti.singularMove;
		493
		494	// Probe endgame tablebases
		495	const int illegalScore = -(MATE0-(ply+1));
		496	int tbScore = illegalScore;
		497	if (tb && depth >= minProbeDepth && !singularSearch) {
		498	TranspositionTable::TTEntry tbEnt;
		499	tbEnt.clear();
		500	if (TBProbe::tbProbe(pos, ply, alpha, beta, tbEnt)) {
		501	tbHits++;
		502	nodesToGo -= 1000;
		503	int type = tbEnt.getType();
		504	int score = tbEnt.getScore(ply);
		505	bool cutOff = false;
		506	if (score == 0 && type == TType::T_EXACT) {
		507	const int maxSwindle = 50;
		508	if (depth < 16 * plyScale) {
		509	if (evalScore == UNKNOWN_SCORE)
		510	evalScore = eval.evalPos(pos);
		511	score = Evaluate::swindleScore(evalScore);
		512	cutOff = true;
		513	} else if (alpha >= maxSwindle) {
		514	tbEnt.setType(TType::T_LE);
		515	score = maxSwindle;
		516	cutOff = true;
		517	} else if (beta <= -maxSwindle) {
		518	tbEnt.setType(TType::T_GE);
		519	score = -maxSwindle;
		520	cutOff = true;
		521	}
		522	} else {
		523	if ( (type == TType::T_EXACT) \|\|
		524	((type == TType::T_GE) && (score >= beta)) \|\|
		525	((type == TType::T_LE) && (score <= alpha)))
		526	cutOff = true;
		527	}
		528	if (cutOff) {
		529	emptyMove.setScore(score);
		530	if (useTT) tt.insert(hKey, emptyMove, tbEnt.getType(), ply, depth, evalScore);
		531	logFile.logNodeEnd(sti.nodeIdx, score, tbEnt.getType(), evalScore, hKey);
		532	return score;
		533	}
		534	if ((type == TType::T_GE) && (score > alpha)) {
		535	tbScore = score;
		536	alpha = score - 1;
		537	}
		538	}
		539	}
		540
		541	int posExtend = inCheck ? plyScale : 0; // Check extension
		542
		543	// If out of depth, perform quiescence search
		544	if (depth + posExtend <= 0) {
		545	q0Eval = evalScore;
		546	sti.bestMove.setMove(0,0,0,0);
		547	int score = quiesce(alpha, beta, ply, 0, inCheck);
		548	int type = TType::T_EXACT;
		549	if (score <= alpha) {
		550	type = TType::T_LE;
		551	} else if (score >= beta) {
		552	type = TType::T_GE;
		553	}
		554	sti.bestMove.setScore(score);
		555	if (useTT) tt.insert(hKey, sti.bestMove, type, ply, depth, q0Eval);
		556	logFile.logNodeEnd(sti.nodeIdx, score, type, q0Eval, hKey);
		557	return score;
		558	}
		559
		560	// Razoring
		561	const bool normalBound = !isLoseScore(alpha) && !isWinScore(beta);
		562	if (normalBound && (depth < 4*plyScale) && (beta == alpha + 1) && !singularSearch) {
		563	if (evalScore == UNKNOWN_SCORE) {
		564	evalScore = eval.evalPos(pos);
		565	}
		566	const int razorMargin = (depth <= plyScale) ? (int)razorMargin1 : (int)razorMargin2; // Pierre-Marie Baty -- added type cast
		567	if (evalScore < beta - razorMargin) {
		568	q0Eval = evalScore;
		569	int score = quiesce(alpha-razorMargin, beta-razorMargin, ply, 0, inCheck);
		570	if (score <= alpha-razorMargin) {
		571	emptyMove.setScore(score);
		572	if (useTT) tt.insert(hKey, emptyMove, TType::T_LE, ply, depth, q0Eval);
		573	logFile.logNodeEnd(sti.nodeIdx, score, TType::T_LE, q0Eval, hKey);
		574	return score;
		575	}
		576	}
		577	}
		578
		579	// Reverse futility pruning
		580	if (!inCheck && (depth < 5*plyScale) && (posExtend == 0) && normalBound && !singularSearch) {
		581	bool mtrlOk;
		582	if (pos.isWhiteMove()) {
		583	mtrlOk = (pos.wMtrl() > pos.wMtrlPawns()) && (pos.wMtrlPawns() > 0);
		584	} else {
		585	mtrlOk = (pos.bMtrl() > pos.bMtrlPawns()) && (pos.bMtrlPawns() > 0);
		586	}
		587	if (mtrlOk) {
		588	int margin;
		589	if (depth <= plyScale) margin = reverseFutilityMargin1;
		590	else if (depth <= 2*plyScale) margin = reverseFutilityMargin2;
		591	else if (depth <= 3*plyScale) margin = reverseFutilityMargin3;
		592	else margin = reverseFutilityMargin4;
		593	if (evalScore == UNKNOWN_SCORE)
		594	evalScore = eval.evalPos(pos);
		595	if (evalScore - margin >= beta) {
		596	emptyMove.setScore(evalScore - margin);
		597	if (useTT) tt.insert(hKey, emptyMove, TType::T_GE, ply, depth, evalScore);
		598	logFile.logNodeEnd(sti.nodeIdx, evalScore - margin, TType::T_GE, evalScore, hKey);
		599	return evalScore - margin;
		600	}
		601	}
		602	}
		603
		604	// Null-move pruning
		605	if ((depth >= 3*plyScale) && !inCheck && sti.allowNullMove && !isWinScore(beta) && !singularSearch) {
		606	bool nullOk;
		607	if (pos.isWhiteMove()) {
		608	nullOk = (pos.wMtrl() > pos.wMtrlPawns()) && (pos.wMtrlPawns() > 0);
		609	} else {
		610	nullOk = (pos.bMtrl() > pos.bMtrlPawns()) && (pos.bMtrlPawns() > 0);
		611	}
		612	const int R = (depth > 6plyScale) ? 4plyScale : 3*plyScale;
		613	if (nullOk) {
		614	if (((ent.getType() == TType::T_EXACT) \|\| (ent.getType() == TType::T_LE)) &&
		615	(ent.getDepth() >= depth - R) && (ent.getScore(ply) < beta))
		616	nullOk = false;
		617	}
		618	if (nullOk) {
		619	if (evalScore == UNKNOWN_SCORE)
		620	evalScore = eval.evalPos(pos);
		621	if (evalScore < beta)
		622	nullOk = false;
		623	}
		624	if (nullOk) {
		625	int score;
		626	{
		627	SplitPointHolder sph(pd, spVec, pending);
		628	if (smp) {
		629	sph.setSp(std::make_shared<SplitPoint>(threadNo, spVec.back(),
		630	searchTreeInfo[ply-1].currentMoveNo,
		631	pos, posHashList, posHashListSize,
		632	sti, kt, ht, alpha, beta, ply, depth / plyScale));
		633	sph.addMove(0, SplitPointMove(Move(), 0, 0, -1, false));
		634	sph.addToQueue();
		635	sph.setOwnerCurrMove(0, alpha);
		636	}
		637	pos.setWhiteMove(!pos.isWhiteMove());
		638	int epSquare = pos.getEpSquare();
		639	pos.setEpSquare(-1);
		640	searchTreeInfo[ply+1].allowNullMove = false;
		641	searchTreeInfo[ply+1].bestMove.setMove(0,0,0,0);
		642	score = -negaScout(smp, tb, -beta, -(beta - 1), ply + 1, depth - R, -1, false);
		643	searchTreeInfo[ply+1].allowNullMove = true;
		644	pos.setEpSquare(epSquare);
		645	pos.setWhiteMove(!pos.isWhiteMove());
		646	}
		647	bool storeInHash = true;
		648	if ((score >= beta) && (depth >= 10 * plyScale)) {
		649	// Null-move verification search
		650	SearchTreeInfo& sti2 = searchTreeInfo[ply-1];
		651	const Move savedMove = sti2.currentMove;
		652	const int savedMoveNo = sti2.currentMoveNo;
		653	const S64 savedNodeIdx2 = sti2.nodeIdx;
		654	sti2.currentMove = Move(1,1,0); // Represents "no move"
		655	sti2.currentMoveNo = -1;
		656	sti2.nodeIdx = sti.nodeIdx;
		657	const S64 savedNodeIdx = sti.nodeIdx;
		658	sti.allowNullMove = false;
		659	score = negaScout(smp, tb, beta - 1, beta, ply, depth - R, recaptureSquare, inCheck);
		660	sti.allowNullMove = true;
		661	sti.nodeIdx = savedNodeIdx;
		662	sti2.currentMove = savedMove;
		663	sti2.currentMoveNo = savedMoveNo;
		664	sti2.nodeIdx = savedNodeIdx2;
		665	searchTreeInfo[ply+1].bestMove.setMove(0,0,0,0);
		666	storeInHash = false;
		667	}
		668	if (smp && (depth - R >= MIN_SMP_DEPTH * plyScale))
		669	pd.fhInfo.addData(-1, searchTreeInfo[ply+1].currentMoveNo, score < beta, false);
		670	if (score >= beta) {
		671	if (isWinScore(score))
		672	score = beta;
		673	emptyMove.setScore(score);
		674	if (storeInHash)
		675	if (useTT) tt.insert(hKey, emptyMove, TType::T_GE, ply, depth, evalScore);
		676	logFile.logNodeEnd(sti.nodeIdx, score, TType::T_GE, evalScore, hKey);
		677	return score;
		678	}
		679	}
		680	}
		681
		682	bool futilityPrune = false;
		683	int futilityScore = alpha;
		684	if (!inCheck && (depth < 5*plyScale) && (posExtend == 0) && normalBound && !singularSearch) {
		685	int margin;
		686	if (depth <= plyScale) margin = futilityMargin1;
		687	else if (depth <= 2*plyScale) margin = futilityMargin2;
		688	else if (depth <= 3*plyScale) margin = futilityMargin3;
		689	else margin = futilityMargin4;
		690	if (evalScore == UNKNOWN_SCORE)
		691	evalScore = eval.evalPos(pos);
		692	futilityScore = evalScore + margin;
		693	if (futilityScore <= alpha)
		694	futilityPrune = true;
		695	}
		696
		697	// Internal iterative deepening
		698	if ((depth > 4*plyScale) && hashMove.isEmpty()) {
		699	bool isPv = beta > alpha + 1;
		700	if (isPv \|\| (depth > 8 * plyScale)) {
		701	SearchTreeInfo& sti2 = searchTreeInfo[ply-1];
		702	Move savedMove = sti2.currentMove;
		703	int savedMoveNo = sti2.currentMoveNo;
		704	S64 savedNodeIdx2 = sti2.nodeIdx;
		705	sti2.currentMove = Move(1,1,0); // Represents "no move"
		706	sti2.currentMoveNo = -1;
		707	sti2.nodeIdx = sti.nodeIdx;
		708
		709	S64 savedNodeIdx = sti.nodeIdx;
		710	int newDepth = isPv ? depth - 2 * plyScale : depth * 3 / 8;
		711	negaScout(smp, tb, alpha, beta, ply, newDepth, -1, inCheck);
		712	sti.nodeIdx = savedNodeIdx;
		713
		714	sti2.currentMove = savedMove;
		715	sti2.currentMoveNo = savedMoveNo;
		716	sti2.nodeIdx = savedNodeIdx2;
		717
		718	tt.probe(hKey, ent);
		719	if (ent.getType() != TType::T_EMPTY)
		720	ent.getMove(hashMove);
		721	}
		722	}
		723
		724	// Generate move list
		725	MoveList moves;
		726	if (inCheck)
		727	MoveGen::checkEvasions(pos, moves);
		728	else
		729	MoveGen::pseudoLegalMoves(pos, moves);
		730	bool seeDone = false;
		731	bool hashMoveSelected = true;
		732	if (hashMove.isEmpty() \|\| !selectHashMove(moves, hashMove)) {
		733	scoreMoveList(moves, ply);
		734	seeDone = true;
		735	hashMoveSelected = false;
		736	}
		737
		738	// Handle singular extension
		739	bool singularExtend = false;
		740	if ((depth > 6 * plyScale) && (posExtend == 0) &&
		741	hashMoveSelected && sti.singularMove.isEmpty() &&
		742	(ent.getType() != TType::T_LE) &&
		743	(ent.getDepth() >= depth - 3 * plyScale) &&
		744	(getMoveExtend(hashMove, recaptureSquare) <= 0) &&
		745	(ply + depth / plyScale < MAX_SEARCH_DEPTH) &&
		746	MoveGen::isLegal(pos, hashMove, inCheck)) {
		747	SearchTreeInfo& sti2 = searchTreeInfo[ply-1];
		748	Move savedMove = sti2.currentMove;
		749	int savedMoveNo = sti2.currentMoveNo;
		750	S64 savedNodeIdx2 = sti2.nodeIdx;
		751	sti2.currentMove = Move(1,1,0); // Represents "no move"
		752	sti2.currentMoveNo = -1;
		753	sti2.nodeIdx = sti.nodeIdx;
		754	S64 savedNodeIdx = sti.nodeIdx;
		755
		756	int newDepth = depth / 2;
		757	int newBeta = ent.getScore(ply) - 25;
		758	sti.singularMove = hashMove;
		759	int singScore = negaScout(smp, tb, newBeta-1, newBeta, ply, newDepth,
		760	recaptureSquare, inCheck);
		761	sti.singularMove.setMove(0,0,0,0);
		762	if (singScore <= newBeta-1)
		763	singularExtend = true;
		764
		765	sti.nodeIdx = savedNodeIdx;
		766	sti2.currentMove = savedMove;
		767	sti2.currentMoveNo = savedMoveNo;
		768	sti2.nodeIdx = savedNodeIdx2;
		769	}
		770
		771	SplitPointHolder sph(pd, spVec, pending);
		772	if (smp) {
		773	sph.setSp(std::make_shared<SplitPoint>(threadNo, spVec.back(),
		774	searchTreeInfo[ply-1].currentMoveNo,
		775	pos, posHashList, posHashListSize,
		776	sti, kt, ht, alpha, beta, ply, depth/plyScale));
		777	for (int mi = 0; mi < moves.size; mi++) {
		778	if ((mi == 1) && !seeDone) {
		779	scoreMoveList(moves, ply, 1);
		780	seeDone = true;
		781	}
		782	if ((mi > 0) \|\| !hashMoveSelected)
		783	selectBest(moves, mi);
		784	}
		785	}
		786
		787	// Determine late move pruning (LMP) limit
		788	int lmpMoveCountLimit = 256;
		789	if (beta == alpha + 1) {
		790	bool lmpOk;
		791	if (pos.isWhiteMove())
		792	lmpOk = (pos.wMtrl() > pos.wMtrlPawns()) && (pos.wMtrlPawns() > 0);
		793	else
		794	lmpOk = (pos.bMtrl() > pos.bMtrlPawns()) && (pos.bMtrlPawns() > 0);
		795	if (lmpOk) {
		796	if (depth <= plyScale) lmpMoveCountLimit = lmpMoveCountLimit1;
		797	else if (depth <= 2 * plyScale) lmpMoveCountLimit = lmpMoveCountLimit2;
		798	else if (depth <= 3 * plyScale) lmpMoveCountLimit = lmpMoveCountLimit3;
		799	else if (depth <= 4 * plyScale) lmpMoveCountLimit = lmpMoveCountLimit4;
		800	}
		801	}
		802
		803	// Start searching move alternatives
		804	UndoInfo ui;
		805	for (int pass = (smp?0:1); pass < 2; pass++) {
		806	bool haveLegalMoves = false;
		807	int b = beta;
		808	int bestScore = illegalScore;
		809	int bestMove = -1;
		810	int lmrCount = 0;
		811	if (tb && pass == 1 && tbScore != illegalScore) {
		812	bestScore = tbScore - 1;
		813	bestMove = -2;
		814	sti.bestMove.setMove(0, 0, 0, 0);
		815	}
		816	for (int mi = 0; mi < moves.size; mi++) {
		817	if (!smp) {
		818	if ((mi == 1) && !seeDone) {
		819	scoreMoveList(moves, ply, 1);
		820	seeDone = true;
		821	}
		822	if ((mi < lmpMoveCountLimit) \|\| (lmrCount <= lmrMoveCountLimit1))
		823	if ((mi > 0) \|\| !hashMoveSelected)
		824	selectBest(moves, mi);
		825	}
		826	Move& m = moves[mi];
		827	int newCaptureSquare = -1;
		828	bool isCapture = (pos.getPiece(m.to()) != Piece::EMPTY);
		829	bool isPromotion = (m.promoteTo() != Piece::EMPTY);
		830	int sVal = std::numeric_limits<int>::min();
		831	bool mayReduce = (m.score() < 53) && (!isCapture \|\| m.score() < 0) && !isPromotion;
		832	bool givesCheck = MoveGen::givesCheck(pos, m);
		833	bool negSEECheck = (depth > 4*plyScale) && givesCheck && negSEE(m);
		834	bool doFutility = false;
		835	if (mayReduce && haveLegalMoves && !givesCheck && !passedPawnPush(pos, m)) {
		836	if (normalBound && !isLoseScore(bestScore) && (mi >= lmpMoveCountLimit))
		837	continue; // Late move pruning
		838	if (futilityPrune)
		839	doFutility = true;
		840	}
		841	int score = illegalScore;
		842	if (doFutility) {
		843	score = futilityScore;
		844	} else {
		845	#ifdef HAS_PREFETCH
		846	if (pass == 1)
		847	tt.prefetch(pos.hashAfterMove(m));
		848	#endif
		849	if ((mi == 0) && m.equals(sti.singularMove))
		850	continue;
		851	if (!MoveGen::isLegal(pos, m, inCheck))
		852	continue;
		853	int moveExtend = (posExtend > 0) ? 0 : getMoveExtend(m, recaptureSquare);
		854	int extend = std::max(posExtend, moveExtend);
		855	if (singularExtend && (mi == 0))
		856	extend = 1*plyScale;
		857	int lmr = 0;
		858	if ((depth >= 2*plyScale) && mayReduce && (extend == 0)) {
		859	if (!givesCheck && !passedPawnPush(pos, m)) {
		860	lmrCount++;
		861	if ((lmrCount > lmrMoveCountLimit2) && (depth > 5*plyScale) && !isCapture) {
		862	lmr = 3*plyScale;
		863	} else if ((lmrCount > lmrMoveCountLimit1) && (depth > 3*plyScale) && !isCapture) {
		864	lmr = 2*plyScale;
		865	} else {
		866	lmr = 1*plyScale;
		867	}
		868	}
		869	}
		870	int newDepth = depth - plyScale + extend - lmr - (negSEECheck ? plyScale : 0);
		871	if (isCapture && (givesCheck \|\| (depth + extend) > plyScale)) {
		872	// Compute recapture target square, but only if we are not going
		873	// into q-search at the next ply.
		874	int fVal = ::pieceValue[pos.getPiece(m.from())];
		875	int tVal = ::pieceValue[pos.getPiece(m.to())];
		876	const int pV = ::pV;
		877	if (std::abs(tVal - fVal) < pV / 2) { // "Equal" capture
		878	sVal = SEE(m);
		879	if (std::abs(sVal) < pV / 2)
		880	newCaptureSquare = m.to();
		881	}
		882	}
		883	if (pass == 0) {
		884	sph.addMove(mi, SplitPointMove(m, lmr, newDepth, newCaptureSquare, givesCheck));
		885	} else {
		886	posHashList[posHashListSize++] = pos.zobristHash();
		887	pos.makeMove(m, ui);
		888	totalNodes++;
		889	nodesToGo--;
		890	sti.currentMove = m;
		891	sti.currentMoveNo = mi;
		892	sti.lmr = lmr;
		893	// S64 n1 = totalNodes; int nomDepth = newDepth;
		894	if (smp) {
		895	int helperScore = sph.setOwnerCurrMove(mi, alpha);
		896	if (helperScore != UNKNOWN_SCORE)
		897	score = helperScore;
		898	}
		899	if (!smp \|\| (score == illegalScore)) {
		900	score = -negaScout(smp, tb, -b, -alpha, ply + 1, newDepth, newCaptureSquare, givesCheck);
		901	if (((lmr > 0) && (score > alpha)) \|\|
		902	((score > alpha) && (score < beta) && (b != beta))) {
		903	sti.lmr = 0;
		904	newDepth += lmr;
		905	score = -negaScout(smp, tb, -beta, -alpha, ply + 1, newDepth, newCaptureSquare, givesCheck);
		906	}
		907	}
		908	if (smp) {
		909	// if (sph.hasHelperThread())
		910	// log([&](std::ostream& os){os << "main seqNo:" << sph.getSeqNo() << " ply:" << ply << " m:" << mi
		911	// << " a:" << alpha << " b:" << beta << " s:" << score
		912	// << " d:" << nomDepth/plyScale << " n:" << (totalNodes-n1);});
		913	if (beta > alpha + 1) {
		914	pd.fhInfo.addPvData(mi, score > alpha);
		915	} else {
		916	pd.fhInfo.addData(mi, searchTreeInfo[ply+1].currentMoveNo,
		917	score <= alpha, !sph.isAllNode());
		918	}
		919	}
		920	posHashListSize--;
		921	pos.unMakeMove(m, ui);
		922	}
		923	}
		924	if (pass == 1) {
		925	if (weak && haveLegalMoves)
		926	if (weakPlaySkipMove(pos, m, ply))
		927	score = illegalScore;
		928	m.setScore(score);
		929
		930	if (score != illegalScore)
		931	haveLegalMoves = true;
		932	bestScore = std::max(bestScore, score);
		933	if (score > alpha) {
		934	alpha = score;
		935	bestMove = mi;
		936	sti.bestMove.setMove(m.from(), m.to(), m.promoteTo(), sti.bestMove.score());
		937	}
		938	if (alpha >= beta) {
		939	if (pos.getPiece(m.to()) == Piece::EMPTY) {
		940	kt.addKiller(ply, m);
		941	ht.addSuccess(pos, m, depth/plyScale);
		942	for (int mi2 = mi - 1; mi2 >= 0; mi2--) {
		943	Move m2 = moves[mi2];
		944	if (pos.getPiece(m2.to()) == Piece::EMPTY)
		945	ht.addFail(pos, m2, depth/plyScale);
		946	}
		947	}
		948	if (useTT) tt.insert(hKey, m, TType::T_GE, ply, depth, evalScore);
		949	logFile.logNodeEnd(sti.nodeIdx, alpha, TType::T_GE, evalScore, hKey);
		950	return alpha;
		951	}
		952	b = alpha + 1;
		953	}
		954	}
		955	if (pass == 0) {
		956	sph.addToQueue();
		957	} else {
		958	if (!haveLegalMoves && !inCheck) {
		959	if (singularSearch) {
		960	logFile.logNodeEnd(sti.nodeIdx, alpha, TType::T_LE, evalScore, hKey);
		961	return alpha; // Only one legal move, fail low to trigger singular extension
		962	}
		963	emptyMove.setScore(0);
		964	if (useTT) tt.insert(hKey, emptyMove, TType::T_EXACT, ply, depth, evalScore);
		965	logFile.logNodeEnd(sti.nodeIdx, 0, TType::T_EXACT, evalScore, hKey);
		966	return 0; // Stale-mate
		967	}
		968	if (tb && bestMove == -2) { // TB win, unknown move
		969	bestScore = tbScore;
		970	emptyMove.setScore(bestScore);
		971	if (useTT) tt.insert(hKey, emptyMove, TType::T_EXACT, ply, depth, evalScore);
		972	logFile.logNodeEnd(sti.nodeIdx, bestScore, TType::T_EXACT, evalScore, hKey);
		973	} else if (bestMove >= 0) {
		974	if (useTT) tt.insert(hKey, moves[bestMove], TType::T_EXACT, ply, depth, evalScore);
		975	logFile.logNodeEnd(sti.nodeIdx, bestScore, TType::T_EXACT, evalScore, hKey);
		976	} else {
		977	emptyMove.setScore(bestScore);
		978	if (useTT) tt.insert(hKey, emptyMove, TType::T_LE, ply, depth, evalScore);
		979	logFile.logNodeEnd(sti.nodeIdx, bestScore, TType::T_LE, evalScore, hKey);
		980	}
		981	return bestScore;
		982	}
		983	}
		984	assert(false);
		985	return 0;
		986	}
		987
		988	int
		989	Search::getMoveExtend(const Move& m, int recaptureSquare) {
		990	if ((m.to() == recaptureSquare)) {
		991	int sVal = SEE(m);
		992	int tVal = ::pieceValue[pos.getPiece(m.to())];
		993	if (sVal > tVal - pV / 2)
		994	return plyScale;
		995	}
		996	bool isCapture = (pos.getPiece(m.to()) != Piece::EMPTY);
		997	if (isCapture && (pos.wMtrlPawns() + pos.bMtrlPawns() > pV)) {
		998	// Extend if going into pawn endgame
		999	int capVal = ::pieceValue[pos.getPiece(m.to())];
		1000	if (pos.isWhiteMove()) {
		1001	if ((pos.wMtrl() == pos.wMtrlPawns()) && (pos.bMtrl() - pos.bMtrlPawns() == capVal))
		1002	return plyScale;
		1003	} else {
		1004	if ((pos.bMtrl() == pos.bMtrlPawns()) && (pos.wMtrl() - pos.wMtrlPawns() == capVal))
		1005	return plyScale;
		1006	}
		1007	}
		1008	return 0;
		1009	}
		1010
		1011	void
		1012	Search::getRootMoves(const MoveList& rootMovesIn,
		1013	std::vector<MoveInfo>& rootMovesOut,
		1014	int maxDepth) {
		1015	MoveList rootMoves(rootMovesIn);
		1016	if ((maxTimeMillis >= 0) \|\| (maxNodes >= 0) \|\| (maxDepth >= 0)) {
		1017	MoveList legalMoves;
		1018	MoveGen::pseudoLegalMoves(pos, legalMoves);
		1019	MoveGen::removeIllegal(pos, legalMoves);
		1020	if (rootMoves.size == legalMoves.size) {
		1021	// Game mode, handle missing TBs
		1022	std::vector<Move> movesToSearch;
		1023	if (TBProbe::getSearchMoves(pos, legalMoves, movesToSearch))
		1024	rootMoves.filter(movesToSearch);
		1025	}
		1026	}
		1027
		1028	// If strength is < 10%, only include a subset of the root moves.
		1029	// At least one move is always included though.
		1030	std::vector<bool> includedMoves(rootMoves.size);
		1031	U64 rndL = pos.zobristHash() ^ randomSeed;
		1032	includedMoves[(int)(rndL % rootMoves.size)] = true;
		1033	double pIncl = (strength < 100) ? strength * strength * 1e-4 : 1.0;
		1034	for (int mi = 0; mi < rootMoves.size; mi++) {
		1035	rndL = 6364136223846793005ULL * rndL + 1442695040888963407ULL;
		1036	double rnd = ((rndL & 0x7fffffffffffffffULL) % 1000000000) / 1e9;
		1037	if (!includedMoves[mi] && (rnd < pIncl))
		1038	includedMoves[mi] = true;
		1039	}
		1040	for (int mi = 0; mi < rootMoves.size; mi++) {
		1041	if (includedMoves[mi]) {
		1042	const Move& m = rootMoves[mi];
		1043	rootMovesOut.push_back(MoveInfo(m, 0));
		1044	}
		1045	}
		1046	}
		1047
		1048	bool
		1049	Search::weakPlaySkipMove(const Position& pos, const Move& m, int ply) const {
		1050	U64 rndL = pos.zobristHash() ^ Position::getHashKey(Piece::EMPTY, m.from()) ^
		1051	Position::getHashKey(Piece::EMPTY, m.to()) ^ randomSeed;
		1052	double rnd = ((rndL & 0x7fffffffffffffffULL) % 1000000000) / 1e9;
		1053
		1054	double s = strength * 1e-3;
		1055	double offs = (17 - 50 * s) / 3;
		1056	double effPly = ply * Evaluate::interpolate(pos.wMtrl() + pos.bMtrl(), 0, 30, ::qV * 4, 100) * 1e-2;
		1057	double t = effPly + offs;
		1058	double p = 1/(1+exp(t)); // Probability to "see" move
		1059	bool easyMove = ((pos.getPiece(m.to()) != Piece::EMPTY) \|\|
		1060	(ply < 2) \|\| (searchTreeInfo[ply-2].currentMove.to() == m.from()));
		1061	if (easyMove)
		1062	p = 1-(1-p)*(1-p);
		1063	if (rnd > p)
		1064	return true;
		1065	return false;
		1066	}
		1067
		1068	int
		1069	Search::quiesce(int alpha, int beta, int ply, int depth, const bool inCheck) {
		1070	int score;
		1071	if (inCheck) {
		1072	score = -(MATE0 - (ply+1));
		1073	} else {
		1074	if ((depth == 0) && (q0Eval != UNKNOWN_SCORE)) {
		1075	score = q0Eval;
		1076	} else {
		1077	score = eval.evalPos(pos);
		1078	if (depth == 0)
		1079	q0Eval = score;
		1080	}
		1081	}
		1082	if (score >= beta)
		1083	return score;
		1084	const int evalScore = score;
		1085	if (score > alpha)
		1086	alpha = score;
		1087	int bestScore = score;
		1088	const bool tryChecks = (depth > -1);
		1089	MoveList moves;
		1090	if (inCheck) {
		1091	MoveGen::checkEvasions(pos, moves);
		1092	} else if (tryChecks) {
		1093	MoveGen::pseudoLegalCapturesAndChecks(pos, moves);
		1094	} else {
		1095	MoveGen::pseudoLegalCaptures(pos, moves);
		1096	}
		1097
		1098	bool realInCheckComputed = false;
		1099	bool realInCheck = false;
		1100	if (depth > -2) {
		1101	realInCheckComputed = true;
		1102	realInCheck = inCheck;
		1103	}
		1104	scoreMoveListMvvLva(moves);
		1105	UndoInfo ui;
		1106	for (int mi = 0; mi < moves.size; mi++) {
		1107	if (mi < quiesceMaxSortMoves) {
		1108	// If the first N moves didn't fail high this is probably an ALL-node,
		1109	// so spending more effort on move ordering is probably wasted time.
		1110	selectBest(moves, mi);
		1111	}
		1112	const Move& m = moves[mi];
		1113	bool givesCheck = false;
		1114	bool givesCheckComputed = false;
		1115	if (inCheck) {
		1116	// Allow all moves
		1117	} else {
		1118	if ((pos.getPiece(m.to()) == Piece::EMPTY) && (m.promoteTo() == Piece::EMPTY)) {
		1119	// Non-capture
		1120	if (!tryChecks)
		1121	continue;
		1122	givesCheck = MoveGen::givesCheck(pos, m);
		1123	givesCheckComputed = true;
		1124	if (!givesCheck)
		1125	continue;
		1126	if (negSEE(m)) // Needed because m.score() is not computed for non-captures
		1127	continue;
		1128	} else {
		1129	if (negSEE(m))
		1130	continue;
		1131	int capt = ::pieceValue[pos.getPiece(m.to())];
		1132	int prom = ::pieceValue[m.promoteTo()];
		1133	int optimisticScore = evalScore + capt + prom + deltaPruningMargin;
		1134	if (optimisticScore < alpha) { // Delta pruning
		1135	if ((pos.wMtrlPawns() > 0) && (pos.wMtrl() > capt + pos.wMtrlPawns()) &&
		1136	(pos.bMtrlPawns() > 0) && (pos.bMtrl() > capt + pos.bMtrlPawns())) {
		1137	if (depth -1 > -2) {
		1138	givesCheck = MoveGen::givesCheck(pos, m);
		1139	givesCheckComputed = true;
		1140	}
		1141	if (!givesCheck) {
		1142	if (optimisticScore > bestScore)
		1143	bestScore = optimisticScore;
		1144	continue;
		1145	}
		1146	}
		1147	}
		1148	}
		1149	}
		1150	if (!realInCheckComputed) {
		1151	realInCheck = MoveGen::inCheck(pos);
		1152	realInCheckComputed = true;
		1153	}
		1154	if (!MoveGen::isLegal(pos, m, realInCheck))
		1155	continue;
		1156
		1157	if (!givesCheckComputed && (depth - 1 > -2))
		1158	givesCheck = MoveGen::givesCheck(pos, m);
		1159	const bool nextInCheck = (depth - 1) > -2 ? givesCheck : false;
		1160
		1161	pos.makeMove(m, ui);
		1162	totalNodes++;
		1163	nodesToGo--;
		1164	score = -quiesce(-beta, -alpha, ply + 1, depth - 1, nextInCheck);
		1165	pos.unMakeMove(m, ui);
		1166	if (score > bestScore) {
		1167	bestScore = score;
		1168	if (score > alpha) {
		1169	if (depth == 0) {
		1170	SearchTreeInfo& sti = searchTreeInfo[ply];
		1171	sti.bestMove.setMove(m.from(), m.to(), m.promoteTo(), score);
		1172	}
		1173	alpha = score;
		1174	if (alpha >= beta)
		1175	return alpha;
		1176	}
		1177	}
		1178	}
		1179	return bestScore;
		1180	}
		1181
		1182
		1183	int
		1184	Search::SEE(const Move& m) {
		1185	int captures[64]; // Value of captured pieces
		1186
		1187	const int kV = ::kV;
		1188
		1189	const int square = m.to();
		1190	if (square == pos.getEpSquare()) {
		1191	captures[0] = ::pV;
		1192	} else {
		1193	captures[0] = ::pieceValue[pos.getPiece(square)];
		1194	if (captures[0] == kV)
		1195	return kV;
		1196	}
		1197	int nCapt = 1; // Number of entries in captures[]
		1198
		1199	UndoInfo ui;
		1200	pos.makeSEEMove(m, ui);
		1201	bool white = pos.isWhiteMove();
		1202	int valOnSquare = ::pieceValue[pos.getPiece(square)];
		1203	U64 occupied = pos.occupiedBB();
		1204	while (true) {
		1205	int bestValue = std::numeric_limits<int>::max();
		1206	U64 atk;
		1207	if (white) {
		1208	atk = BitBoard::bPawnAttacks[square] & pos.pieceTypeBB(Piece::WPAWN) & occupied;
		1209	if (atk != 0) {
		1210	bestValue = ::pV;
		1211	} else {
		1212	atk = BitBoard::knightAttacks[square] & pos.pieceTypeBB(Piece::WKNIGHT) & occupied;
		1213	if (atk != 0) {
		1214	bestValue = ::nV;
		1215	} else {
		1216	U64 bAtk = BitBoard::bishopAttacks(square, occupied) & occupied;
		1217	atk = bAtk & pos.pieceTypeBB(Piece::WBISHOP);
		1218	if (atk != 0) {
		1219	bestValue = ::bV;
		1220	} else {
		1221	U64 rAtk = BitBoard::rookAttacks(square, occupied) & occupied;
		1222	atk = rAtk & pos.pieceTypeBB(Piece::WROOK);
		1223	if (atk != 0) {
		1224	bestValue = ::rV;
		1225	} else {
		1226	atk = (bAtk \| rAtk) & pos.pieceTypeBB(Piece::WQUEEN);
		1227	if (atk != 0) {
		1228	bestValue = ::qV;
		1229	} else {
		1230	atk = BitBoard::kingAttacks[square] & pos.pieceTypeBB(Piece::WKING) & occupied;
		1231	if (atk != 0) {
		1232	bestValue = kV;
		1233	} else {
		1234	break;
		1235	}
		1236	}
		1237	}
		1238	}
		1239	}
		1240	}
		1241	} else {
		1242	atk = BitBoard::wPawnAttacks[square] & pos.pieceTypeBB(Piece::BPAWN) & occupied;
		1243	if (atk != 0) {
		1244	bestValue = ::pV;
		1245	} else {
		1246	atk = BitBoard::knightAttacks[square] & pos.pieceTypeBB(Piece::BKNIGHT) & occupied;
		1247	if (atk != 0) {
		1248	bestValue = ::nV;
		1249	} else {
		1250	U64 bAtk = BitBoard::bishopAttacks(square, occupied) & occupied;
		1251	atk = bAtk & pos.pieceTypeBB(Piece::BBISHOP);
		1252	if (atk != 0) {
		1253	bestValue = ::bV;
		1254	} else {
		1255	U64 rAtk = BitBoard::rookAttacks(square, occupied) & occupied;
		1256	atk = rAtk & pos.pieceTypeBB(Piece::BROOK);
		1257	if (atk != 0) {
		1258	bestValue = ::rV;
		1259	} else {
		1260	atk = (bAtk \| rAtk) & pos.pieceTypeBB(Piece::BQUEEN);
		1261	if (atk != 0) {
		1262	bestValue = ::qV;
		1263	} else {
		1264	atk = BitBoard::kingAttacks[square] & pos.pieceTypeBB(Piece::BKING) & occupied;
		1265	if (atk != 0) {
		1266	bestValue = kV;
		1267	} else {
		1268	break;
		1269	}
		1270	}
		1271	}
		1272	}
		1273	}
		1274	}
		1275	}
		1276	captures[nCapt++] = valOnSquare;
		1277	if (valOnSquare == kV)
		1278	break;
		1279	valOnSquare = bestValue;
		1280	occupied &= ~(atk & (0-atk)); // Pierre-Marie Baty -- signedness fix
		1281	white = !white;
		1282	}
		1283	pos.unMakeSEEMove(m, ui);
		1284
		1285	int score = 0;
		1286	for (int i = nCapt - 1; i > 0; i--)
		1287	score = std::max(0, captures[i] - score);
		1288	return captures[0] - score;
		1289	}
		1290
		1291	void
		1292	Search::scoreMoveList(MoveList& moves, int ply, int startIdx) {
		1293	for (int i = startIdx; i < moves.size; i++) {
		1294	Move& m = moves[i];
		1295	bool isCapture = (pos.getPiece(m.to()) != Piece::EMPTY) \|\| (m.promoteTo() != Piece::EMPTY);
		1296	int score = 0;
		1297	if (isCapture) {
		1298	int seeScore = signSEE(m);
		1299	int v = pos.getPiece(m.to());
		1300	int a = pos.getPiece(m.from());
		1301	score = Evaluate::pieceValueOrder[v] * 8 - Evaluate::pieceValueOrder[a];
		1302	if (seeScore > 0)
		1303	score += 100;
		1304	else if (seeScore == 0)
		1305	score += 50;
		1306	else
		1307	score -= 50;
		1308	score *= 100;
		1309	}
		1310	int ks = kt.getKillerScore(ply, m);
		1311	if (ks > 0) {
		1312	score += ks + 50;
		1313	} else {
		1314	int hs = ht.getHistScore(pos, m);
		1315	score += hs;
		1316	}
		1317	m.setScore(score);
		1318	}
		1319	}
		1320
		1321	bool
		1322	Search::selectHashMove(MoveList& moves, const Move& hashMove) {
		1323	for (int i = 0; i < moves.size; i++) {
		1324	Move& m = moves[i];
		1325	if (m.equals(hashMove)) {
		1326	m.setScore(10000);
		1327	std::swap(moves[i], moves[0]);
		1328	return true;
		1329	}
		1330	}
		1331	return false;
		1332	}
		1333
		1334	void
		1335	Search::initNodeStats() {
		1336	nodesByPly.clear();
		1337	nodesByDepth.clear();
		1338	}
		1339
		1340	void
		1341	Search::setThreadNo(int tNo) {
		1342	threadNo = tNo;
		1343	if (threadNo > 0)
		1344	nodesBetweenTimeCheck = 1000;
		1345	mainNumaNode = Numa::instance().isMainNode(threadNo);
		1346	}

Subversion Repositories Games.Chess Giants

Games.Chess Giants/engine-texel/search.cpp – Rev 99