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

                                 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 "ChessV.h"
#include "Board.h"
#include "Piece.h"
#include "Movement.h"


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

// ***********************************************************************
// *
// *	Clear
// *
// *	clears all moves off the stack; resets all cursors

void MovementList::Clear()
{
	moveCursor = 0;
	pickupCursor = 0;
	dropCursor = 0;
	currentMove = 0;
	quiescentSearch = false;
}

// ***********************************************************************
// *
// *	CopyMoveToList
// *
// *	this function is used to copy a move from this MovementList
// *	onto the top of another MovementList.  the return value is
// *	the move index into the stack onto which it was added.

int MovementList::CopyMoveToList
	( int moveNumber,			//	index into moves of move to copy
	  MovementList &other )	//	movement stack to copy to
{
	//	initialize reference to the requested move
	MoveInfo &moveInfo = moves[moveNumber];

	other.BeginMoveCopy( moveInfo.type, moveInfo.fromSquare, moveInfo.toSquare, 
		moveInfo.tag, moveInfo.promotion );

	int firstPickup = moveNumber == 0 ? 0 : moves[moveNumber - 1].pickupCursor;
	int firstDrop = moveNumber == 0 ? 0 : moves[moveNumber - 1].dropCursor;
	int nCaptures = (moveInfo.pickupCursor - firstPickup) - (moveInfo.dropCursor - firstDrop);

	//	push all pickups
	for( int pickup = firstPickup; pickup < moveInfo.pickupCursor; pickup++ )
		other.AddPickUp( pickups[pickup].GetSquareNumber() );

	//	push all drops (normally only one)
	for( int drop = firstDrop; drop < moveInfo.dropCursor; drop++ )
		other.AddDrop( drops[drop].GetPiece(), 
			drops[drop].GetSquareNumber(), drops[drop].GetSwapType() );

	return other.EndMoveCopy( moveInfo.evaluation );
}


/************************************************************************\ 
**************************************************************************
**                                                                      **
**                   ADDING MOVES TO THE LIST                           **
**                                                                      **
**  These functions are called by PieceType::GenerateMoves and          **
**  PieceType::GenerateCaptures.  Game classes may also override        **
**  the AddSpecialMoves function to manually push special moves onto    **
**  the stack.  The ChessGame class does this to implement castling     **
**  and En Passant.                                                     **
**                                                                      **
**************************************************************************
\************************************************************************/

// ***********************************************************************
// *
// *	AddMove
// *
// *	adds a "standard move" to the movement list.  a standard move is a
// *	normal chess move in which only one piece is moved, and no capture
// *	is involved.  this function does handle promotions, though.

void MovementList::AddMove
	( int fromSquareNumber,		//	square to lift piece from
	  int toSquareNumber )		//	square onto which to drop the piece
{
	Piece **sourceSquare      = board->GetSquareReference( fromSquareNumber );
	Piece **targetSquare      = board->GetSquareReference( toSquareNumber );
	Piece *pieceBeingMoved    = *sourceSquare;
	Piece *pieceBeingCaptured = *targetSquare;
	ASSERT(pieceBeingCaptured == NULL);

	// *** determine PROMOTIONS available *** ///
	PieceType *types[20];
	Piece *pieces[20];
	int promotionTypes = 0;
	int promotionPieces = 0;
	if( pieceBeingMoved->GetPromotion().GetPromotionCapability() != NoPromotion &&
		pieceBeingMoved->GetPromotionZone().IsInZone( toSquareNumber ) )
	{
		if( pieceBeingMoved->GetPromotion().GetPromotionCapability() == PromoteToSpecificType )
		{
			promotionTypes = 1;
			types[0] = &(pieceBeingMoved->GetPromotion().GetTypeToPromoteTo());
		}
		else if( pieceBeingMoved->GetPromotion().GetPromotionCapability() == PromoteToVariableTypes )
		{
			promotionTypes = board->GetGame().EnumeratePromotions( pieceBeingMoved, 
				fromSquareNumber, toSquareNumber, types, quiescentSearch );
		}
		else if( pieceBeingMoved->GetPromotion().GetPromotionCapability() == PromoteByReplacement )
		{
			promotionPieces = board->GetGame().EnumeratePromotions( pieceBeingMoved, 
				fromSquareNumber, toSquareNumber, pieces, quiescentSearch );
		}
		else if( pieceBeingMoved->GetPromotion().GetPromotionCapability() == PromoteByReplacementOrToVariableTypes )
		{
			promotionTypes = board->GetGame().EnumeratePromotions( pieceBeingMoved, 
				fromSquareNumber, toSquareNumber, types, quiescentSearch );
			promotionPieces = board->GetGame().EnumeratePromotions( pieceBeingMoved, 
				fromSquareNumber, toSquareNumber, pieces, quiescentSearch );
		}
		if( promotionTypes + promotionPieces == 0 )
			//	no promotion available - the move is therefore illegal
			return;
	}

	//	we loop here, because we might actually push several moves here, in 
	//	the case of a move which promotes a piece to any of multiple types, 
	//	such as pawn promotion in Chess - a call to AddMove which moves a 
	//	pawn to the eigth rank will actually push four moves, one for each 
	//	type of piece to which the pawn can promote. 
	do
	{
		// *** ADD MOVE INFORMATION *** //
		moves[moveCursor].pPieceMoved = pieceBeingMoved;
		moves[moveCursor].originalType = &(pieceBeingMoved->GetType());
		moves[moveCursor].fromSquare = fromSquareNumber;
		moves[moveCursor].toSquare = toSquareNumber;
		moves[moveCursor].tag = 0;

		//	the move begins by picking up the source piece
		pickups[pickupCursor++] = PickUp( pieceBeingMoved, fromSquareNumber );

		//	assume at this point that move is a StandardMove
		moves[moveCursor].type = StandardMove;

		// *** PROMOTION *** //
		moves[moveCursor].promotion = NULL;
		if( promotionTypes > 0 )
		{
			moves[moveCursor].promotion = types[--promotionTypes];
			if( moves[moveCursor].promotion == &(pieceBeingMoved->GetType()) )
				//	we are not actually switching types, so no promotion
				moves[moveCursor].promotion = NULL;
			//	drop the moving piece on the target square
			drops[dropCursor++] = Drop( pieceBeingMoved, toSquareNumber, moves[moveCursor].promotion );
		}
		else if( promotionPieces > 0 )
		{
			if( pieces[promotionPieces-1] != pieceBeingMoved )
			{
				moves[moveCursor].type = Replacement;
				moves[moveCursor].promotion = &(pieces[promotionPieces-1]->GetType());
			}
			//	drop the replacement piece on the target square
			drops[dropCursor++] = Drop( pieces[--promotionPieces], toSquareNumber, NULL );
		}
		else
		{
			//	drop the moving piece on the target square
			drops[dropCursor++] = Drop( pieceBeingMoved, toSquareNumber, NULL );
		}

		//	initialize moveOrder array
		moveOrder[moveCursor] = moveCursor;

		//	store this info so we know which pickups and
		//	drops belong to this move
		moves[moveCursor].pickupCursor = pickupCursor;
		moves[moveCursor].dropCursor = dropCursor;
		moveCursor++;

		bool isLegal = true;
		if( checkForLegality && !loadingGame )
		{
			isLegal = MakeMove( moveCursor - 1 );
			if( isLegal )
			{
				//	this is the root movement list, so we 
				//	do more acurate move ordering here, by 
				//	making the move, and calling QuiescentSearch
				board->currentDepth++;
				moves[moveCursor-1].evaluation = -board->QuiescentSearch( -INFINITY, INFINITY, -1000, All );
				board->currentDepth--;
				UnmakeMove( moveCursor - 1 );
			}
			else
			{
				UnmakeMove( moveCursor - 1 );
				moveCursor--;
				pickupCursor--;
				dropCursor--;
			}
		}
		else
		{
			// *** EVALUATION *** //

			//	we assign an evaluation to the move here, to determine 
			//	the order into which the moves will be sorted
			MoveInfo &move = moves[moveCursor-1];

			if( move == hashtableMove )
				//	move looked up from hash table; gets 2nd hightest ordering
				move.evaluation = INFINITY;
			else if( move == board->killer1[board->currentDepth] || 
					 move == board->killer2[board->currentDepth] )
			{
				//	killer moves are ordered next (actually, captures come
				//	next, but they aren't handled by this function)
				move.evaluation = 3600;
			}
			else if( board->currentDepth > 2 && 
					 (move == board->killer1[board->currentDepth-2] || 
					  move == board->killer2[board->currentDepth-2]) )
			{
				move.evaluation = 3400;
			}
			else
			{
				//	all other moves are ordered last; they are ordered differently 
				//	if we are in the opening
				if( board->gamePly < 20 )
				{
					if( move.pPieceMoved->GetType().IsPawn() )
					{
						//	base eval for a move of a pawn in the opening is based on which 
						//	file it occupies.  moving center pawns is good; edge pawns is bad
						move.evaluation = board->openingMoveEvalForPawnBasedOnFile[board->files[0][move.toSquare]];
						if( move.pPieceMoved->HasMoved() )
						{
							//	we seldom want to move a pawn twice in the opening
							move.evaluation -= 10;
							if( move.pPieceMoved->HasMovedTwice() )
								//	we really don't want to move it 3 times!
								move.evaluation -= 50;
						}
					}
					else
					{
						//	eval based on the value of the square they take - the value of the 
						//	square they leave so as to order moves to the center higher
						if( move.pPieceMoved->GetType().UsingSquareBonusTables() )
						{
							int *table = move.pPieceMoved->GetType().GetSquareBonusTable( 0 );
							move.evaluation = table[board->flipSquare[move.pPieceMoved->GetPlayerNumber()][move.toSquare]] - 
								table[board->flipSquare[move.pPieceMoved->GetPlayerNumber()][move.fromSquare]];
						}
						else
							move.evaluation = board->squareValues[move.toSquare] - 
								board->squareValues[move.fromSquare];

						//	bonus for promotions to piece types of higher value
						if( move.promotion != NULL )
							move.evaluation += move.promotion->GetBaseValue() - pieceBeingMoved->GetType().GetBaseValue();

						//	in the opening, we want to move pieces that haven't been moved, 
						//	but we don't want to move the heavy pieces (rooks and queens), and 
						//	we don't want to move the King (save that for castling, which is
						//	not handled by this funciton
						if( !move.pPieceMoved->HasMoved() )
						{
							if( move.pPieceMoved->GetBaseValue() < 4000 && !move.pPieceMoved->GetType().IsRoyal() )
								move.evaluation += 50 + ((4000 - move.pPieceMoved->GetBaseValue()) >> 5) ;
							else
								move.evaluation -= 50;
						}
						else
						{
							//	we don't want to move pieces again that have already moved
							move.evaluation -= 50;
							if( move.pPieceMoved->HasMovedTwice() )
								//	we really don't want to move a piece 3 times!!!
								move.evaluation -= 50;
						}
					}
				}
				else
				{
					//	eval based on the value of the square they take - the value of the 
					//	square they leave so as to order moves to the center higher
					if( move.pPieceMoved->GetType().UsingSquareBonusTables() )
					{
						int *table = move.pPieceMoved->GetType().GetSquareBonusTable( 1 );
						move.evaluation = table[board->flipSquare[move.pPieceMoved->GetPlayerNumber()][move.toSquare]] - 
							table[board->flipSquare[move.pPieceMoved->GetPlayerNumber()][move.fromSquare]];
					}
					else
						move.evaluation = board->squareValues[move.toSquare] - 
							board->squareValues[move.fromSquare];

					if( move.promotion != NULL )
						//	bonus for promotions to piece types of higher value
						move.evaluation += move.promotion->GetBaseValue() - pieceBeingMoved->GetType().GetBaseValue();

					//	bonus for historically successful moves
					move.evaluation += board->history[board->currentDepth][move.fromSquare * board->nSquares + move.toSquare];
				}
			}
		}
	}
	while( promotionTypes + promotionPieces > 0 );
}

// ***********************************************************************
// *
// *	AddCapture
// *
// *	adds a "standard capture" to the movement list.  a standard capture
// *	is a normal chess capture.  En Passant is an example of a move
// *	that is not a standard capture, and could not be handled by this
// *	function, because the piece being captured isn't on the
// *	target square.

static Piece *testingPointer = NULL;
static Piece *testingPointer2 = NULL;

void MovementList::AddCapture
	( int fromSquareNumber,
	  int toSquareNumber )
{
	Piece **sourceSquare      = board->GetSquareReference( fromSquareNumber );
	Piece **targetSquare      = board->GetSquareReference( toSquareNumber );
	Piece *pieceBeingMoved    = *sourceSquare;
	Piece *pieceBeingCaptured = *targetSquare;
	ASSERT(pieceBeingCaptured != NULL);
	testingPointer = pieceBeingMoved;
	testingPointer2 = pieceBeingCaptured;


	// *** determine PROMOTIONS available *** //
	PieceType *types[20];
	Piece *pieces[20];
	int promotionTypes = 0;
	int promotionPieces = 0;
	if( pieceBeingMoved->GetPromotion().GetPromotionCapability() != NoPromotion &&
		pieceBeingMoved->GetPromotionZone().IsInZone( toSquareNumber ) )
	{
		if( pieceBeingMoved->GetPromotion().GetPromotionCapability() == PromoteToSpecificType )
		{
			promotionTypes = 1;
			types[0] = &(pieceBeingMoved->GetPromotion().GetTypeToPromoteTo());
		}
		else if( pieceBeingMoved->GetPromotion().GetPromotionCapability() == PromoteToVariableTypes )
		{
			promotionTypes = board->GetGame().EnumeratePromotions( pieceBeingMoved, 
				fromSquareNumber, toSquareNumber, types, quiescentSearch );
		}
		else if( pieceBeingMoved->GetPromotion().GetPromotionCapability() == PromoteByReplacement )
		{
			promotionPieces = board->GetGame().EnumeratePromotions( pieceBeingMoved, 
				fromSquareNumber, toSquareNumber, pieces, quiescentSearch );
		}
		else if( pieceBeingMoved->GetPromotion().GetPromotionCapability() == PromoteByReplacementOrToVariableTypes )
		{
			promotionTypes = board->GetGame().EnumeratePromotions( pieceBeingMoved, 
				fromSquareNumber, toSquareNumber, types, quiescentSearch );
			promotionPieces = board->GetGame().EnumeratePromotions( pieceBeingMoved, 
				fromSquareNumber, toSquareNumber, pieces, quiescentSearch );
		}
		if( promotionTypes + promotionPieces == 0 )
			//	the move is therefore illegal
			return;
	}

	//	we loop here, because we might actually push several moves here, in 
	//	the case of a move which promotes a piece to any of multiple types, 
	//	such as pawn promotion in Chess - a call to AddMove which moves a 
	//	pawn to the eigth rank will actually push four moves, one for each 
	//	type of piece to which the pawn could promote. 
	do
	{
		//	** ADD MOVE INFORMATION **  //
		moves[moveCursor].pPieceMoved = pieceBeingMoved;
		moves[moveCursor].originalType = &(pieceBeingMoved->GetType());
		moves[moveCursor].fromSquare = fromSquareNumber;
		moves[moveCursor].toSquare = toSquareNumber;
		moves[moveCursor].type = StandardCapture;
		moves[moveCursor].tag = 0;

		//	the move begins by picking up the source piece
		pickups[pickupCursor++] = PickUp( pieceBeingMoved, fromSquareNumber );

		//	pick up the captured piece
		pickups[pickupCursor++] = PickUp( pieceBeingCaptured, toSquareNumber );

		// *** PROMOTION *** //
		moves[moveCursor].promotion = NULL;
		if( promotionTypes > 0 )
		{
			moves[moveCursor].promotion = types[--promotionTypes];
			if( moves[moveCursor].promotion == &(pieceBeingMoved->GetType()) )
				//	we are not actually switching types, so no promotion
				moves[moveCursor].promotion = NULL;
			//	drop the moving piece on the target square
			drops[dropCursor++] = Drop( pieceBeingMoved, toSquareNumber, moves[moveCursor].promotion );
		}
		else if( promotionPieces > 0 )
		{
			if( pieces[promotionPieces-1] != pieceBeingMoved )
			{
				moves[moveCursor].type = CaptureWithReplacement;
				moves[moveCursor].promotion = &(pieces[promotionPieces-1]->GetType());
			}
			//	drop the replacement piece on the target square
			drops[dropCursor++] = Drop( pieces[--promotionPieces], toSquareNumber, NULL );
		}
		else
		{
			//	drop the moving piece on the target square
			drops[dropCursor++] = Drop( pieceBeingMoved, toSquareNumber, NULL );
		}

		//	initialize moveOrder array
		moveOrder[moveCursor] = moveCursor;

		//	store this info so we know which pickups and
		//	drops belong to this move
		moves[moveCursor].pickupCursor = pickupCursor;
		moves[moveCursor].dropCursor = dropCursor;
		moveCursor++;

		if( hashtableMove.GetMoveType() == StandardCapture && 
			hashtableMove.GetFromSquare() == fromSquareNumber && 
			hashtableMove.GetToSquare() == toSquareNumber )
			hashtableMoveFound = true;

		bool isLegal = true;
		if( checkForLegality )
		{
			isLegal = MakeMove( moveCursor - 1 );
			if( isLegal )
			{
				//	this is the root movement list, so we 
				//	do more acurate move ordering here, by 
				//	making the move, and calling QuiescentSearch
				board->currentDepth++;
				moves[moveCursor-1].evaluation = -board->QuiescentSearch( -INFINITY, INFINITY, -1000, All );
				board->currentDepth--;
				UnmakeMove( moveCursor - 1 );
			}
			else
			{
				UnmakeMove( moveCursor - 1 );
				moveCursor--;
				dropCursor--;
				pickupCursor -= 2;
			}
		}
		else
		{
			MoveInfo &move = moves[moveCursor-1];

			//	perform fast evaluation of the likely value of this move
			if( move == hashtableMove )
				//	move looked up from hash table; gets the hightest ordering
				move.evaluation = INFINITY;
			else
			{
				//	for all remaining captures, it depends on whether or not we
				//	are in quiescent search.  in quiescent search, we use
				//	static exchange evaluation to assign a value to all captures
				//	where the value of the target is smaller than the attacker.
				//	in normal search, we don't use the expensive SEE function,
				//	rather we order all captures first and use the fast 
				//	MVV/LVA method ordering
				if( quiescentSearch )
				{
					if( theGame->UseStaticExchangeEvaluation() && 
						pieceBeingCaptured->GetBaseValue() < pieceBeingMoved->GetBaseValue() )
					{
						int exchange = EvaluateExchange( moveCursor - 1 );
						if( exchange >= 0 )
							move.evaluation = pieceBeingCaptured->GetBaseValue() - 
								(pieceBeingMoved->GetBaseValue() >> 4);
						else
							move.evaluation = -10000;
					}
					else
						move.evaluation = pieceBeingCaptured->GetBaseValue() - 
							(pieceBeingMoved->GetBaseValue() >> 4);
				}
				else
				{
					if( theGame->UseStaticExchangeEvaluation() && 
						pieceBeingCaptured->GetBaseValue() < pieceBeingMoved->GetBaseValue() )
					{
						int exchange = EvaluateExchange( moveCursor - 1 );
						if( exchange > 0 )
							move.evaluation = pieceBeingCaptured->GetBaseValue() - 
								(pieceBeingMoved->GetBaseValue() >> 4) + 5500 ;
						else if( exchange == 0 )
							move.evaluation = pieceBeingCaptured->GetBaseValue() - 
								(pieceBeingMoved->GetBaseValue() >> 4) + 2500 ;
						else
							move.evaluation = pieceBeingCaptured->GetBaseValue() - 
								(pieceBeingMoved->GetBaseValue() >> 4) + 1000 ; 
					}
					else
						move.evaluation = pieceBeingCaptured->GetBaseValue() - 
							(pieceBeingMoved->GetBaseValue() >> 4) + 5000 + 
							board->squareValues[move.toSquare] - 
							board->squareValues[move.fromSquare];
				}

				//	adjustment for promotions
				if( move.promotion != NULL )
					move.evaluation += move.promotion->GetBaseValue() - pieceBeingMoved->GetType().GetBaseValue();
			}
		}
	}
	while( promotionTypes + promotionPieces > 0 );
}

// ***********************************************************************
// *
// *	AddIguiCapture
// *
// *	pushes an "igui capture" onto the stack.  an igui capture is a
// *	capture where the capturing piece doesn't actually move.  
// *	nothing else happens except that the target piece is removed.

void MovementList::AddIguiCapture
	( int fromSquareNumber,
	  int toSquareNumber )
{
	Piece **sourceSquare      = board->GetSquareReference( fromSquareNumber );
	Piece **targetSquare      = board->GetSquareReference( toSquareNumber );
	Piece *pieceBeingMoved    = *sourceSquare;
	Piece *pieceBeingCaptured = *targetSquare;
	ASSERT(pieceBeingCaptured != NULL);

	//	** PUSH MOVE INFORMATION **  //
	moves[moveCursor].pPieceMoved = pieceBeingMoved;
	moves[moveCursor].originalType = &(pieceBeingMoved->GetType());
	moves[moveCursor].fromSquare = fromSquareNumber;
	moves[moveCursor].toSquare = toSquareNumber;
	moves[moveCursor].type = IguiCapture;
	moves[moveCursor].tag = 0;

	pickups[pickupCursor++] = PickUp( pieceBeingCaptured, toSquareNumber );

	//	initialize moveOrder array
	moveOrder[moveCursor] = moveCursor;

	//	store this info so we know which pickups and
	//	drops belong to this move
	moves[moveCursor].pickupCursor = pickupCursor;
	moves[moveCursor].dropCursor = dropCursor;
	moveCursor++;

	if( checkForLegality )
	{
		bool isLegal = MakeMove( moveCursor - 1 );
		if( isLegal )
		{
			//	this is the root movement list, so we 
			//	do more acurate move ordering here, by 
			//	making the move, and calling QuiescentSearch
			board->currentDepth++;
			moves[moveCursor-1].evaluation = -board->QuiescentSearch( -INFINITY, INFINITY, -1000, All );
			board->currentDepth--;
			UnmakeMove( moveCursor - 1 );
		}
		else
		{
			UnmakeMove( moveCursor - 1 );
			moveCursor--;
			pickupCursor--;
		}
	}
	else
	{
		//	evaluate all igui captures as the value of the free material,
		//	plus a significant bonus; Igui captures should be ordered very high
		moves[moveCursor-1].evaluation = pieceBeingCaptured->GetBaseValue() + 4000;
	}
}

// ***********************************************************************
// *
// *	BeginMoveAdd
// *
// *	for games to implement complex or multi-part moves, like castling
// *	and en passant, a Game class must override the virtual function 
// *	AddSpecialMoves, and manually push those moves onto the stack.
// *	they are pushed by calling BeginMoveAdd, and then any number of
// *	calls to AddPickUp and AddDrop, and then completed by calling
// *	EndMoveAdd.

void MovementList::BeginMoveAdd
	( MoveType moveType,
	  int fromSquareNumber,
	  int toSquareNumber, 
	  byte tag )
{
	moves[moveCursor].promotion = NULL;
	moves[moveCursor].fromSquare = (short) fromSquareNumber;
	moves[moveCursor].toSquare = (short) toSquareNumber;
	moves[moveCursor].type = moveType;
	moves[moveCursor].pPieceMoved = board->GetSquareContents( fromSquareNumber );
	moves[moveCursor].originalType = &(board->GetSquareContents( fromSquareNumber )->GetType());
	moves[moveCursor].tag = tag;

	//	initialize moveOrder array
	moveOrder[moveCursor] = moveCursor;

	//	store temporary cursor values, in case this move turns out to be 
	//	illegal, in which case we need to restore the original values
	tempPickupCursor = pickupCursor;
	tempDropCursor = dropCursor;
}

// ***********************************************************************
// *
// *	AddPickUp

void MovementList::AddPickUp
	( int squareNumber )
{
	Piece *piece = board->GetSquareContents( squareNumber );

	ASSERT(piece != NULL);
	ASSERT(!piece->IsCaptured());
	ASSERT(piece->GetSquareNumber() == squareNumber);

	//	the move begins by picking up the source piece
	pickups[pickupCursor++] = PickUp( piece, squareNumber );
}

// ***********************************************************************
// *
// *	AddDrop

void MovementList::AddDrop
	( Piece *piece,
	  int squareNumber,
	  PieceType *newType )
{
	if( piece < (Piece *) ((void *) 0x1000UL) )
	{
		ASSERT(FALSE);
	}
	drops[dropCursor++] = Drop( piece, squareNumber, newType );
}

// ***********************************************************************
// *
// *	EndMoveAdd

int MovementList::EndMoveAdd
	( int evaluation )
{
	moves[moveCursor].pickupCursor = pickupCursor;
	moves[moveCursor].dropCursor = dropCursor;
	moves[moveCursor].evaluation = evaluation;
	moveCursor++;

	if( hashtableMove.GetMoveType() == moves[moveCursor-1].type && 
		hashtableMove.GetFromSquare() == moves[moveCursor-1].fromSquare && 
		hashtableMove.GetToSquare() == moves[moveCursor-1].toSquare )
		hashtableMoveFound = true;

	bool isLegal = true;
	if( checkForLegality )
	{
		bool isLegal = MakeMove( moveCursor - 1 );
		if( isLegal )
		{
			//	this is the root movement list, so we 
			//	do more acurate move ordering here, by 
			//	making the move, and calling QuiescentSearch
			board->currentDepth++;
			moves[moveCursor-1].evaluation = -board->QuiescentSearch( -INFINITY, INFINITY, -1000, All );
			board->currentDepth--;
			UnmakeMove( moveCursor - 1 );
		}
		else
		{
			UnmakeMove( moveCursor - 1 );
			pickupCursor = tempPickupCursor;
			dropCursor = tempDropCursor;
			moveCursor--;
		}
	}
	return moveCursor - 1;
}

// ***********************************************************************
// *
// *	BeginMoveCopy
// *
// *	this funciton, along with AddPickUp, AddDrop, and EndMoveCopy, are 
// *	used by the CopyMoveToList function.

