MoveGeneratorLUT.cpp

#include "chess.h"

// generates sliding moves using a lookup table (only for bishop, rook and queen)
// moves for other pieces are generated using the 088 move generator

MoveLUTItem MoveGeneratorLUT::slidingMoveTable[1456+896+560];	 // for queen, rook and bishop
uint32      MoveGeneratorLUT::slidingModeStart[3][64];			 // start indices from all board positions for all sliding pieces


// adds the temp. moves generated by 088 MoveGenerator to the lookup table
void MoveGeneratorLUT::addGeneratedMoves(uint32 &lutIndex, uint32 next1)
{
	uint32 n = MoveGenerator::nMoves;
	next1 = lutIndex + n;
	for (uint32 j=0; j < n; j++)
	{
		slidingMoveTable[lutIndex].tosq  = MoveGenerator::moves[j].dst;
		slidingMoveTable[lutIndex].next0 = lutIndex + 1;
		slidingMoveTable[lutIndex].next1 = next1;
		lutIndex++;
	}
	assert((lutIndex == next1));
	MoveGenerator::nMoves = 0;
}

// initialize the look up tables used for table driven sliding move generation
void MoveGeneratorLUT::init()
{
	uint32 lutIndex = 0;

	BoardPosition pos;
	pos.chance = 0;
	Move tempMoves[MAX_SINGLE_PIECE_MOVES];

	// initialize the 088 MoveGenerator to help generating the look up table

	MoveGenerator::pos = &pos;
	MoveGenerator::chance = 0;
	MoveGenerator::moves = tempMoves;
	MoveGenerator::nMoves = 0;

	// 1. bishop moves
	for (uint32 i=0; i < 64; i++)
	{
		uint32 rank = i / 8;
		uint32 file = i % 8;
		slidingModeStart[SLIDING_PIECE_INDEX(BISHOP)][i] = lutIndex;


		// clear the board and place a single piece on it at the location 'i'
		Utils::clearBoard(&pos);
		uint32 curPos = INDEX088(rank, file);
		pos.board[curPos] = COLOR_PIECE(WHITE, BISHOP);

		uint32 overWriteNext1FromHere = lutIndex;

		MoveGenerator::generateSlidingMoves(curPos,   0xf);    // north-west
		addGeneratedMoves(lutIndex, 0);

		MoveGenerator::generateSlidingMoves(curPos,  0x11);    // north-east
		if (MoveGenerator::nMoves) overWriteNext1FromHere = lutIndex;
		addGeneratedMoves(lutIndex, 0);

		MoveGenerator::generateSlidingMoves(curPos,  -0x11);   // south-west
		if (MoveGenerator::nMoves) overWriteNext1FromHere = lutIndex;
		addGeneratedMoves(lutIndex, 0);

		MoveGenerator::generateSlidingMoves(curPos,  -0xf);    // south-east
		if (MoveGenerator::nMoves) overWriteNext1FromHere = lutIndex;
		addGeneratedMoves(lutIndex, 0);

		for(uint32 j = overWriteNext1FromHere; j<lutIndex; j++) 
			slidingMoveTable[j].next1 = 0;

		slidingMoveTable[lutIndex - 1].next0 = 0;
	}

	// 2. rook moves
	for (uint32 i=0; i < 64; i++)
	{
		uint32 rank = i / 8;
		uint32 file = i % 8;
		slidingModeStart[SLIDING_PIECE_INDEX(ROOK)][i] = lutIndex;
		
		// clear the board and place a single piece on it at the location 'i'
		Utils::clearBoard(&pos);
		
		uint32 curPos = INDEX088(rank, file);
		pos.board[curPos] = COLOR_PIECE(WHITE, ROOK);

		uint32 overWriteNext1FromHere = lutIndex;

		MoveGenerator::generateSlidingMoves(curPos,  0x10);    // up
		addGeneratedMoves(lutIndex, 0);

		MoveGenerator::generateSlidingMoves(curPos, -0x10);    // down
		if (MoveGenerator::nMoves) overWriteNext1FromHere = lutIndex;
		addGeneratedMoves(lutIndex, 0);

		MoveGenerator::generateSlidingMoves(curPos,   0x1);    // right
		if (MoveGenerator::nMoves) overWriteNext1FromHere = lutIndex;
		addGeneratedMoves(lutIndex, 0);

		MoveGenerator::generateSlidingMoves(curPos,  -0x1);    // left
		if (MoveGenerator::nMoves) overWriteNext1FromHere = lutIndex;
		addGeneratedMoves(lutIndex, 0);

		for(uint32 j = overWriteNext1FromHere; j<lutIndex; j++) 
			slidingMoveTable[j].next1 = 0;

		slidingMoveTable[lutIndex - 1].next0 = 0;
	}

	// 3. queen moves
	for (uint32 i=0; i < 64; i++)
	{
		uint32 rank = i / 8;
		uint32 file = i % 8;
		slidingModeStart[SLIDING_PIECE_INDEX(QUEEN)][i] = lutIndex;
		
		// clear the board and place a single piece on it at the location 'i'
		Utils::clearBoard(&pos);
		
		uint32 curPos = INDEX088(rank, file);
		pos.board[curPos] = COLOR_PIECE(WHITE, QUEEN);

		uint32 overWriteNext1FromHere = lutIndex;

		MoveGenerator::generateSlidingMoves(curPos,  0x10);    // up
		addGeneratedMoves(lutIndex, 0);

		MoveGenerator::generateSlidingMoves(curPos, -0x10);    // down
		if (MoveGenerator::nMoves) overWriteNext1FromHere = lutIndex;
		addGeneratedMoves(lutIndex, 0);

		MoveGenerator::generateSlidingMoves(curPos,   0x1);    // right
		if (MoveGenerator::nMoves) overWriteNext1FromHere = lutIndex;
		addGeneratedMoves(lutIndex, 0);

		MoveGenerator::generateSlidingMoves(curPos,  -0x1);    // left
		if (MoveGenerator::nMoves) overWriteNext1FromHere = lutIndex;
		addGeneratedMoves(lutIndex, 0);

		MoveGenerator::generateSlidingMoves(curPos,   0xf);    // north-west
		if (MoveGenerator::nMoves) overWriteNext1FromHere = lutIndex;
		addGeneratedMoves(lutIndex, 0);

		MoveGenerator::generateSlidingMoves(curPos,  0x11);    // north-east
		if (MoveGenerator::nMoves) overWriteNext1FromHere = lutIndex;
		addGeneratedMoves(lutIndex, 0);

		MoveGenerator::generateSlidingMoves(curPos,  -0x11);   // south-west
		if (MoveGenerator::nMoves) overWriteNext1FromHere = lutIndex;
		addGeneratedMoves(lutIndex, 0);

		MoveGenerator::generateSlidingMoves(curPos,  -0xf);    // south-east
		if (MoveGenerator::nMoves) overWriteNext1FromHere = lutIndex;
		addGeneratedMoves(lutIndex, 0);

		for(uint32 j = overWriteNext1FromHere; j<lutIndex; j++) 
			slidingMoveTable[j].next1 = 0;

		slidingMoveTable[lutIndex - 1].next0 = 0;
	}

	//printf("lutIndex is now: %d\n", lutIndex);
}

#if 0
void MoveGeneratorLUT::generateSlidingMoves(uint32 origPiece, uint32 index88, uint32 index)
{
	uint32 side2moveBit = chance + 1;
	uint32 *table = (uint32 *) slidingMoveTable;

	// taken from http://chessprogramming.wikispaces.com/Table-driven+Move+Generation
	uint32 slidingPiece = SLIDING_PIECE_INDEX(origPiece);
	uint32 node = slidingModeStart[slidingPiece][index];

	do {
		node  = table[node];
		uint32 tosq  = node & 0xFF;	// MoveLUTItem.tosq
		uint32 piece = pos->board[tosq];
		
		moves[nMoves].capturedPiece = piece;
		moves[nMoves].dst = tosq;
		moves[nMoves].flags = 0;
		moves[nMoves].src = index88;
		
		nMoves += (piece & side2moveBit) == 0;		// add the move only if it was empty or opponent square
		node = (node >> (piece & 0x1C)) & 0xFFF;	// magic to jump to correct next index
	}
	while (node);
}
#endif

// this more readable version is actually a bit faster :-/
// uselss magic jumps and strance encoded bits (at least on x86)
void MoveGeneratorLUT::generateSlidingMoves(uint32 origPiece, uint32 index88, uint32 index)
{
	uint32 side2moveBit = chance + 1;

	// taken from http://chessprogramming.wikispaces.com/Table-driven+Move+Generation
	uint32 slidingPiece = SLIDING_PIECE_INDEX(origPiece);
	uint32 lutIndex = slidingModeStart[slidingPiece][index];

	do {
		MoveLUTItem node  = slidingMoveTable[lutIndex];
		uint32 tosq  = node.tosq;
		uint32 piece = pos->board[tosq];
		
		moves[nMoves].capturedPiece = piece;
		moves[nMoves].dst = tosq;
		moves[nMoves].flags = 0;
		moves[nMoves].src = index88;
		
		nMoves += (piece & side2moveBit) == 0;		// add the move only if it was empty or opponent square

		lutIndex = ISEMPTY(piece) ? node.next0 : node.next1;
	}
	while (lutIndex);
}

