
/***************************************************************************

                                 ChessV

                   COPYRIGHT (C) 2005 BY GREGORY STRONG

This file is part of ChessV.  ChessV is free software; you can redistribute
it and/or modify it under the terms of the GNU General Public License as 
published by the Free Software Foundation; either version 2 of the License, 
or (at your option) any later version.

ChessV is distributed in the hope that it will be useful, but WITHOUT ANY 
WARRANTY; without even the implied warranty of MERCHANTABILITY or 
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for 
more details; the file 'COPYING' contains the License text, but if for
some reason you need a copy, please write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

****************************************************************************/


#include "StdAfx.h"
#include "Board.h"
#include "Game.h"
#include "Piece.h"
#include "ChessV.h"
#include "Statistics.h"
#include "Personality.h"


// *** DEBUG MEMORY ALLOCATION *** //
#ifdef _DEBUG
#define new SAFE_NEW
#endif


static long long int recaptureExtensions = 0;
static long long int checkExtensions = 0;
static long long int pvExtensions = 0;


#define SAVE_KILLER(move)                                                     \
	if( move.type == StandardMove &&                                          \
		move.promotion == NULL && move.tag == 0 )                             \
	{                                                                         \
		if( (Movement) move != killer1[currentDepth] )                        \
		{                                                                     \
			killer2[currentDepth] = killer1[currentDepth];                    \
			killer1[currentDepth] = (Movement) move;                          \
		}                                                                     \
	}                                                                         