void MovementList::BeginMoveCopy
	( MoveType moveType,
	  int fromSquareNumber,
	  int toSquareNumber, 
	  byte tag,
	  PieceType *promotion )
{
	moves[moveCursor].promotion = promotion;
	moves[moveCursor].fromSquare = (short) fromSquareNumber;
	moves[moveCursor].toSquare = (short) toSquareNumber;
	moves[moveCursor].type = moveType;
	moves[moveCursor].pPieceMoved = board->GetSquareContents( fromSquareNumber );
	moves[moveCursor].originalType = &(board->GetSquareContents( fromSquareNumber )->GetType());
	moves[moveCursor].tag = tag;

	//	initialize moveOrder array
	moveOrder[moveCursor] = moveCursor;
}

// ***********************************************************************
// *
// *	EndMoveCopy

int MovementList::EndMoveCopy
	( int evaluation )
{
	moves[moveCursor].pickupCursor = pickupCursor;
	moves[moveCursor].dropCursor = dropCursor;
	moves[moveCursor].evaluation = evaluation;
	return moveCursor++;
}

// ***********************************************************************
// *
// *	Pop
// *	
// *	removes the top move(s) from the stack

void MovementList::Pop
	( int moveCount )
{
	for( int i = 0; i < moveCount; i++ )
	{
		moveCursor--;
		if( moveCursor == 0 )
		{
			pickupCursor = 0;
			dropCursor = 0;
		}
		else
		{
			pickupCursor = moves[moveCursor-1].pickupCursor;
			dropCursor = moves[moveCursor-1].dropCursor;
		}
	}
}

/************************************************************************\ 
**************************************************************************
**                                                                      **
**                    MAKING and UNMAKING MOVES                         **
**                                                                      **
**************************************************************************
\************************************************************************/

// ***********************************************************************
// *
// *	MakeNextMove
// *
// *	makes the next move in the move order.  the move is then checked
// *	for legality.  if illegal, the move is undone, and the next move
// *	is tried, repeatedly until a legal move is found.  the function
// *	returns true if a legal move was found, false if we ran out of moves
// *	

bool MovementList::MakeNextMove()
{
	bool moveCompleted = false;

	//	if there are no moves at all, then give up here
	if( moveCursor == 0 )
		return false;

	if( quiescentSearch )
	{
		//	in quisecent search, we don't sort the moves ahead of time;
		//	instead we will look through all moves here and pick the best
		//	one; if we get an early cut-off, we saved the time of sorting
		while( !moveCompleted )
		{
			int bestMoveIndex = 0;
			int bestMoveEval = moves[0].evaluation;
			for( int x = 1; x < moveCursor; x++ )
				if( moves[x].evaluation > bestMoveEval )
				{
					bestMoveIndex = x;
					bestMoveEval = moves[x].evaluation;
				}

			if( bestMoveEval < 0 )
				//	the only captures left are (probably) losing captures,
				//	which we will not try in quiescent-search
				return false;

			//	now that we have our "best" move, set its evaluation
			//	to a negatvie number so it won't be tried again
			moves[bestMoveIndex].evaluation = -INFINITY;
			currentMove = bestMoveIndex;

			if( !MakeMove( bestMoveIndex ) )
				//	move was not legal, so undo it
				UnmakeMove();
			else
			{
				MoveInfo &mi = GetCurrentMove();
				moveCompleted = true;
			}
		}
	}
	else
	{
		while( currentMove < moveCursor && !moveCompleted )
		{
			if( !MakeMove( moveOrder[currentMove] ) )
			{
				UnmakeMove();
			}
			else
				moveCompleted = true;
		}
	}
	return moveCompleted;
}

// ***********************************************************************
// *
// *	UnmakeMove
// *
// *	unmakes the last move that was made

void MovementList::UnmakeMove()
{
	#ifdef _DEBUG
	ASSERT(indexOfMoveMade >= 0);
	#endif

	//	going back up
	board->gamePly--;

	//	initialize reference to the requested move
	MoveInfo &moveInfo = moves[indexOfMoveMade];

	//	undo all drops (normally only one)
	int firstDrop = indexOfMoveMade == 0 ? 0 : moves[indexOfMoveMade-1].dropCursor;
	for( int drop = firstDrop; drop < moveInfo.dropCursor; drop++ )
		UndoDrop( drop, moveInfo );

	//	undo all pickups
	int firstPickup = indexOfMoveMade == 0 ? 0 : moves[indexOfMoveMade-1].pickupCursor;
	for( int pickup = firstPickup; pickup < moveInfo.pickupCursor; pickup++ )
		UndoPickUp( pickup, moveInfo );

	//	flip the current player
	board->currentPlayer = FLIP(board->currentPlayer);

	//	increment currentMove; so that the next call to 
	//	MakeNextMove will get the move after this one
	currentMove++;
	indexOfMoveMade = -1;

	#ifdef _DEBUG
	AssertValid();
	board->AssertValid();
	#endif
}

/************************************************************************\ 
**************************************************************************
**                                                                      **
**                        GENERATING MOVES                              **
**                                                                      **
**  GenerateMoves and GenerateCaptures are the two functions which      **
**  perform all move generation.  These functions also call the Game    **
**  class's AddSpecialMoves function, for implementation of game-       **
**  specific moves.  GenerateCaptures is only called during the         **
**  quiescient search.                                                  **
**                                                                      **
**************************************************************************
\************************************************************************/

// ***********************************************************************
// *
// *	GenerateMoves
// *	
// *	clears the contents of the stack, and then generates all
// *	pseudo-legal moves, which are pushed onto the stack

void MovementList::GenerateMoves
	( NodeType nodeType )
{
	GenerateMoves( Movement(), Movement(), nodeType );
}

void MovementList::GenerateMoves
	( Movement lookupMove, 
	  Movement secondaryMove, 
	  NodeType nodeType )
{
	Clear();
	quiescentSearch = false;
	hashtableMove = lookupMove;
	secondMove = secondaryMove;
	hashtableMoveFound = false;

	#ifdef _DEBUG
	board->AssertValid();
	#endif

	//	notify the game class prior to move generation.  this is used by 
	//	Ultima (for one) to fill out the immobilized matrix to freeze pieces
	board->GetGame().AboutToGenerateMoves( board->currentPlayer, board->currentDepth );

	if( board->GetGame().HasCustomMoveGeneration() )
	{
		board->GetGame().GenerateMoves( board->currentPlayer, *this );
	}
	else
	{
		for( int currentPiece = 0; 
			currentPiece < board->nPieces[board->currentPlayer]; 
			currentPiece++ )
		{
			//	loop through all pieces owned by this player
			if( !(board->pieces[board->currentPlayer][currentPiece]->IsCaptured()) ) 
			{
				if( !(board->IsImmobilized( board->pieces[board->currentPlayer][currentPiece]->GetSquareNumber() )) )
				{
					//	if the piece hasn't been captured, and it is not immobilized, then generate moves for it
					board->pieces[board->currentPlayer][currentPiece]->GenerateMoves( *this, *board );
				}
				else
					if( board->GetGame().ImmobilizedPiecesCanCommitSuicide() && 
						!board->pieces[board->currentPlayer][currentPiece]->GetType().IsRoyal() )
					{
						BeginMoveAdd( SuicideMove, board->pieces[board->currentPlayer][currentPiece]->GetSquareNumber(), -1 );
						AddPickUp( board->pieces[board->currentPlayer][currentPiece]->GetSquareNumber() );
						EndMoveAdd( -(board->pieces[board->currentPlayer][currentPiece]->GetBaseValue()) );
					}
			}
		}
		board->pGame->AddSpecialMoves( board->currentPlayer, *this, board->gameRecords[board->gamePly-1], false );
	}

	#ifdef _DEBUG
//	if( hashtableMove != Movement() && !hashtableMoveFound )
//		ASSERT(FALSE);
	#endif

	//	*** MOVE ORDERING ***  // 
	OrderMoves( lookupMove, nodeType );
}

void MovementList::AddBitBoard64Moves
	( int fromSquare, 
	  BitBoard64 toSquares )
{
	int square;
	BitBoard64 captures = toSquares & board->BB64_GetBlockers();
	BitBoard64 moves = toSquares & ~captures;

	while( captures )
	{
		square = captures.ExtractLSB();
		AddCapture( fromSquare, square );
	}

	while( moves )
	{
		square = moves.ExtractLSB();
		AddMove( fromSquare, square );
	}

/*	while( toSquares )
	{
		square = toSquares.GetFirstBit();
		toSquares.ToggleBit( square );
		if( board->GetSquareContents( square ) == NULL )
			AddMove( fromSquare, square );
		else
			AddCapture( fromSquare, square );
	}*/
}

