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

                                 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"


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

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

// ***********************************************************************
// *
// *	CopyMoveToStack
// *
// *	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::CopyMoveToStack
	( 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.BeginMoveAdd( moveInfo.type, moveInfo.fromSquare, moveInfo.toSquare, moveInfo.tag );

	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.EndMoveAdd( moveInfo.evaluation );
}


/************************************************************************\ 
**************************************************************************
**                                                                      **
**                 PUSHING MOVES ONTO THE STACK                         **
**                                                                      **
**  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
// *
// *	pushes a "standard move" onto the stack.  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);

	//	make sure we don't add this move in the case where we were able to 
	//	defer move generation, try the hashtable move, but did not generate a 
	//	cut-off and were forced to generate moves anyway.  in this case, we 
	//	want to make sure not to add the hashtable move again, since we have 
	//	already tried it (first.)
	if( hashtableMove.GetMoveType() != StandardMove ||
		hashtableMove.GetFromSquare() != fromSquareNumber || 
		hashtableMove.GetToSquare() != toSquareNumber )
	{
		//	******************  //
		//	*** PROMOTIONS ***  //
		//	******************  //

		PieceType *types[20];
		int promotionTypes = 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 );
			}
			if( promotionTypes == 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
		{
			// *** PUSH 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 );

			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 );

			//	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 )
			{
				isLegal = MakeMove( moveCursor - 1 );
				UnmakeMove( moveCursor - 1 );
				if( isLegal )
				{
					moves[moveCursor-1].evaluation = 0;
				}
				else
				{
					moveCursor--;
					pickupCursor--;
					dropCursor--;
				}
			}
			if( isLegal )
			{
				// *** 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 == board->pvTable[1][board->currentDepth] )
					//	this is the Principal Variation (PV) move; highest ordering
					move.evaluation = INFINITY;
				else if( move == hashtableMove )
					//	move looked up from hash table; gets 2nd hightest ordering
					move.evaluation = 90000;
				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 = 10000;
				else
				{
					//	all other moves are ordered last; they are ordered by 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]] - 1000;
					}
					else
						move.evaluation = board->squareValues[move.toSquare] - 
							board->squareValues[move.fromSquare] - 1000;

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

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

// ***********************************************************************
// *
// *	AddCapture
// *
// *	pushes a "standard capture" onto the stack.  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;


	// *** PROMOTIONS *** ///
	PieceType *types[20];
	int promotionTypes = 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 );
		}
		if( promotionTypes == 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
	{
		//	** PUSH 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 );

		moves[moveCursor].type = StandardCapture;
		//	pick up the captured piece
		pickups[pickupCursor++] = PickUp( pieceBeingCaptured, toSquareNumber );

		//	promotions
		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 );

		//	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 )
		{
			isLegal = MakeMove( moveCursor - 1 );
			UnmakeMove( moveCursor - 1 );
			if( !isLegal )
			{
				moveCursor--;
				dropCursor--;
				pickupCursor -= 2;
			}
		}
		if( isLegal )
		{
			MoveInfo &move = moves[moveCursor-1];
			//	perform fast evaluation of the likely value of this move
			if( move == board->pvTable[1][board->currentDepth] )
				//	this is the Principal Variation (PV) move; highest ordering
				move.evaluation = INFINITY;
			else if( move == hashtableMove )
				//	move looked up from hash table; gets 2nd hightest ordering
				move.evaluation = 90000;
			else
			{
				//	for all remaining captures, it depends on whether or not we
				//	are in quiescent search or not.  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 )
					move.evaluation = EvaluateExchange( moveCursor - 1 );
				else
					move.evaluation = pieceBeingCaptured->GetBaseValue() - 
									(pieceBeingMoved->GetBaseValue() >> 4) + 5000;
				//	adjustment for promotions
				if( move.promotion != NULL )
					move.evaluation += move.promotion->GetBaseValue() - pieceBeingMoved->GetType().GetBaseValue();
			}
		}
	}
	while( promotionTypes > 0 );
}

// ***********************************************************************
// *
// *	PushIguiCapture
// *
// *	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::PushIguiCapture
	( 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++;

	//	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() + 2000;
}

// ***********************************************************************
// *
// *	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;
}

// ***********************************************************************
// *
// *	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 )
{
	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++;

	bool isLegal = true;
	if( checkForLegality )
	{
		isLegal = MakeMove( moveCursor - 1 );
		UnmakeMove( moveCursor - 1 );
		if( !isLegal )
		{
			moveCursor--;
			if( moveCursor == 0 )
			{
				pickupCursor = 0;
				dropCursor = 0;
			}
			else
			{
				pickupCursor = moves[moveCursor-1].pickupCursor;
				dropCursor = moves[moveCursor-1].dropCursor;
			}
		}
	}
	return moveCursor - 1;
}

// ***********************************************************************
// *
// *	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;
		}
	}
}

// ***********************************************************************
// *
// *	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( moveGenerationDefered )
	{
		//	we defered the move generation in hopes that the hash table 
		//	move was good enough to cause a beta-cutoff.  
		if( triedHashtableMove )
		{
			//	since we are here, the has move was not good enough to 
			//	cause a cut-off, so we really do need to generate moves.
			PerformMoveGeneration( Movement(), currentNodeType );
			moveGenerationDefered = false;
		}
		else
		{
			//	make the move suggested by the hashtable (Transposition Table)
			triedHashtableMove = true;
			MakeMove( 0 );
			return true;
		}
	}

	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
				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()
{
	//	going back up
	board->gamePly--;

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

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

	//	undo all pickups
	int firstPickup = moveOrder[currentMove] == 0 ? 0 : moves[moveOrder[currentMove] - 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++;

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

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

void MovementList::GenerateMoves
	( Movement hashMove, 
	  NodeType nodeType )
{
	Clear();
	quiescentSearch = false;
	currentNodeType = nodeType;

	triedHashtableMove = false;
	if( hashtableMove.GetMoveType() == StandardMove )
	{
		moveGenerationDefered = true;
		hashtableMove.Clear();
		AddMove( hashMove.GetFromSquare(), hashMove.GetToSquare() );
		hashtableMove = hashMove;
	}
	else
	{
		moveGenerationDefered = false;
		PerformMoveGeneration( hashMove, nodeType );
	}
}

void MovementList::GenerateBitBoard64Moves()
{
	BitBoard64 pieces;
	BitBoard64 moves;
	BitBoard64 notFriends = ~board->bb64_friends[board->currentPlayer];
	int square;

	//	horizontal sliders
	pieces = board->bb64_rook_sliders[board->currentPlayer];
	while( pieces )
	{
		square = pieces.GetFirstBit();
		pieces.ToggleBit( square );
		moves = board->rook00attack[square * board->rook00attackWidth + 
			((board->bb64_blocker >> board->shift00[square]) & board->mask00[square])] | 
			board->rook90attack[square * board->rook90attackWidth + 
			((board->bb64_blocker90 >> board->shift90[square]) & board->mask90[square])];
		PushBitBoard64Moves( square, moves & notFriends );
	}
}

void MovementList::PushBitBoard64Moves
	( int fromSquare, 
	  BitBoard64 toSquares )
{
	int 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
	( NodeType nodeType )
{
	Clear();
	quiescentSearch = true;
	hashtableMove = Movement();
	currentNodeType = nodeType;
	moveGenerationDefered = false;

	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 captures for it
				board->pieces[board->currentPlayer][currentPiece]->GenerateCaptures( *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( *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.
}

// ***********************************************************************
// *
// *	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 )
{
	if( iDepth >= 3 )
	{
		for( int i = 0; i < moveCursor; i++ )
		{
			MoveInfo &move = GetMove( moveOrder[i] );
			if( move == board->pvTable[1][1] )
				move.evaluation = 100000 + iDepth;
		}
	}

	//	initialize moveOrder array
	for( int i = 0; i < moveCursor; i++ )
		moveOrder[i] = i;

	//	perform insertion sort
	int index;
	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                             **
**                                                                      **
**************************************************************************
\************************************************************************/

