/*
	File:		MBCMoveGenerator.h
	Contains:	Generate all legal moves from a position
	Version:	1.0
	Copyright:	© 2003 by Apple Computer, Inc., all rights reserved.

	File Ownership:

		DRI:				Matthias Neeracher    x43683

	Writers:

		(MN)	Matthias Neeracher

	Change History (most recent first):

		$Log: MBCMoveGenerator.mm,v $
		Revision 1.4  2003/07/14 23:19:56  neerache
		Record color of generated moves
		
		Revision 1.3  2003/07/02 21:00:07  neerache
		Added MBCMoveCollection
		
		Revision 1.2  2003/06/30 04:58:22  neerache
		Make MBCMoveBuilder a protocol, rename methods to be clearer
		
		Revision 1.1  2003/06/16 05:28:32  neerache
		Added move generation facility
		
*/

#include "MBCMoveGenerator.h"

@implementation MBCMoveCounter

- (int)count
{
	return fCount;
}

- (void) startMoveList:(BOOL)white
{
	fCount 		= 0;
	fCounting	= true;
}

- (void) startUnambiguousMoves
{
	fCounting = false;
}

- (void) endMoveList
{
}


- (void) validMove:(MBCPiece)piece from:(MBCSquare)from to:(MBCSquare)to
{
    fCount += fCounting;
}

- (void) validMove:(MBCPiece)piece from:(MBCSquare)from to:(MBCSquare)to 
  capturing:(MBCPiece) victim
{
	fCount += fCounting;
}

- (void) validDrop:(MBCPiece)piece at:(MBCSquare)at
{
    fCount += fCounting;
}

- (void) validCastle:(MBCPiece)king kingSide:(BOOL)kingSide;
{
    fCount += fCounting;
}

@end

@implementation MBCDebugMoveBuilder

+ (id)debugMoveBuilder
{
	return [[[MBCDebugMoveBuilder alloc] init] autorelease];
}

- (void) startMoveList:(BOOL)white
{
	fUnambiguous		= false;
	fMoves				= [[NSMutableArray alloc] init];
	fUnambiguousMoves 	= [[NSMutableArray alloc] init];
	fDrops				= [[NSMutableArray alloc] init];
}

- (void) startUnambiguousMoves
{
	fUnambiguous		= true;
}

- (void) endMoveList
{
	NSLog(@"Moves:       %@\n", 
		  [fMoves componentsJoinedByString:@" "]);
	NSLog(@"Unambiguous: %@\n", 
		  [fUnambiguousMoves componentsJoinedByString:@" "]);
	if ([fDrops count])
		NSLog(@"Drops:       %@\n", 
			  [fDrops componentsJoinedByString:@" "]);
}

const char * sPieces = " KQBNRP";

- (void) validMove:(MBCPiece)piece from:(MBCSquare)from to:(MBCSquare)to
{
	if (fUnambiguous)
		[fUnambiguousMoves 
			addObject: [NSString stringWithFormat:@"%c%c%d",
								 sPieces[piece], 
								 Col(to), Row(to)]];
	else
		[fMoves 
			addObject: [NSString stringWithFormat:@"%c%c%d-%c%d",
								 sPieces[piece], 
								 Col(from), Row(from),
								 Col(to), Row(to)]];
}

- (void) validMove:(MBCPiece)piece from:(MBCSquare)from to:(MBCSquare)to 
	capturing:(MBCPiece)victim
{
	if (fUnambiguous)
		[fUnambiguousMoves 
			addObject: [NSString stringWithFormat:@"%cx%c%d",
								 sPieces[piece], 
								 Col(to), Row(to)]];
	else
		[fMoves 
			addObject: [NSString stringWithFormat:@"%c%c%dx%c%d",
								 sPieces[piece], 
								 Col(from), Row(from),
								 Col(to), Row(to)]];
}

- (void) validDrop:(MBCPiece)piece at:(MBCSquare)at
{
	[fDrops addObject: [NSString stringWithFormat:@"%c@%c%d",
								 sPieces[piece], 
								 Col(at), Row(at)]];	
}

- (void) validCastle:(MBCPiece)king kingSide:(BOOL)kingSide;
{
	[(fUnambiguous ? fUnambiguousMoves : fMoves)
		addObject:kingSide ? @"O-O" : @"O-O-O"];
}

@end

void MBCMoveCollection::AddMove(
		bool unambig, MBCPiece piece, MBCSquare from, MBCSquare to)
{
	MBCPieceMoves & moves = 
		(unambig ? fUnambiguousMoves : fMoves)[Piece(piece)];
	int instance;
	for (instance = 0; instance < moves.fNumInstances; ++instance)
		if (moves.fFrom[instance] == from)
			goto foundInstance;
	moves.fFrom[moves.fNumInstances++] = from;
 foundInstance:
	moves.fTo[instance] |= (1llu << to);
}

void MBCMoveCollection::AddDrop(MBCPiece piece, MBCSquare at)
{
	if ((piece = MBCPiece(piece)) == PAWN) {
		fPawnDrops			|= (1llu << at);
	} else {	
		fPieceDrops 		|= (1llu << at);
		fDroppablePieces	|= (1 << piece);
	}
}