void MovementList::AddBitBoard96Moves
	( int fromSquare, 
	  BitBoard96 toSquares )
{
	int square;

	BitBoard96 captures = toSquares & board->BB96_GetBlockers();
	BitBoard96 moves = toSquares & ~captures;

	while( captures )
	{
		square = captures.GetFirstBit();
		captures.ToggleBit( square );
		AddCapture( fromSquare, square );
	}

	while( moves )
	{
		square = moves.GetFirstBit();
		moves.ToggleBit( square );
		AddMove( fromSquare, square );
	}

/*	while( toSquares )
	{
		square = toSquares.GetFirstBit();
		toSquares.ToggleBit( square );
		if( board->GetSquareContents( square ) == NULL )
			AddMove( fromSquare, square );
		else
			AddCapture( fromSquare, square );
	}*/
}

// ***********************************************************************
// *
// *	GenerateCaptures
// *	
// *	clears the contents of the stack, and then generates all
// *	pseudo-legal captures, which are pushed onto the stack

void MovementList::GenerateCaptures
	( Movement lookupMove, 
	  NodeType nodeType )
{
	Clear();
	quiescentSearch = true;
	hashtableMove = lookupMove;
	secondMove = Movement();
	hashtableMoveFound = false;

	board->GetGame().AboutToGenerateMoves( board->currentPlayer, board->currentDepth );

	if( board->GetGame().HasCustomCaptureGeneration() )
	{
		board->GetGame().GenerateCaptures( board->currentPlayer, *this );
	}
	else
	{
		for( int currentPiece = 0; 
			currentPiece < board->nPieces[board->currentPlayer]; 
			currentPiece++ )
		{
			//	loop through all pieces owned by this player
			if( !(board->pieces[board->currentPlayer][currentPiece]->IsCaptured()) )
			{
				//	if the piece hasn't been captured, and it is not immobilized, then generate captures for it
				board->pieces[board->currentPlayer][currentPiece]->GenerateCaptures( *this, *board );
			}
		}
		board->pGame->AddSpecialMoves( board->currentPlayer, *this, board->gameRecords[board->gamePly-1], true );
	}

	//	*** MOVE ORDERING ***  // 
	//	no move ordering is performed in quiescent search; it's faster
	//	to pick the best moves one at a time as we need them.
}

void MovementList::AddBitBoard64Captures
	( int fromSquare, 
	  BitBoard64 toSquares )
{
	int square;
	while( toSquares )
	{
		square = toSquares.ExtractLSB();
		AddCapture( fromSquare, square );
	}
}

void MovementList::AddBitBoard96Captures
	( int fromSquare, 
	  BitBoard96 toSquares )
{
	int square;
	while( toSquares )
	{
		square = toSquares.GetFirstBit();
		toSquares.ToggleBit( square );
			AddCapture( fromSquare, square );
	}
}

// ***********************************************************************
// *
// *	ReorderRoot
// *
// *	this function is called before re-calling SearchRoot after each
// *	iterative deepening; at the root level move ordering is done
// *	differently.  each time we finish searching a root node, we store
// *	its evaluation back into the MoveInfo structure.  so, to reorder
// *	the root nodes for the next iteration, we just need to do an
// *	insertion sort, initializing the moveOrder array in the order
// *	of the evaluations, from best to worst.

void MovementList::ReorderRoot( int iDepth )
{
	int hashScore;
	HashType hashType = board->hashTable.Lookup( iDepth, 1, hashScore, hashtableMove );
	int i;
	
	//	initialize moveOrder array
	for( i = 0; i < moveCursor; i++ )
	{
		MoveInfo &move = GetMove( i );
		if( move == hashtableMove )
			move.evaluation = INFINITY;
		else if( move.evaluation == INFINITY )
			move.evaluation = move.evaluation - 1000 + iDepth;
		moveOrder[i] = i;
	}

	//	perform insertion sort
	int index = 0;
	int indexValue;
	for( i = 1; i < moveCursor; i++ )
	{
		index = i;
		indexValue = GetMove( moveOrder[i] ).evaluation;
		int j = i;
		while( j > 0 && GetMove( moveOrder[j-1] ).evaluation < indexValue )
		{
			moveOrder[j] = moveOrder[j-1];
			j--;
		}
		moveOrder[j] = index;
	}
}

// ***********************************************************************
// *
// *	AdjustUIElements
// *

void MovementList::AdjustUIElements
	( int moveNumber )
{
	int move = moveNumber;
	int firstPickup = move == 0 ? 0 : moves[move-1].pickupCursor;
	int firstDrop = move == 0 ? 0 : moves[move-1].dropCursor;
	int nPickups = moves[move].pickupCursor - firstPickup;
	int nDrops = moves[move].dropCursor - firstDrop;
	if( nPickups > 1 && nDrops == 1 && moves[move].type != StandardCapture )
	{
		for( int pickupNumber = firstPickup + 1; 
			 pickupNumber < moves[move].pickupCursor; pickupNumber++ )
		{
			PickUp &pickup = pickups[pickupNumber];
			if( pickup.GetSquareNumber() != moves[move].toSquare )
			{
				extraCaptureSquares[extraCaptures++] = pickup.GetSquareNumber();
				board->InvalidateSquare( pickup.GetSquareNumber() );
			}
		}
	}
}

/************************************************************************\ 
**************************************************************************
**                                                                      **
**                         helper functions                             **
**                                                                      **
**************************************************************************
\************************************************************************/

// ***********************************************************************
// *
// *	OrderMoves
// *
// *	this function just performs an insertion sort to fill in
// *	the moveOrder array.  they are ordered according to the 
// *	evaluations assigned in the AddMove, AddCapture, etc.
// *	functions.
// *	
// *	after sorted, they should be ordered as follows:
// *	
// *		1. PV move
// *		2. hash move
// *		3. captures
// *		4. killer moves
// *		5. moves that boost piece-square-table values the most
// 
void MovementList::OrderMoves
	( Movement hashMove,
	  NodeType nodeType )
{
	//	perform insertion sort
	int index;
	int indexValue;
	for( int i = 1; i < moveCursor; i++ )
	{
		index = i;
		indexValue = moves[moveOrder[i]].evaluation;
		int j = i;
		while( j > 0 && moves[moveOrder[j-1]].evaluation < indexValue )
		{
			moveOrder[j] = moveOrder[j-1];
			j--;
		}
		moveOrder[j] = index;
	}
}

// ***********************************************************************
// *
// *	OrderCaptures
// *
// *	in QuiescentSearch, this function is called instead of OrderMoves.
// *	we will handle this very differently; in fact, we are not going to
// *	perform any ordering at all at this time; we will just set the flag
// *	quiescentSearch to true, and then the MakeNextMove function will
// *	know we are in the QuiescentSearch, and rather than consulting the
// *	moveOrder array to determine which move is next, it will look
// *	through ALL moves in the buffer each time, picking the best one.
// *	this is good because we often get cut-offs here, so an early 
// *	cut-off saves us a lot of time that would have been spent sorting.

void MovementList::OrderCaptures
	( Movement hashMove,
	  NodeType nodeType )
{
	quiescentSearch = true;
}


// ***********************************************************************
// *
// *	PerformPickUp
// *

void MovementList::PerformPickUp
	( int index, MoveInfo &info )
{
	Piece *piece = pickups[index].GetPiece();
	int squareNumber = pickups[index].GetSquareNumber();
	Piece **square = board->GetSquareReference( squareNumber );

	#ifdef _DEBUG
	ASSERT(piece->GetSquareNumber() == squareNumber);
	ASSERT(*square == piece);
	#endif

	//	store the flags of this piece, so we can restore them
	pickups[index].flags = piece->flags;

	//	remove the piece's positional hashes and material value
	board->primaryHash   ^= piece->GetPrimaryHash( squareNumber );
	board->secondaryHash ^= piece->GetSecondaryHash( squareNumber );
	board->material[piece->GetPlayerNumber()] -= piece->GetBaseValue();
	if( piece->IsPawn() )
	{
		board->primaryPawnHash   ^= piece->GetPrimaryHash( squareNumber );
		board->secondaryPawnHash ^= piece->GetSecondaryHash( squareNumber );
		board->pawnMaterial[piece->GetPlayerNumber()] -= piece->GetBaseValue();
	}

	//	empty the vacated square
	*square = NULL;

	//	update bitboards
	switch( board->GetBitBoardType() )
	{
	  case BITBOARD_64:
		static_cast<PieceType64 &>(piece->GetType()).ClearPiece( piece->GetPlayerNumber(), squareNumber );
		board->bb64_blocker.ToggleBit( squareNumber );
		board->bb64_blocker90.ToggleBit( board->rotate90[squareNumber] );
		board->bb64_blocker45.ToggleBit( board->rotate45[squareNumber] );
		board->bb64_blocker135.ToggleBit( board->rotate135[squareNumber] );
		board->bb64_friends[piece->GetPlayerNumber()].ToggleBit( squareNumber );
		break;

	  case BITBOARD_96:
		static_cast<PieceType96 &>(piece->GetType()).ClearPiece( piece->GetPlayerNumber(), squareNumber );
		board->bb96_blocker.ToggleBit( squareNumber );
		board->bb96_blocker90.ToggleBit( board->rotate90[squareNumber] );
		board->bb96_blocker45.ToggleBit( board->rotate45[squareNumber] );
		board->bb96_blocker135.ToggleBit( board->rotate135[squareNumber] );
		board->bb96_friends[piece->GetPlayerNumber()].ToggleBit( squareNumber );
		break;

	  case BITBOARD_128:
		static_cast<PieceType128 &>(piece->GetType()).ClearPiece( piece->GetPlayerNumber(), squareNumber );
		board->bb128_blocker.ToggleBit( squareNumber );
		board->bb128_blocker90.ToggleBit( board->rotate90[squareNumber] );
		board->bb128_blocker45.ToggleBit( board->rotate45[squareNumber] );
		board->bb128_blocker135.ToggleBit( board->rotate135[squareNumber] );
		board->bb128_friends[piece->GetPlayerNumber()].ToggleBit( squareNumber );
		break;

	  case BITBOARD_NONE:
		break;
	}

	piece->SetCapturedStatus( true );
	board->nCapturedPieces++;
}