void MovementList::PerformMoveGeneration
	( Movement hashMove, 
	  NodeType nodeType )
{
	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( *this, board->gameRecords[board->gamePly-1], false );

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


// ***********************************************************************
// *
// *	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. historical moves
// *		6. moves to squares of highest value
// 
void MovementList::OrderMoves
	( Movement hashMove,
	  NodeType nodeType )
{
	//	perform insertion sort
	int index;
	int indexValue;
	for( int 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;
	}
}

// ***********************************************************************
// *
// *	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
	board->primaryHash   ^= piece->GetPrimaryHash( squareNumber );
	board->secondaryHash ^= piece->GetSecondaryHash( squareNumber );
	if( piece->IsPawn() )
	{
		board->primaryPawnHash   ^= piece->GetPrimaryHash( squareNumber );
		board->secondaryPawnHash ^= piece->GetSecondaryHash( squareNumber );
	}

	//	empty the vacated square
	*square = NULL;

	//	update bitboards
	switch( board->GetGame().GetBitBoardType() )
	{
	  case BITBOARD_64:
		piece->GetType().BB64_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_blocker315.ToggleBit( board->rotate315[squareNumber] );
		board->bb64_friends[piece->GetPlayerNumber()].ToggleBit( squareNumber );
		board->bb64_rook_sliders[piece->GetPlayerNumber()] ^= 
			(BitBoard64::GetPositionBitBoard( squareNumber ) & piece->GetType().BB64_IsOrthogonalSlider());
		board->bb64_diag_sliders[piece->GetPlayerNumber()] ^= 
			(BitBoard64::GetPositionBitBoard( squareNumber ) & piece->GetType().BB64_IsDiagonalSlider());
		break;

	  case BITBOARD_NONE:
		break;
	}

	piece->SetCapturedStatus( true );
	board->nCapturedPieces++;
	board->material[piece->GetPlayerNumber()] -= piece->GetBaseValue();
}