void MBCMoveCollection::AddCastle(bool kingSide)
{
	if (kingSide)
		fCastleKingside = true;
	else
		fCastleQueenside = true;
}

@implementation MBCMoveCollector

- (MBCMoveCollection *) collection
{
	return &fCollection;
}

- (void) startMoveList:(BOOL)white
{
	fUnambiguous				= false;
	memset(&fCollection, 0, sizeof(MBCMoveCollection));
	fCollection.fWhiteMoves		= white;
}

- (void) startUnambiguousMoves
{
	fUnambiguous	= true;
}

- (void) endMoveList
{
}

- (void) validMove:(MBCPiece)piece from:(MBCSquare)from to:(MBCSquare)to
{
	fCollection.AddMove(fUnambiguous, piece, from, to);
}

- (void) validMove:(MBCPiece)piece from:(MBCSquare)from to:(MBCSquare)to
	capturing:(MBCPiece)victim
{
	fCollection.AddMove(fUnambiguous, piece, from, to);
}

- (void) validDrop:(MBCPiece)piece at:(MBCSquare)at
{
	fCollection.AddDrop(piece, at);
}

- (void) validCastle:(MBCPiece)king kingSide:(BOOL)kingSide
{
	fCollection.AddCastle(kingSide);
}

@end

MBCMoveGenerator::MBCMoveGenerator(id <MBCMoveBuilder> builder, 
								   MBCVariant variant,
								   long flags)
	: fBuilder(builder), fFlags(flags), fVariant(variant),
	 fPieceFilter(EMPTY), fTargetFilter(kInvalidSquare)
{
}

void MBCMoveGenerator::SetVariant(MBCVariant variant)
{
	fVariant = variant;
}

void MBCMoveGenerator::Generate(bool white, const MBCPieces & position)
{
	[fBuilder startMoveList:white];
	
	fColor		=	white ? kWhitePiece : kBlackPiece;
	fPosition	=	&position;	

	memset(fTargetUsed, 0, 64*sizeof(uint8_t));
	memset(fTargetAmbiguous, 0, 64*sizeof(uint8_t));
	
	TryMoves(false);

	[fBuilder startUnambiguousMoves];

	TryMoves(true);

	[fBuilder endMoveList];
}

void MBCMoveGenerator::Ambiguities(MBCSquare from, MBCSquare to, 
								   const MBCPieces & position)
{
	MBCPiece p	= position.fBoard[from];
	
	fPieceFilter	= What(p);
	fTargetFilter	= to;
	
	Generate(Color(p) == kWhitePiece, position);

	fPieceFilter	= EMPTY;
	fTargetFilter	= kInvalidSquare;
}

bool MBCMoveGenerator::InCheck(bool white, const MBCPieces & position)
{
	id 					saveBuilder = fBuilder;
	MBCMoveCounter *	counter		= [[MBCMoveCounter alloc] init];
	MBCPiece 			king		= (white?kWhitePiece:kBlackPiece) | KING;

	fBuilder		= counter;

	for (MBCSquare i = Square('a', 1); i<=Square('h', 8); ++i)
		if (What(position.fBoard[i]) == king) {
			fTargetFilter	= i;
			Generate(!white, position);
			fTargetFilter 	= kInvalidSquare;
			
			break;
		}

	bool res = [counter count] > 0;
	fBuilder = saveBuilder;
	[counter release];

	return res;
}

void MBCMoveGenerator::TryMoves(bool unambiguous)
{
	fUnambiguous	= unambiguous;
	
	for (MBCSquare i = Square('a', 1); i<=Square('h', 8); ++i) {
		MBCPiece piece = fPosition->fBoard[i];
		if (fPieceFilter ? What(piece) == fPieceFilter 
			: (piece && Color(piece) == fColor)
		)
			TryMoves(Piece(piece), i);
	}
	if (fTargetFilter == kInvalidSquare) {
		if (fVariant != kVarSuicide)
			TryCastle();
		if (fVariant == kVarCrazyhouse)
			TryDrops();
	}
}