int Board::SearchRoot
	( int alpha, 
	  int beta, 
	  int depth,
	  int &eval )
{
	currentDepth = 1;			//	current search depth

	int bestMoveIndex = 0;		//	stores the index of the best move found so far

	bool extend = false;		//	true means we should extend the depth of 
								//	search, because we are in check, or
								//	some other conditions.

	int score = -INFINITY;
	int bestScore = -INFINITY;
	Movement bestMoveNextLevel;
	NodeType nodeType = PV;

	// *** BOOKKEEPING *** //
	if( STAT_LOOKUP(nodeCount) % 8192LL == 0LL )
		//	every so often, we call Bookkeeping() to check 
		//	to see if time has run out, and to update the display
		Bookkeeping();

	//	call Game override to test for wins/losses/draws in
	//	case of insufficient material, or because the game 
	//	has unusual victory conditions
	if( pGame->TestForWinLossDraw( score ) )
		return score;

	// *** CHECK EXTENSION *** //
	if( inCheck[currentDepth] )
	{
		STAT_INCREMENT(checkExtensions)
		depth++;
		extend = true;
		TRACE("check extension, new depth = %d", depth);
	}

	//	loop through all the generated moves; at the root, 
	//	these moves are guaranteed to be legal
	MovementList &list = movementLists[1];
	list.ResetCurrentMove();
	bool earlyExit = false;
	bool movesRemaining = true;
	bool firstMove = true;

	while( timeLeft && !earlyExit && movesRemaining )
	{
		#ifdef _DEBUG
		ASSERT(currentDepth == 1);
		AssertValid();
		word32 priHash = primaryHash;
		word32 secHash = secondaryHash;
		word32 priPawnHash = primaryPawnHash;
		word32 secPawnHash = secondaryPawnHash;
		#endif

		//	make the move
		STAT_INCREMENT(nodeCount);
		if( !list.MakeNextMove() )
		{
			movesRemaining = false;
			continue;
		}

		MoveInfo &mi = list.GetCurrentMove();

		if( firstMove )
		{
			TRACE_MOVE("searching move %s to depth %d (a=%d, b=%d)\n", list.GetCurrentMove(), depth - 1, -beta, -alpha);

			//	go deeper (recursively)
			currentDepth++;
			score = -Search( -beta, -alpha, depth - 1, true, PV, bestMoveNextLevel );
			currentDepth--;
			firstMove = false;

			//	The following occurs when we are re-searching a fail high move
			//	and now it has fail low.  This can be disastrous, so immediately
			//	adjust alpha and research (this time it will be a full-window search.)
			if( beta == INFINITY && score <= alpha )
			{
				alpha = -INFINITY;
				currentDepth++;
				score = -Search( -beta, -alpha, depth - 1, true, PV, bestMoveNextLevel );
				currentDepth--;
			}
		}
		else
		{
			TRACE_MOVE("searching move %s to depth %d (a=%d, b=%d)\n", list.GetCurrentMove(), depth - 1, -alpha - 1, -alpha);

			//	go deeper (recursively)
			//	after the first move, we search with a zero-width window... in other words, we 
			//	use alpha - 1 instead of beta.  we do this because we are only trying to show 
			//	that each move after the first is inferior to the first.  if it is indeed 
			//	inferior, then we don't care by how much.  if it fails high, though, then 
			//	we will need to research.  the extra cost of researching, though, is much 
			//	less than the savings gained from doing a zero-width search of all moves 
			//	after the first.
			nodeType = Cut;
			currentDepth++;
			score = -Search( -alpha - 1, -alpha, depth - 1, true, nodeType, bestMoveNextLevel );
			currentDepth--;

			if( score > alpha && score < beta )
			{
				//	score is outsize window; we must repeat the search with full window
				TRACE("move score of %d is outside zero-search window; researching ...\n", score);
				TRACE_MOVE("searching move %s to depth %d (a=%d, b=%d)\n", list.GetCurrentMove(), depth - 1, -beta, -score);

				nodeType = PV;
				currentDepth++;
				score = -Search( -beta, -score, depth - 1, true, nodeType, bestMoveNextLevel );
				currentDepth--;
			}

		}

		TRACE("move score = %d\n", score);

		int moveIndex = list.GetCurrentMoveIndex();
		MoveInfo &move = list.GetCurrentMove();

		//	undo the move
		list.UnmakeMove();

		#ifdef _DEBUG
		AssertValid();
		ASSERT(primaryHash == priHash);
		ASSERT(secondaryHash == secHash);
		ASSERT(primaryPawnHash == priPawnHash);
		ASSERT(secondaryPawnHash == secPawnHash);
		int dbg_sq;
		for( dbg_sq = 0; dbg_sq < nSquares; dbg_sq++ )
			if( GetSquareContents( dbg_sq ) != NULL )
				ASSERT( GetSquareContents( dbg_sq )->GetSquareNumber() == GetSquareContents( dbg_sq )->GetRealSquareNumber() );
		int dbg_piece;
		int dbg_player;
		for( dbg_player = 0; dbg_player < 2; dbg_player++ )
			for( dbg_piece = 0; dbg_piece < nPieces[dbg_player]; dbg_piece++ )
			{
				ASSERT( pieces[dbg_player][dbg_piece]->IsCaptured() == pieces[dbg_player][dbg_piece]->IsReallyCaptured() );
				if( !pieces[dbg_player][dbg_piece]->IsCaptured() )
					ASSERT( pieces[dbg_player][dbg_piece]->GetSquareNumber() == pieces[dbg_player][dbg_piece]->GetRealSquareNumber() );
			}
		#endif

		if( score > bestScore && timeLeft )
		{
			bestScore = score;
			bestMoveIndex = moveIndex;

			//	check our current score against alpha
			if( score > alpha )
			{
				alpha = score;
				rootScore = alpha;

				if( score >= beta )
				{
					//	save this move as a Killer Move
					SAVE_KILLER(move)
					//	beta cut-off, no need to search any further
					earlyExit = true;
				}
			}
		}

		if( !timeLeft )
			//	out of time, return best move so far
			return bestMoveIndex;

		if( bestScore == MATE )
		{
			//	we can't do better than checkmate ...
			eval = bestScore;
			return bestMoveIndex;
		}
	}

	MoveInfo &bestMove = list.GetMove( bestMoveIndex );
	SAVE_KILLER(bestMove)

	//	check for a draw by fifty-move rule,
	//	if this game has such a rule
	if( pGame->GetAutoDrawPeriod() > 0 )
		if( gamePly - gameRecords[gamePly].lastCaptureOrPawn >
			pGame->GetAutoDrawPeriod() )
			//	it's a draw
			return pGame->GetDrawScore();

	eval = score;
	return bestMoveIndex;
}