// ***********************************************************************
// *
// *	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
	board->primaryHash   ^= piece->GetPrimaryHash( squareNumber );
	board->secondaryHash ^= piece->GetSecondaryHash( squareNumber );
	if( piece->IsPawn() )
	{
		board->primaryPawnHash   ^= piece->GetPrimaryHash( squareNumber );
		board->secondaryPawnHash ^= piece->GetSecondaryHash( squareNumber );
	}

	//	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 )
		//	set the has-castled flag
		piece->flags |= FLAGS_HAS_CASTLED;

	//	update bitboards
	switch( board->GetGame().GetBitBoardType() )
	{
	  case BITBOARD_64:
		piece->GetType().BB64_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_blocker315.ToggleBit( board->rotate315[squareNumber] );
		board->bb64_friends[piece->GetPlayerNumber()].ToggleBit( squareNumber );
		board->bb64_rook_sliders[piece->GetPlayerNumber()] ^= 
			(BitBoard64::GetPositionBitBoard( squareNumber ) & piece->GetType().BB64_IsOrthogonalSlider());
		board->bb64_diag_sliders[piece->GetPlayerNumber()] ^= 
			(BitBoard64::GetPositionBitBoard( squareNumber ) & piece->GetType().BB64_IsDiagonalSlider());
		break;

	  case BITBOARD_NONE:
		break;
	}

	piece->SetCapturedStatus( false );
	board->nCapturedPieces--;
	board->material[piece->GetPlayerNumber()] += piece->GetBaseValue();
}

// ***********************************************************************
// *
// *	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
	board->primaryHash   ^= piece->GetPrimaryHash( squareNumber );
	board->secondaryHash ^= piece->GetSecondaryHash( squareNumber );
	if( piece->IsPawn() )
	{
		board->primaryPawnHash   ^= piece->GetPrimaryHash( squareNumber );
		board->secondaryPawnHash ^= piece->GetSecondaryHash( squareNumber );
	}

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

	//	update bitboards
	switch( board->GetGame().GetBitBoardType() )
	{
	  case BITBOARD_64:
		piece->GetType().BB64_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_blocker315.ToggleBit( board->rotate315[squareNumber] );
		board->bb64_friends[piece->GetPlayerNumber()].ToggleBit( squareNumber );
		board->bb64_rook_sliders[piece->GetPlayerNumber()] ^= 
			(BitBoard64::GetPositionBitBoard( squareNumber ) & piece->GetType().BB64_IsOrthogonalSlider());
		board->bb64_diag_sliders[piece->GetPlayerNumber()] ^= 
			(BitBoard64::GetPositionBitBoard( squareNumber ) & piece->GetType().BB64_IsDiagonalSlider());
		break;

	  case BITBOARD_NONE:
		break;
	}

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

	piece->SetCapturedStatus( false );
	board->nCapturedPieces--;
	board->material[piece->GetPlayerNumber()] += piece->GetBaseValue();
}

// ***********************************************************************
// *
// *	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
	board->primaryHash   ^= piece->GetPrimaryHash( squareNumber );
	board->secondaryHash ^= piece->GetSecondaryHash( squareNumber );
	if( piece->IsPawn() )
	{
		board->primaryPawnHash   ^= piece->GetPrimaryHash( squareNumber );
		board->secondaryPawnHash ^= piece->GetSecondaryHash( squareNumber );
	}

	//	clear the square
	*square = NULL;

	//	update bitboards
	switch( board->GetGame().GetBitBoardType() )
	{
	  case BITBOARD_64:
		piece->GetType().BB64_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_blocker315.ToggleBit( board->rotate315[squareNumber] );
		board->bb64_friends[piece->GetPlayerNumber()].ToggleBit( squareNumber );
		board->bb64_rook_sliders[piece->GetPlayerNumber()] ^= 
			(BitBoard64::GetPositionBitBoard( squareNumber ) & piece->GetType().BB64_IsOrthogonalSlider());
		board->bb64_diag_sliders[piece->GetPlayerNumber()] ^= 
			(BitBoard64::GetPositionBitBoard( squareNumber ) & piece->GetType().BB64_IsDiagonalSlider());
		break;

	  case BITBOARD_NONE:
		break;
	}

	piece->SetCapturedStatus( true );
	board->nCapturedPieces++;
	board->material[piece->GetPlayerNumber()] -= piece->GetBaseValue();

	//	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 );
	}
}