// ***********************************************************************
// *
// *	PerformDrop
// *

void MovementList::PerformDrop
	( int index, MoveInfo &info )
{
	Piece *piece = drops[index].GetPiece();
	int squareNumber = drops[index].GetSquareNumber();
	Piece **square = board->GetSquareReference( squareNumber );

	//	check for promotion
	if( drops[index].GetSwapType() != NULL )
	{
		PieceType *oldType = &(piece->GetType());
		board->gameRecords[board->gamePly].promotionValue -= piece->GetBaseValue();
		piece->SwitchType( drops[index].GetSwapType() );
		board->gameRecords[board->gamePly].promotionValue += piece->GetBaseValue();
		//	set the is-promoted flag
		piece->flags |= FLAGS_IS_PROMOTED;
		//	save the old type, so we can swap back when undoing the move
		drops[index].SetSwapType( oldType );
	}

	//	add the piece's positional hashes and material value
	board->primaryHash   ^= piece->GetPrimaryHash( squareNumber );
	board->secondaryHash ^= piece->GetSecondaryHash( squareNumber );
	board->material[piece->GetPlayerNumber()] += piece->GetBaseValue();
	if( piece->IsPawn() )
	{
		board->primaryPawnHash   ^= piece->GetPrimaryHash( squareNumber );
		board->secondaryPawnHash ^= piece->GetSecondaryHash( squareNumber );
		board->pawnMaterial[piece->GetPlayerNumber()] += piece->GetBaseValue();
	}

	//	drop piece on square
	*square = piece;
	//	update the moving piece's location
	piece->SetSquare( squareNumber );
	//	set the piece's the has-moved-twice and has-moved-three-times flags
	piece->flags |= (piece->flags & (FLAGS_HAS_MOVED | FLAGS_HAS_MOVED_TWICE)) << 1;
	//	set the moving piece's has-moved flag
	piece->flags |= FLAGS_HAS_MOVED;
	//	set the has-castled flag (if necessary)
	if( info.type == Castling || 
		info.type == FlexibleCastling || 
		info.type == FreeCastling || 
		info.type == UserCastling )
		//	set the has-castled flag
		piece->flags |= FLAGS_HAS_CASTLED;

	//	update bitboards
	switch( board->GetBitBoardType() )
	{
	  case BITBOARD_64:
		dynamic_cast<PieceType64 &>(piece->GetType()).SetPiece( piece->GetPlayerNumber(), squareNumber );
		board->bb64_blocker.ToggleBit( squareNumber );
		board->bb64_blocker90.ToggleBit( board->rotate90[squareNumber] );
		board->bb64_blocker45.ToggleBit( board->rotate45[squareNumber] );
		board->bb64_blocker135.ToggleBit( board->rotate135[squareNumber] );
		board->bb64_friends[piece->GetPlayerNumber()].ToggleBit( squareNumber );
		break;

	  case BITBOARD_96:
		dynamic_cast<PieceType96 &>(piece->GetType()).SetPiece( piece->GetPlayerNumber(), squareNumber );
		board->bb96_blocker.ToggleBit( squareNumber );
		board->bb96_blocker90.ToggleBit( board->rotate90[squareNumber] );
		board->bb96_blocker45.ToggleBit( board->rotate45[squareNumber] );
		board->bb96_blocker135.ToggleBit( board->rotate135[squareNumber] );
		board->bb96_friends[piece->GetPlayerNumber()].ToggleBit( squareNumber );
		break;

	  case BITBOARD_128:
		dynamic_cast<PieceType128 &>(piece->GetType()).SetPiece( piece->GetPlayerNumber(), squareNumber );
		board->bb128_blocker.ToggleBit( squareNumber );
		board->bb128_blocker90.ToggleBit( board->rotate90[squareNumber] );
		board->bb128_blocker45.ToggleBit( board->rotate45[squareNumber] );
		board->bb128_blocker135.ToggleBit( board->rotate135[squareNumber] );
		board->bb128_friends[piece->GetPlayerNumber()].ToggleBit( squareNumber );
		break;

	  case BITBOARD_NONE:
		break;
	}

	piece->SetCapturedStatus( false );
	board->nCapturedPieces--;
}

// ***********************************************************************
// *
// *	UndoPickUp
// *

void MovementList::UndoPickUp
	( int index, MoveInfo &info )
{
	Piece *piece = pickups[index].GetPiece();
	int squareNumber = pickups[index].GetSquareNumber();
	Piece **square = board->GetSquareReference( squareNumber );

	//	restore the piece's flags
	piece->flags = pickups[index].flags;

	//	restore the piece's positional hashes and material value
	board->primaryHash   ^= piece->GetPrimaryHash( squareNumber );
	board->secondaryHash ^= piece->GetSecondaryHash( squareNumber );
	board->material[piece->GetPlayerNumber()] += piece->GetBaseValue();
	if( piece->IsPawn() )
	{
		board->primaryPawnHash   ^= piece->GetPrimaryHash( squareNumber );
		board->secondaryPawnHash ^= piece->GetSecondaryHash( squareNumber );
		board->pawnMaterial[piece->GetPlayerNumber()] += piece->GetBaseValue();
	}

	//	place piece back on square
	*square = piece;

	//	update bitboards
	switch( board->GetBitBoardType() )
	{
	  case BITBOARD_64:
		dynamic_cast<PieceType64 &>(piece->GetType()).SetPiece( piece->GetPlayerNumber(), squareNumber );
		board->bb64_blocker.ToggleBit( squareNumber );
		board->bb64_blocker90.ToggleBit( board->rotate90[squareNumber] );
		board->bb64_blocker45.ToggleBit( board->rotate45[squareNumber] );
		board->bb64_blocker135.ToggleBit( board->rotate135[squareNumber] );
		board->bb64_friends[piece->GetPlayerNumber()].ToggleBit( squareNumber );
		break;

	  case BITBOARD_96:
		dynamic_cast<PieceType96 &>(piece->GetType()).SetPiece( piece->GetPlayerNumber(), squareNumber );
		board->bb96_blocker.ToggleBit( squareNumber );
		board->bb96_blocker90.ToggleBit( board->rotate90[squareNumber] );
		board->bb96_blocker45.ToggleBit( board->rotate45[squareNumber] );
		board->bb96_blocker135.ToggleBit( board->rotate135[squareNumber] );
		board->bb96_friends[piece->GetPlayerNumber()].ToggleBit( squareNumber );
		break;

	  case BITBOARD_128:
		dynamic_cast<PieceType128 &>(piece->GetType()).SetPiece( piece->GetPlayerNumber(), squareNumber );
		board->bb128_blocker.ToggleBit( squareNumber );
		board->bb128_blocker90.ToggleBit( board->rotate90[squareNumber] );
		board->bb128_blocker45.ToggleBit( board->rotate45[squareNumber] );
		board->bb128_blocker135.ToggleBit( board->rotate135[squareNumber] );
		board->bb128_friends[piece->GetPlayerNumber()].ToggleBit( squareNumber );
		break;

	  case BITBOARD_NONE:
		break;
	}

	//	reset the piece's copy of the square information
	piece->SetSquare( squareNumber );

	piece->SetCapturedStatus( false );
	board->nCapturedPieces--;
}

// ***********************************************************************
// *
// *	UndoDrop
// *