int Board::Search
	( int alpha, 
	  int beta, 
	  int depth,
	  bool tryNullMove,
	  NodeType nodeType, 
	  Movement &bestMoveFound )
{
	int score = -INFINITY;
	int nullScore = -INFINITY;
	bool extend = false;
	int bestScore = -INFINITY;
	Movement bestMoveNextLevel;
	bool Singular = singular && nodeType == PV;

	inCheck[currentDepth] = (!pGame->IsGoalToCheckmate() || 
		gameRecords[gamePly-1].moveType == NullMove) ? false : IsInCheck(
//			gameRecords[gamePly-1].oldSquareNumber, 
//			gameRecords[gamePly-1].pieceMoved->GetSquareNumber()
		);

	//	bookkeeping and time check
	if( STAT_LOOKUP(nodeCount) % 8192LL == 0LL )
		Bookkeeping();

	if( !timeLeft )
		//	out of time; exiting ...
		return 0;

	//	call Game override to test for wins/losses/draws in
	//	case of insufficient material, or because the game 
	//	has unusual victory conditions
	if( pGame->TestForWinLossDraw( score ) )
		return score;

	//	check for draw by repetition
	if( IsDraw() )
		return( pGame->GetDrawScore() );

	// *** CHECK EXTENSION *** //
	if( inCheck[currentDepth] && currentDepth < iDepth )
	{
		STAT_INCREMENT(checkExtensions)
		extend = true;
		depth++;
	}

	//	has the search reached the desired depth?
	if( depth <= 0 )
	{
		//	it's not necessarily safe to evaluate here; we need to 
		//	look for a stable ("quiescent") position before evaluating
		if( pGame->UseQuiescentSearch() )
		{
			score = QuiescentSearch( alpha, beta, 1, nodeType );
			return score;
		}
		else
		{
			return Evaluate( alpha, beta );
		}
	}

	//	*********************************  //
	//	*** TRANSPOSITION TABLE check ***  //
	//	*********************************  //

	int hashScore;
	Movement hashMove;
	HashType hashType = hashTable.Lookup( depth, currentDepth, hashScore, hashMove );

	bool wasLowerBound = false;

	if( hashType != NoHash )
	{
		switch( hashType )
		{
		  case Exact:
			STAT_INCREMENT(ttExactCount)
			return hashScore;

		  case UpperBound:
			STAT_INCREMENT(ttUpperBoundCount)
			beta = MIN(beta, hashScore);
			tryNullMove = false;
			break;

		  case LowerBound:
			STAT_INCREMENT(ttLowerBoundCount)
			wasLowerBound = true;
			alpha = hashScore;
			break;

		  case Quiescent:
		  case PoorDraft:
			break;
		}
		if( alpha >= beta )
			return hashScore;
	}

	int originalAlpha = alpha;

	// ***************** //
	// *** Null Move *** //
	// ***************** //

	//	conditions for null move:
	//	  - not in check
	//	  - we didn't just make a null move
	//	  - we don't have a risk of zugzwang 
	//		(because we're not in the endgame)
	//	  - depth is >= R + 1
	//	  - not at a PV node
	//	  - the material balance + a margin 
	//		is above the upper bound (beta)
	//	what we do after null move:
	//	  - if score is >= beta, we can get an early cutoff and exit
	//	  - if score is close to -MATE, we're in danger, so extend

	int nullReduction = depth >= 9 ? 4 : (depth >= 6 ? 3 : 2);
	if( currentDepth > 4 && inCheck[currentDepth-2] && inCheck[currentDepth-4] )
		tryNullMove = false;
	if( tryNullMove && !inCheck[currentDepth] && currentDepth > 1 && 
		depth > nullReduction + 1 && nodeType != PV && 
		nCapturedPieces < theGame->GetEndgameCaptureThreshold() && 
		beta < MATE - 100 && beta > -MATE + 100 && 
		GetMaterial() + 2800 > beta )
	{
		//	perform the null move
		TRACE("performing null move, depth = %d", depth - NULL_REDUCTION);
		gameRecords[gamePly].pieceMoved = NULL;
		gameRecords[gamePly].primaryHash = 0UL;
		gameRecords[gamePly].moveType = NullMove;
		gameRecords[gamePly].materialCaptured = 0;
		gameRecords[gamePly].promotionValue = 0;
		gameRecords[gamePly].checkingSquare = -1;
		gameRecords[gamePly].gameFlags = gameRecords[gamePly-1].gameFlags;
		gameRecords[gamePly].gameInt1 = gameRecords[gamePly-1].gameInt1;
		gameRecords[gamePly].gameInt2 = gameRecords[gamePly-1].gameInt2;
		gamePly++;
		currentPlayer = FLIP(currentPlayer);

		//	now search with reduced depth
		currentDepth++;
		nullScore = -Search( -beta, -beta + 1, depth - nullReduction - 1, false, nodeType, bestMoveNextLevel );
		currentDepth--;
		TRACE("null move score = %d\n", score);

		//	undo the null move
		currentPlayer = FLIP(currentPlayer);
		gamePly--;

		if( !timeLeft )
			return( 0 );

		if( nullScore >= beta )
		{
			STAT_INCREMENT(nullCutoffs)

			//	store information into the hash table
			hashTable.Store( depth - nullReduction - 1, nullScore, LowerBound, Movement() );

			return beta;
		}

		//	we are in serious danger of being checkmated; extend the search
		if( nullScore < -INFINITY + 500 && !extend && currentDepth <= (iDepth << 1) )
		{
			STAT_INCREMENT(mateThreatExtensions)
			extend = true;
			depth++;
		}
	}

	// *** RAZORING *** //
/*	if( nodeType != PV && depth <= 3 && 
		!inCheck[currentDepth] && 
		GetMaterial() < beta - pGame->GetRazorMargin() )
	{
		int qscore = QuiescentSearch( alpha, beta, 1, nodeType );
		if( qscore < beta - 500 - (500 * depth) )
		{
			STAT_INCREMENT(nodesRazored)
			return qscore;
		}
	}*/

	// *** INTERNAL ITERATIVE DEEPENING *** //
	if( !hashMove.IsValid() && 
		((nodeType == PV && depth >= 4) || 
		 (nodeType == Cut && depth >= 7)) )
	{
		if( nodeType == PV )
		{
			score = Search( alpha, beta, depth - 2, false, nodeType, hashMove );
			if( score <= alpha )
				score = Search( -INFINITY, alpha + 1, depth - 2, false, nodeType, hashMove );
		}
		else
		{
			score = Search( alpha, beta, depth - 4, false, nodeType, hashMove );
			if( score <= alpha )
				score = Search( -INFINITY, alpha + 1, depth - 4, false, nodeType, hashMove );
		}
	}

	// *** MOVE GENERATION *** //	
	MovementList &list = GetCurrentMovementList();

	list.GenerateMoves( hashMove, Movement(), nodeType );

	// *** RECAPTURE EXTENSION *** //
//	int recaptureSquare = -2;
//	int recaptureDelta = (100 * personality);
//	if( !extend && currentDepth <= iDepth + 2 && 
//		gameRecords[gamePly-1].pieceMoved != NULL &&
//		gameRecords[gamePly-1].materialCaptured > 0 )
		//	candidate for recapture extension on this square
//		recaptureSquare = gameRecords[gamePly-1].pieceMoved->GetSquareNumber();


	// *** FUTILITY and RAZORING *** //

	//	Futility: at depth 2 or 1, if there are no extensions and we are quite 
	//	bad, then we prune out all non checking moves and capturing moves that 
	//	don't bring us up back to alpha.

	//  NOTE: in the ending, that is, when the number of captured pieces exceeds 
	//	the engame capture margin specified by the Game sub-class, futility pruning 
	//	is disabled (along with null-move)

	bool cut = false;
	int material = GetMaterial();
	cut = !extend && nodeType != PV && depth == 2 && 
		nCapturedPieces < theGame->GetEndgameCaptureThreshold() &&
		material + pGame->GetExtendedFutilityMargin() <= alpha;
	if( !cut )
	{
		cut = !extend && nodeType != PV && depth == 1 && 
			nCapturedPieces < theGame->GetEndgameCaptureThreshold() &&
			material + pGame->GetFutilityMargin() <= alpha;
	}

	//	update node type
	NodeType originalNodeType = nodeType;
	switch( nodeType )
	{
	  case Cut:
		nodeType = All;
		break;

	  case All:
		nodeType = Cut;
		break;

	  case PV:
		STAT_INCREMENT(pvNodeEncountered)
		break;
	}
		

	//	initialize parameters for move loop
	int bestMoveIndex = 0;
	int nMove = 0;
	int nStandardMove = 0;
	bool movesRemaining = true;
	bool firstMoveExtended = false;
	bool firstMoveBest = true;
	MoveInfo presentMove;

	// ***************** //
	// *** Move Loop *** //
	// ***************** //
	while( movesRemaining )
	{
		#ifdef _DEBUG
		AssertValid();
		word32 priHash = primaryHash;
		word32 secHash = secondaryHash;
		word32 priPawnHash = primaryPawnHash;
		word32 secPawnHash = secondaryPawnHash;
		int dbg_player, dbg_piece;
		for( dbg_player = 0; dbg_player < 2; dbg_player++ )
			for( dbg_piece = 0; dbg_piece < nPieces[dbg_player]; dbg_piece++ )
				pieces[dbg_player][dbg_piece]->dbg_squareNumber[currentDepth] = pieces[dbg_player][dbg_piece]->GetSquareNumber();
		#endif

		//	make the move
		STAT_INCREMENT(nodeCount);
		if( !list.MakeNextMove() )
		{
			//	no legal moves left
			movesRemaining = false;
			continue;
		}

		presentMove = list.GetCurrentMove();
		nMove++;
		if( presentMove.type == StandardMove )
			nStandardMove++;

		// *** RECAPTURE EXTENSION *** //
		int extendMove = 0;
//		if( gameRecords[gamePly-1].pieceMoved->GetSquareNumber() == recaptureSquare && !extend )
//		{
//			int delta = gameRecords[gamePly-1].materialCaptured - 
//				        gameRecords[gamePly-2].materialCaptured;
//			if( (delta >= -recaptureDelta && delta <= recaptureDelta) || 
//				gameRecords[gamePly-2].promotionValue > 0 )
//			{
				//	extend this move by 1
//				STAT_INCREMENT(recaptureExtensions)
//				extendMove = 1;
//			}
//		}

		if( nMove == 1 )
		{
			TRACE_MOVE("searching move %s to depth %d (a=%d, b=%d)\n", list.GetCurrentMove(), depth + extendMove - 1, -beta, -alpha);

			//	go deeper (recursively) by searching with the full alpha-beta window
			currentDepth++;
			score = -Search( -beta, -alpha, depth + extendMove - 1, true, nodeType, bestMoveNextLevel );
			currentDepth--;

			if( extend || extendMove )
				firstMoveExtended = true;
		}
		else
		{
			// *** FUTILITY PRUNING *** //
			if( cut && presentMove.type == StandardMove )
			{
				MoveInfo &move = list.GetCurrentMove();
				if( !pGame->IsGoalToCheckmate() || 
					!pGame->IsSquareAttacked( kings[FLIP(currentPlayer)]->GetSquareNumber(), currentPlayer ) )
				{
					//	this node is futility pruned!
					//	undo move and continue to next iteration of move loop
					TRACE_MOVE0("move %s is futility pruned!\n", list.GetCurrentMove());
					list.UnmakeMove();
					STAT_INCREMENT(nodesPruned);
					continue;
				}
			}

			// *** LATE MOVE REDUCTION *** //
			int reduction =
				depth >= 2 && !extend && nMove > 6 && nStandardMove > 2 && presentMove.type == StandardMove
				? MIN( depth, nMove ) / 10 + 1 : 0;

			if( nodeType == PV )
				nodeType = Cut;

			//	go deeper (recursively)
			TRACE_MOVE("searching move %s to depth %d (a=%d, b=%d)\n", list.GetCurrentMove(), depth + extendMove - 1, -alpha - 1, -alpha);
			currentDepth++;
			score = -Search( -alpha - 1, -alpha, depth + extendMove - reduction - 1, true, nodeType, bestMoveNextLevel );
			if( reduction > 0 && score >= beta )
				//	research without reduction
				score = -Search( -alpha - 1, -alpha, depth + extendMove - 1, true, nodeType, bestMoveNextLevel );
			currentDepth--;

			if( score > bestScore )
			{
				firstMoveBest = false;
				if( originalNodeType == PV )
					nodeType = PV;
				if( score > alpha && score < beta )
				{
					//	we need to re-scan with full window
					TRACE("move score of %d is outside zero-search window; researching ...\n", score);
					TRACE_MOVE("searching move %s to depth %d (a=%d, b=%d)\n", list.GetCurrentMove(), depth + extendMove - 1, -beta, -score);
					currentDepth++;
					score = -Search( -beta, -score, depth + extendMove - 1, true, nodeType, bestMoveNextLevel );
					currentDepth--;
				}
			}
		}
		TRACE("move score = %d\n", score);

		int moveIndex = list.GetCurrentMoveIndex();

		//	undo the move
		list.UnmakeMove();

		#ifdef _DEBUG
		for( dbg_player = 0; dbg_player < 2; dbg_player++ )
			for( dbg_piece = 0; dbg_piece < nPieces[dbg_player]; dbg_piece++ )
				if( !pieces[dbg_player][dbg_piece]->IsCaptured() )
					ASSERT(pieces[dbg_player][dbg_piece]->dbg_squareNumber[currentDepth] == pieces[dbg_player][dbg_piece]->GetSquareNumber());
		AssertValid();
		ASSERT(primaryHash == priHash);
		ASSERT(secondaryHash == secHash);
		ASSERT(primaryPawnHash == priPawnHash);
		ASSERT(secondaryPawnHash == secPawnHash);
		#endif

		if( score > bestScore && timeLeft )
		{
			bestScore = score;

			//	check our current score vs. alpha
			if( score > alpha )
			{
				bestMoveIndex = moveIndex;
				MoveInfo &moveInfo = list.GetMove( moveIndex );
				bestMoveNextLevel = (Movement) moveInfo;
				if( score >= beta )
				{
					//	*** BETA CUT-OFF *** //

					//	we can "prune" out part of the search tree.  simply put,
					//	we can do this without risk of missing a good move because:
					//		the opponent is not going to let the player to move achieve 
					//		this position, because there is some choice the opponent could
					//		make (higher up) that would avoid it.  of course, we are assuming 
					//		here that the opponent will always make the best move he can. 

					TRACE("BETA CUT-OFF, storing lower bound of %d in TT and returning\n", score);

					if( score > originalAlpha )
					{
						//	update the killer moves
						SAVE_KILLER(moveInfo)

						//	history heuristic
						if( depth >= 3 )
							history[currentDepth][moveInfo.fromSquare * nSquares + moveInfo.toSquare] += ((depth - 2) * (depth - 2) * 4);
					}

					//	store information into the hash table
					hashTable.Store( depth, score, LowerBound, (Movement) moveInfo );

					//	failing high ...
					return score;
				}
				alpha = score;
			}
		}

		if( !timeLeft )
			return( 0 );
	}

	//	check for checkmate or stalemate
	if( nMove == 0 )
	{
		//	no legal moves. :(
		if( pGame->IsGoalToCheckmate() && inCheck[currentDepth] )
		{
			//	checkmate
			alpha = -INFINITY + currentDepth;
			TRACE("CHECKMATE detected!!! alpha is now %d\n", alpha);
		}
		else
		{
			//	stalemate
			alpha = -pGame->GetStalemateScore();
			TRACE("STALEMATE detected!!! alpha is now %d\n", alpha);
		}
	}
	else
	{
		//	check for a draw by fifty-move rule,
		//	if this game has one
		if( pGame->GetAutoDrawPeriod() > 0 )
			if( gamePly - gameRecords[gamePly].lastCaptureOrPawn > pGame->GetAutoDrawPeriod() )
			{
				//	it's a draw
				TRACE("DRAW BY REPETITION detected!!! returning draw score of %d\n", pGame->GetDrawScore());
				return pGame->GetDrawScore();
			}
	}

	MoveInfo &moveInfo = list.GetMove( bestMoveIndex );

	if( originalNodeType == PV && firstMoveBest )
		STAT_INCREMENT(pvNodeFirstMoveCorrect)

	if( alpha > originalAlpha )
	{
		// *** KILLER MOVE *** //
		SAVE_KILLER(moveInfo)

		//	history heuristic
		if( depth >= 3 )
			history[currentDepth][moveInfo.fromSquare * nSquares + moveInfo.toSquare] += ((depth - 2) * (depth - 2) * 2);

		// *** TRANSPOSITION TABLE Exact *** //
		hashTable.Store( depth, alpha, Exact, (Movement) moveInfo );
	}
	else
	{
		// *** TRANSPOSITION TABLE Upper Bound *** //
		hashTable.Store( depth, alpha, UpperBound, Movement() );
	}

	//	failing low ... return alpha (upper bound)
	return alpha;
}