void MBCMoveGenerator::TryMoves(MBCPiece piece, MBCSquare from)
{
	switch (piece) {
	case PAWN: {
		int 	 dir = fColor == kWhitePiece ? 1 : -1;
		unsigned orig= fColor == kWhitePiece ? 2 : 7;
		
		if (TryMove(piece, from, 0, dir)	// Single step always permitted
		 && Row(from) == orig				// How about a double step?
		)
			TryMove(piece, from, 0, 2*dir);// Double step
		TryMove(piece, from, -1, dir);		// Capture left
		TryMove(piece, from,  1, dir);		// Capture right
		break; }
	case ROOK:
		TryMoves(piece, from,  1,  0);
		TryMoves(piece, from, -1,  0);
		TryMoves(piece, from,  0,  1);
		TryMoves(piece, from,  0, -1);
		break;
	case KNIGHT:
		TryMove(piece, from,  1,  2);
		TryMove(piece, from,  2,  1);
		TryMove(piece, from,  2, -1);
		TryMove(piece, from,  1, -2);
		TryMove(piece, from, -1, -2);
		TryMove(piece, from, -2, -1);
		TryMove(piece, from, -2,  1);
		TryMove(piece, from, -1,  2);
		break;
	case BISHOP:
		TryMoves(piece, from,  1,  1);
		TryMoves(piece, from,  1, -1);
		TryMoves(piece, from, -1, -1);
		TryMoves(piece, from, -1,  1);
		break;
	case QUEEN:
		TryMoves(piece, from,  1,  0);
		TryMoves(piece, from, -1,  0);
		TryMoves(piece, from,  0,  1);
		TryMoves(piece, from,  0, -1);
		TryMoves(piece, from,  1,  1);
		TryMoves(piece, from,  1, -1);
		TryMoves(piece, from, -1, -1);
		TryMoves(piece, from, -1,  1);
		break;
	case KING:
		TryMove(piece, from,  1,  0);
		TryMove(piece, from, -1,  0);
		TryMove(piece, from,  0,  1);
		TryMove(piece, from,  0, -1);
		TryMove(piece, from,  1,  1);
		TryMove(piece, from,  1, -1);
		TryMove(piece, from, -1, -1);
		TryMove(piece, from, -1,  1);

		break;
	}
}

void MBCMoveGenerator::TryMoves(MBCPiece piece, MBCSquare from, 
								int dCol, int dRow)
{
	int dc	= 0;
	int dr	= 0;

	while (TryMove(piece, from, (dc += dCol), (dr += dRow)))
		;
}

bool MBCMoveGenerator::TryMove(MBCPiece piece, MBCSquare from,
							   int dCol, int dRow)
{
	char col	= Col(from)+dCol;
	int	 row	= Row(from)+dRow;

	if (col < 'a' || col > 'h' || row < 1 || row > 8)
		return false;
	else
		return TryMove(piece, from, Square(col, row));
}

bool MBCMoveGenerator::TryMove(MBCPiece piece, MBCSquare from, MBCSquare to)
{
	MBCPiece victim = fPosition->fBoard[to];

	if (fTargetFilter != kInvalidSquare && to != fTargetFilter)
		return !victim; // Try again if square was clear

	if (victim && Color(victim) == fColor)
		return false;	// Field is blocked by own piece
	
	if (piece == PAWN) // Pawns move straight, capture diagonally
		if (Col(from) != Col(to)) { // Attempted capture
			if (!victim) // Field is empty, try en passant
				if (fPosition->fEnPassant == to) // Yup
					victim = Opposite(fColor) | PAWN;
				else
					return false;
		} else if (victim) // Straight move is blocked
			return false;
	
	uint8_t pieceMask = 1 << piece;
	
	if (fUnambiguous) {
		// 
		// Simplify language model
		//
		if (fTargetAmbiguous[to] & pieceMask) // Amiguous move, don't do it
			return !victim; // Don't move further after capture
	} else {
		fTargetAmbiguous[to] |= fTargetUsed[to] & pieceMask;
		fTargetUsed[to]      |= pieceMask;
	}
	if (victim)
		[fBuilder validMove:piece from:from to:to capturing:victim];
	else 
		[fBuilder validMove:piece from:from to:to];
	
	return !victim;	// Don't move further after capture
}

void MBCMoveGenerator::TryCastle()
{
	int row	= fColor == kWhitePiece ? 1 : 8;

	MBCPiece  king			= fColor | KING;
	MBCPiece  rook			= fColor | ROOK;
	MBCSquare kingPos 		= Square('e', row);
	MBCSquare kingRookPos	= Square('h', row);
	MBCSquare queenRookPos	= Square('a', row);

	if (fPosition->fBoard[kingPos] != king) // King moved
		return;
	
	bool kingSide = fPosition->fBoard[kingRookPos]==rook 
		&& !fPosition->fBoard[Square('g', row)]
		&& !fPosition->fBoard[Square('f', row)];
	bool queenSide= fPosition->fBoard[queenRookPos]==rook 
		&& !fPosition->fBoard[Square('b', row)]
		&& !fPosition->fBoard[Square('c', row)]
		&& !fPosition->fBoard[Square('d', row)];

	if (fUnambiguous && kingSide && queenSide)
		return;

	if (kingSide)
		[fBuilder validCastle:king kingSide:YES];
	if (queenSide)
		[fBuilder validCastle:king kingSide:NO];
}

void MBCMoveGenerator::TryDrops()
{
	for (MBCPiece p = QUEEN; p <= PAWN; ++p) {
		MBCPiece piece = fColor | p;
		int	pawn	   = p==PAWN;
		if (!fPosition->fInHand[piece])
			continue;
		for (MBCSquare i = Square('a', 1+pawn); i <= Square('h', 8-pawn); ++i)
			if (!fPosition->fBoard[i])
				[fBuilder validDrop:piece at:i];
	}
}

// Local Variables:
// mode:ObjC
// End: