WebSVN – Games.Chess Giants – Blame – /engine-protector (BROKEN)/search.c

Rev	Author	Line No.	Line
112	pmbaty	1	/*
		2	Protector -- a UCI chess engine
		3
		4	Copyright (C) 2009-2010 Raimund Heid (Raimund_Heid@yahoo.com)
		5
		6	This program is free software: you can redistribute it and/or modify
		7	it under the terms of the GNU General Public License as published by
		8	the Free Software Foundation, either version 3 of the License, or
		9	(at your option) any later version.
		10
		11	This program is distributed in the hope that it will be useful,
		12	but WITHOUT ANY WARRANTY; without even the implied warranty of
		13	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
		14	GNU General Public License for more details.
		15
		16	You should have received a copy of the GNU General Public License
		17	along with this program. If not, see <http://www.gnu.org/licenses/>.
		18
		19	*/
		20
		21	#include <stdio.h>
		22	#include <stdlib.h>
		23	#include <string.h>
		24	#include <assert.h>
		25	#include <time.h>
		26	#include <math.h>
		27	#include "search.h"
		28	#include "matesearch.h"
		29	#include "io.h"
		30	#include "movegeneration.h"
		31	#include "hash.h"
		32	#include "evaluation.h"
		33	#include "book.h"
		34	#include "coordination.h"
		35	#include "xboard.h"
		36
		37	#ifdef INCLUDE_TABLEBASE_ACCESS
		38	#include "tablebase.h"
		39	#endif
		40
		41	/* #define DEBUG_THREAD_COORDINATION */
		42
		43	extern bool resetSharedHashtable;
		44	const int HASH_DEPTH_OFFSET = 3;
		45	const UINT64 GUI_NODE_COUNT_MIN = 250000;
		46
		47	#define NUM_FUTILITY_MARGIN_VALUES 13
		48	#define NUM_LOG_VALUES 256
		49	INT32 checkTimeCount = 0;
		50
		51	int quietMoveCountLimit[2][32]; /* number of quiet moves to be examined @ specific restDepth */
		52	int quietPvMoveReduction[64][64]; /* [restDepth][moveCount] */
		53	int quietMoveReduction[2][64][64]; /* [variationType][restDepth][moveCount] */
		54	int futilityMargin[NUM_FUTILITY_MARGIN_VALUES + 1]; /* [restDepth] */
		55	int maxPieceValue[16]; /* the maximal value of a piece type */
		56
		57	/* Prototypes */
		58	static int searchBest(Variation * variation, int alpha, int beta,
		59	const int ply, const int restDepth, const bool pvNode,
		60	const bool cutNode, Move * bestMove, Move excludeMove,
		61	const bool tryEarlyPrunings); // Pierre-Marie Baty -- missing const in prototype
		62
		63	static bool moveIsQuiet(const Move move, const Position * position)
		64	{
		65	return (bool) (position->piece[getToSquare(move)] == NO_PIECE &&
		66	getNewPiece(move) == NO_PIECE &&
		67	(getToSquare(move) != position->enPassantSquare \|\|
		68	pieceType(position->piece[getFromSquare(move)]) != PAWN));
		69	}
		70
		71	static void checkTerminationConditions(Variation * variation)
		72	{
		73	if (variation->searchStatus == SEARCH_STATUS_RUNNING)
		74	{
		75	if (variation->terminate != FALSE &&
		76	(variation->iteration > 1 \|\| variation->threadNumber > 0))
		77	{
		78	variation->searchStatus = SEARCH_STATUS_TERMINATE;
		79	}
		80	}
		81	}
		82
		83	bool checkNodeExclusion(int restDepth)
		84	{
		85	return restDepth >= 6 * DEPTH_RESOLUTION && getNumberOfThreads() > 1;
		86	}
		87
		88	static bool hasDangerousPawns(const Position * position, const Color color)
		89	{
		90	if (color == WHITE)
		91	{
		92	return (bool)
		93	((position->piecesOfType[WHITE_PAWN] & squaresOfRank[RANK_7]) !=
		94	EMPTY_BITBOARD);
		95	}
		96	else
		97	{
		98	return (bool)
		99	((position->piecesOfType[BLACK_PAWN] & squaresOfRank[RANK_2]) !=
		100	EMPTY_BITBOARD);
		101	}
		102	}
		103
		104	int getEvalValue(Variation * variation)
		105	{
		106	EvaluationBase base;
		107
		108	base.ownColor = variation->ownColor;
		109	return
		110	getValue(&variation->singlePosition, &base, variation->pawnHashtable,
		111	variation->kingsafetyHashtable);
		112	}
		113
		114	static int getStaticValue(Variation * variation, const int ply)
		115	{
		116	PlyInfo *pi = &variation->plyInfo[ply];
		117
		118	if (pi->staticValueAvailable == FALSE)
		119	{
		120	EvaluationBase base;
		121
		122	base.ownColor = variation->ownColor;
		123	pi->staticValue = pi->refinedStaticValue =
		124	getValue(&variation->singlePosition, &base, variation->pawnHashtable,
		125	variation->kingsafetyHashtable);
		126	pi->staticValueAvailable = TRUE;
		127	}
		128	else
		129	{
		130	assert(pi->staticValue == getEvalValue(variation));
		131	}
		132
		133	return pi->staticValue;
		134	}
		135
		136	static int getRefinedStaticValue(Variation * variation, const int ply)
		137	{
		138	PlyInfo *pi = &variation->plyInfo[ply];
		139
		140	if (pi->staticValueAvailable == FALSE)
		141	{
		142	EvaluationBase base;
		143
		144	base.ownColor = variation->ownColor;
		145	pi->staticValue = pi->refinedStaticValue =
		146	getValue(&variation->singlePosition, &base, variation->pawnHashtable,
		147	variation->kingsafetyHashtable);
		148	pi->staticValueAvailable = TRUE;
		149	}
		150	else
		151	{
		152	assert(pi->staticValue == getEvalValue(variation));
		153	}
		154
		155	return pi->refinedStaticValue;
		156	}
		157
		158	static void updateGains(Variation * variation, const int ply)
		159	{
		160	if (variation->plyInfo[ply].gainsUpdated == FALSE &&
		161	variation->plyInfo[ply - 1].quietMove != FALSE)
		162	{
		163	const int moveIndex = variation->plyInfo[ply - 1].indexCurrentMove;
		164	INT16 *storedGain = &variation->positionalGain[moveIndex];
		165	const INT16 currentDiff = (INT16)
		166	(getStaticValue(variation, ply) +
		167	variation->plyInfo[ply - 1].staticValue);
		168
		169	*storedGain =
		170	(currentDiff >= (storedGain) ? currentDiff : (storedGain) - 1);
		171	}
		172
		173	variation->plyInfo[ply].gainsUpdated = TRUE;
		174	}
		175
		176	static void updateCounterMoves(Variation * variation, const int ply,
		177	Move counterMove)
		178	{
		179	if (variation->plyInfo[ply - 1].currentMove != NULLMOVE)
		180	{
		181	const int moveIndex = variation->plyInfo[ply - 1].indexCurrentMove;
		182
		183	if (counterMove != variation->counterMove1[moveIndex])
		184	{
		185	variation->counterMove2[moveIndex] =
		186	variation->counterMove1[moveIndex];
		187	variation->counterMove1[moveIndex] = counterMove;
		188	}
		189	}
		190	}
		191
		192	static void updateFollowupMoves(Variation * variation, const int ply,
		193	Move followupMove)
		194	{
		195	if (variation->plyInfo[ply - 2].currentMove != NULLMOVE)
		196	{
		197	const int moveIndex = variation->plyInfo[ply - 2].indexCurrentMove;
		198
		199	if (followupMove != variation->followupMove1[moveIndex])
		200	{
		201	variation->followupMove2[moveIndex] =
		202	variation->followupMove1[moveIndex];
		203	variation->followupMove1[moveIndex] = followupMove;
		204	}
		205	}
		206	}
		207
		208	static bool positionIsWellKnown(Variation * variation,
		209	Position * position,
		210	const UINT64 hashKey,
		211	Hashentry ** bestTableHit,
		212	const int ply, const int alpha,
		213	const int beta, const int restDepth,
		214	const bool pvNode,
		215	const bool updateGainValues,
		216	Move * hashmove,
		217	const Move excludeMove, int *value)
		218	{
		219	Hashentry *tableHit = getHashentry(getSharedHashtable(),
		220	hashKey);
		221
		222	if (tableHit != NULL)
		223	{ /* 45% */
		224	const int importance = getHashentryImportance(tableHit);
		225	const int flag = getHashentryFlag(tableHit);
		226	const int hashEntryValue =
		227	calcEffectiveValue(getHashentryValue(tableHit), ply);
		228	PlyInfo *pi = &variation->plyInfo[ply];
		229
		230	*bestTableHit = tableHit;
		231	*value = hashEntryValue;
		232
		233	/*
		234	if (getHashentryStaticValue(tableHit) != getStaticValue(variation, ply))
		235	{
		236	logDebug("hv=%d sv=%d ev=%d\n", getHashentryStaticValue(tableHit),
		237	getStaticValue(variation, ply), getEvalValue(variation));
		238	dumpVariation(variation);
		239	}
		240	*/
		241
		242	assert(getHashentryStaticValue(tableHit) ==
		243	getStaticValue(variation, ply));
		244
		245	if (pi->staticValueAvailable == FALSE)
		246	{
		247	pi->staticValue = pi->refinedStaticValue =
		248	getHashentryStaticValue(tableHit);
		249	pi->staticValueAvailable = TRUE;
		250
		251	if (updateGainValues)
		252	{
		253	updateGains(variation, ply);
		254	}
		255	}
		256
		257	if (pvNode == FALSE && excludeMove != NULLMOVE &&
		258	restDepth <= importance && flag != HASHVALUE_EVAL)
		259	{ /* 99% */
		260	assert(flag == HASHVALUE_UPPER_LIMIT \|\|
		261	flag == HASHVALUE_EXACT \|\| flag == HASHVALUE_LOWER_LIMIT);
		262	assert(hashEntryValue >= VALUE_MATED &&
		263	hashEntryValue < -VALUE_MATED);
		264
		265	switch (flag)
		266	{
		267	case HASHVALUE_UPPER_LIMIT:
		268	if (hashEntryValue <= alpha)
		269	{
		270	*value = (hashEntryValue <= VALUE_MATED ?
		271	alpha : hashEntryValue);
		272
		273	return TRUE;
		274	}
		275
		276	if (restDepth >= HASH_DEPTH_OFFSET &&
		277	hashEntryValue < getStaticValue(variation, ply))
		278	{
		279	variation->plyInfo[ply].refinedStaticValue = hashEntryValue;
		280	}
		281	break;
		282
		283	case HASHVALUE_EXACT:
		284	*value = hashEntryValue;
		285
		286	return TRUE;
		287
		288	case HASHVALUE_LOWER_LIMIT:
		289	if (hashEntryValue >= beta)
		290	{
		291	*value = (hashEntryValue >= -VALUE_MATED ?
		292	beta : hashEntryValue);
		293
		294	return TRUE;
		295	}
		296
		297	if (restDepth >= HASH_DEPTH_OFFSET &&
		298	hashEntryValue > getStaticValue(variation, ply))
		299	{
		300	variation->plyInfo[ply].refinedStaticValue = hashEntryValue;
		301	}
		302	break;
		303
		304	default:;
		305	}
		306	}
		307	}
		308
		309	if (*bestTableHit != 0)
		310	{
		311	hashmove = (Move) getHashentryMove(bestTableHit);
		312
		313	if (*hashmove != NO_MOVE)
		314	{ /* 81% */
		315	assert(moveIsPseudoLegal(position, *hashmove));
		316
		317	if (moveIsPseudoLegal(position, *hashmove))
		318	{
		319	assert(moveIsLegal(position, *hashmove));
		320	}
		321	else
		322	{
		323	*hashmove = NO_MOVE;
		324	}
		325	}
		326	}
		327
		328	return FALSE;
		329	}
		330
		331	static int searchBestQuiescence(Variation * variation, int alpha, int beta,
		332	const int ply, const int restDepth,
		333	Move * bestMove, const bool pvNode)
		334	{
		335	const int oldAlpha = alpha;
		336	UINT8 hashentryFlag;
		337	UINT8 hashDepth = (restDepth >= 0 ? 2 : 1);
		338	Position *position = &variation->singlePosition;
		339	int best = VALUE_MATED, currentValue = VALUE_MATED, historyLimit, i;
		340	const int VALUE_MATE_HERE = -VALUE_MATED - ply + 1;
		341	const int VALUE_MATED_HERE = VALUE_MATED + ply;
		342	Movelist movelist;
		343	Move currentMove, bestReply, hashmove = NO_MOVE;
		344	const bool inCheck = variation->plyInfo[ply - 1].currentMoveIsCheck;
		345	EvaluationBase base;
		346	Hashentry *bestTableHit = 0;
		347	int hashValue;
		348
		349	assert(alpha >= VALUE_MATED && alpha <= -VALUE_MATED);
		350	assert(beta >= VALUE_MATED && beta <= -VALUE_MATED);
		351	assert(alpha < beta);
		352	assert(ply > 0 && ply < MAX_DEPTH);
		353	assert(restDepth < DEPTH_RESOLUTION);
		354	assert(passiveKingIsSafe(position));
		355	assert((inCheck != FALSE) == (activeKingIsSafe(position) == FALSE));
		356
		357	*bestMove = NO_MOVE;
		358	variation->plyInfo[ply].quietMove = FALSE; /* avoid subsequent gain updates */
		359	variation->plyInfo[ply].pv.length = 0;
		360	variation->plyInfo[ply].pv.move[0] = NO_MOVE;
		361	movelist.positionalGain = &(variation->positionalGain[0]);
		362
		363	variation->nodes++;
		364	checkTerminationConditions(variation);
		365
		366	if (variation->searchStatus != SEARCH_STATUS_RUNNING &&
		367	variation->iteration > 1)
		368	{
		369	return 0;
		370	}
		371
		372	/* Check for a draw according to the 50-move-rule */
		373	/* ---------------------------------------------- */
		374	if (position->halfMoveClock > 100)
		375	{
		376	return variation->drawScore[position->activeColor];
		377	}
		378
		379	/* Check for a draw by repetition. */
		380	/* ------------------------------- */
		381	historyLimit = POSITION_HISTORY_OFFSET + variation->ply -
		382	position->halfMoveClock;
		383
		384	assert(historyLimit >= 0);
		385
		386	for (i = POSITION_HISTORY_OFFSET + variation->ply - 4;
		387	i >= historyLimit; i -= 2)
		388	{
		389	if (position->hashKey == variation->positionHistory[i])
		390	{
		391	return variation->drawScore[position->activeColor];
		392	}
		393	}
		394
		395	/* Probe the transposition table */
		396	/* ----------------------------- */
		397
		398	if (positionIsWellKnown(variation, position, position->hashKey,
		399	&bestTableHit, ply, alpha, beta,
		400	hashDepth, pvNode, FALSE,
		401	&hashmove, NO_MOVE, &hashValue))
		402	{
		403	*bestMove = hashmove;
		404
		405	return hashValue;
		406	}
		407
		408	if (hashmove != NO_MOVE && inCheck == FALSE &&
		409	moveIsQuiet(hashmove, position))
		410	{
		411	hashmove = NO_MOVE;
		412	}
		413
		414	if (inCheck == FALSE)
		415	{
		416	const bool staticValueAvailable =
		417	variation->plyInfo[ply].staticValueAvailable;
		418
		419	assert(flipTest(position,
		420	variation->pawnHashtable,
		421	variation->kingsafetyHashtable) != FALSE);
		422
		423	if (staticValueAvailable == FALSE)
		424	{
		425	base.ownColor = variation->ownColor;
		426	best = getValue(position,
		427	&base,
		428	variation->pawnHashtable,
		429	variation->kingsafetyHashtable);
		430	variation->plyInfo[ply].staticValue =
		431	variation->plyInfo[ply].refinedStaticValue = best;
		432	variation->plyInfo[ply].staticValueAvailable = TRUE;
		433	}
		434	else
		435	{
		436	best = variation->plyInfo[ply].staticValue;
		437	}
		438
		439	if (bestTableHit != 0)
		440	{
		441	const int flag = getHashentryFlag(bestTableHit);
		442	const int requiredFlag = (hashValue > best ?
		443	HASHVALUE_LOWER_LIMIT :
		444	HASHVALUE_UPPER_LIMIT);
		445
		446	if (flag == requiredFlag)
		447	{
		448	best = hashValue;
		449	}
		450	}
		451
		452	if (best > alpha)
		453	{
		454	alpha = best;
		455
		456	if (best >= beta)
		457	{
		458	if (staticValueAvailable == FALSE)
		459	{
		460	UINT8 hashentryFlag = HASHVALUE_EVAL;
		461
		462	setHashentry(getSharedHashtable(), position->hashKey,
		463	calcHashtableValue(best, ply),
		464	0, packedMove(NO_MOVE), hashentryFlag,
		465	(INT16) getStaticValue(variation, ply));
		466	}
		467
		468	return best;
		469	}
		470	}
		471
		472	currentValue = best;
		473	}
		474
		475	if (ply >= MAX_DEPTH)
		476	{
		477	assert(flipTest(position,
		478	variation->pawnHashtable,
		479	variation->kingsafetyHashtable) != FALSE);
		480
		481	return getStaticValue(variation, ply);
		482	}
		483
		484	if (alpha < VALUE_MATED_HERE && inCheck == FALSE)
		485	{
		486	alpha = VALUE_MATED_HERE;
		487
		488	if (alpha >= beta)
		489	{
		490	return VALUE_MATED_HERE;
		491	}
		492	}
		493
		494	if (beta > VALUE_MATE_HERE)
		495	{
		496	beta = VALUE_MATE_HERE;
		497
		498	if (beta <= alpha)
		499	{
		500	return VALUE_MATE_HERE;
		501	}
		502	}
		503
		504	initQuiescenceMovelist(&movelist, &variation->singlePosition,
		505	&variation->plyInfo[ply],
		506	&variation->historyValue[0],
		507	hashmove, restDepth, inCheck);
		508	initializePlyInfo(variation);
		509
		510	while ((currentMove = getNextMove(&movelist)) != NO_MOVE)
		511	{
		512	int value, newDepth =
		513	(inCheck ? restDepth : restDepth - DEPTH_RESOLUTION);
		514	int optValue = currentValue + 43 +
		515	maxPieceValue[position->piece[getToSquare(currentMove)]];
		516	const Square toSquare = getToSquare(currentMove);
		517
		518	if (pvNode == FALSE && inCheck == FALSE && optValue < alpha &&
		519	optValue > VALUE_ALMOST_MATED &&
		520	movesAreEqual(currentMove, hashmove) == FALSE &&
		521	getNewPiece(currentMove) != (Piece) QUEEN &&
		522	numberOfNonPawnPieces(position, position->activeColor) > 1 &&
		523	(pieceType(position->piece[getFromSquare(currentMove)]) != PAWN \|\|
		524	colorRank(position->activeColor, toSquare) != RANK_7))
		525	{
		526	const bool enPassant = (bool)
		527	(toSquare == position->enPassantSquare &&
		528	pieceType(position->piece[getFromSquare(currentMove)]) == PAWN);
		529
		530	if (getNewPiece(currentMove) != NO_PIECE)
		531	{
		532	optValue +=
		533	maxPieceValue[getNewPiece(currentMove)] - basicValue[PAWN];
		534	}
		535
		536	if (enPassant)
		537	{
		538	optValue += maxPieceValue[PAWN];
		539	}
		540
		541	if (optValue < alpha && moveIsCheck(currentMove, position) == FALSE)
		542	{
		543	best = max(best, optValue);
		544
		545	continue;
		546	}
		547	}
		548
		549	assert(moveIsPseudoLegal(position, currentMove));
		550
		551	if (makeMoveFast(variation, currentMove) != 0 \|\|
		552	passiveKingIsSafe(&variation->singlePosition) == FALSE)
		553	{
		554	unmakeLastMove(variation);
		555
		556	continue;
		557	}
		558
		559	variation->plyInfo[ply].currentMoveIsCheck =
		560	activeKingIsSafe(&variation->singlePosition) == FALSE;
		561
		562	assert(position->piece[getToSquare(currentMove)] != NO_PIECE \|\|
		563	(getToSquare(currentMove) == position->enPassantSquare &&
		564	position->piece[getFromSquare(currentMove)] ==
		565	(PAWN \| position->activeColor)) \|\|
		566	getNewPiece(currentMove) != NO_PIECE \|\|
		567	inCheck \|\| variation->plyInfo[ply].currentMoveIsCheck);
		568
		569	assert(inCheck != FALSE \|\|
		570	basicValue[position->piece[getFromSquare(currentMove)]] <=
		571	basicValue[position->piece[getToSquare(currentMove)]] \|\|
		572	seeMove(position, currentMove) >= 0);
		573
		574	value = -searchBestQuiescence(variation, -beta, -alpha, ply + 1,
		575	newDepth, &bestReply, pvNode);
		576
		577	unmakeLastMove(variation);
		578
		579	if (variation->searchStatus != SEARCH_STATUS_RUNNING &&
		580	variation->iteration > 1)
		581	{
		582	return 0;
		583	}
		584
		585	if (value > best)
		586	{
		587	best = value;
		588
		589	if (best > alpha)
		590	{
		591	alpha = best;
		592	*bestMove = currentMove;
		593
		594	if (pvNode)
		595	{
		596	appendMoveToPv(&(variation->plyInfo[ply].pv),
		597	&(variation->plyInfo[ply - 1].pv), currentMove);
		598	}
		599
		600	if (best >= beta)
		601	{
		602	break;
		603	}
		604	}
		605	}
		606	}
		607
		608	if (best == VALUE_MATED)
		609	{
		610	/* mate */
		611
		612	assert(inCheck != FALSE);
		613
		614	best = VALUE_MATED + ply;
		615	}
		616
		617	/* Store the value in the transposition table. */
		618	/* ------------------------------------------- */
		619	if (best >= beta)
		620	{
		621	hashentryFlag = HASHVALUE_LOWER_LIMIT;
		622	}
		623	else
		624	{
		625	hashentryFlag = (best > oldAlpha && pvNode ?
		626	HASHVALUE_EXACT : HASHVALUE_UPPER_LIMIT);
		627	}
		628
		629	setHashentry(getSharedHashtable(), position->hashKey,
		630	calcHashtableValue(best, ply),
		631	hashDepth, packedMove(*bestMove), hashentryFlag,
		632	(INT16) getStaticValue(variation, ply));
		633
		634	return best;
		635	}
		636
		637	static bool moveIsCastling(const Move move, const Position * position)
		638	{
		639	return (bool) (pieceType(position->piece[getFromSquare(move)]) == KING &&
		640	distance(getFromSquare(move), getToSquare(move)) == 2);
		641	}
		642
		643	static bool isPassedPawnMove(const Square pawnSquare,
		644	const Square targetSquare,
		645	const Position * position)
		646	{
		647	const Piece piece = position->piece[pawnSquare];
		648
		649	if (pieceType(piece) == PAWN)
		650	{
		651	return pawnIsPassed(position, targetSquare, pieceColor(piece));
		652	}
		653	else
		654	{
		655	return FALSE;
		656	}
		657	}
		658
		659	static int getSingleMoveExtensionDepth(const bool pvNode)
		660	{
		661	return (pvNode ? 6 : 8) * DEPTH_RESOLUTION;
		662	}
		663
		664	static int searchBest(Variation * variation, int alpha, int beta,
		665	const int ply, const int restDepth, const bool pvNode,
		666	const bool cutNode, Move * bestMove, Move excludeMove,
		667	const bool tryEarlyPrunings)
		668	{
		669	Position *position = &variation->singlePosition;
		670	int best = VALUE_MATED;
		671	const int VALUE_MATE_HERE = -VALUE_MATED - ply + 1;
		672	const int VALUE_MATED_HERE = VALUE_MATED + ply;
		673	const int numPieces =
		674	numberOfNonPawnPieces(position, position->activeColor);
		675	Movelist movelist;
		676	UINT8 hashentryFlag;
		677	int i, historyLimit, numMovesPlayed = 0;
		678	Move hashmove = NO_MOVE;
		679	Hashentry *bestTableHit = 0;
		680	Move currentMove, bestReply;
		681	const bool inCheck = variation->plyInfo[ply - 1].currentMoveIsCheck;
		682	const int rdBasic = restDepth / DEPTH_RESOLUTION;
		683	bool singularExtensionNode = FALSE;
		684	int hashEntryValue = 0;
		685	const UINT64 hashKey = position->hashKey;
		686	const bool cutsAreAllowed = (bool) (abs(beta) < -(VALUE_ALMOST_MATED));
		687	int variationType = (ply < 2 ? 1 : 0);
		688	int quietMoveIndex[MAX_MOVES_PER_POSITION], quietMoveCount = 0;
		689	int deferCount = 0;
		690
		691	*bestMove = NO_MOVE;
		692	variation->plyInfo[ply].quietMove = FALSE; /* avoid subsequent gain updates */
		693	variation->plyInfo[ply].isHashMove = FALSE;
		694	variation->plyInfo[ply].pv.length = 0;
		695	variation->plyInfo[ply].pv.move[0] = NO_MOVE;
		696	movelist.positionalGain = &(variation->positionalGain[0]);
		697
		698	if (ply + 1 > variation->selDepth)
		699	{
		700	variation->selDepth = ply + 1;
		701	}
		702
		703	assert(alpha >= VALUE_MATED && alpha <= -VALUE_MATED);
		704	assert(beta >= VALUE_MATED && beta <= -VALUE_MATED);
		705	assert(alpha < beta);
		706	assert(ply > 0 && ply < MAX_DEPTH);
		707	assert(passiveKingIsSafe(position));
		708	assert((inCheck != FALSE) == (activeKingIsSafe(position) == FALSE));
		709
		710	/* Check for a draw according to the 50-move-rule */
		711	/* ---------------------------------------------- */
		712	if (position->halfMoveClock > 100)
		713	{
		714	return variation->drawScore[position->activeColor];
		715	}
		716
		717	/* Check for a draw by repetition. */
		718	/* ------------------------------- */
		719	historyLimit = POSITION_HISTORY_OFFSET + variation->ply -
		720	position->halfMoveClock;
		721
		722	assert(historyLimit >= 0);
		723
		724	for (i = POSITION_HISTORY_OFFSET + variation->ply - 4;
		725	i >= historyLimit; i -= 2)
		726	{
		727	if (position->hashKey == variation->positionHistory[i])
		728	{
		729	return variation->drawScore[position->activeColor];
		730	}
		731	}
		732
		733	if (restDepth < DEPTH_RESOLUTION)
		734	{ /* 63% */
		735	int qsValue;
		736
		737	qsValue =
		738	searchBestQuiescence(variation, alpha, beta, ply, 0, bestMove,
		739	pvNode);
		740
		741	if (inCheck == FALSE &&
		742	variation->plyInfo[ply].staticValueAvailable != FALSE)
		743	{
		744	updateGains(variation, ply);
		745	}
		746
		747	return qsValue;
		748	}
		749
		750	variation->nodes++;
		751	checkTerminationConditions(variation);
		752
		753	if (variation->searchStatus != SEARCH_STATUS_RUNNING &&
		754	variation->iteration > 1)
		755	{
		756	return 0;
		757	}
		758
		759	#ifdef INCLUDE_TABLEBASE_ACCESS
		760	/* Probe the tablebases in case of reduced material */
		761	/* ------------------------------------------------ */
		762	if (ply >= 2 && (pvNode \|\| restDepth >= 10 * DEPTH_RESOLUTION) &&
		763	position->numberOfPieces[WHITE] +
		764	position->numberOfPieces[BLACK] <= 6 &&
		765	excludeMove == NO_MOVE && tbAvailable != FALSE)
		766	{
		767	int tbValue;
		768
		769	tbValue = probeTablebase(position);
		770
		771	if (tbValue != TABLEBASE_ERROR)
		772	{
		773	variation->tbHits++;
		774
		775	if (tbValue == 0)
		776	{
		777	return variation->drawScore[position->activeColor];
		778	}
		779
		780	return (tbValue > 0 ? tbValue - ply : tbValue + ply);
		781	}
		782	}
		783	#endif
		784
		785	/* Probe the transposition table */
		786	/* ----------------------------- */
		787	if (excludeMove == NO_MOVE)
		788	{
		789	int hashValue;
		790
		791	if (positionIsWellKnown(variation, position, hashKey,
		792	&bestTableHit, ply, alpha, beta,
		793	restDepth + HASH_DEPTH_OFFSET, pvNode,
		794	inCheck == FALSE, &hashmove, excludeMove,
		795	&hashValue))
		796	{
		797	*bestMove = hashmove;
		798
		799	if (hashValue >= beta && *bestMove != NO_MOVE &&
		800	moveIsQuiet(*bestMove, position))
		801	{
		802	Move killerMove = *bestMove;
		803	const Piece movingPiece =
		804	position->piece[getFromSquare(killerMove)];
		805
		806	setMoveValue(&killerMove, movingPiece);
		807	registerKillerMove(&variation->plyInfo[ply], killerMove);
		808	}
		809
		810	return hashValue;
		811	}
		812	}
		813
		814	if (inCheck == FALSE)
		815	{
		816	updateGains(variation, ply);
		817	}
		818
		819	if (ply >= 2)
		820	{
		821	if (variation->plyInfo[ply].staticValue >=
		822	variation->plyInfo[ply - 2].staticValue \|\|
		823	variation->plyInfo[ply].staticValueAvailable == FALSE \|\|
		824	variation->plyInfo[ply - 2].staticValueAvailable == FALSE)
		825	{
		826	variationType = 1;
		827	}
		828	}
		829
		830	if (ply >= MAX_DEPTH)
		831	{
		832	return getStaticValue(variation, ply);
		833	}
		834
		835	if (alpha < VALUE_MATED_HERE && inCheck == FALSE)
		836	{
		837	alpha = VALUE_MATED_HERE;
		838
		839	if (alpha >= beta)
		840	{
		841	return VALUE_MATED_HERE;
		842	}
		843	}
		844
		845	if (beta > VALUE_MATE_HERE)
		846	{
		847	beta = VALUE_MATE_HERE;
		848
		849	if (beta <= alpha)
		850	{
		851	return VALUE_MATE_HERE;
		852	}
		853	}
		854
		855	initializePlyInfo(variation);
		856
		857	if (tryEarlyPrunings == FALSE)
		858	{
		859	goto checkAvailableMoves;
		860	}
		861
		862	/* Razoring */
		863	if (pvNode == FALSE && restDepth < 4 * DEPTH_RESOLUTION &&
		864	inCheck == FALSE && hashmove == NO_MOVE && cutsAreAllowed &&
		865	hasDangerousPawns(position, position->activeColor) == FALSE)
		866	{
		867	const int limit = alpha - (204 + 22 * restDepth);
		868
		869	if (getRefinedStaticValue(variation, ply) < limit)
		870	{
		871	const int qsValue =
		872	searchBestQuiescence(variation, limit - 1, limit, ply, 0,
		873	bestMove, pvNode);
		874
		875	if (qsValue < limit)
		876	{
		877	return qsValue;
		878	}
		879	}
		880	}
		881
		882	/* Static nullmove pruning */
		883	if (pvNode == FALSE && restDepth < 4 * DEPTH_RESOLUTION &&
		884	inCheck == FALSE && cutsAreAllowed && excludeMove == NO_MOVE &&
		885	numPieces >= 2 &&
		886	!hasDangerousPawns(position, opponent(position->activeColor)))
		887	{
		888	const int referenceValue =
		889	getRefinedStaticValue(variation, ply) - (40 + 41 * restDepth);
		890
		891	if (referenceValue >= beta)
		892	{
		893	return referenceValue;
		894	}
		895	}
		896
		897	/* Nullmove pruning with verification */
		898	if (restDepth >= 2 * DEPTH_RESOLUTION && inCheck == FALSE &&
		899	pvNode == FALSE && cutsAreAllowed && excludeMove == NO_MOVE &&
		900	numPieces >= 2 && getRefinedStaticValue(variation, ply) >= beta)
		901	{ /* 16-32% */
		902	const int diff = getRefinedStaticValue(variation, ply) - beta;
		903	const int additionalReduction = min(diff / 110, 3) * DEPTH_RESOLUTION;
		904	const int newDepth =
		905	restDepth - 3 * DEPTH_RESOLUTION - restDepth / 4 -
		906	additionalReduction;
		907	const int verificationDepth =
		908	(numPieces >= 3 ? 12 : 6) * DEPTH_RESOLUTION;
		909	int nullValue;
		910
		911	assert(flipTest(position,
		912	variation->pawnHashtable,
		913	variation->kingsafetyHashtable) != FALSE);
		914
		915	makeMoveFast(variation, NULLMOVE);
		916	variation->plyInfo[ply].currentMoveIsCheck = FALSE;
		917	nullValue = -searchBest(variation, -beta, -beta + 1, ply + 1,
		918	newDepth, pvNode, !cutNode, &bestReply,
		919	NO_MOVE, FALSE);
		920	unmakeLastMove(variation);
		921
		922	if (nullValue >= VALUE_MATE_HERE)
		923	{
		924	nullValue = beta;
		925	}
		926
		927	if (nullValue >= beta && newDepth >= DEPTH_RESOLUTION &&
		928	restDepth >= verificationDepth)
		929	{ /* 2% */
		930	const int noNullValue = searchBest(variation, alpha, beta, ply,
		931	newDepth,
		932	FALSE, FALSE, &bestReply,
		933	NULLMOVE, FALSE);
		934
		935	if (noNullValue >= beta)
		936	{ /* 99% */
		937	best = nullValue;
		938
		939	goto storeResult;
		940	}
		941	}
		942	else if (nullValue >= beta)
		943	{ /* 70% */
		944	if (numPieces >= 3)
		945	{
		946	best = nullValue;
		947
		948	goto storeResult;
		949	}
		950	else
		951	{
		952	return nullValue;
		953	}
		954	}
		955	}
		956
		957	/* Try to find a quick refutation of the opponent's previous move */
		958	if (pvNode == FALSE && cutsAreAllowed &&
		959	restDepth >= 5 * DEPTH_RESOLUTION && excludeMove == NO_MOVE &&
		960	inCheck == FALSE)
		961	{
		962	const int limit = beta + 192;
		963	const int staticValue = getRefinedStaticValue(variation, ply);
		964	const Move qrHashmove = (hashmove != NO_MOVE &&
		965	position->piece[getToSquare(hashmove)] !=
		966	NO_PIECE ? hashmove : NO_MOVE);
		967
		968	initCaptureMovelist(&movelist, &variation->singlePosition,
		969	&variation->plyInfo[ply],
		970	&variation->historyValue[0], qrHashmove, inCheck);
		971
		972	while ((currentMove = getNextMove(&movelist)) != NO_MOVE)
		973	{
		974	const Square toSquare = getToSquare(currentMove);
		975	const Piece capturedPiece = position->piece[toSquare];
		976	int moveValue;
		977
		978	if (staticValue + maxPieceValue[capturedPiece] < limit - 38)
		979	{
		980	continue;
		981	}
		982
		983	/* Execute the current move and check if it is legal. */
		984	/* -------------------------------------------------- */
		985	if (makeMoveFast(variation, currentMove) != 0 \|\|
		986	passiveKingIsSafe(&variation->singlePosition) == FALSE)
		987	{
		988	unmakeLastMove(variation);
		989
		990	continue;
		991	}
		992
		993	variation->plyInfo[ply].currentMoveIsCheck =
		994	activeKingIsSafe(&variation->singlePosition) == FALSE;
		995	variation->plyInfo[ply].indexCurrentMove =
		996	historyIndex(currentMove, position);
		997	variation->plyInfo[ply].quietMove = FALSE;
		998	variation->plyInfo[ply].isHashMove = FALSE;
		999
		1000	moveValue = -searchBest(variation, -limit, -limit + 1, ply + 1,
		1001	restDepth - 4 * DEPTH_RESOLUTION, FALSE,
		1002	!cutNode, &bestReply, NO_MOVE, TRUE);
		1003
		1004	unmakeLastMove(variation);
		1005
		1006	if (moveValue >= limit)
		1007	{
		1008	best = moveValue;
		1009	*bestMove = currentMove;
		1010
		1011	goto storeResult;
		1012	}
		1013	}
		1014	}
		1015
		1016	checkAvailableMoves:
		1017
		1018	/* Internal iterative deepening. */
		1019	/* ----------------------------- */
		1020	if (hashmove == NO_MOVE &&
		1021	restDepth >= (pvNode ? 3 : 7) * DEPTH_RESOLUTION &&
		1022	(pvNode \|\| (inCheck == FALSE &&
		1023	getRefinedStaticValue(variation, ply) >= beta - 100)))
		1024	{
		1025	const Move excludeHere =
		1026	(excludeMove != NO_MOVE ? excludeMove : NULLMOVE);
		1027	const int searchDepth =
		1028	(pvNode ? restDepth - 2 * DEPTH_RESOLUTION : restDepth / 2);
		1029
		1030	searchBest(variation, alpha, beta, ply, searchDepth, pvNode,
		1031	TRUE, &bestReply, excludeHere, FALSE);
		1032
		1033	if (moveIsPseudoLegal(position, bestReply))
		1034	{
		1035	hashmove = bestReply;
		1036	}
		1037
		1038	if (hashmove != NO_MOVE && excludeMove == NO_MOVE &&
		1039	restDepth >= getSingleMoveExtensionDepth(pvNode))
		1040	{
		1041	Hashentry *tableHit = getHashentry(getSharedHashtable(),
		1042	variation->singlePosition.
		1043	hashKey);
		1044
		1045	if (tableHit != 0)
		1046	{
		1047	bestTableHit = tableHit;
		1048	}
		1049	}
		1050	}
		1051
		1052	/* Check if the conditions for a singular extension are met */
		1053	if (bestTableHit != 0 && excludeMove == NO_MOVE && hashmove != NO_MOVE)
		1054	{
		1055	const int singleMoveExtensionDepth =
		1056	getSingleMoveExtensionDepth(pvNode);
		1057	/* const int singleMoveExtensionDepth = 8 * DEPTH_RESOLUTION; */
		1058	const int importance =
		1059	getHashentryImportance(bestTableHit) - HASH_DEPTH_OFFSET;
		1060	const int flag = getHashentryFlag(bestTableHit);
		1061
		1062	if (restDepth >= singleMoveExtensionDepth &&
		1063	importance >= restDepth - 3 * DEPTH_RESOLUTION &&
		1064	flag != HASHVALUE_UPPER_LIMIT)
		1065	{
		1066	singularExtensionNode = TRUE;
		1067	hashEntryValue =
		1068	calcEffectiveValue(getHashentryValue(bestTableHit), ply);
		1069	}
		1070	}
		1071
		1072	if (ply >= 1)
		1073	{
		1074	const int moveIndex = variation->plyInfo[ply - 1].indexCurrentMove;
		1075
		1076	variation->plyInfo[ply].killerMove3 =
		1077	variation->counterMove1[moveIndex];
		1078	variation->plyInfo[ply].killerMove4 =
		1079	variation->counterMove2[moveIndex];
		1080	}
		1081	else
		1082	{
		1083	variation->plyInfo[ply].killerMove3 = NO_MOVE;
		1084	variation->plyInfo[ply].killerMove4 = NO_MOVE;
		1085	}
		1086
		1087	if (ply >= 2)
		1088	{
		1089	const int moveIndex = variation->plyInfo[ply - 2].indexCurrentMove;
		1090
		1091	variation->plyInfo[ply].killerMove5 =
		1092	variation->followupMove1[moveIndex];
		1093	variation->plyInfo[ply].killerMove6 =
		1094	variation->followupMove2[moveIndex];
		1095	}
		1096	else
		1097	{
		1098	variation->plyInfo[ply].killerMove5 = NO_MOVE;
		1099	variation->plyInfo[ply].killerMove6 = NO_MOVE;
		1100	}
		1101
		1102	initStandardMovelist(&movelist, &variation->singlePosition,
		1103	&variation->plyInfo[ply],
		1104	&variation->historyValue[0], hashmove, inCheck);
		1105
		1106	/* Ensure that a static value for this ply is available. */
		1107	getStaticValue(variation, ply);
		1108
		1109	/* Loop through all moves in this node. */
		1110	/* ------------------------------------ */
		1111	while ((currentMove = getNextMove(&movelist)) != NO_MOVE)
		1112	{
		1113	const int stage = moveGenerationStage[movelist.currentStage];
		1114	int value = 0, newDepth;
		1115	int extension = 0;
		1116	const int moveIndex = min(63, numMovesPlayed);
		1117	const int depthIndex = min(63, rdBasic);
		1118	const int gain =
		1119	variation->positionalGain[historyIndex(currentMove, position)];
		1120	const int reduction =
		1121	(pvNode ? quietPvMoveReduction[depthIndex][moveIndex] :
		1122	quietMoveReduction[variationType][depthIndex][moveIndex] +
		1123	(cutNode /* \|\| gain < 0 */ ? DEPTH_RESOLUTION : 0));
		1124	bool check;
		1125	const bool quietMove = moveIsQuiet(currentMove, position);
		1126	const Square toSquare = getToSquare(currentMove);
		1127	const Piece capturedPiece = position->piece[toSquare];
		1128	bool reduce = FALSE, nodeWasBlocked = FALSE;
		1129
		1130	if (variation->searchStatus != SEARCH_STATUS_RUNNING &&
		1131	variation->iteration > 1)
		1132	{
		1133	return 0;
		1134	}
		1135
		1136	if (excludeMove != NO_MOVE && movesAreEqual(currentMove, excludeMove))
		1137	{
		1138	assert(excludeMove != NULLMOVE);
		1139
		1140	continue; /* exclude excludeMove */
		1141	}
		1142
		1143	variation->plyInfo[ply].indexCurrentMove =
		1144	historyIndex(currentMove, position);
		1145	variation->plyInfo[ply].quietMove = quietMove;
		1146	variation->plyInfo[ply].isHashMove =
		1147	movesAreEqual(currentMove, hashmove);
		1148
		1149	assert(moveIsPseudoLegal(position, currentMove));
		1150	assert(hashmove == NO_MOVE \|\| numMovesPlayed > 0 \|\|
		1151	movesAreEqual(currentMove, hashmove));
		1152
		1153	/* Optimistic futility cuts */
		1154	if (pvNode == FALSE && inCheck == FALSE && quietMove != FALSE &&
		1155	!isPassedPawnMove(getFromSquare(currentMove), toSquare, position) &&
		1156	!moveIsCastling(currentMove, position) &&
		1157	best > VALUE_ALMOST_MATED && cutsAreAllowed && restDepth < 32)
		1158	{
		1159	bool moveIsRelevant = FALSE;
		1160	const int predictedDepth = restDepth - reduction;
		1161
		1162	if (numMovesPlayed >= quietMoveCountLimit[variationType][restDepth])
		1163	{
		1164	if (simpleMoveIsCheck(position, currentMove))
		1165	{
		1166	moveIsRelevant = TRUE;
		1167	}
		1168	else
		1169	{
		1170	continue;
		1171	}
		1172	}
		1173
		1174	if (moveIsRelevant == FALSE &&
		1175	predictedDepth <= NUM_FUTILITY_MARGIN_VALUES)
		1176	{
		1177	const int futLimit =
		1178	getRefinedStaticValue(variation, ply) + gain +
		1179	futilityMargin[predictedDepth];
		1180
		1181	if (futLimit < beta)
		1182	{
		1183	if (simpleMoveIsCheck(position, currentMove))
		1184	{
		1185	moveIsRelevant = TRUE;
		1186	}
		1187	else
		1188	{
		1189	if (futLimit > best)
		1190	{
		1191	best = futLimit;
		1192	}
		1193
		1194	continue;
		1195	}
		1196	}
		1197	}
		1198
		1199	if (moveIsRelevant == FALSE &&
		1200	predictedDepth < 4 * DEPTH_RESOLUTION &&
		1201	seeMove(position, currentMove) < 0 &&
		1202	simpleMoveIsCheck(position, currentMove) == FALSE)
		1203	{
		1204	continue;
		1205	}
		1206	}
		1207
		1208	/* Execute the current move and check if it is legal. */
		1209	/* -------------------------------------------------- */
		1210	if (makeMoveFast(variation, currentMove) != 0 \|\|
		1211	passiveKingIsSafe(&variation->singlePosition) == FALSE)
		1212	{
		1213	unmakeLastMove(variation);
		1214
		1215	continue;
		1216	}
		1217
		1218	if (numMovesPlayed > 0 && inCheck == FALSE &&
		1219	stage == MGS_REST && deferCount < 10 &&
		1220	checkNodeExclusion(restDepth))
		1221	{
		1222	if (nodeIsInUse(position->hashKey, restDepth))
		1223	{
		1224	deferMove(&movelist, currentMove);
		1225	deferCount++;
		1226	unmakeLastMove(variation);
		1227	continue;
		1228	}
		1229	else
		1230	{
		1231	nodeWasBlocked = setNodeUsage(position->hashKey, restDepth);
		1232	}
		1233	}
		1234
		1235	/* Check the conditions for search extensions and finally */
		1236	/* calculate the rest depth for the next ply. */
		1237	/* ------------------------------------------------------ */
		1238	variation->plyInfo[ply].currentMoveIsCheck = check =
		1239	activeKingIsSafe(&variation->singlePosition) == FALSE;
		1240
		1241	if (check)
		1242	{
		1243	unmakeLastMove(variation);
		1244
		1245	if (seeMove(position, currentMove) >= 0)
		1246	{
		1247	extension = DEPTH_RESOLUTION;
		1248	}
		1249
		1250	makeMoveFast(variation, currentMove);
		1251	}
		1252
		1253	if (pvNode)
		1254	{
		1255	if (pieceType(position->piece[toSquare]) == PAWN &&
		1256	pawnIsPassed(position, toSquare,
		1257	opponent(position->activeColor)))
		1258	{
		1259	extension = DEPTH_RESOLUTION;
		1260	}
		1261	else if (capturedPiece != NO_PIECE &&
		1262	pieceType(capturedPiece) != PAWN &&
		1263	numberOfNonPawnPieces(position, WHITE) ==
		1264	numberOfNonPawnPieces(position, BLACK))
		1265	{
		1266	extension = DEPTH_RESOLUTION;
		1267	}
		1268	}
		1269
		1270	if (singularExtensionNode != FALSE &&
		1271	extension < DEPTH_RESOLUTION &&
		1272	movesAreEqual(currentMove, hashmove))
		1273	{
		1274	const int limitValue = hashEntryValue - (266 * restDepth) / 256;
		1275
		1276	assert(excludeMove == NO_MOVE);
		1277
		1278	if (limitValue > VALUE_ALMOST_MATED &&
		1279	limitValue < -VALUE_ALMOST_MATED)
		1280	{
		1281	int excludeValue;
		1282	PlyInfo pi = variation->plyInfo[ply];
		1283
		1284	unmakeLastMove(variation);
		1285	excludeValue =
		1286	searchBest(variation, limitValue - 1, limitValue, ply,
		1287	restDepth / 2, FALSE, cutNode, &bestReply,
		1288	hashmove, FALSE);
		1289	makeMoveFast(variation, currentMove);
		1290	variation->plyInfo[ply] = pi;
		1291
		1292	if (excludeValue < limitValue)
		1293	{
		1294	extension = DEPTH_RESOLUTION;
		1295	}
		1296	}
		1297	}
		1298
		1299	newDepth = restDepth - DEPTH_RESOLUTION + extension;
		1300
		1301	/* History pruning */
		1302	/* --------------- */
		1303	if (inCheck == FALSE && extension == 0 &&
		1304	restDepth >= 3 * DEPTH_RESOLUTION && quietMove != FALSE &&
		1305	stage != MGS_GOOD_CAPTURES_AND_PROMOTIONS &&
		1306	movesAreEqual(currentMove,
		1307	variation->plyInfo[ply].killerMove1) == FALSE &&
		1308	movesAreEqual(currentMove,
		1309	variation->plyInfo[ply].killerMove2) == FALSE &&
		1310	isPassedPawnMove(toSquare, toSquare, position) == FALSE)
		1311	{
		1312	reduce = TRUE;
		1313	}
		1314
		1315	/* Recursive search */
		1316	/* ---------------- */
		1317	if (pvNode && numMovesPlayed == 0)
		1318	{
		1319	value = -searchBest(variation, -beta, -alpha, ply + 1,
		1320	newDepth, pvNode, FALSE, &bestReply, NO_MOVE,
		1321	TRUE);
		1322	}
		1323	else
		1324	{
		1325	const Move cm1 = variation->plyInfo[ply].killerMove3;
		1326	const Move cm2 = variation->plyInfo[ply].killerMove4;
		1327	const bool counterMove = movesAreEqual(currentMove, cm1) \|\|
		1328	movesAreEqual(currentMove, cm2);
		1329	const int effectiveReduction =
		1330	max(0, reduction - (counterMove ? DEPTH_RESOLUTION : 0));
		1331	const int minRestDepth = (pvNode ? DEPTH_RESOLUTION : 0);
		1332	const int reducedRestDepth =
		1333	max(minRestDepth, newDepth - effectiveReduction);
		1334
		1335	bool fullDepthSearch = TRUE;
		1336
		1337	if (reduce && effectiveReduction > 0)
		1338	{
		1339	value = -searchBest(variation, -alpha - 1, -alpha, ply + 1,
		1340	reducedRestDepth, FALSE, TRUE,
		1341	&bestReply, NO_MOVE, TRUE);
		1342
		1343	if (value > alpha && effectiveReduction >= 4 * DEPTH_RESOLUTION &&
		1344	stage != MGS_KILLER_MOVES)
		1345	{
		1346	const int limitedRestDepth =
		1347	max(DEPTH_RESOLUTION, newDepth - 2 * DEPTH_RESOLUTION);
		1348
		1349	value = -searchBest(variation, -alpha - 1, -alpha, ply + 1,
		1350	limitedRestDepth, FALSE,
		1351	TRUE, &bestReply, NO_MOVE, TRUE);
		1352	}
		1353
		1354	fullDepthSearch = (bool) (value > alpha);
		1355	}
		1356
		1357	if (fullDepthSearch)
		1358	{
		1359	value = -searchBest(variation, -alpha - 1, -alpha, ply + 1,
		1360	newDepth, FALSE, !cutNode, &bestReply,
		1361	NO_MOVE, TRUE);
		1362
		1363	if (pvNode && value > alpha && value < beta)
		1364	{ /* 2% */
		1365	value = -searchBest(variation, -beta, -alpha, ply + 1,
		1366	newDepth, TRUE, FALSE, &bestReply,
		1367	NO_MOVE, TRUE);
		1368	}
		1369	}
		1370	}
		1371
		1372	assert(value >= VALUE_MATED && value <= -VALUE_MATED);
		1373
		1374	if (nodeWasBlocked)
		1375	{
		1376	resetNodeUsage(position->hashKey, restDepth);
		1377	}
		1378
		1379	unmakeLastMove(variation);
		1380	numMovesPlayed++;
		1381
		1382	if (quietMove && inCheck == FALSE)
		1383	{
		1384	quietMoveIndex[quietMoveCount++] =
		1385	historyIndex(currentMove, position);
		1386	}
		1387
		1388	/* Calculate the parameters controlling the search tree. */
		1389	/* ----------------------------------------------------- */
		1390	if (value > best)
		1391	{ /* 32% */
		1392	best = value;
		1393
		1394	if (best > alpha)
		1395	{ /* 63% */
		1396	alpha = best;
		1397	*bestMove = currentMove;
		1398
		1399	if (pvNode)
		1400	{
		1401	appendMoveToPv(&(variation->plyInfo[ply].pv),
		1402	&(variation->plyInfo[ply - 1].pv), currentMove);
		1403	}
		1404
		1405	if (best >= beta)
		1406	{ /* 99% */
		1407	break;
		1408	}
		1409	}
		1410	}
		1411	}
		1412
		1413	/* No legal move was found. Check if it's mate or stalemate. */
		1414	/* --------------------------------------------------------- */
		1415	if (best == VALUE_MATED)
		1416	{
		1417	if (excludeMove != NO_MOVE && excludeMove != NULLMOVE)
		1418	{
		1419	return beta - 1;
		1420	}
		1421
		1422	if (inCheck)
		1423	{
		1424	/* mate */
		1425
		1426	best = VALUE_MATED + ply;
		1427	}
		1428	else
		1429	{
		1430	/* stalemate */
		1431
		1432	best = variation->drawScore[position->activeColor];
		1433	}
		1434	}
		1435
		1436	/* Calculate the parameters controlling the move ordering. */
		1437	/* ------------------------------------------------------- */
		1438	if (bestMove != NO_MOVE && moveIsQuiet(bestMove, position) &&
		1439	inCheck == FALSE &&
		1440	(excludeMove == NO_MOVE \|\| excludeMove == NULLMOVE))
		1441	{
		1442	Move killerMove = *bestMove;
		1443	const Piece movingPiece = position->piece[getFromSquare(killerMove)];
		1444	const int index = historyIndex(*bestMove, position);
		1445	const UINT16 bestMoveValue = (UINT16)
		1446	(variation->historyValue[index] +
		1447	((HISTORY_MAX - variation->historyValue[index]) * restDepth) / 256);
		1448	int i;
		1449
		1450	for (i = 0; i < quietMoveCount; i++)
		1451	{
		1452	const int historyIdx = quietMoveIndex[i];
		1453
		1454	variation->historyValue[historyIdx] = (UINT16)
		1455	(variation->historyValue[historyIdx] -
		1456	(variation->historyValue[historyIdx] * restDepth) / 128);
		1457	assert(variation->historyValue[historyIdx] <= HISTORY_MAX);
		1458	}
		1459
		1460	variation->historyValue[index] = bestMoveValue;
		1461	assert(variation->historyValue[index] <= HISTORY_MAX);
		1462
		1463	setMoveValue(&killerMove, movingPiece);
		1464	registerKillerMove(&variation->plyInfo[ply], killerMove);
		1465	updateCounterMoves(variation, ply, killerMove);
		1466
		1467	if (ply >= 2 && variation->plyInfo[ply - 1].isHashMove)
		1468	{
		1469	updateFollowupMoves(variation, ply, killerMove);
		1470	}
		1471	}
		1472
		1473	storeResult:
		1474
		1475	/* Store the value in the transposition table. */
		1476	/* ------------------------------------------- */
		1477	if ((excludeMove == NO_MOVE \|\| excludeMove == NULLMOVE) &&
		1478	variation->searchStatus == SEARCH_STATUS_RUNNING)
		1479	{
		1480	if (best >= beta)
		1481	{
		1482	hashentryFlag = HASHVALUE_LOWER_LIMIT;
		1483	}
		1484	else
		1485	{
		1486	hashentryFlag = (pvNode && *bestMove != NO_MOVE ?
		1487	HASHVALUE_EXACT : HASHVALUE_UPPER_LIMIT);
		1488	}
		1489
		1490	setHashentry(getSharedHashtable(), hashKey,
		1491	calcHashtableValue(best, ply),
		1492	(UINT8) (restDepth + HASH_DEPTH_OFFSET),
		1493	packedMove(*bestMove), hashentryFlag,
		1494	(INT16) getStaticValue(variation, ply));
		1495
		1496	#ifdef SEND_HASH_ENTRIES
		1497	if (hashentryFlag == HASHVALUE_EXACT &&
		1498	restDepth >= minPvHashEntrySendDepth &&
		1499	ply <= maxPvHashEntrySendHeight)
		1500	{
		1501	const long timestamp = getTimestamp();
		1502	const long elapsedTime = timestamp - variation->startTime;
		1503	const long intervalTime = timestamp - variation->hashSendTimestamp;
		1504
		1505	if (elapsedTime >= minPvHashEntrySendTime &&
		1506	intervalTime >= pvHashEntriesSendInterval)
		1507	{
		1508	Hashentry entry =
		1509	constructHashEntry(hashKey, calcHashtableValue(best, ply),
		1510	(INT16) getStaticValue(variation, ply),
		1511	(UINT8) (restDepth + HASH_DEPTH_OFFSET),
		1512	packedMove(*bestMove), 0, hashentryFlag);
		1513
		1514	sendHashentry(&entry);
		1515	variation->hashSendTimestamp = timestamp;
		1516	}
		1517	}
		1518	#endif
		1519	}
		1520
		1521	return best;
		1522	}
		1523
		1524	void copyPvFromHashtable(Variation * variation, const int pvIndex,
		1525	PrincipalVariation * pv, const Move bestBaseMove)
		1526	{
		1527	Move bestMove = NO_MOVE;
		1528
		1529	if (pvIndex == 0)
		1530	{
		1531	bestMove = bestBaseMove;
		1532	}
		1533	else
		1534	{
		1535	Hashentry *tableHit = getHashentry(getSharedHashtable(),
		1536	variation->singlePosition.hashKey);
		1537
		1538	if (tableHit != NULL)
		1539	{
		1540	Move currentMove = (Move) getHashentryMove(tableHit);
		1541
		1542	if (moveIsLegal(&variation->singlePosition, currentMove))
		1543	{
		1544	bestMove = (Move) getHashentryMove(tableHit);
		1545	}
		1546	}
		1547	}
		1548
		1549	if (bestMove != NO_MOVE && pvIndex < MAX_DEPTH)
		1550	{
		1551	pv->move[pvIndex] = (UINT16) bestMove;
		1552	pv->move[pvIndex + 1] = (UINT16) NO_MOVE;
		1553	pv->length = pvIndex + 1;
		1554	makeMove(variation, bestMove);
		1555	copyPvFromHashtable(variation, pvIndex + 1, pv, bestBaseMove);
		1556	unmakeLastMove(variation);
		1557	}
		1558	else
		1559	{
		1560	pv->move[pvIndex] = (UINT16) NO_MOVE;
		1561	pv->length = pvIndex;
		1562	}
		1563	}
		1564
		1565	static void copyPvToHashtable(Variation * variation,
		1566	PrincipalVariation * pv, const int pvIndex)
		1567	{
		1568	Move move = (Move) pv->move[pvIndex];
		1569
		1570	if (pvIndex < pv->length && moveIsLegal(&variation->singlePosition, move))
		1571	{
		1572	UINT8 importance = (UINT8) HASH_DEPTH_OFFSET;
		1573	bool entryExists = FALSE;
		1574	Move bestMove = NO_MOVE;
		1575	Hashentry *tableHit = getHashentry(getSharedHashtable(),
		1576	variation->singlePosition.hashKey);
		1577
		1578	if (tableHit != 0)
		1579	{
		1580	bestMove = (Move) getHashentryMove(tableHit);
		1581	importance = max(importance, getHashentryImportance(tableHit));
		1582
		1583	if (bestMove != NO_MOVE && movesAreEqual(bestMove, move))
		1584	{
		1585	entryExists = TRUE;
		1586	}
		1587	}
		1588
		1589	if (entryExists == FALSE)
		1590	{
		1591	UINT8 hashentryFlag = HASHVALUE_LOWER_LIMIT;
		1592
		1593	/* Store the move in the transposition table. */
		1594	/* ------------------------------------------- */
		1595
		1596	setHashentry(getSharedHashtable(),
		1597	variation->singlePosition.hashKey, VALUE_MATED,
		1598	importance, packedMove(move),
		1599	hashentryFlag, getEvalValue(variation));
		1600	}
		1601
		1602	makeMove(variation, move);
		1603	copyPvToHashtable(variation, pv, pvIndex + 1);
		1604	unmakeLastMove(variation);
		1605	}
		1606	}
		1607
		1608	static void registerBestMove(Variation * variation, Move * move,
		1609	const int value)
		1610	{
		1611	if (variation->searchStatus == SEARCH_STATUS_RUNNING)
		1612	{
		1613	setMoveValue(move, value);
		1614	variation->bestBaseMove = *move;
		1615
		1616	if (variation->iteration > 4 && variation->numberOfCurrentBaseMove > 1)
		1617	{
		1618	variation->bestMoveChangeCount += 256;
		1619	}
		1620	}
		1621	}
		1622
		1623	static int getBaseMoveValue(Variation * variation, const Move move,
		1624	const int alpha, const int beta,
		1625	const bool fullWindow)
		1626	{
		1627	int depth = DEPTH_RESOLUTION * variation->iteration;
		1628	int value;
		1629	Move bestReply;
		1630
		1631	assert(alpha >= VALUE_MATED);
		1632	assert(alpha <= -VALUE_MATED);
		1633	assert(beta >= VALUE_MATED);
		1634	assert(beta <= -VALUE_MATED);
		1635	assert(alpha < beta);
		1636
		1637	makeMoveFast(variation, move);
		1638
		1639	if (variation->nodes > GUI_NODE_COUNT_MIN &&
		1640	variation->threadNumber == 0 && variation->handleSearchEvent != 0)
		1641	{
		1642	getGuiSearchMutex();
		1643	variation->handleSearchEvent(SEARCHEVENT_NEW_BASEMOVE, variation);
		1644	releaseGuiSearchMutex();
		1645	}
		1646
		1647	if (activeKingIsSafe(&variation->singlePosition) == FALSE)
		1648	{
		1649	variation->plyInfo[0].currentMoveIsCheck = TRUE;
		1650	depth += DEPTH_RESOLUTION;
		1651	}
		1652	else
		1653	{
		1654	variation->plyInfo[0].currentMoveIsCheck = FALSE;
		1655	}
		1656
		1657	if (fullWindow)
		1658	{
		1659	value = -searchBest(variation, -beta, -alpha, 1,
		1660	depth - DEPTH_RESOLUTION, TRUE, FALSE,
		1661	&bestReply, NO_MOVE, TRUE);
		1662	}
		1663	else
		1664	{
		1665	value = -searchBest(variation, -alpha - 1, -alpha, 1,
		1666	depth - DEPTH_RESOLUTION, FALSE, TRUE,
		1667	&bestReply, NO_MOVE, TRUE);
		1668
		1669	if (value > alpha)
		1670	{
		1671	value = -searchBest(variation, -beta, -alpha, 1,
		1672	depth - DEPTH_RESOLUTION, TRUE,
		1673	FALSE, &bestReply, NO_MOVE, TRUE);
		1674	}
		1675	}
		1676
		1677	unmakeLastMove(variation);
		1678
		1679	return value;
		1680	}
		1681
		1682	int getPvScoreType(int value, int alpha, int beta)
		1683	{
		1684	if (value <= alpha)
		1685	{
		1686	return HASHVALUE_UPPER_LIMIT;
		1687	}
		1688	else if (value >= beta)
		1689	{
		1690	return HASHVALUE_LOWER_LIMIT;
		1691	}
		1692	else
		1693	{
		1694	return HASHVALUE_EXACT;
		1695	}
		1696	}
		1697
		1698	static void sendPvInfo(Variation * variation, const int eventType)
		1699	{
		1700	if ((variation->nodes > GUI_NODE_COUNT_MIN \|\|
		1701	eventType == SEARCHEVENT_PLY_FINISHED) &&
		1702	variation->threadNumber == 0 && variation->handleSearchEvent != 0)
		1703	{
		1704	int i;
		1705
		1706	getGuiSearchMutex();
		1707
		1708	for (i = 0; i < numPvs && variation->pv[i].length > 0; i++)
		1709	{
		1710	variation->pvId = i;
		1711	variation->handleSearchEvent(eventType, variation);
		1712	}
		1713
		1714	releaseGuiSearchMutex();
		1715	}
		1716	}
		1717
		1718	static void exploreBaseMoves(Variation * variation, Movelist * basemoves,
		1719	const int aspirationWindow)
		1720	{
		1721	const int previousBest = variation->previousBest;
		1722	const int ply = 0;
		1723	Position *position = &variation->singlePosition;
		1724	const bool fullWindow = (bool) (variation->iteration <= 3);
		1725	int window = aspirationWindow, best;
		1726	bool exactValueFound = FALSE;
		1727	const int staticValue = getEvalValue(variation);
		1728	int alpha =
		1729	(fullWindow ? VALUE_MATED : max(VALUE_MATED, previousBest - window));
		1730	int beta =
		1731	(fullWindow ? -VALUE_MATED : min(-VALUE_MATED, previousBest + window));
		1732
		1733	variation->failingLow = FALSE;
		1734	variation->selDepth = variation->iteration;
		1735	initializePvsOfVariation(variation);
		1736
		1737	do
		1738	{
		1739	int pvCount = 0, worstValue = VALUE_MATED;
		1740	const int numPvLimit = min(basemoves->numberOfMoves, numPvs);
		1741
		1742	initializeMoveValues(basemoves);
		1743	resetPvsOfVariation(variation);
		1744	best = VALUE_MATED;
		1745
		1746	for (variation->numberOfCurrentBaseMove = 1;
		1747	variation->numberOfCurrentBaseMove <= basemoves->numberOfMoves;
		1748	variation->numberOfCurrentBaseMove++)
		1749	{
		1750	int value;
		1751	const int icm = variation->numberOfCurrentBaseMove - 1;
		1752	const bool searchBelowBest = fullWindow \|\| numPvs > 1;
		1753	const bool pvNode = (bool) (icm == 0 \|\| searchBelowBest);
		1754	const int searchAlpha = (searchBelowBest ? alpha : max(alpha, best));
		1755
		1756	resetPlyInfo(variation);
		1757	variation->currentBaseMove = basemoves->moves[icm];
		1758	variation->plyInfo[ply].indexCurrentMove =
		1759	historyIndex(variation->currentBaseMove, position);
		1760
		1761	value = getBaseMoveValue(variation, basemoves->moves[icm],
		1762	searchAlpha, beta, pvNode);
		1763
		1764	if (variation->searchStatus != SEARCH_STATUS_RUNNING &&
		1765	variation->iteration > 1)
		1766	{
		1767	break;
		1768	}
		1769
		1770	if (icm == 0 \|\| value > searchAlpha)
		1771	{
		1772	PrincipalVariation pv;
		1773
		1774	setMoveValue(&basemoves->moves[icm], value);
		1775	pv.score = value;
		1776	pv.scoreType = getPvScoreType(value, searchAlpha, beta);
		1777	appendMoveToPv(&(variation->plyInfo[0].pv), &pv,
		1778	basemoves->moves[icm]);
		1779	addPvByScore(variation, &pv);
		1780
		1781	if (++pvCount >= numPvLimit)
		1782	{
		1783	sendPvInfo(variation, SEARCHEVENT_NEW_PV);
		1784	}
		1785
		1786	if (icm == 0 \|\| value > best)
		1787	{
		1788	registerBestMove(variation, &basemoves->moves[icm], value);
		1789
		1790	if (value > best && value < beta)
		1791	{
		1792	variation->completePv = pv;
		1793	}
		1794	}
		1795	}
		1796
		1797	if (value > best)
		1798	{
		1799	best = value;
		1800
		1801	if (value >= beta && numPvs == 1)
		1802	{
		1803	break;
		1804	}
		1805	}
		1806	}
		1807
		1808	/* Store the value in the transposition table. */
		1809	/* ------------------------------------------- */
		1810	if (variation->searchStatus == SEARCH_STATUS_RUNNING)
		1811	{
		1812	UINT8 hashentryFlag;
		1813	const int depth = DEPTH_RESOLUTION * variation->iteration;
		1814	const Move bestMove = variation->bestBaseMove;
		1815
		1816	if (best > alpha)
		1817	{
		1818	hashentryFlag =
		1819	(best >= beta ? HASHVALUE_LOWER_LIMIT : HASHVALUE_EXACT);
		1820	}
		1821	else
		1822	{
		1823	hashentryFlag = HASHVALUE_UPPER_LIMIT;
		1824	}
		1825
		1826	setHashentry(getSharedHashtable(), position->hashKey,
		1827	calcHashtableValue(best, ply),
		1828	(UINT8) (depth + HASH_DEPTH_OFFSET),
		1829	packedMove(bestMove), hashentryFlag,
		1830	(INT16) staticValue);
		1831	}
		1832
		1833	worstValue = (numPvs == 1 ? best :
		1834	max(VALUE_MATED + 3, variation->pv[numPvs - 1].score));
		1835
		1836	if (best >= beta)
		1837	{
		1838	beta = min(-VALUE_MATED, best + window);
		1839	}
		1840	else if (worstValue <= alpha && worstValue > VALUE_MATED + 2)
		1841	{
		1842	alpha = max(VALUE_MATED, alpha - window);
		1843	variation->failingLow = TRUE;
		1844	}
		1845	else
		1846	{
		1847	exactValueFound = TRUE; /* exact value found */
		1848	}
		1849
		1850	window = window + window / 2;
		1851
		1852	sortMoves(basemoves);
		1853
		1854	assert(fullWindow == TRUE \|\|
		1855	movesAreEqual(basemoves->moves[0], variation->bestBaseMove));
		1856
		1857	if (variation->threadNumber == 0)
		1858	{
		1859	copyPvToHashtable(variation, &variation->completePv, 0);
		1860	}
		1861	}
		1862	while (variation->searchStatus == SEARCH_STATUS_RUNNING &&
		1863	exactValueFound == FALSE);
		1864
		1865	variation->pv[0].score = getMoveValue(variation->bestBaseMove);
		1866
		1867	if (variation->threadNumber == 0 && variation->iteration > 1 &&
		1868	variation->completePv.length <= 1)
		1869	{
		1870	PrincipalVariation tmpPv;
		1871
		1872	copyPvFromHashtable(variation, 0, &tmpPv, variation->bestBaseMove);
		1873
		1874	if (tmpPv.length > 1)
		1875	{
		1876	variation->completePv = tmpPv;
		1877	}
		1878	}
		1879
		1880	sendPvInfo(variation, SEARCHEVENT_PLY_FINISHED);
		1881	}
		1882
		1883	static void initializePawnHashtable(PawnHashInfo * pawnHashtable)
		1884	{
		1885	int i;
		1886
		1887	for (i = 0; i < PAWN_HASHTABLE_SIZE; i++)
		1888	{
		1889	pawnHashtable[i].hashKey = 0;
		1890	}
		1891	}
		1892
		1893	static void initializeKingsafetyHashtable(KingSafetyHashInfo *
		1894	kingsafetyHashtable)
		1895	{
		1896	int i;
		1897
		1898	for (i = 0; i < KINGSAFETY_HASHTABLE_SIZE; i++)
		1899	{
		1900	kingsafetyHashtable[i].hashKey = 0;
		1901	}
		1902	}
		1903
		1904	static void updatePieceValues()
		1905	{
		1906	maxPieceValue[WHITE_QUEEN] = maxPieceValue[BLACK_QUEEN] =
		1907	max(getOpeningValue(basicValue[WHITE_QUEEN]),
		1908	getEndgameValue(basicValue[WHITE_QUEEN])) - 42;
		1909	maxPieceValue[WHITE_ROOK] = maxPieceValue[BLACK_ROOK] =
		1910	max(getOpeningValue(basicValue[WHITE_ROOK]),
		1911	getEndgameValue(basicValue[WHITE_ROOK]));
		1912	maxPieceValue[WHITE_BISHOP] = maxPieceValue[BLACK_BISHOP] =
		1913	max(getOpeningValue(basicValue[WHITE_BISHOP]),
		1914	getEndgameValue(basicValue[WHITE_BISHOP]));
		1915	maxPieceValue[WHITE_KNIGHT] = maxPieceValue[BLACK_KNIGHT] =
		1916	max(getOpeningValue(basicValue[WHITE_KNIGHT]),
		1917	getEndgameValue(basicValue[WHITE_KNIGHT]));
		1918	maxPieceValue[WHITE_PAWN] = maxPieceValue[BLACK_PAWN] =
		1919	max(getOpeningValue(basicValue[WHITE_PAWN]),
		1920	getEndgameValue(basicValue[WHITE_PAWN]));
		1921	}
		1922
		1923	Move search(Variation * variation, Movelist * acceptableSolutions)
		1924	{
		1925	Movelist movelist;
		1926	long timeTarget;
		1927	int stableIterationCount = 0;
		1928	int stableBestMoveCount = 0;
		1929	Move bestMove = NO_MOVE;
		1930	UINT64 nodeCount = 0;
		1931	int iv1 = 0, iv2 = 0, iv3 = 0;
		1932
		1933	if (resetSharedHashtable)
		1934	{
		1935	resetHashtable(getSharedHashtable());
		1936	initializePawnHashtable(variation->pawnHashtable);
		1937	initializeKingsafetyHashtable(variation->kingsafetyHashtable);
		1938	resetSharedHashtable = FALSE;
		1939	}
		1940
		1941	resetHistoryValues(variation);
		1942	resetGainValues(variation);
		1943
		1944	variation->ply = 0;
		1945	variation->ownColor = variation->singlePosition.activeColor;
		1946	variation->nodes = variation->nodesAtTimeCheck = 0;
		1947	variation->startTimeProcess = getProcessTimestamp();
		1948	variation->timestamp = variation->startTime + 1;
		1949	variation->hashSendTimestamp = variation->startTime;
		1950	variation->tbHits = 0;
		1951	variation->numPvUpdates = 0;
		1952	variation->terminateSearchOnPonderhit = FALSE;
		1953	variation->previousBest = getStaticValue(variation, 0);
		1954	variation->bestBaseMove = NO_MOVE;
		1955	variation->failingLow = FALSE;
		1956	movelist.positionalGain = &(variation->positionalGain[0]);
		1957	initializePlyInfo(variation);
		1958	getLegalMoves(variation, &movelist);
		1959
		1960	#ifdef TRACE_EVAL
		1961	getValue(&variation->singlePosition, VALUE_MATED, -VALUE_MATED,
		1962	variation->pawnHashtable, variation->kingsafetyHashtable);
		1963	#endif
		1964
		1965	#ifdef USE_BOOK
		1966	if (globalBook.indexFile != NULL && globalBook.moveFile != NULL &&
		1967	&variation->singlePosition->moveNumber <= 12)
		1968	{
		1969	Move bookMove = getBookmove(&globalBook,
		1970	&variation->singlePosition->hashKey,
		1971	&movelist);
		1972
		1973	if (bookMove != NO_MOVE)
		1974	{
		1975	variation->bestBaseMove = bookMove;
		1976	variation->searchStatus = SEARCH_STATUS_TERMINATE;
		1977	variation->finishTime = getTimestamp();
		1978
		1979	if (variation->handleSearchEvent != 0)
		1980	{
		1981	getGuiSearchMutex();
		1982	variation->handleSearchEvent(SEARCHEVENT_SEARCH_FINISHED,
		1983	variation);
		1984	releaseGuiSearchMutex();
		1985	}
		1986
		1987	variation->nodes = 0;
		1988
		1989	return variation->bestBaseMove;
		1990	}
		1991	}
		1992	#endif
		1993
		1994	variation->numberOfBaseMoves = movelist.numberOfMoves;
		1995	setMoveValue(&variation->bestBaseMove, VALUE_MATED);
		1996
		1997	for (variation->iteration = 1; variation->iteration <= MAX_DEPTH;
		1998	variation->iteration++)
		1999	{
		2000	long calculationTime;
		2001	int iterationValue, aspirationWindow;
		2002
		2003	variation->ply = 0;
		2004
		2005	aspirationWindow =
		2006	min(12, max(8, (abs(iv1 - iv2) + abs(iv2 - iv3)) / 2));
		2007	exploreBaseMoves(variation, &movelist, aspirationWindow);
		2008	calculationTime =
		2009	(unsigned long) (getTimestamp() - variation->startTime);
		2010
		2011	if (movesAreEqual(variation->bestBaseMove, bestMove))
		2012	{
		2013	stableBestMoveCount++;
		2014	}
		2015	else
		2016	{
		2017	stableBestMoveCount = 0;
		2018	}
		2019
		2020	bestMove = variation->bestBaseMove;
		2021	iv3 = iv2;
		2022	iv2 = iv1;
		2023	iv1 = iterationValue = getMoveValue(variation->bestBaseMove);
		2024
		2025	variation->previousBest = iterationValue;
		2026
		2027	assert(calculationTime >= 0);
		2028
		2029	if (acceptableSolutions != 0 &&
		2030	listContainsMove(acceptableSolutions, variation->bestBaseMove))
		2031	{
		2032	stableIterationCount++;
		2033
		2034	if (stableIterationCount == 1)
		2035	{
		2036	nodeCount = variation->nodes;
		2037	}
		2038	}
		2039	else
		2040	{
		2041	stableIterationCount = 0;
		2042	nodeCount = variation->nodes;
		2043	}
		2044
		2045	/* Check for a fail low. */
		2046	/* --------------------- */
		2047
		2048	if (variation->numberOfBaseMoves == 1)
		2049	{
		2050	timeTarget = (19 * variation->timeTarget) / 256;
		2051	}
		2052	else
		2053	{
		2054	const int timeWeight = 160 +
		2055	(223 * variation->bestMoveChangeCount) / 256;
		2056
		2057	timeTarget = (timeWeight * variation->timeTarget) / 256;
		2058	}
		2059
		2060	variation->bestMoveChangeCount =
		2061	(17 * variation->bestMoveChangeCount) / 32;
		2062
		2063	getGuiSearchMutex();
		2064
		2065	if (variation->threadNumber == 0 &&
		2066	variation->searchStatus == SEARCH_STATUS_RUNNING &&
		2067	variation->iteration > 8 && variation->timeLimit != 0 &&
		2068	calculationTime >= timeTarget)
		2069	{
		2070	#ifdef DEBUG_THREAD_COORDINATION
		2071	logDebug
		2072	("Time target reached (%lu/%lu ms, %lu%%)).\n",
		2073	calculationTime, variation->timeTarget,
		2074	(calculationTime * 100) / variation->timeTarget);
		2075	#endif
		2076
		2077	if (variation->ponderMode)
		2078	{
		2079	variation->terminateSearchOnPonderhit = TRUE;
		2080
		2081	#ifdef DEBUG_THREAD_COORDINATION
		2082	logDebug("Setting ponder termination flag.\n");
		2083	#endif
		2084	}
		2085	else
		2086	{
		2087	variation->searchStatus = SEARCH_STATUS_TERMINATE;
		2088
		2089	#ifdef DEBUG_THREAD_COORDINATION
		2090	logDebug("Terminating search.\n");
		2091	#endif
		2092	}
		2093	}
		2094
		2095	if (variation->searchStatus == SEARCH_STATUS_RUNNING &&
		2096	(getMoveValue(variation->bestBaseMove) <=
		2097	VALUE_MATED + variation->iteration \|\|
		2098	getMoveValue(variation->bestBaseMove) >=
		2099	-VALUE_MATED - variation->iteration))
		2100	{
		2101	#ifdef DEBUG_THREAD_COORDINATION
		2102	logDebug("Best value out of bounds (%d). Terminating search.\n",
		2103	getMoveValue(variation->bestBaseMove));
		2104	#endif
		2105	variation->searchStatus = SEARCH_STATUS_TERMINATE;
		2106	}
		2107
		2108	if (variation->searchStatus == SEARCH_STATUS_RUNNING &&
		2109	variation->iteration == MAX_DEPTH)
		2110	{
		2111	#ifdef DEBUG_THREAD_COORDINATION
		2112	logDebug("Max depth reached. Terminating search.\n");
		2113	#endif
		2114	variation->searchStatus = SEARCH_STATUS_TERMINATE;
		2115	}
		2116
		2117	if (acceptableSolutions != 0 && stableIterationCount >= 1 &&
		2118	(getMoveValue(variation->bestBaseMove) > 20000 \|\|
		2119	(stableIterationCount >= 2 &&
		2120	(getMoveValue(variation->bestBaseMove) >= 25 \|\|
		2121	(getTimestamp() - variation->startTime) >= 3000))))
		2122	{
		2123	#ifdef DEBUG_THREAD_COORDINATION
		2124	logDebug("Solution found (value=%d). Terminating search.\n",
		2125	getMoveValue(variation->bestBaseMove));
		2126	#endif
		2127	variation->searchStatus = SEARCH_STATUS_TERMINATE;
		2128	}
		2129
		2130	if (variation->searchStatus != SEARCH_STATUS_RUNNING)
		2131	{
		2132	variation->terminateSearchOnPonderhit = TRUE;
		2133	variation->searchStatus = SEARCH_STATUS_TERMINATE;
		2134
		2135	variation->finishTime = getTimestamp();
		2136	variation->finishTimeProcess = getProcessTimestamp();
		2137
		2138	if (variation->threadNumber == 0)
		2139	{
		2140	incrementDate(getSharedHashtable());
		2141
		2142	if (variation->handleSearchEvent != 0)
		2143	{
		2144	variation->handleSearchEvent(SEARCHEVENT_SEARCH_FINISHED,
		2145	variation);
		2146	}
		2147	}
		2148	}
		2149
		2150	if (variation->searchStatus != SEARCH_STATUS_RUNNING)
		2151	{
		2152	#ifdef DEBUG_THREAD_COORDINATION
		2153	logReport
		2154	("search status != SEARCH_STATUS_RUNNING -> exiting search.\n",
		2155	getMoveValue(variation->bestBaseMove));
		2156	#endif
		2157
		2158	releaseGuiSearchMutex();
		2159	break;
		2160	}
		2161
		2162	releaseGuiSearchMutex();
		2163	}
		2164
		2165	variation->nodes = nodeCount;
		2166
		2167	if (statCount1 != 0 \|\| statCount2 != 0)
		2168	{
		2169	logReport("statCount1=%lld statCount2=%lld (%lld%%) \n",
		2170	statCount1, statCount2,
		2171	(statCount2 * 100) / max(1, statCount1));
		2172	}
		2173
		2174	return variation->bestBaseMove;
		2175	}
		2176
		2177	/* #define DEBUG_FUT_VALUES */
		2178
		2179	static void initializeArrays(void)
		2180	{
		2181	int i, j;
		2182
		2183	for (i = 0; i < 64; i++)
		2184	{
		2185	for (j = 0; j < 64; j++)
		2186	{
		2187	if (i == 0 \|\| j == 0)
		2188	{
		2189	quietPvMoveReduction[i][j] =
		2190	quietMoveReduction[0][i][j] = quietMoveReduction[1][i][j] = 0;
		2191	}
		2192	else
		2193	{
		2194	const double baseFactor = log((double) (i)) * log((double) (j));
		2195	const double pvReduction = baseFactor / 2.93;
		2196	const double nonPvReduction = 0.33 + baseFactor / 2.21;
		2197
		2198	quietPvMoveReduction[i][j] =
		2199	(int) (pvReduction >= 1.0 ?
		2200	floor(pvReduction * DEPTH_RESOLUTION) : 0);
		2201	quietMoveReduction[0][i][j] =
		2202	quietMoveReduction[1][i][j] =
		2203	(int) (nonPvReduction >= 1.0 ?
		2204	floor(nonPvReduction * DEPTH_RESOLUTION) : 0);
		2205
		2206	if (quietMoveReduction[0][i][j] > 2 * DEPTH_RESOLUTION)
		2207	{
		2208	quietMoveReduction[0][i][j] += DEPTH_RESOLUTION;
		2209	}
		2210	else if (quietMoveReduction[0][i][j] > DEPTH_RESOLUTION)
		2211	{
		2212	quietMoveReduction[0][i][j] += DEPTH_RESOLUTION / 2;
		2213	}
		2214	}
		2215	}
		2216	}
		2217
		2218	for (i = 0; i < 32; i++)
		2219	{
		2220	quietMoveCountLimit[0][i] = (int) (2.4 + 0.231 * pow(i, 1.8));
		2221	quietMoveCountLimit[1][i] = (int) (3.1 + 0.344 * pow(i + 0.78, 1.8));
		2222
		2223	#ifdef DEBUG_FUT_VALUES
		2224	logDebug("mcl[%d]=%d\n", i, quietMoveCountLimit[i]);
		2225	#endif
		2226	}
		2227
		2228	for (i = 0; i <= NUM_FUTILITY_MARGIN_VALUES; i++)
		2229	{
		2230	futilityMargin[i] = (3125 * i) / 64 - 12800 / 256;
		2231
		2232	#ifdef DEBUG_FUT_VALUES
		2233	if (j <= 2)
		2234	{
		2235	logDebug("fm[%d][%d]=%d\n", i, j, futilityMargin[i][j]);
		2236	}
		2237	#endif
		2238	}
		2239
		2240	updatePieceValues();
		2241
		2242	#ifdef DEBUG_FUT_VALUES
		2243	getKeyStroke();
		2244	#endif
		2245	}
		2246
		2247	int initializeModuleSearch(void)
		2248	{
		2249	initializeArrays();
		2250
		2251	return 0;
		2252	}
		2253
		2254	int testModuleSearch(void)
		2255	{
		2256	return 0;
		2257	}

Subversion Repositories Games.Chess Giants

Games.Chess Giants/engine-protector (BROKEN)/search.c – Rev 112