int MoveGeneratorLUT::generateMoves (BoardPosition *position, Move *generatedMoves)
{
    pos = position;
    moves = generatedMoves;
    nMoves = 0;
    chance = pos->chance;

	// still uses code from 0x88 move generator
	// for non-sliding pieces
	// TODO: unify everything to use lookup tables
	// for knight move and king's normal moves it should be simple
	// special handling for pawn and king special moves needed

    // loop through all the squares in the board
    // TODO: maybe keep a list of squares containing white and black pieces?
    uint32 i, j;
    for (i = 0; i < 8; i++)
    {
        for (j = 0; j < 8; j++)
        {
            uint32 index088 = INDEX088(i, j);
            uint32 colorpiece = position->board[index088];
            if(IS_OF_COLOR(colorpiece, chance))
            {
				uint32 piece = PIECE(colorpiece);
				switch(piece)
				{
					case BISHOP:
					case ROOK:
					case QUEEN:
						generateSlidingMoves(piece, index088, i*8 | j);
						break;
					case PAWN:
						generatePawnMoves(index088);
						break;
					case KNIGHT:
						generateKnightMoves(index088);
						break;
					case KING:
						generateKingMoves(index088);
						break;
				}
            }
        }
    }

    return nMoves;
}


// static members have to be defined seperately.. what the crap! ?
BoardPosition *MoveGeneratorLUT::pos;
Move *MoveGeneratorLUT::moves;
uint32 MoveGeneratorLUT::nMoves;
uint32 MoveGeneratorLUT::chance;



// TODO: get rid of everything below this by using lookup table for pawn, knight and king too

void MoveGeneratorLUT::addMove(uint32 src, uint32 dst, uint8 oldPiece, uint8 flags)
{
    moves[nMoves].src = (uint8) src;
    moves[nMoves].dst = (uint8) dst;
    moves[nMoves].capturedPiece = (uint8) oldPiece;
    moves[nMoves].flags = flags;
    nMoves++;
}

void MoveGeneratorLUT::addPromotions(uint32 src, uint32 dst, uint8 oldPiece)
{
    addMove(src, dst, oldPiece, PROMOTION_QUEEN);
    addMove(src, dst, oldPiece, PROMOTION_KNIGHT);
    addMove(src, dst, oldPiece, PROMOTION_ROOK);
    addMove(src, dst, oldPiece, PROMOTION_BISHOP);        
}