// ***********************************************************************
// *
// *	MoveMove
// *
// *	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];

	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);

	//	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 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 )
		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;
}

// ***********************************************************************
// *
// *	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 i;
	for( i = 0; i < nPlayerAttackers[0]; i++ )
		playerAttackOrder[0][i] = i;
	for( i = 0; i < nPlayerAttackers[1]; i++ )
		playerAttackOrder[1][i] = i;

	//	perform insertion sort of player 0 attackers
	int index;
	int indexValue;
	for( i = 1; i < nPlayerAttackers[0]; i++ )
	{
		index = i;
		indexValue = playerAttackers[0][playerAttackOrder[0][i]].baseValue;
		int j = i;
		while( j > 0 && playerAttackers[0][playerAttackOrder[0][j-1]].baseValue > indexValue )
		{
			playerAttackOrder[0][j] = playerAttackOrder[0][j-1];
			j--;
		}
		playerAttackOrder[0][j] = index;
	}
	//	perform insertion sort of player 1 attackers
	for( i = 1; i < nPlayerAttackers[1]; i++ )
	{
		index = i;
		indexValue = playerAttackers[1][playerAttackOrder[1][i]].baseValue;
		int j = i;
		while( j > 0 && playerAttackers[1][playerAttackOrder[1][j-1]].baseValue > indexValue )
		{
			playerAttackOrder[1][j] = playerAttackOrder[1][j-1];
			j--;
		}
		playerAttackOrder[1][j] = index;
	}

	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( cursor[xside] == nPlayerAttackers[xside] )
			break;
		swapList[n] = swapList[n-1] + lastval;
		n++;
		AttackVector vector = playerAttackers[xside][playerAttackOrder[xside][cursor[xside]]];
		cursor[xside]++;
		lastval = vector.baseValue;

		//	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 )
		{
			Piece *piece = board->GetSquareContents( square );
			if( piece != NULL )
			{
				square = -1;
				if( piece->GetType().GetAttackRange( piece->GetPlayerNumber(), oppositeDirection ) <= steps )
				{
					//	insert new piece in place
					int nPlayer = piece->GetPlayerNumber();
					index = nPlayerAttackers[nPlayer];
					indexValue = piece->GetBaseValue();
					int j = index;
					while( j > cursor[nPlayer] && playerAttackers[nPlayer][playerAttackOrder[nPlayer][j-1]].baseValue > indexValue )
					{
						playerAttackOrder[nPlayer][j] = playerAttackOrder[nPlayer][j-1];
						j--;
					}
					playerAttackOrder[nPlayer][j] = index;
					nPlayerAttackers[nPlayer]++;
				}
			}
			else
			{
				square = matrix[square];
				steps++;
			}
		}
		break;

		if( cursor[side] == nPlayerAttackers[side] )
			break;
		swapList[n] = swapList[n-1] + lastval;
		n++;
		vector = playerAttackers[side][playerAttackOrder[side][cursor[side]]];
		cursor[side]++;
		lastval = -vector.baseValue;

		//	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 )
		{
			Piece *piece = board->GetSquareContents( square );
			if( piece != NULL )
			{
				square = -1;
				if( piece->GetType().GetAttackRange( piece->GetPlayerNumber(), oppositeDirection ) <= steps )
				{
					//	insert new piece in place
					int nPlayer = piece->GetPlayerNumber();
					index = nPlayerAttackers[nPlayer];
					indexValue = piece->GetBaseValue();
					int j = index;
					while( j > cursor[nPlayer] && playerAttackers[nPlayer][playerAttackOrder[nPlayer][j-1]].baseValue > indexValue )
					{
						playerAttackOrder[nPlayer][j] = playerAttackOrder[nPlayer][j-1];
						j--;
					}
					playerAttackOrder[nPlayer][j] = index;
					nPlayerAttackers[nPlayer]++;
				}
			}
			else
			{
				square = matrix[square];
				steps++;
			}
		}
		break;
	}

	//	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];
}

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