void MovementList::UndoDrop
	( int index, MoveInfo &info )
{
	Piece *piece = drops[index].GetPiece();
	int squareNumber = drops[index].GetSquareNumber();
	ASSERT(squareNumber == piece->GetSquareNumber());
	Piece **square = board->GetSquareReference( squareNumber );

	//	clear the piece's positional hashes and material value
	board->primaryHash   ^= piece->GetPrimaryHash( squareNumber );
	board->secondaryHash ^= piece->GetSecondaryHash( squareNumber );
	board->material[piece->GetPlayerNumber()] -= piece->GetBaseValue();
	if( piece->IsPawn() )
	{
		board->primaryPawnHash   ^= piece->GetPrimaryHash( squareNumber );
		board->secondaryPawnHash ^= piece->GetSecondaryHash( squareNumber );
		board->pawnMaterial[piece->GetPlayerNumber()] -= piece->GetBaseValue();
	}

	//	clear the square
	*square = NULL;

	//	update bitboards
	switch( board->GetBitBoardType() )
	{
	  case BITBOARD_64:
		dynamic_cast<PieceType64 &>(piece->GetType()).ClearPiece( piece->GetPlayerNumber(), squareNumber );
		board->bb64_blocker.ToggleBit( squareNumber );
		board->bb64_blocker90.ToggleBit( board->rotate90[squareNumber] );
		board->bb64_blocker45.ToggleBit( board->rotate45[squareNumber] );
		board->bb64_blocker135.ToggleBit( board->rotate135[squareNumber] );
		board->bb64_friends[piece->GetPlayerNumber()].ToggleBit( squareNumber );
		break;

	  case BITBOARD_96:
		dynamic_cast<PieceType96 &>(piece->GetType()).ClearPiece( piece->GetPlayerNumber(), squareNumber );
		board->bb96_blocker.ToggleBit( squareNumber );
		board->bb96_blocker90.ToggleBit( board->rotate90[squareNumber] );
		board->bb96_blocker45.ToggleBit( board->rotate45[squareNumber] );
		board->bb96_blocker135.ToggleBit( board->rotate135[squareNumber] );
		board->bb96_friends[piece->GetPlayerNumber()].ToggleBit( squareNumber );
		break;

	  case BITBOARD_128:
		dynamic_cast<PieceType128 &>(piece->GetType()).ClearPiece( piece->GetPlayerNumber(), squareNumber );
		board->bb128_blocker.ToggleBit( squareNumber );
		board->bb128_blocker90.ToggleBit( board->rotate90[squareNumber] );
		board->bb128_blocker45.ToggleBit( board->rotate45[squareNumber] );
		board->bb128_blocker135.ToggleBit( board->rotate135[squareNumber] );
		board->bb128_friends[piece->GetPlayerNumber()].ToggleBit( squareNumber );
		break;

	  case BITBOARD_NONE:
		break;
	}

	piece->SetCapturedStatus( true );
	board->nCapturedPieces++;

	//	was this drop a promotion?  if so, change the type back
	if( drops[index].GetSwapType() != NULL )
	{
		PieceType *oldType = &(piece->GetType());
		piece->SwitchType( drops[index].GetSwapType() );
		drops[index].SetSwapType( oldType );
	}
}

// ***********************************************************************
// *
// *	MakeMove
// *
// *	this helper funciton makes the move with the specified index

bool MovementList::MakeMove( int moveNumber )
{
	//	initialize reference to the requested move
	MoveInfo &moveInfo = moves[moveNumber];
	indexOfMoveMade = moveNumber;

	int firstPickup = 0;
	int firstDrop = 0; 
	if( moveNumber > 0 )
	{
		firstPickup = moves[moveNumber - 1].pickupCursor;
		firstDrop = moves[moveNumber - 1].dropCursor;
	}
	int nCaptures = (moveInfo.pickupCursor - firstPickup) - (moveInfo.dropCursor - firstDrop);

	//	store information into the board's gameRecords array
	board->gameRecords[board->gamePly].primaryHash = board->GetPrimaryHash();
	board->gameRecords[board->gamePly].moveType = moveInfo.type;
	board->gameRecords[board->gamePly].pieceMoved = moveInfo.pPieceMoved;
	board->gameRecords[board->gamePly].oldSquareNumber = moveInfo.fromSquare;
	board->gameRecords[board->gamePly].materialCaptured = 0;
	board->gameRecords[board->gamePly].promotionValue = 0;
	board->gameRecords[board->gamePly].lastCaptureOrPawn = 
		board->gameRecords[board->gamePly-1].lastCaptureOrPawn;
	if( pickups[firstPickup].GetPiece()->IsPawn() || nCaptures > 0 )
		board->gameRecords[board->gamePly].lastCaptureOrPawn = board->gamePly;
	board->gameRecords[board->gamePly].gameFlags = board->gameRecords[board->gamePly-1].gameFlags;
	board->gameRecords[board->gamePly].gameInt1 = board->gameRecords[board->gamePly-1].gameInt1;
	board->gameRecords[board->gamePly].gameInt2 = board->gameRecords[board->gamePly-1].gameInt2;

	//	perform all pickups
	for( int pickup = firstPickup; pickup < moveInfo.pickupCursor; pickup++ )
	{
		PerformPickUp( pickup, moveInfo );
		if( moveInfo.pickupCursor - pickup <= nCaptures )
		{
			Piece *piece = pickups[pickup].GetPiece();
			board->gameRecords[board->gamePly].materialCaptured += piece->GetBaseValue();
		}
	}

	//	perform all drops (normally only one, but Castling is one exception)
	for( int drop = firstDrop; drop < moveInfo.dropCursor; drop++ )
	{
		PerformDrop( drop, moveInfo );
	}

	//	ok, now pass message to the Game class, so it can update any info
	//	it may need to as a result of this move.  this also gives the Game
	//	class the chance to return false, indicating that the move is illegal
	bool isLegal = theGame->MoveBeingMade( moveInfo, board->gameRecords[board->gamePly] );

	//	if this is a game where the goal is Checkmate, we need to make sure that
	//	the move isn't illegal because the side which just moved is in Check
	if( isLegal && theGame->IsGoalToCheckmate() )
	{
		if( theGame->HasSpecialCheckTesting() )
			isLegal = !theGame->IsInCheck( board->GetKing( board->currentPlayer ) );
		else
//			if( moveInfo.pPieceMoved == board->GetKing( moveInfo.pPieceMoved->GetPlayerNumber() ) || 
//				board->FastCheckTest() )
				isLegal = !board->IsInCheck();
//			else
//				isLegal = !board->IsInCheck( moveInfo.fromSquare );
	}

	//	flip the current player
	board->currentPlayer = FLIP(board->currentPlayer);

	//	increment the game ply
	board->gamePly++;

	#ifdef _DEBUG
	AssertValid();
	board->AssertValid();
	#endif

	return isLegal;
}

bool MovementList::MakeMove( Movement movement )
{
	for( int x = 0; x < moveCursor; x++ )
	{
		if( moves[x] == movement )
		{
			return MakeMove( x );
		}
	}
	return false;
}

// ***********************************************************************
// *
// *	UnmakeMove
// *
// *	unmakes the move with the specified index

void MovementList::UnmakeMove( int moveNumber )
{
	//	going back up
	board->gamePly--;

	//	initialize reference to the requested move
	MoveInfo &moveInfo = moves[moveNumber];

	//	undo all drops (normally only one)
	int firstDrop = moveNumber == 0 ? 0 : moves[moveNumber - 1].dropCursor;
	for( int drop = firstDrop; drop < moveInfo.dropCursor; drop++ )
		UndoDrop( drop, moveInfo );

	//	undo all pickups
	int firstPickup = moveNumber == 0 ? 0 : moves[moveNumber - 1].pickupCursor;
	for( int pickup = firstPickup; pickup < moveInfo.pickupCursor; pickup++ )
		UndoPickUp( pickup, moveInfo );

	//	flip the current player
	board->currentPlayer = FLIP(board->currentPlayer);

	#ifdef _DEBUG
	AssertValid();
	board->AssertValid();
	#endif
}

// ***********************************************************************
// *
// *	EvaluateExchange
// *
// *	performs Static Exchange Evaluation (SEE) and returns the likely
// *	value of this exchange.  this function does have the known bug
// *	that pinned pieces are not detected as such, and are factored
// *	into the exchange calcuation when they shouldn't be.