void MoveGeneratorLUT::generatePawnMoves(uint32 curPos)
{
    uint32 finalRank = chance ?  0 : 7;
    uint32 curRank   = RANK(curPos);

    // pawn advancement
    
    // single square forward
    uint32 offset  = chance ? -16 : 16;
    uint32 newPos  = curPos + offset;
    uint32 newRank = RANK(newPos);

    if (ISVALIDPOS(newPos) && ISEMPTY(pos->board[newPos]))
    {
        if(newRank == finalRank)
        {
            // promotion
            addPromotions(curPos, newPos, EMPTY_SQUARE);
        }
        else
        {
            addMove(curPos, newPos, EMPTY_SQUARE, 0);

            // two squares forward
            uint32 startRank = chance ?  6 : 1;
            if (curRank == startRank)
            {
                newPos += offset;
                if (ISEMPTY(pos->board[newPos]))
                    addMove(curPos, newPos, EMPTY_SQUARE, 0);
            }
        }
    }

    // captures
    offset = chance ? -15 : 15;
    newPos = curPos + offset;
    uint32 capturedPiece = pos->board[newPos];
    if (ISVALIDPOS(newPos) && IS_ENEMY_COLOR(capturedPiece, chance))
    {
        if(newRank == finalRank)
        {
            // promotion
            addPromotions(curPos, newPos, capturedPiece);
        }
        else
        {
            addMove(curPos, newPos, capturedPiece, 0);
        }
    }

    offset = chance ? -17 : 17;
    newPos = curPos + offset;
    capturedPiece = pos->board[newPos];
    if (ISVALIDPOS(newPos) && IS_ENEMY_COLOR(capturedPiece, chance))
    {
        if(newRank == finalRank)
        {
            // promotion
            addPromotions(curPos, newPos, capturedPiece);
        }
        else
        {
            addMove(curPos, newPos, capturedPiece, 0);
        }
    }

    // En-passent
    if (pos->enPassent)
    {
        uint32 enPassentFile = pos->enPassent - 1;
        uint32 enPassentRank = chance ? 4 : 3;
        if ((curRank == enPassentRank) && (abs(FILE(curPos) - enPassentFile) == 1))
        {
            uint32 finalRank = chance ? 5 : 2;
            newPos = INDEX088(finalRank, enPassentFile);
            addMove(curPos, newPos, COLOR_PIECE(!chance, PAWN), EN_PASSENT);
        }
    }
}

void MoveGeneratorLUT::generateOffsetedMove(uint32 curPos, uint32 offset)
{
    uint32 newPos = curPos + offset;
    if(ISVALIDPOS(newPos))
    {
        uint8 capturedPiece = pos->board[newPos];
        if (!IS_OF_COLOR(capturedPiece, chance))
            addMove(curPos, newPos, capturedPiece, 0);
    }
}

void MoveGeneratorLUT::generateOffsetedMoves(uint32 curPos, const uint32 jumpTable[], int n)
{
    for (int i = 0; i < n; i++)
    {
        generateOffsetedMove(curPos, jumpTable[i]);
    }
}

void MoveGeneratorLUT::generateKnightMoves(uint32 curPos)
{
    const uint32 jumpTable[] = {0x1F, 0x21, 0xE, 0x12, -0x12, -0xE, -0x21, -0x1F};
    generateOffsetedMoves(curPos, jumpTable, 8);
}

void MoveGeneratorLUT::generateKingMoves(uint32 curPos)
{
    // normal moves
    const uint32 jumpTable[] = {0xF, 0x10, 0x11, 0x1, -0x1, -0x11, -0x10, -0xF};
    generateOffsetedMoves(curPos, jumpTable, 8);

    // castling
    uint32 castleFlag = chance ? pos->blackCastle : pos->whiteCastle ;
    if ((castleFlag & CASTLE_FLAG_KING_SIDE) && ISEMPTY(pos->board[curPos+1]) && ISEMPTY(pos->board[curPos+2]))
    {
        // no need to check for king's and rook's position as if they have moved, the castle flag would be zero
        // TODO: check if any of the squares involved is in check!
        addMove(curPos, curPos + 0x2, EMPTY_SQUARE, CASTLE_KING_SIDE);
    }
    if ((castleFlag & CASTLE_FLAG_QUEEN_SIDE) && ISEMPTY(pos->board[curPos-1]) && 
        ISEMPTY(pos->board[curPos-2]) && ISEMPTY(pos->board[curPos-3]))
    {
        // no need to check for king's and rook's position as if they have moved, the castle flag would be zero
        // TODO: check if any of the squares involved is in check!
        addMove(curPos, curPos - 0x2, EMPTY_SQUARE, CASTLE_QUEEN_SIDE);
    }
}