int Board::QuiescentSearch
	( int alpha, 
	  int beta, 
	  int qdepth,
	  NodeType nodeType )
{
	int originalAlpha = alpha;
	int score = -INFINITY;

	inCheck[currentDepth] = !pGame->IsGoalToCheckmate() ? false : IsInCheck();
//			(pGame->HasSpecialCheckTesting() ? IsInCheck() :
//			 IsInCheck( gameRecords[gamePly-1].oldSquareNumber, 
//			 gameRecords[gamePly-1].pieceMoved->GetSquareNumber() ));

	if( qdepth >= 0 && STAT_LOOKUP(nodeCount) % 8192LL == 0LL )
		Bookkeeping();

	//	call Game override to test for wins/losses/draws in
	//	case of insufficient material, or because the game 
	//	has unusual victory conditions
	if( pGame->TestForWinLossDraw( score ) )
		return score;

	//	have we exceeded the maximum depth?
	if( currentDepth == maximumDepth )
		return Evaluate( alpha, beta );

	//	check for draw by repetition
	if( IsDraw() )
		return( pGame->GetDrawScore() );

	//	see if our position is good enough that we can exit early
	int standpat = Evaluate( alpha, beta );
	if( standpat >= beta )
	{
		QTRACE("Q-Search standing pat at %d\n", standpat);
		return( standpat );
	}
	if( standpat > alpha )
		alpha = standpat;

	//	*** MOVE GENERATION ***  //	
	MovementList &list = GetCurrentMovementList();
	list.GenerateCaptures( Movement(), nodeType );

	bool movesRemaining = true;
	bool anyLegalMove = false;
	int bestMoveIndex = 0;
	while( movesRemaining ) 
	{
		#ifdef _DEBUG
		AssertValid();
		word32 priHash = primaryHash;
		word32 secHash = secondaryHash;
		word32 priPawnHash = primaryPawnHash;
		word32 secPawnHash = secondaryPawnHash;
		#endif

		//	make the move
		if( qdepth >= 0 )
		{
			STAT_INCREMENT(qnodeCount);
			STAT_INCREMENT(nodeCount);
		}
		if( !list.MakeNextMove() )
		{
			movesRemaining = false;
			continue;
		}

		MoveInfo &presentMove = list.GetCurrentMove();
		anyLegalMove = true;

		// *** FUTILITY PRUNING *** //
		if( qdepth >= 1 )
		{
			int materialCaptured = gameRecords[gamePly-1].materialCaptured;
			if( standpat + materialCaptured + 1000 < alpha )
			{
				list.UnmakeMove();
				continue;
			}
		}

		//	go deeper (recursively)
		QTRACE_MOVE("Q-Searching move %s (a=%d, b=%d)\n", list.GetCurrentMove(), -beta, -alpha);
		currentDepth++;
		score = -QuiescentSearch( -beta, -alpha, qdepth + 1, nodeType );
		currentDepth--;
		QTRACE("move score = %d\n", score);

		int moveIndex = list.GetCurrentMoveIndex();

		//	undo the move
		list.UnmakeMove();

		#ifdef _DEBUG
		AssertValid();
		ASSERT(primaryHash == priHash);
		ASSERT(secondaryHash == secHash);
		ASSERT(primaryPawnHash == priPawnHash);
		ASSERT(secondaryPawnHash == secPawnHash);
		#endif

	    //	check our current score vs. alpha
		if( score > alpha )
		{
			alpha = score;
			bestMoveIndex = moveIndex;

			if( score >= beta )
			{
				QTRACE("BETA CUT-OFF in Q-Search, score=%d\n", score);

				//	don't add to hashtable here; as far as I know,
				//	the hashtable is useless in q-search.

				return score; // ?!?! Same question here ...
			}
		}
	}

	if( !anyLegalMove )
		//	don't return checkmate score in q-search
		return standpat;

	return alpha;
}

void Board::CheckAllMoveLists()
{
	for( int x = 0; x < MAX_DEPTH; x++ )
	{
		if( movementLists[x].GetBoard() != this )
		{
			ASSERT(FALSE);
		}
	}
}