int MovementList::EvaluateExchange( int moveNumber )
{
	//	initialize reference to the requested move
	MoveInfo &moveInfo = moves[moveNumber];
	Piece *pieceBeingMoved = board->GetSquareContents( moveInfo.fromSquare );
	Piece *pieceBeingCaptured = board->GetSquareContents( moveInfo.toSquare );

	//	perform static exchange evaluation
	int nPlayerAttackers[2];
	int side = pieceBeingMoved->GetPlayerNumber();
	int xside = FLIP(side);

	board->BuildAttackerList( moveInfo.toSquare, playerAttackers, nPlayerAttackers, pieceBeingMoved );

	int lastval;
	if( moveInfo.promotion != NULL )
	{
		swapList[0] = moveInfo.promotion->GetBaseValue() - 
				        pieceBeingMoved->GetBaseValue();
		lastval = -moveInfo.promotion->GetBaseValue();
	}
	else
	{
		swapList[0] = pieceBeingCaptured->GetBaseValue();
		lastval = -pieceBeingMoved->GetBaseValue();
	}
	int n = 1;
	int cursor[2];
	cursor[0] = 0;
	cursor[1] = 0;
	while( true )
	{
		if( nPlayerAttackers[xside] == 0 )
			break;
		swapList[n] = swapList[n-1] + lastval;
		n++;

		//	find next attacker
		int index = 0;
		int indexValue = playerAttackers[xside][0].baseValue;
		for( int  x = 1; x < nPlayerAttackers[xside]; x++ )
			if( playerAttackers[xside][x].baseValue < indexValue )
			{
				index = x;
				indexValue = playerAttackers[xside][x].baseValue;
			}
		AttackVector vector = playerAttackers[xside][index];
		lastval = vector.baseValue;
		if( nPlayerAttackers[xside] > 1 && index != nPlayerAttackers[xside] - 1 )
			playerAttackers[xside][index] = playerAttackers[xside][nPlayerAttackers[xside] - 1];
		nPlayerAttackers[xside]--;

		//	look behind this piece for another piece
		int *matrix = board->movementMatrix[vector.directionNumber];
		int square = matrix[vector.piece->GetSquareNumber()];
		int oppositeDirection = board->GetDirection( vector.directionNumber ).GetOppositeDirectionNumber();
		int steps = vector.distanceToTarget + 1;
		while( square != -1 && 
			(steps <= board->GetAttackRange( 0, vector.directionNumber ) || 
			 steps <= board->GetAttackRange( 1, vector.directionNumber )) )
		{
			Piece *piece = board->GetSquareContents( square );
			if( piece != NULL )
			{
				square = -1;
				if( piece->GetType().GetAttackRange( piece->GetPlayerNumber(), oppositeDirection ) >= steps )
				{
					//	before adding this attacker, we might need to ensure that 
					//	we haven't already seen this piece when looking in another direction
					bool addThisPiece = true;
					int nPlayer = piece->GetPlayerNumber();
					if( board->DoesBoardWrapAround() || 
						board->GetDirection( vector.directionNumber ).IsAuxilaryDirection() )
					{
						for( int y = 0; y < nPlayerAttackers[nPlayer] && addThisPiece; y++ )
							if( playerAttackers[nPlayer][y].piece == piece )
								//	we already have this piece, so don't add it
								addThisPiece = false;
					}
					if( addThisPiece )
					{
						//	insert new attacker
						index = nPlayerAttackers[nPlayer];
						playerAttackers[nPlayer][index].piece = piece;
						playerAttackers[nPlayer][index].directionNumber = vector.directionNumber;
						playerAttackers[nPlayer][index].baseValue = piece->GetBaseValue();
						playerAttackers[nPlayer][index].distanceToTarget = steps;
						nPlayerAttackers[nPlayer]++;
					}
				}
			}
			else
			{
				square = matrix[square];
				steps++;
			}
		}

		if( nPlayerAttackers[side] == 0 )
			break;
		swapList[n] = swapList[n-1] + lastval;
		n++;

		//	find next attacker
		index = 0;
		indexValue = playerAttackers[side][0].baseValue;
		for( int  x = 1; x < nPlayerAttackers[side]; x++ )
			if( playerAttackers[side][x].baseValue < indexValue )
			{
				index = x;
				indexValue = playerAttackers[side][x].baseValue;
			}
		vector = playerAttackers[side][index];
		lastval = -vector.baseValue;

		if( nPlayerAttackers[side] > 1 && index != nPlayerAttackers[side] - 1 )
			playerAttackers[side][index] = playerAttackers[side][nPlayerAttackers[side] - 1];
		nPlayerAttackers[side]--;

		//	look behind this piece for another piece
		matrix = board->movementMatrix[vector.directionNumber];
		square = matrix[vector.piece->GetSquareNumber()];
		oppositeDirection = board->GetDirection( vector.directionNumber ).GetOppositeDirectionNumber();
		while( square != -1 && 
			(steps <= board->GetAttackRange( 0, vector.directionNumber ) || 
			 steps <= board->GetAttackRange( 1, vector.directionNumber )) )
		{
			Piece *piece = board->GetSquareContents( square );
			if( piece != NULL )
			{
				square = -1;
				if( piece->GetType().GetAttackRange( piece->GetPlayerNumber(), oppositeDirection ) >= steps )
				{
					//	before adding this attacker, we might need to ensure that 
					//	we haven't already seen this piece when looking in another direction
					bool addThisPiece = true;
					int nPlayer = piece->GetPlayerNumber();
					if( board->DoesBoardWrapAround() || 
						board->GetDirection( vector.directionNumber ).IsAuxilaryDirection() )
					{
						for( int y = 0; y < nPlayerAttackers[nPlayer] && addThisPiece; y++ )
							if( playerAttackers[nPlayer][y].piece == piece )
								//	we already have this piece, so don't add it
								addThisPiece = false;
					}
					if( addThisPiece )
					{
						//	insert new attacker
						index = nPlayerAttackers[nPlayer];
						playerAttackers[nPlayer][index].piece = piece;
						playerAttackers[nPlayer][index].directionNumber = vector.directionNumber;
						playerAttackers[nPlayer][index].baseValue = piece->GetBaseValue();
						playerAttackers[nPlayer][index].distanceToTarget = steps;
						nPlayerAttackers[nPlayer]++;
					}
				}
			}
			else
			{
				square = matrix[square];
				steps++;
			}
		}
	}

	//	at this stage, we have the swap scores in a list.  we just need to 
	//	mini-max the scores from the bottom up to the top of the list.
	--n;
	while( n )
	{
		if( n & 1 )
		{
			if( swapList[n] <= swapList[n-1] )
				swapList[n-1] = swapList[n]; 
		}
		else
		{
			if( swapList[n] >= swapList[n-1] )
				swapList[n-1] = swapList[n]; 
		}
		--n;
	}
	return swapList[0];
}

// ***********************************************************************
// *
// *	PretendMoveWasBeingMade
// *
// *	this function updates the provided primary hash and secondary 
// *	hash as they would be updated if the given move was actually 
// *	being performed.  no pieces are actually moved, however.  this 
// *	function is used when the PV information is being displayed to 
// *	the user.  the PV is reconstructed from the root by looking up 
// *	all moves from the hash table.

void MovementList::PretendMoveWasBeingMade
	( Movement move, 
	  word32 &priHash, 
	  word32 &secHash )
{
	//	find the requested move
	int moveNumber;
	MoveInfo *pMoveInfo = NULL;
	for( moveNumber = 0; moveNumber < moveCursor; moveNumber++ )
		if( moves[moveNumber] == move )
		{
			pMoveInfo = &(moves[moveNumber]);
			break;
		}

	ASSERT(pMoveInfo != NULL);

	int firstPickup = 0;
	int firstDrop = 0; 
	if( moveNumber > 0 )
	{
		firstPickup = moves[moveNumber - 1].pickupCursor;
		firstDrop = moves[moveNumber - 1].dropCursor;
	}

	//	perform all pickups
	for( int index = firstPickup; index < pMoveInfo->pickupCursor; index++ )
	{
		Piece *piece = pickups[index].GetPiece();
		int squareNumber = pickups[index].GetSquareNumber();
		priHash ^= piece->GetPrimaryHash( squareNumber );
		secHash ^= piece->GetSecondaryHash( squareNumber );
	}

	//	perform all drops (normally only one, but Castling is one exception)
	for( int index2 = firstDrop; index2 < pMoveInfo->dropCursor; index2++ )
	{
		static Drop *drop = drops + index2;
		Piece *piece = drops[index2].GetPiece();
		int squareNumber = drops[index2].GetSquareNumber();
		priHash ^= piece->GetPrimaryHash( squareNumber );
		secHash ^= piece->GetSecondaryHash( squareNumber );
	}
}

void MovementList::AssertValid()
{
	ASSERT(board != NULL);

	ASSERT_NO_MANS_LAND(1)
	ASSERT_NO_MANS_LAND(2)
	ASSERT_NO_MANS_LAND(3)

	int pickup = 0;
	int drop = 0;
	for( int x = 0; x < moveCursor; x++ )
	{
		pickup = moves[x].pickupCursor;
		drop = moves[x].dropCursor;
	}
}

void MovementList::Output
	( FILE *fi )
{
	for( int x = 0; x < moveCursor; x++ )
	{
		MoveInfo &move = moves[moveOrder[x]];
		fprintf( fi, "  move %d: from %d to %d, eval %d \n", 
			x, move.fromSquare, move.toSquare, move.evaluation );
	}
	fprintf( fi, "\n" );
}

void MovementList::ResetMoveOrdering()
{
	for( int x = 0; x < moveCursor; x++ )
		moveOrder[x] = x;
}
