diff options
Diffstat (limited to 'src/generate.c')
| -rwxr-xr-x | src/generate.c | 3270 |
1 files changed, 3270 insertions, 0 deletions
diff --git a/src/generate.c b/src/generate.c new file mode 100755 index 0000000..f1ebab8 --- /dev/null +++ b/src/generate.c @@ -0,0 +1,3270 @@ +/** + +Copyright (c) Scott Gasch + +Module Name: + + generate.c + +Abstract: + + This module contains two move generators: a pseudo legal move + generator and a pseudo legal escaping move generator. The former + is called in positions where side on move is not in check and the + latter is called when the side on move is in check. Note: both of + these generators produce pseudo-legal moves. The normal move + generator is pretty bad: it does not bother to see if moves expose + their own king to check or if castles pass through check + etc... Instead it relies on MakeMove to throw out any illegal + moves it generates. The escape generator is better in that it + produces less illegal moves. But it is still possible to generate + some with it. An example: it will generate replies to check that + may include capturing moves that are illegal because the capturing + piece is pinned to the (already in check) king. Both generators + produce a set of moves that contains the true legal set of moves in + a position as a subset; if a move is legal it will be produced. + + This module also contains some code to flag moves as checking + moves and score moves after they are generated. + +Author: + + Scott Gasch ([email protected]) 11 May 2004 + +Revision History: + + $Id: generate.c 345 2007-12-02 22:56:42Z scott $ + +**/ + +#include "chess.h" +#include "psqt.h" + +// +// Note: this order is important because of how EvalQueen works +// +const INT g_iQKDeltas[] = { + -17, -16, -15, -1, +1, +17, +15, +16, 0 }; + +static void +_FindUnblockedSquares(IN MOVE_STACK *pStack, + IN POSITION *pos) +/** + +Routine description: + + Given a position, find, count and mark all squares that are + unblocked for the king of the side not on move. For example: + + +---+---+---+---+- - - The squares marked with *'s in this + |***| K |***|*Q*| diagram are unblocked for the K. As + +---+---+---+---+- - - you can see, there are nine of them. + |*P*|***|***| | + +---+---+---+---+- - - Note the piece at the end of an unblocked + | |***| |*P*| ray from the king is on an unblocked + +---+---+---+---+- - - square (and its color doesn't matter) + | |*R*| | | + +---+---+---+---+- - - This stuff is used to flag checking moves + | | | | | as they are generated. + . . . . . + + Also note: this is one of the most called routines in the engine; + speed is of the essence here. + +Parameters: + + MOVE_STACK *pStack : move stack pointer + POSITION *pos : position pointer + +Return value: + + void + +**/ +{ + register ULONG u; + COOR cKing = pos->cNonPawns[FLIP(pos->uToMove)][0]; + COOR c; + ULONG uPly = pStack->uPly; +#ifdef DEBUG + PIECE pKing = pos->rgSquare[cKing].pPiece; + ULONG uCount = 0; + COOR cx; + + ASSERT(IS_ON_BOARD(cKing)); + ASSERT(IS_KING(pKing)); + ASSERT(GET_COLOR(pKing) != pos->uToMove); +#endif + + // + // Adjust the unblocked key value for this ply... + // + pStack->uUnblockedKeyValue[uPly]++; +#ifdef DEBUG + FOREACH_SQUARE(c) + { + if (!IS_ON_BOARD(c)) continue; + ASSERT(pStack->sUnblocked[uPly][c].uKey != + pStack->uUnblockedKeyValue[uPly]); + } +#endif + + u = 0; + ASSERT(g_iQKDeltas[u] != 0); + do + { + c = cKing + g_iQKDeltas[u]; + while(IS_ON_BOARD(c)) + { + pStack->sUnblocked[uPly][c].uKey = + pStack->uUnblockedKeyValue[uPly]; + pStack->sUnblocked[uPly][c].iPointer = -1 * g_iQKDeltas[u]; +#ifdef DEBUG + ASSERT(-g_iQKDeltas[u] == DIRECTION_BETWEEN_SQUARES(c,cKing)); + ASSERT(pStack->sUnblocked[uPly][c].iPointer != 0); + cx = c; + do + { + cx += pStack->sUnblocked[uPly][c].iPointer; + } + while(IS_ON_BOARD(cx) && (IS_EMPTY(pos->rgSquare[cx].pPiece))); + ASSERT(cx == cKing); + uCount++; +#endif + if (!IS_EMPTY(pos->rgSquare[c].pPiece)) + { + break; + } + c += g_iQKDeltas[u]; + } + u++; + } + while(g_iQKDeltas[u] != 0); + ASSERT(uCount > 2); + ASSERT(uCount < 28); +} + +#define SQUARE_IS_UNBLOCKED(c) (uUnblocked == kp[(c)].uKey) +#define DIR_FROM_SQ_TO_KING(c) (kp[(c)].iPointer) + +FLAG +WouldGiveCheck(IN SEARCHER_THREAD_CONTEXT *ctx, + IN MOVE mv) +/** + +Routine description: + + Determine whether a move is a checking move or not. For this + function to work properly _FindUnblockedSquares must have been + called at the start of generation. + + Note: this is one of the most called codepaths in the engine, + speed is of the essence here. + +Parameters: + + MOVE_STACK *pStack : the move stack + POSITION *pos : the board + MOVE mv : the move under consideration + +Return value: + + FLAG : TRUE if the move is checking, FALSE otherwise + +**/ +{ + // + // TODO: consider adding a hash table to see if sig+mv would + // give check. Is this worth it? + // + MOVE_STACK *pStack = &(ctx->sMoveStack); + POSITION *pos = &(ctx->sPosition); + COOR cTo = mv.cTo; + COOR cFrom = mv.cFrom; + PIECE pPiece = mv.pMoved; + COOR xKing = pos->cNonPawns[FLIP(GET_COLOR(pPiece))][0]; + KEY_POINTER *kp = &(pStack->sUnblocked[ctx->uPly][0]); + ULONG uUnblocked = pStack->uUnblockedKeyValue[ctx->uPly]; + COOR cEpSquare; + int iDelta; + + ASSERT(ctx->uPly < MAX_PLY_PER_SEARCH); + ASSERT(PositionsAreEquivalent(&(pStack->board[ctx->uPly]), pos)); + ASSERT(mv.uMove); + ASSERT(IS_KING(pos->rgSquare[xKing].pPiece)); + ASSERT(IS_ON_BOARD(cTo)); + ASSERT(IS_ON_BOARD(cFrom)); + ASSERT(pPiece); + + // + // Phase 1: Does this move directly attack the king? + // + + // + // You can't attack one king directly with the other except by + // castling (in which case the rook is doing the attack). + // + if (IS_KING(pPiece)) + { + if (!IS_SPECIAL_MOVE(mv)) + { + goto exposes; + } + + ASSERT((mv.cFrom == E8) || (mv.cFrom == E1)); + pPiece &= ~4; + ASSERT(!IS_KING(pPiece)); + ASSERT(IS_ROOK(pPiece)); + ASSERT(pPiece == (BLACK_ROOK | GET_COLOR(pPiece))); + + switch(cTo) + { + case C1: + cTo = D1; + if (SQUARE_IS_UNBLOCKED(E1) && + (DIR_FROM_SQ_TO_KING(E1) == 1)) + { + ASSERT(RANK1(xKing)); + return(MOVE_FLAG_CHECKING); + } + break; + case G1: + cTo = F1; + if (SQUARE_IS_UNBLOCKED(E1) && + (DIR_FROM_SQ_TO_KING(E1) == -1)) + { + ASSERT(RANK1(xKing)); + return(MOVE_FLAG_CHECKING); + } + break; + case C8: + cTo = D8; + if (SQUARE_IS_UNBLOCKED(E8) && + (DIR_FROM_SQ_TO_KING(E8) == 1)) + { + ASSERT(RANK8(xKing)); + return(MOVE_FLAG_CHECKING); + } + break; + case G8: + cTo = F8; + if (SQUARE_IS_UNBLOCKED(E8) && + (DIR_FROM_SQ_TO_KING(E8) == -1)) + { + ASSERT(RANK8(xKing)); + return(MOVE_FLAG_CHECKING); + } + break; +#ifdef DEBUG + default: + UtilPanic(SHOULD_NOT_GET_HERE, + NULL, NULL, NULL, NULL, + __FILE__, __LINE__); + break; +#endif + } + } + + // + // Ok, either its not a king or its a castle move and we are thinking + // about the rook now. + // + + // + // Check the attack vector table + // + ASSERT(!IS_KING(pPiece)); + iDelta = 0; + if (mv.pPromoted) + { + ASSERT(IS_PAWN(pPiece)); + ASSERT(GET_COLOR(pPiece) == GET_COLOR(mv.pPromoted)); + pPiece = mv.pPromoted; + ASSERT(!IS_PAWN(pPiece)); + iDelta = cFrom - cTo; + ASSERT(iDelta != 0); + } + + // + // Does pPiece attack xKing directly if there are not pieces in + // the way? + // + if (0 != (CHECK_VECTOR_WITH_INDEX((int)cTo - (int)xKing, + GET_COLOR(pPiece)) & + (1 << PIECE_TYPE(pPiece)))) + { + // + // We don't toggle knight squares as unblocked... so if the sq + // is unblocked then piece must not be a knight. Note: this + // logical OR replaced with bitwise equivalent for speed. + // + if ((SQUARE_IS_UNBLOCKED(cTo)) | (IS_KNIGHT(pPiece))) + { +#ifdef DEBUG + if (SQUARE_IS_UNBLOCKED(cTo)) + { + ASSERT(!IS_KNIGHT(pPiece)); + } + else + { + ASSERT(IS_KNIGHT(pPiece)); + } +#endif + return(MOVE_FLAG_CHECKING); + } + ASSERT(!IS_PAWN(pPiece)); + + // + // Special case: if this is a pawn that just promoted, and the + // from square was unblocked, this pawn in its new state can + // check the king. + // + if ((DIR_FROM_SQ_TO_KING(cFrom) == iDelta) && + (SQUARE_IS_UNBLOCKED(cFrom))) + { + return(MOVE_FLAG_CHECKING); + } + } + + exposes: + // + // We now know that the move itself does not directly attack the + // enemy king. We will now see if that move exposes check to the + // enemy king. + // + + // + // A move cannot expose check directly if its from square is not + // an unblocked square. But if it is unblocked, we will have to + // scan behind the piece to see if there is some attacker. + // + if (SQUARE_IS_UNBLOCKED(cFrom)) + { + // + // Piece moves towards the king on the same ray? Cannot be + // check. Piece moves away from the king on the same ray? + // Cannot be check. + // + if (DIRECTION_BETWEEN_SQUARES(cTo, xKing) != + DIR_FROM_SQ_TO_KING(cFrom)) + { + if (IS_ON_BOARD(FasterExposesCheck(pos, cFrom, xKing))) + { + ASSERT(IS_ON_BOARD(ExposesCheck(pos, cFrom, xKing))); + return(MOVE_FLAG_CHECKING); + } + } + } + + // + // There is one last special case. If this move was enpassant + // it's possible that the removal of the enemy pawn has exposed + // the enemy king to check. + // + // rnb2bnr/ppp3pp/4k3/1B1qPpB1/4p1Q1/8/PPP2PPP/RN2K1NR w - f6 0 0 + // rn5r/pp4pp/8/5qk1/1b2pP2/4K3/PPP3PP/RN4NR b - f3 0 0 + // + if (IS_ENPASSANT(mv)) + { + ASSERT(IS_PAWN(pPiece)); + ASSERT(VALID_EP_SQUARE(cTo)); + ASSERT(cTo == pos->cEpSquare); + cEpSquare = cTo + 16 * g_iBehind[(GET_COLOR(pPiece))]; +#ifdef DEBUG + if (GET_COLOR(pPiece)) + { + ASSERT(cEpSquare == (cTo + 16)); + } + else + { + ASSERT(cEpSquare == (cTo - 16)); + } +#endif + ASSERT(IS_PAWN(pos->rgSquare[cEpSquare].pPiece)); + ASSERT(OPPOSITE_COLORS(pPiece, pos->rgSquare[cEpSquare].pPiece)); + + // + // Logical OR replaced with bitwise for speed. + // + if (((SQUARE_IS_UNBLOCKED(cEpSquare)) | + (SQUARE_IS_UNBLOCKED(cFrom))) && + (IS_ON_BOARD(ExposesCheckEp(pos, cEpSquare, cFrom, cTo, xKing)))) + { + return(MOVE_FLAG_CHECKING); + } + } + + // + // No direct check + no exposed check = no check. + // + return(0); +} + + +static void FORCEINLINE +_AddNormalMove(IN MOVE_STACK *pStack, + IN POSITION *pos, + IN COOR cFrom, + IN COOR cTo, + IN PIECE pCap) +/** + +Routine description: + + Adds a move from the generator functions to the stack of generated + moves. + +Parameters: + + MOVE_STACK *pStack : the move stack + POSITION *pos : the board position + COOR cFrom : the move's from square + COOR cTo : the move's to square + PIECE pCap : what was captured (if anything) + +Return value: + + static void FORCEINLINE + +**/ +{ + PIECE pMoved = pos->rgSquare[cFrom].pPiece; + ULONG uPly = pStack->uPly; + MOVE_STACK_MOVE_VALUE_FLAGS *pMvf; + + ASSERT(pMoved); + ASSERT(GET_COLOR(pMoved) == pos->uToMove); + ASSERT(IS_ON_BOARD(cFrom)); + ASSERT(IS_ON_BOARD(cTo)); + + pMvf = &(pStack->mvf[pStack->uEnd[uPly]]); + pMvf->mv.uMove = MAKE_MOVE_WITH_NO_PROM_OR_FLAGS(cFrom, cTo, pMoved, pCap); + pStack->uEnd[uPly]++; + + ASSERT(pMvf->mv.uMove == MAKE_MOVE(cFrom, cTo, pMoved, pCap, 0, 0)); + ASSERT(SanityCheckMove(pos, pMvf->mv)); +} + + +static void FORCEINLINE +_AddEnPassant(IN MOVE_STACK *pStack, + IN POSITION *pos, + IN COOR cFrom, + IN COOR cTo) +/** + +Routine description: + + Add an en passant pawn capture to the move stack. + +Parameters: + + MOVE_STACK *pStack : the move stack + POSITION *pos : the board position + COOR cFrom : the from square + COOR cTo : the to square (and en passant square) + +Return value: + + static void + +**/ +{ + PIECE pMoved = BLACK_PAWN | pos->uToMove; + PIECE pCaptured = FLIP(pMoved); + ULONG uPly = pStack->uPly; + MOVE_STACK_MOVE_VALUE_FLAGS *pMvf; + + ASSERT(pCaptured == (BLACK_PAWN | (FLIP(pos->uToMove)))); + ASSERT(IS_ON_BOARD(cFrom)); + ASSERT(IS_ON_BOARD(cTo)); + ASSERT(RANK4(cFrom) || RANK5(cFrom)); + ASSERT(VALID_EP_SQUARE(cTo)); + ASSERT(IS_PAWN(pos->rgSquare[cFrom].pPiece)); + ASSERT(GET_COLOR(pos->rgSquare[cFrom].pPiece) == pos->uToMove); + + pMvf = &(pStack->mvf[pStack->uEnd[uPly]]); + pMvf->mv.uMove = + MAKE_MOVE(cFrom, cTo, pMoved, pCaptured, 0, MOVE_FLAG_SPECIAL); + pStack->uEnd[uPly]++; + + ASSERT(SanityCheckMove(pos, pMvf->mv)); +} + + +static void FORCEINLINE +_AddCastle(IN MOVE_STACK *pStack, + IN POSITION *pos, + IN COOR cFrom, + IN COOR cTo) +/** + +Routine description: + + Add a castle move to the move stack. + +Parameters: + + MOVE_STACK *pStack, + POSITION *pos, + COOR cFrom, + COOR cTo + +Return value: + + static void FORCEINLINE + +**/ +{ + PIECE pMoved = BLACK_KING | pos->uToMove; + ULONG uPly = pStack->uPly; + MOVE_STACK_MOVE_VALUE_FLAGS *pMvf; + + ASSERT(IS_ON_BOARD(cFrom)); + ASSERT(IS_ON_BOARD(cTo)); + ASSERT((E1 == cFrom) || (E8 == cFrom)); + ASSERT(IS_KING(pos->rgSquare[cFrom].pPiece)); + ASSERT(GET_COLOR(pos->rgSquare[cFrom].pPiece) == pos->uToMove); + + pMvf = &(pStack->mvf[pStack->uEnd[uPly]]); + pMvf->mv.uMove = MAKE_MOVE(cFrom, cTo, pMoved, 0, 0, MOVE_FLAG_SPECIAL); + pStack->uEnd[uPly]++; + + ASSERT(SanityCheckMove(pos, pMvf->mv)); +} + + +static void FORCEINLINE +_AddPromote(IN MOVE_STACK *pStack, + IN POSITION *pos, + IN COOR cFrom, + IN COOR cTo) +/** + +Routine description: + + Adds a pawn promotion (set of) moves to the move stack. This can + be a capture-promotion or non-capture promotion. This function + pushes several moves onto the move stack, one for each possible + promotion target. + +Parameters: + + MOVE_STACK *pStack : the move stack + POSITION *pos : the board position + COOR cFrom : the move's from square + COOR cTo : the move's to square + +Return value: + + static void + +**/ +{ + PIECE pMoved = BLACK_PAWN | pos->uToMove; + PIECE pCaptured = pos->rgSquare[cTo].pPiece; + ULONG uPly = pStack->uPly; + MOVE_STACK_MOVE_VALUE_FLAGS *pMvf; + ULONG u; + +#define ARRAY_LENGTH_TARG (4) + const static PIECE pTarg[ARRAY_LENGTH_TARG] = { BLACK_QUEEN, + BLACK_ROOK, + BLACK_BISHOP, + BLACK_KNIGHT }; + + ASSERT(IS_ON_BOARD(cFrom)); + ASSERT(IS_ON_BOARD(cTo)); + ASSERT(RANK1(cTo) || RANK8(cTo)); + ASSERT(RANK7(cFrom) || RANK2(cFrom)); + ASSERT(ARRAY_LENGTH(pTarg) == ARRAY_LENGTH_TARG); + ASSERT(IS_PAWN(pos->rgSquare[cFrom].pPiece)); + + for (u = 0; u < ARRAY_LENGTH_TARG; u++) + { + pMvf = &(pStack->mvf[pStack->uEnd[uPly]]); + pMvf->mv.uMove = MAKE_MOVE(cFrom, cTo, pMoved, pCaptured, + pTarg[u] | pos->uToMove, MOVE_FLAG_SPECIAL); + pStack->uEnd[uPly]++; + ASSERT(SanityCheckMove(pos, pMvf->mv)); + } +#undef ARRAY_LENGTH_TARG +} + + +static void FORCEINLINE +_AddDoubleJump(IN MOVE_STACK *pStack, + IN POSITION *pos, + IN COOR cFrom, + IN COOR cTo) +/** + +Routine description: + + This function adds a pawn double jump to the move stack. + +Parameters: + + MOVE_STACK *pStack : the move stack + POSITION *pos : the board position + COOR cFrom : the move's from square + COOR cTo : the move's to square + +Return value: + + static void + +**/ +{ + PIECE pMoved = BLACK_PAWN | pos->uToMove; + ULONG uPly = pStack->uPly; + MOVE_STACK_MOVE_VALUE_FLAGS *pMvf; + + ASSERT(IS_ON_BOARD(cFrom)); + ASSERT(IS_ON_BOARD(cTo)); + ASSERT(RANK2(cFrom) || RANK7(cFrom)); + ASSERT(RANK4(cTo) || RANK5(cTo)); + ASSERT(IS_PAWN(pos->rgSquare[cFrom].pPiece)); + + pMvf = &(pStack->mvf[pStack->uEnd[uPly]]); + pMvf->mv.uMove = MAKE_MOVE(cFrom, cTo, pMoved, 0, 0, MOVE_FLAG_SPECIAL); + pStack->uEnd[uPly]++; + + ASSERT(SanityCheckMove(pos, pMvf->mv)); +} + + +const INT g_iNDeltas[] = { + -33, -31, -18, -14, +14, +18, +31, +33, 0 }; + +void +GenerateKnight(IN MOVE_STACK *pStack, + IN POSITION *pos, + IN COOR cKnight) +/** + +Routine description: + + This function is called by GenerateMoves' JumpTable. Its job + is to generate and push pseudo-legal knight moves for the + knight sitting on square cKnight. + +Parameters: + + MOVE_STACK *pStack : the move stack + POSITION *pos : the board position + COOR cKnight : the knight's location + +Return value: + + void + +**/ +{ + COOR c; + ULONG u = 0; + PIECE p; + + ASSERT(IS_KNIGHT(pos->rgSquare[cKnight].pPiece)); + ASSERT(GET_COLOR(pos->rgSquare[cKnight].pPiece) == pos->uToMove); + ASSERT(g_iNDeltas[u] != 0); + + do + { + c = cKnight + g_iNDeltas[u]; + u++; + if (IS_ON_BOARD(c)) + { + p = pos->rgSquare[c].pPiece; + + // + // This logical OR replaced with bitwise OR; the effect is + // the same the the bitwise is marginally faster. + // + if (IS_EMPTY(p) | (OPPOSITE_COLORS(p, pos->uToMove))) + { + _AddNormalMove(pStack, pos, cKnight, c, p); + } + } + } + while(0 != g_iNDeltas[u]); +} + +void +GenerateWhiteKnight(IN MOVE_STACK *pStack, + IN POSITION *pos, + IN COOR cKnight) +{ + COOR c; + ULONG u = 0; + PIECE p; + + ASSERT(IS_KNIGHT(pos->rgSquare[cKnight].pPiece)); + ASSERT(GET_COLOR(pos->rgSquare[cKnight].pPiece) == pos->uToMove); + ASSERT(g_iNDeltas[u] != 0); + + do + { + c = cKnight + g_iNDeltas[u]; + u++; + if (IS_ON_BOARD(c)) + { + p = pos->rgSquare[c].pPiece; + + // + // Note: this test covers empty squares also -- it is just + // testing that the low order bit (color bit) of p is zero + // which is true for black pieces and empty squares. This + // is done for speed over readability. + // + if (GET_COLOR(p) == BLACK) + { + ASSERT(IS_EMPTY(p) || (GET_COLOR(p) == BLACK)); + _AddNormalMove(pStack, pos, cKnight, c, p); + } + } + } + while(0 != g_iNDeltas[u]); +} + +// +// These logical AND/ORs replaced with bitwise AND/OR; the effect is +// the same the the bitwise is marginally faster. +// +#define BLOCKS_THE_CHECK(sq) \ + ((iAttackDelta != 0) & \ + (iAttackDelta == DIRECTION_BETWEEN_SQUARES(cAttacker, (sq))) & \ + (((cAttacker > cKing) & ((sq) > cKing)) | \ + ((cAttacker < cKing) & ((sq) < cKing)))) + +void +SaveMeKnight(IN MOVE_STACK *pStack, + IN POSITION *pos, + IN COOR cKnight, + IN COOR cKing, + IN COOR cAttacker) +/** + +Routine description: + + This routine is called by GenerateEscapes' JumpTable. Its job is + to generate moves by the knight on square cKnight that alleviate + check to the king on square cKing. The (lone) piece attacking the + king is on square cAttacker. + +Parameters: + + MOVE_STACK *pStack : the move stack + POSITION *pos : the board position + COOR cKnight : the location of the knight + COOR cKing : the location of the friendly king + COOR cAttacker : the location of the checking piece + +Return value: + + void + +**/ +{ + COOR c, cExposed; + int iAttackDelta = DIRECTION_BETWEEN_SQUARES(cAttacker, cKing); + ULONG u = 0; + PIECE p; + + ASSERT(InCheck(pos, pos->uToMove)); + ASSERT(IS_KNIGHT(pos->rgSquare[cKnight].pPiece)); + ASSERT(GET_COLOR(pos->rgSquare[cKnight].pPiece) == pos->uToMove); + ASSERT(GET_COLOR(pos->rgSquare[cKnight].pPiece) == + GET_COLOR(pos->rgSquare[cKing].pPiece)); + ASSERT(OPPOSITE_COLORS(pos->rgSquare[cAttacker].pPiece, + pos->rgSquare[cKing].pPiece)); + ASSERT(g_iNDeltas[u] != 0); + + do + { + c = cKnight + g_iNDeltas[u]; + u++; + if (IS_ON_BOARD(c)) + { + if ((c == cAttacker) || BLOCKS_THE_CHECK(c)) + { + cExposed = ExposesCheck(pos, cKnight, cKing); + if (!IS_ON_BOARD(cExposed) || (cExposed == c)) + { + p = pos->rgSquare[c].pPiece; + ASSERT(!p || + OPPOSITE_COLORS(p, pos->rgSquare[cKnight].pPiece)); + ASSERT(!p || (c == cAttacker)); + _AddNormalMove(pStack, pos, cKnight, c, p); + } + } + } + } + while(0 != g_iNDeltas[u]); +} + + +const INT g_iBDeltas[] = { + -17, -15, +15, +17, 0 }; + +void +GenerateBishop(IN MOVE_STACK *pStack, + IN POSITION *pos, + IN COOR cBishop) +/** + +Routine description: + + This routine is called by GenerateMoves' JumpTable to generate + pseudo-legal bishop moves by the piece at cBishop. + +Parameters: + + MOVE_STACK *pStack : the move stack + POSITION *pos : the board position + COOR cBishop : the bishop location + +Return value: + + void + +**/ +{ + COOR c; + PIECE p; + + ASSERT(IS_BISHOP(pos->rgSquare[cBishop].pPiece)); + ASSERT(GET_COLOR(pos->rgSquare[cBishop].pPiece) == pos->uToMove); + + // + // Note: manually unrolled loop + // + c = cBishop - 17; + while(IS_ON_BOARD(c)) + { + p = pos->rgSquare[c].pPiece; + if (IS_EMPTY(p)) + { + _AddNormalMove(pStack, pos, cBishop, c, 0); + } + else + { + if (OPPOSITE_COLORS(p, pos->uToMove)) + { + _AddNormalMove(pStack, pos, cBishop, c, p); + } + break; + } + c += -17; + } + + c = cBishop - 15; + while(IS_ON_BOARD(c)) + { + p = pos->rgSquare[c].pPiece; + if (IS_EMPTY(p)) + { + _AddNormalMove(pStack, pos, cBishop, c, 0); + } + else + { + if (OPPOSITE_COLORS(p, pos->uToMove)) + { + _AddNormalMove(pStack, pos, cBishop, c, p); + } + break; + } + c += -15; + } + + c = cBishop + 15; + while(IS_ON_BOARD(c)) + { + p = pos->rgSquare[c].pPiece; + if (IS_EMPTY(p)) + { + _AddNormalMove(pStack, pos, cBishop, c, 0); + } + else + { + if (OPPOSITE_COLORS(p, pos->uToMove)) + { + _AddNormalMove(pStack, pos, cBishop, c, p); + } + break; + } + c += 15; + } + + c = cBishop + 17; + while(IS_ON_BOARD(c)) + { + p = pos->rgSquare[c].pPiece; + if (IS_EMPTY(p)) + { + _AddNormalMove(pStack, pos, cBishop, c, 0); + } + else + { + if (OPPOSITE_COLORS(p, pos->uToMove)) + { + _AddNormalMove(pStack, pos, cBishop, c, p); + } + break; + } + c += 17; + } +} + + +void +SaveMeBishop(IN MOVE_STACK *pStack, + IN POSITION *pos, + IN COOR cBishop, + IN COOR cKing, + IN COOR cAttacker) +/** + +Routine description: + + This routine is called by GenerateEscapes' JumpTable in order to + generate moves by the bishop at cBishop to alleviate check on its + friendly king (at cKing) which is being checked by a piece at + cAttacker. + +Parameters: + + MOVE_STACK *pStack : the move stack + POSITION *pos : the board position + COOR cBishop : the bishop's location + COOR cKing : the friendly king's location + COOR cAttacker : the checking piece's location + +Return value: + + void + +**/ +{ + int iAttackDelta = DIRECTION_BETWEEN_SQUARES(cAttacker, cKing); + COOR c; + COOR cExposed; + ULONG u = 0; + PIECE p; + + ASSERT(InCheck(pos, pos->uToMove)); + ASSERT(IS_BISHOP(pos->rgSquare[cBishop].pPiece)); + ASSERT(GET_COLOR(pos->rgSquare[cBishop].pPiece) == pos->uToMove); + ASSERT(GET_COLOR(pos->rgSquare[cBishop].pPiece) == + GET_COLOR(pos->rgSquare[cKing].pPiece)); + ASSERT(OPPOSITE_COLORS(pos->rgSquare[cAttacker].pPiece, + pos->rgSquare[cKing].pPiece)); + ASSERT(g_iBDeltas[u] != 0); + + do + { + c = cBishop + g_iBDeltas[u]; + while(IS_ON_BOARD(c)) + { + p = pos->rgSquare[c].pPiece; + if ((c == cAttacker) || BLOCKS_THE_CHECK(c)) + { + ASSERT(!p || + OPPOSITE_COLORS(p, pos->rgSquare[cBishop].pPiece)); + ASSERT(!p || (c == cAttacker)); + cExposed = ExposesCheck(pos, cBishop, cKing); + if (!IS_ON_BOARD(cExposed) || (cExposed == c)) + { + _AddNormalMove(pStack, pos, cBishop, c, p); + break; + } + } + else if (!IS_EMPTY(p)) + { + break; + } + c += g_iBDeltas[u]; + } + u++; + } + while(0 != g_iBDeltas[u]); +} + + +const INT g_iRDeltas[] = { + -1, +1, +16, -16, 0 }; + + +void +GenerateRook(IN MOVE_STACK *pStack, + IN POSITION *pos, + IN COOR cRook) +/** + +Routine description: + + This routine is called by GenerateMoves' JumpTable in order to + generate pseudo-legal moves for the rook at position cRook. + +Parameters: + + MOVE_STACK *pStack : the move stack + POSITION *pos : the board position + COOR cRook : the rook's location + +Return value: + + void + +**/ +{ + COOR c; + PIECE p; + + ASSERT(IS_ROOK(pos->rgSquare[cRook].pPiece)); + ASSERT(GET_COLOR(pos->rgSquare[cRook].pPiece) == pos->uToMove); + + // + // Note: manually unrolled loop + // + c = cRook - 1; + while(IS_ON_BOARD(c)) + { + p = pos->rgSquare[c].pPiece; + if (IS_EMPTY(p)) + { + _AddNormalMove(pStack, pos, cRook, c, 0); + } + else + { + if (OPPOSITE_COLORS(p, pos->uToMove)) + { + _AddNormalMove(pStack, pos, cRook, c, p); + } + break; + } + c += -1; + } + + c = cRook + 1; + while(IS_ON_BOARD(c)) + { + p = pos->rgSquare[c].pPiece; + if (IS_EMPTY(p)) + { + _AddNormalMove(pStack, pos, cRook, c, 0); + } + else + { + if (OPPOSITE_COLORS(p, pos->uToMove)) + { + _AddNormalMove(pStack, pos, cRook, c, p); + } + break; + } + c += 1; + } + + c = cRook + 16; + while(IS_ON_BOARD(c)) + { + p = pos->rgSquare[c].pPiece; + if (IS_EMPTY(p)) + { + _AddNormalMove(pStack, pos, cRook, c, 0); + } + else + { + if (OPPOSITE_COLORS(p, pos->uToMove)) + { + _AddNormalMove(pStack, pos, cRook, c, p); + } + break; + } + c += 16; + } + + c = cRook - 16; + while(IS_ON_BOARD(c)) + { + p = pos->rgSquare[c].pPiece; + if (IS_EMPTY(p)) + { + _AddNormalMove(pStack, pos, cRook, c, 0); + } + else + { + if (OPPOSITE_COLORS(p, pos->uToMove)) + { + _AddNormalMove(pStack, pos, cRook, c, p); + } + break; + } + c += -16; + } +} + +void +SaveMeRook(IN MOVE_STACK *pStack, + IN POSITION *pos, + IN COOR cRook, + IN COOR cKing, + IN COOR cAttacker) +/** + +Routine description: + + This routine is called by GenerateEscapes' JumpTable in order to + generate moves by the rook at location cRook that alleviate check + to the king at cKing. The lone checking piece is at cAttacker. + +Parameters: + + MOVE_STACK *pStack : the move stack + POSITION *pos : the board position + COOR cRook : the rook's location + COOR cKing : the king's location + COOR cAttacker : the checker's location + +Return value: + + void + +**/ +{ + int iAttackDelta = DIRECTION_BETWEEN_SQUARES(cAttacker, cKing); + COOR c; + COOR cExposed; + ULONG u = 0; + PIECE p; + + ASSERT(InCheck(pos, pos->uToMove)); + ASSERT(IS_ROOK(pos->rgSquare[cRook].pPiece)); + ASSERT(GET_COLOR(pos->rgSquare[cRook].pPiece) == pos->uToMove); + ASSERT(GET_COLOR(pos->rgSquare[cRook].pPiece) == pos->uToMove); + ASSERT(GET_COLOR(pos->rgSquare[cRook].pPiece) == + GET_COLOR(pos->rgSquare[cKing].pPiece)); + ASSERT(OPPOSITE_COLORS(pos->rgSquare[cAttacker].pPiece, + pos->rgSquare[cKing].pPiece)); + ASSERT(g_iRDeltas[u] != 0); + + do + { + c = cRook + g_iRDeltas[u]; + while(IS_ON_BOARD(c)) + { + p = pos->rgSquare[c].pPiece; + if ((c == cAttacker) || BLOCKS_THE_CHECK(c)) + { + ASSERT(!p || + OPPOSITE_COLORS(p, pos->rgSquare[cRook].pPiece)); + ASSERT(!p || (c == cAttacker)); + cExposed = ExposesCheck(pos, cRook, cKing); + if (!IS_ON_BOARD(cExposed) || (cExposed == c)) + { + _AddNormalMove(pStack, pos, cRook, c, p); + break; + } + } + else if (!IS_EMPTY(p)) + { + break; + } + c += g_iRDeltas[u]; + } + u++; + } + while(0 != g_iRDeltas[u]); +} + + +void +GenerateQueen(IN MOVE_STACK *pStack, + IN POSITION *pos, + IN COOR cQueen) +/** + +Routine description: + + This routine is called by GenerateMoves' JumpTable in order to + generate pseudo-legal moves for the queen at position cQueen. + +Parameters: + + MOVE_STACK *pStack : the move stack + POSITION *pos : the board position + COOR cQueen : the queen's location + +Return value: + + void + +**/ +{ + COOR c; + ULONG u = 0; + PIECE p; + + ASSERT(IS_QUEEN(pos->rgSquare[cQueen].pPiece)); + ASSERT(GET_COLOR(pos->rgSquare[cQueen].pPiece) == pos->uToMove); + ASSERT(g_iQKDeltas[u] != 0); + + do + { + c = cQueen + g_iQKDeltas[u]; + while(IS_ON_BOARD(c)) + { + p = pos->rgSquare[c].pPiece; + if (IS_EMPTY(p)) + { + _AddNormalMove(pStack, pos, cQueen, c, 0); + } + else + { + if (OPPOSITE_COLORS(p, pos->uToMove)) + { + _AddNormalMove(pStack, pos, cQueen, c, p); + } + break; + } + c += g_iQKDeltas[u]; + } + u++; + } + while(0 != g_iQKDeltas[u]); +} + + +void +SaveMeQueen(IN MOVE_STACK *pStack, + IN POSITION *pos, + IN COOR cQueen, + IN COOR cKing, + IN COOR cAttacker) +/** + +Routine description: + + This routine is called by code in GenerateEscapes in order to + generate moves by the queen at square cQueen that alleviate check + on the friendly king at square cKing. The lone enemy piece that + is checking the king is sitting on square cAttacker. + +Parameters: + + MOVE_STACK *pStack : the move stack + POSITION *pos : the board position + COOR cQueen : the queen's location + COOR cKing : the friendly king's location + COOR cAttacker : the attacker's location + +Return value: + + void + +**/ +{ + COOR c; + COOR cExposed; + int iAttackDelta = DIRECTION_BETWEEN_SQUARES(cAttacker, cKing); + ULONG u = 0; + PIECE p; + + ASSERT(InCheck(pos, pos->uToMove)); + ASSERT(IS_QUEEN(pos->rgSquare[cQueen].pPiece)); + ASSERT(GET_COLOR(pos->rgSquare[cQueen].pPiece) == pos->uToMove); + ASSERT(GET_COLOR(pos->rgSquare[cQueen].pPiece) == pos->uToMove); + ASSERT(GET_COLOR(pos->rgSquare[cQueen].pPiece) == + GET_COLOR(pos->rgSquare[cKing].pPiece)); + ASSERT(OPPOSITE_COLORS(pos->rgSquare[cAttacker].pPiece, + pos->rgSquare[cKing].pPiece)); + ASSERT(g_iQKDeltas[u] != 0); + + do + { + c = cQueen + g_iQKDeltas[u]; + while(IS_ON_BOARD(c)) + { + p = pos->rgSquare[c].pPiece; + if ((c == cAttacker) || BLOCKS_THE_CHECK(c)) + { + ASSERT(!p || + OPPOSITE_COLORS(p, pos->rgSquare[cQueen].pPiece)); + ASSERT(!p || (c == cAttacker)); + cExposed = ExposesCheck(pos, cQueen, cKing); + if (!IS_ON_BOARD(cExposed) || (cExposed == c)) + { + _AddNormalMove(pStack, pos, cQueen, c, p); + break; + } + } + else if (!IS_EMPTY(p)) + { + break; + } + c += g_iQKDeltas[u]; + } + u++; + } + while(0 != g_iQKDeltas[u]); +} + +void +GenerateBlackKing(IN MOVE_STACK *pStack, + IN POSITION *pos, + IN COOR cKing) +/** + +Routine description: + + This function is called by GenerateMoves in order to generate + pseudo-legal moves for the black king at square cKing. Note: this + function often generates illegal castling moves and relies on the + MakeMove code to decide about the legality of the castle. + +Parameters: + + MOVE_STACK *pStack : the move stack + POSITION *pos : the board position + COOR cKing : the king location + +Return value: + + void + +**/ +{ + COOR c; + ULONG u = 0; + PIECE p; + + ASSERT(IS_KING(pos->rgSquare[cKing].pPiece)); + ASSERT(GET_COLOR(pos->rgSquare[cKing].pPiece) == pos->uToMove); + ASSERT(g_iQKDeltas[u] != 0); + + do + { + c = cKing + g_iQKDeltas[u]; + u++; + if (IS_ON_BOARD(c)) + { + p = pos->rgSquare[c].pPiece; + + // + // This logical OR replaced with bitwise OR; the effect is + // the same the the bitwise is marginally faster. + // + if (IS_EMPTY(p) | (GET_COLOR(p))) + { + _AddNormalMove(pStack, pos, cKing, c, p); + } + } + } + while(0 != g_iQKDeltas[u]); + + if ((pos->bvCastleInfo & BLACK_CAN_CASTLE) == 0) return; +#ifdef DEBUG + p = pos->rgSquare[E8].pPiece; + ASSERT(IS_KING(p)); + ASSERT(cKing == E8); +#endif + + // + // Note: no castling through check is enforced at the time the + // move is played. This is a "pseudo-legal" move when generated. + // + if ((pos->bvCastleInfo & CASTLE_BLACK_SHORT) && + (IS_EMPTY(pos->rgSquare[G8].pPiece)) && + (IS_EMPTY(pos->rgSquare[F8].pPiece))) + { + ASSERT(pos->rgSquare[H8].pPiece == BLACK_ROOK); + _AddCastle(pStack, pos, E8, G8); + } + + if ((pos->bvCastleInfo & CASTLE_BLACK_LONG) && + (IS_EMPTY(pos->rgSquare[C8].pPiece)) && + (IS_EMPTY(pos->rgSquare[D8].pPiece)) && + (IS_EMPTY(pos->rgSquare[B8].pPiece))) + { + ASSERT(pos->rgSquare[A8].pPiece == BLACK_ROOK); + _AddCastle(pStack, pos, E8, C8); + } +} + +// +// N.B. There is no SaveYourselfBlackKing or SaveYourselfWhiteKing +// because this functionality is built into phase 1 of +// GenerateEscapes. +// + +void +GenerateWhiteKing(IN MOVE_STACK *pStack, + IN POSITION *pos, + IN COOR cKing) +/** + +Routine description: + + This function is called by GenerateMoves in order to generate + pseudo-legal king moves by the white king at square cKing. Note: + it often generates illegal castling moves and relies on the code + in MakeMove to determine the legality of castles. + +Parameters: + + MOVE_STACK *pStack : the move stack + POSITION *pos : the board position + COOR cKing : the king location + +Return value: + + void + +**/ +{ + COOR c; + ULONG u = 0; + PIECE p; + + ASSERT(IS_KING(pos->rgSquare[cKing].pPiece)); + ASSERT(GET_COLOR(pos->rgSquare[cKing].pPiece) == pos->uToMove); + ASSERT(g_iQKDeltas[u] != 0); + + do + { + c = cKing + g_iQKDeltas[u]; + u++; + if (IS_ON_BOARD(c)) + { + p = pos->rgSquare[c].pPiece; + + // + // Note: this test covers empty squares also -- it is just + // testing that the low order bit (color bit) of p is zero + // which is true for black pieces and empty squares. This + // is done for speed over readability. + // + if (GET_COLOR(p) == BLACK) + { + ASSERT(IS_EMPTY(p) || (GET_COLOR(p) == BLACK)); + _AddNormalMove(pStack, pos, cKing, c, p); + } + } + } + while(0 != g_iQKDeltas[u]); + + if ((pos->bvCastleInfo & WHITE_CAN_CASTLE) == 0) return; +#ifdef DEBUG + p = pos->rgSquare[E1].pPiece; + ASSERT(IS_KING(p)); + ASSERT(cKing == E1); +#endif + + // + // Note: no castling through check is enforced at the time the + // move is played. This is a "pseudo-legal" move when generated. + // + if ((pos->bvCastleInfo & CASTLE_WHITE_SHORT) && + (IS_EMPTY(pos->rgSquare[G1].pPiece)) && + (IS_EMPTY(pos->rgSquare[F1].pPiece))) + { + ASSERT(pos->rgSquare[H1].pPiece == WHITE_ROOK); + _AddCastle(pStack, pos, E1, G1); + } + + if ((pos->bvCastleInfo & CASTLE_WHITE_LONG) && + (IS_EMPTY(pos->rgSquare[C1].pPiece)) && + (IS_EMPTY(pos->rgSquare[B1].pPiece)) && + (IS_EMPTY(pos->rgSquare[D1].pPiece))) + { + ASSERT(pos->rgSquare[A1].pPiece == WHITE_ROOK); + _AddCastle(pStack, pos, E1, C1); + } +} + + +void +GenerateWhitePawn(IN MOVE_STACK *pStack, + IN POSITION *pos, + IN COOR cPawn) +/** + +Routine description: + + This function is called by GenerateMoves in order to generate + pseudo-legal pawn moves by the pawn at cPawn. It handles + en passant captures, double jumps, promotions, etc... + +Parameters: + + MOVE_STACK *pStack : the move stack + POSITION *pos : the board position + COOR cPawn : the pawn's location + +Return value: + + void + +**/ +{ + ULONG uRank = RANK(cPawn); + PIECE p; + COOR cTo; + + ASSERT(IS_PAWN(pos->rgSquare[cPawn].pPiece)); + ASSERT(GET_COLOR(pos->rgSquare[cPawn].pPiece) == pos->uToMove); + ASSERT((RANK(cPawn) >= 2) && (RANK(cPawn) <= 7)); + + if (uRank != 7) + { + cTo = cPawn - 16; + if (IS_EMPTY(pos->rgSquare[cTo].pPiece)) + { + _AddNormalMove(pStack, pos, cPawn, cTo, 0); + if (uRank == 2) + { + cTo = cPawn - 32; + if (IS_EMPTY(pos->rgSquare[cTo].pPiece)) + { + _AddDoubleJump(pStack, pos, cPawn, cTo); + } + } + } + cTo = cPawn - 15; + if (IS_ON_BOARD(cTo)) + { + if (cTo == pos->cEpSquare) + { + _AddEnPassant(pStack, pos, cPawn, cTo); + } + p = pos->rgSquare[cTo].pPiece; + + // + // This logical AND replaced with bitwise AND; the effect + // is the same the the bitwise is marginally faster. + // + if (!IS_EMPTY(p) & (GET_COLOR(p) == BLACK)) + { + _AddNormalMove(pStack, pos, cPawn, cTo, p); + } + } + cTo = cPawn - 17; + if (IS_ON_BOARD(cTo)) + { + if (cTo == pos->cEpSquare) + { + _AddEnPassant(pStack, pos, cPawn, cTo); + } + p = pos->rgSquare[cTo].pPiece; + + // + // This logical AND replaced with bitwise AND; the effect + // is the same the the bitwise is marginally faster. + // + if (!IS_EMPTY(p) & (GET_COLOR(p) == BLACK)) + { + _AddNormalMove(pStack, pos, cPawn, cTo, p); + } + } + } + else + { + ASSERT(RANK7(cPawn)); + cTo = cPawn - 16; + if (IS_EMPTY(pos->rgSquare[cTo].pPiece)) + { + _AddPromote(pStack, pos, cPawn, cTo); + } + cTo = cPawn - 15; + if (IS_ON_BOARD(cTo)) + { + p = pos->rgSquare[cTo].pPiece; + + // + // This logical AND replaced with bitwise AND; the effect + // is the same the the bitwise is marginally faster. + // + if (!IS_EMPTY(p) & (GET_COLOR(p) == BLACK)) + { + _AddPromote(pStack, pos, cPawn, cTo); + } + } + cTo = cPawn - 17; + if (IS_ON_BOARD(cTo)) + { + p = pos->rgSquare[cTo].pPiece; + + // + // This logical AND replaced with bitwise AND; the effect + // is the same the the bitwise is marginally faster. + // + if (!IS_EMPTY(p) & (GET_COLOR(p) == BLACK)) + { + _AddPromote(pStack, pos, cPawn, cTo); + } + } + } +} + + +void +SaveMeWhitePawn(IN MOVE_STACK *pStack, + IN POSITION *pos, + IN COOR cPawn, + IN COOR cKing, + IN COOR cAttacker) +/** + +Routine description: + + This function is called by the GenerateEscapes code in order to + ask for a pawn's help in alleviating check on the king at square + cKing. The lone attacker to said king is on square cAttacker. + +Parameters: + + MOVE_STACK *pStack : the move stack + POSITION *pos : the board position + COOR cPawn : the pawn's location + COOR cKing : the friendly king's location + COOR cAttacker : the location of the lone checker to the king + +Return value: + + void + +**/ +{ + ULONG uRank = RANK(cPawn); + PIECE p; + COOR cTo; + COOR cExposed; + int iAttackDelta = DIRECTION_BETWEEN_SQUARES(cAttacker, cKing); + + ASSERT(InCheck(pos, pos->uToMove)); + ASSERT(IS_PAWN(pos->rgSquare[cPawn].pPiece)); + ASSERT(GET_COLOR(pos->rgSquare[cPawn].pPiece) == WHITE); + ASSERT(GET_COLOR(pos->rgSquare[cPawn].pPiece) == pos->uToMove); + ASSERT(GET_COLOR(pos->rgSquare[cPawn].pPiece) == pos->uToMove); + ASSERT(GET_COLOR(pos->rgSquare[cPawn].pPiece) == + GET_COLOR(pos->rgSquare[cKing].pPiece)); + ASSERT(OPPOSITE_COLORS(pos->rgSquare[cAttacker].pPiece, + pos->rgSquare[cKing].pPiece)); + ASSERT((RANK(cPawn) >= 2) && (RANK(cPawn) <= 7)); + + if (uRank != 7) + { + cTo = cPawn - 16; + if (IS_EMPTY(pos->rgSquare[cTo].pPiece)) + { + if (BLOCKS_THE_CHECK(cTo) && + !IS_ON_BOARD(ExposesCheck(pos, cPawn, cKing))) + { + _AddNormalMove(pStack, pos, cPawn, cTo, 0); + } + + if (uRank == 2) + { + cTo = cPawn - 32; + if (IS_EMPTY(pos->rgSquare[cTo].pPiece) && + BLOCKS_THE_CHECK(cTo) && + !IS_ON_BOARD(ExposesCheck(pos, cPawn, cKing))) + { + _AddDoubleJump(pStack, pos, cPawn, cTo); + } + } + } + + cTo = cPawn - 15; + if (cTo == cAttacker) + { + cExposed = ExposesCheck(pos, cPawn, cKing); + if (!IS_ON_BOARD(cExposed) || (cExposed == cAttacker)) + { + p = pos->rgSquare[cTo].pPiece; + ASSERT(!IS_EMPTY(p)); + ASSERT(GET_COLOR(p) == BLACK); + ASSERT(IS_ON_BOARD(cTo)); + _AddNormalMove(pStack, pos, cPawn, cTo, p); + } + } + + // + // N.B. There is no possible way to block check with an + // en-passant capture because by definition the last move made + // by the other side was the pawn double jump. So only handle + // if the double jumping enemy pawn is the attacker and we can + // kill it en passant. + // + if ((cTo == pos->cEpSquare) && (cAttacker == cTo + 16)) + { + _AddEnPassant(pStack, pos, cPawn, cTo); + } + + cTo = cPawn - 17; + if (cTo == cAttacker) + { + cExposed = ExposesCheck(pos, cPawn, cKing); + if (!IS_ON_BOARD(cExposed) || (cExposed == cAttacker)) + { + p = pos->rgSquare[cTo].pPiece; + ASSERT(!IS_EMPTY(p)); + ASSERT(GET_COLOR(p) == BLACK); + ASSERT(IS_ON_BOARD(cTo)); + _AddNormalMove(pStack, pos, cPawn, cTo, p); + } + } + if ((cTo == pos->cEpSquare) && (cAttacker == cTo + 16)) + { + _AddEnPassant(pStack, pos, cPawn, cTo); + } + } + else + { + ASSERT(RANK7(cPawn)); + cTo = cPawn - 16; + if (BLOCKS_THE_CHECK(cTo) && IS_EMPTY(pos->rgSquare[cTo].pPiece)) + { + _AddPromote(pStack, pos, cPawn, cTo); + } + + cTo = cPawn - 15; + if (cTo == cAttacker) + { + cExposed = ExposesCheck(pos, cPawn, cKing); + if (!IS_ON_BOARD(cExposed) || (cExposed == cAttacker)) + { + p = pos->rgSquare[cTo].pPiece; + ASSERT(!IS_EMPTY(p)); + ASSERT(GET_COLOR(p) == BLACK); + ASSERT(IS_ON_BOARD(cTo)); + _AddPromote(pStack, pos, cPawn, cTo); + } + } + + cTo = cPawn - 17; + if (cTo == cAttacker) + { + cExposed = ExposesCheck(pos, cPawn, cKing); + if (!IS_ON_BOARD(cExposed) || (cExposed == cAttacker)) + { + p = pos->rgSquare[cTo].pPiece; + ASSERT(!IS_EMPTY(p)); + ASSERT(GET_COLOR(p) == BLACK); + ASSERT(IS_ON_BOARD(cTo)); + _AddPromote(pStack, pos, cPawn, cTo); + } + } + } +} + + +void +GenerateBlackPawn(IN MOVE_STACK *pStack, + IN POSITION *pos, + IN COOR cPawn) +/** + +Routine description: + + This code is called by GenerateMoves in order to handle move + generation for the black pawn on square cPawn. It handles + en passant captures, double jumps, and promotion. + +Parameters: + + MOVE_STACK *pStack : the move stack + POSITION *pos : the position + COOR cPawn : the pawn location + +Return value: + + void + +**/ +{ + ULONG uRank = RANK(cPawn); + PIECE p; + COOR cTo; + + ASSERT(IS_PAWN(pos->rgSquare[cPawn].pPiece)); + ASSERT(GET_COLOR(pos->rgSquare[cPawn].pPiece) == pos->uToMove); + ASSERT((RANK(cPawn) >= 2) && (RANK(cPawn) <= 7)); + + if (uRank != 2) + { + cTo = cPawn + 16; + if (IS_EMPTY(pos->rgSquare[cTo].pPiece)) + { + _AddNormalMove(pStack, pos, cPawn, cTo, 0); + if (uRank == 7) + { + cTo = cPawn + 32; + if (IS_EMPTY(pos->rgSquare[cTo].pPiece)) + { + _AddDoubleJump(pStack, pos, cPawn, cTo); + } + } + } + cTo = cPawn + 15; + if (IS_ON_BOARD(cTo)) + { + if (cTo == pos->cEpSquare) + { + _AddEnPassant(pStack, pos, cPawn, cTo); + } + p = pos->rgSquare[cTo].pPiece; + + // + // This logical AND replaced with bitwise AND; the effect + // is the same the the bitwise is marginally faster. + // + if (!IS_EMPTY(p) & (GET_COLOR(p))) + { + _AddNormalMove(pStack, pos, cPawn, cTo, p); + } + } + cTo = cPawn + 17; + if (IS_ON_BOARD(cTo)) + { + if (cTo == pos->cEpSquare) + { + _AddEnPassant(pStack, pos, cPawn, cTo); + } + p = pos->rgSquare[cTo].pPiece; + + // + // This logical AND replaced with bitwise AND; the effect + // is the same the the bitwise is marginally faster. + // + if (!IS_EMPTY(p) & (GET_COLOR(p))) + { + _AddNormalMove(pStack, pos, cPawn, cTo, p); + } + } + } + else + { + ASSERT(RANK2(cPawn)); + cTo = cPawn + 16; + if (IS_EMPTY(pos->rgSquare[cTo].pPiece)) + { + _AddPromote(pStack, pos, cPawn, cTo); + } + cTo = cPawn + 15; + if (IS_ON_BOARD(cTo)) + { + p = pos->rgSquare[cTo].pPiece; + + // + // This logical AND replaced with bitwise AND; the effect + // is the same the the bitwise is marginally faster. + // + if (!IS_EMPTY(p) & (GET_COLOR(p))) + { + _AddPromote(pStack, pos, cPawn, cTo); + } + } + cTo = cPawn + 17; + if (IS_ON_BOARD(cTo)) + { + p = pos->rgSquare[cTo].pPiece; + + // + // This logical AND replaced with bitwise AND; the effect + // is the same the the bitwise is marginally faster. + // + if (!IS_EMPTY(p) & (GET_COLOR(p))) + { + _AddPromote(pStack, pos, cPawn, cTo); + } + } + } +} + + +void +SaveMeBlackPawn(IN MOVE_STACK *pStack, + IN POSITION *pos, + IN COOR cPawn, + IN COOR cKing, + IN COOR cAttacker) +/** + +Routine description: + + This code is called to ask for a black pawn's help in alleviating + check to its king. The pawn is on square cPawn. The friendly + king is on square cKing. The lone enemy piece attacking it is on + square cAttacker. + +Parameters: + + MOVE_STACK *pStack : the move stack + POSITION *pos : the board position + COOR cPawn : the pawn location + COOR cKing : the friendly king location + COOR cAttacker : the lone checker location + +Return value: + + void + +**/ +{ + ULONG uRank = RANK(cPawn); + PIECE p; + COOR cTo; + COOR cExposed; + int iAttackDelta = DIRECTION_BETWEEN_SQUARES(cAttacker, cKing); + + ASSERT(InCheck(pos, pos->uToMove)); + ASSERT(IS_PAWN(pos->rgSquare[cPawn].pPiece)); + ASSERT(GET_COLOR(pos->rgSquare[cPawn].pPiece) == BLACK); + ASSERT(GET_COLOR(pos->rgSquare[cPawn].pPiece) == pos->uToMove); + ASSERT(GET_COLOR(pos->rgSquare[cPawn].pPiece) == pos->uToMove); + ASSERT(GET_COLOR(pos->rgSquare[cPawn].pPiece) == + GET_COLOR(pos->rgSquare[cKing].pPiece)); + ASSERT(OPPOSITE_COLORS(pos->rgSquare[cAttacker].pPiece, + pos->rgSquare[cKing].pPiece)); + ASSERT((RANK(cPawn) >= 2) && (RANK(cPawn) <= 7)); + + if (uRank != 2) + { + cTo = cPawn + 16; + if (IS_EMPTY(pos->rgSquare[cTo].pPiece)) + { + if (BLOCKS_THE_CHECK(cTo) && + !IS_ON_BOARD(ExposesCheck(pos, cPawn, cKing))) + { + _AddNormalMove(pStack, pos, cPawn, cTo, 0); + } + + if (uRank == 7) + { + cTo = cPawn + 32; + if (IS_EMPTY(pos->rgSquare[cTo].pPiece) && + BLOCKS_THE_CHECK(cTo) && + !IS_ON_BOARD(ExposesCheck(pos, cPawn, cKing))) + { + _AddDoubleJump(pStack, pos, cPawn, cTo); + } + } + } + + cTo = cPawn + 15; + if (cTo == cAttacker) + { + cExposed = ExposesCheck(pos, cPawn, cKing); + if (!IS_ON_BOARD(cExposed) || (cExposed == cAttacker)) + { + p = pos->rgSquare[cTo].pPiece; + ASSERT(!IS_EMPTY(p)); + ASSERT(GET_COLOR(p) == WHITE); + ASSERT(IS_ON_BOARD(cTo)); + _AddNormalMove(pStack, pos, cPawn, cTo, p); + } + } + + // + // N.B. There is no possible way to block check with an + // en-passant capture because by definition the last move made + // by the other side was the pawn double jump. So only handle + // if the double jumping enemy pawn is the attacker and we can + // kill it en passant. + // + if ((cTo == pos->cEpSquare) && + (cAttacker == cTo - 16)) + { + _AddEnPassant(pStack, pos, cPawn, cTo); + } + + cTo = cPawn + 17; + if (cTo == cAttacker) + { + cExposed = ExposesCheck(pos, cPawn, cKing); + if (!IS_ON_BOARD(cExposed) || (cExposed == cAttacker)) + { + p = pos->rgSquare[cTo].pPiece; + ASSERT(!IS_EMPTY(p)); + ASSERT(GET_COLOR(p) == WHITE); + ASSERT(IS_ON_BOARD(cTo)); + _AddNormalMove(pStack, pos, cPawn, cTo, p); + } + } + if ((cTo == pos->cEpSquare) && + (cAttacker == cTo - 16)) + { + _AddEnPassant(pStack, pos, cPawn, cTo); + } + } + else + { + ASSERT(RANK2(cPawn)); + cTo = cPawn + 16; + if (BLOCKS_THE_CHECK(cTo) && + IS_EMPTY(pos->rgSquare[cTo].pPiece)) + { + _AddPromote(pStack, pos, cPawn, cTo); + } + + cTo = cPawn + 15; + if (cTo == cAttacker) + { + cExposed = ExposesCheck(pos, cPawn, cKing); + if (!IS_ON_BOARD(cExposed) || (cExposed == cAttacker)) + { + p = pos->rgSquare[cTo].pPiece; + ASSERT(!IS_EMPTY(p)); + ASSERT(GET_COLOR(p) == WHITE); + ASSERT(IS_ON_BOARD(cTo)); + _AddPromote(pStack, pos, cPawn, cTo); + } + } + + cTo = cPawn + 17; + if (cTo == cAttacker) + { + cExposed = ExposesCheck(pos, cPawn, cKing); + if (!IS_ON_BOARD(cExposed) || (cExposed == cAttacker)) + { + p = pos->rgSquare[cTo].pPiece; + ASSERT(!IS_EMPTY(p)); + ASSERT(GET_COLOR(p) == WHITE); + ASSERT(IS_ON_BOARD(cTo)); + _AddPromote(pStack, pos, cPawn, cTo); + } + } + } +} + + +void +InvalidGenerator(IN UNUSED MOVE_STACK *pStack, + IN UNUSED POSITION *pos, + IN UNUSED COOR cPawn) +/** + +Routine description: + + If you'd like to make a call, please hang up and try your call + again... + +Parameters: + + IN UNUSED MOVE_STACK *pStack, + IN UNUSED POSITION *pos, + IN UNUSED COOR cPawn + +Return value: + + void + +**/ +{ + UtilPanic(SHOULD_NOT_GET_HERE, + NULL, NULL, NULL, NULL, + __FILE__, __LINE__); +} + + +void +InvalidSaveMe(IN UNUSED MOVE_STACK *pStack, + IN UNUSED POSITION *pos, + IN UNUSED COOR cPawn, + IN UNUSED COOR cKing, + IN UNUSED COOR cAttacker) +/** + +Routine description: + + ...if you need help, please dial the operator. + +Parameters: + + IN UNUSED MOVE_STACK *pStack, + IN UNUSED POSITION *pos, + IN UNUSED COOR cPawn, + IN UNUSED COOR cKing, + IN UNUSED COOR cAttacker + +Return value: + + void + +**/ +{ + UtilPanic(SHOULD_NOT_GET_HERE, + NULL, NULL, NULL, NULL, + __FILE__, __LINE__); +} + + +static void +_GenerateAllMoves(IN MOVE_STACK *pStack, + IN POSITION *pos) +/** + +Routine description: + + This code generates all pseudo-legal moves in a position. Please + see notes at the top of this module for details. + +Parameters: + + MOVE_STACK *pStack : the move stack + POSITION *pos : the board position + +Return value: + + static void + +**/ +{ + COOR c; + static void (*JumpTable[])(MOVE_STACK *, POSITION *, COOR) = + { + InvalidGenerator, // EMPTY + InvalidGenerator, // EMPTY | WHITE + InvalidGenerator, // 2 (BLACK_PAWN) + InvalidGenerator, // 3 (WHITE_PAWN) + GenerateKnight, // 4 (BLACK_KNIGHT) + GenerateWhiteKnight, // 5 (WHITE_KNIGHT) + GenerateBishop, // 6 (BLACK_BISHOP) + GenerateBishop, // 7 (WHITE_BISHOP) + GenerateRook, // 8 (BLACK_ROOK) + GenerateRook, // 9 (WHITE_ROOK) + GenerateQueen, // 10 (BLACK_QUEEN) + GenerateQueen, // 11 (WHITE_QUEEN) + GenerateBlackKing, // 12 (BLACK_KING) + GenerateWhiteKing // 13 (WHITE_KING) + }; + ULONG u; +#ifdef DEBUG + PIECE p; +#endif + + for(u = pos->uNonPawnCount[pos->uToMove][0] - 1; + u != (ULONG)-1; + u--) + { + c = pos->cNonPawns[pos->uToMove][u]; +#ifdef DEBUG + ASSERT(IS_ON_BOARD(c)); + p = pos->rgSquare[c].pPiece; + ASSERT(!IS_EMPTY(p)); + ASSERT(!IS_PAWN(p)); + ASSERT(GET_COLOR(p) == pos->uToMove); +#endif + (JumpTable[pos->rgSquare[c].pPiece])(pStack, pos, c); + } + + if (pos->uToMove == BLACK) + { + for(u = 0; u < pos->uPawnCount[BLACK]; u++) + { + c = pos->cPawns[BLACK][u]; +#ifdef DEBUG + ASSERT(IS_ON_BOARD(c)); + p = pos->rgSquare[c].pPiece; + ASSERT(!IS_EMPTY(p)); + ASSERT(IS_PAWN(p)); + ASSERT(GET_COLOR(p) == pos->uToMove); +#endif + GenerateBlackPawn(pStack, pos, c); + } + } else { + ASSERT(pos->uToMove == WHITE); + for(u = 0; u < pos->uPawnCount[WHITE]; u++) + { + c = pos->cPawns[WHITE][u]; +#ifdef DEBUG + ASSERT(IS_ON_BOARD(c)); + p = pos->rgSquare[c].pPiece; + ASSERT(!IS_EMPTY(p)); + ASSERT(IS_PAWN(p)); + ASSERT(GET_COLOR(p) == pos->uToMove); +#endif + GenerateWhitePawn(pStack, pos, c); + } + } +} + + + +static ULONG +_GenerateEscapes(IN MOVE_STACK *pStack, + IN POSITION *pos) +/** + +Routine description: + + This function is called when side to move is in check in order to + generate pseudo-legal escapes from check. All legal escapes from + check are a subset of the moves returned by this function. In + general it's pretty good; the only bug I know about is that it + will generate a capture that alleviates check where the capturing + piece is pinned to the king (and thus the capture is illegal). + The purpose of this function is to allow the search to detect when + there is one legal reply to check and possibly extend. + +Parameters: + + MOVE_STACK *pStack : the move stack + POSITION *pos : the board + +Return value: + + ULONG : the number of pieces checking the king + +**/ +{ + ULONG u; + ULONG v; + COOR c; + COOR cDefender; + PIECE p; + PIECE pKing; + COOR cKing = pos->cNonPawns[pos->uToMove][0]; + int iIndex; + SEE_LIST rgCheckers; + int iDelta; + ULONG uReturn = 0; + static void (*JumpTable[]) + (MOVE_STACK *, POSITION *, COOR, COOR, COOR) = + { + InvalidSaveMe, // EMPTY + InvalidSaveMe, // EMPTY | WHITE + InvalidSaveMe, // 2 (BLACK_PAWN) + InvalidSaveMe, // 3 (WHITE_PAWN) + SaveMeKnight, // 4 (BLACK_KNIGHT) + SaveMeKnight, // 5 (WHITE_KNIGHT) + SaveMeBishop, // 6 (BLACK_BISHOP) + SaveMeBishop, // 7 (WHITE_BISHOP) + SaveMeRook, // 8 (BLACK_ROOK) + SaveMeRook, // 9 (WHITE_ROOK) + SaveMeQueen, // 10 (BLACK_QUEEN) + SaveMeQueen, // 11 (WHITE_QUEEN) + InvalidSaveMe, // kings already considered + InvalidSaveMe // kings already considered + }; + + ASSERT(IS_KING(pos->rgSquare[cKing].pPiece)); + ASSERT(TRUE == InCheck(pos, pos->uToMove)); + + // + // Use the SEE function GetAttacks to find out how many pieces are + // giving check and from whence. Note: we don't sort rgCheckers + // here; maybe it would be worth trying. In any event it + // shouldn't be affected by treating the list as a minheap + // vs. as a sorted list. + // + GetAttacks(&rgCheckers, pos, cKing, FLIP(pos->uToMove)); + ASSERT(rgCheckers.uCount > 0); + ASSERT(rgCheckers.uCount < 17); + uReturn = rgCheckers.uCount; + + // + // Phase I: See if the king can flee or take the checking piece. + // + pKing = pos->rgSquare[cKing].pPiece; + ASSERT(GET_COLOR(pKing) == pos->uToMove); + ASSERT(IS_KING(pKing)); + ASSERT(OPPOSITE_COLORS(pKing, rgCheckers.data[0].pPiece)); + u = 0; + while(0 != g_iQKDeltas[u]) + { + c = cKing + g_iQKDeltas[u]; + u++; + if (IS_ON_BOARD(c)) + { + p = pos->rgSquare[c].pPiece; + + // + // This logical OR replaced with bitwise OR; the effect is + // the same the the bitwise is marginally faster. + // + if (IS_EMPTY(p) | (OPPOSITE_COLORS(p, pKing))) + { + if (FALSE == IsAttacked(c, pos, FLIP(pos->uToMove))) + { + // + // So we know the destination square is not under + // attack right now... but that could be because + // the present (pre-move) king position "blocks" + // the attack. Detect this. + // + for (v = 0; + v < rgCheckers.uCount; + v++) + { + ASSERT(OPPOSITE_COLORS(pKing, + rgCheckers.data[v].pPiece)); + if (!IS_PAWN(rgCheckers.data[v].pPiece) && + !IS_KNIGHT(rgCheckers.data[v].pPiece)) + { + iIndex = (int)rgCheckers.data[v].cLoc - + (int)cKing; + iDelta = CHECK_DELTA_WITH_INDEX(iIndex); + ASSERT(iDelta); + + iIndex = (int)rgCheckers.data[v].cLoc - + (int)c; + if (iDelta == CHECK_DELTA_WITH_INDEX(iIndex)) + { + goto loop; + } + } + } + ASSERT(v == rgCheckers.uCount); + + // + // If we get here the square is not under attack + // and it does not contain our own piece. It's + // either empty or contains an enemy piece. + // + ASSERT(!p || OPPOSITE_COLORS(pKing, p)); + _AddNormalMove(pStack, pos, cKing, c, p); + uReturn += 0x00010000; + } + } + } + loop: + ; + } + + // + // N.B. If there is more than one piece checking the king then + // there is no way to escape check by blocking check with another + // piece or capturing the offending piece. The two attackers + // cannot be on the same rank, file or diagonal because this would + // depend on the previous position being illegal. + // + if (rgCheckers.uCount > 1) + { +#ifdef DEBUG + // + // Note: the above comment is correct but this assertion fails + // on positions that we made up to run TestSearch. Disabled + // for now. + // +#if 0 + iDelta = DIRECTION_BETWEEN_SQUARES(rgCheckers.data[0].cLoc, cKing); + for (v = 1; v < rgCheckers.uCount; v++) + { + if (DIRECTION_BETWEEN_SQUARES(rgCheckers.data[v].cLoc, cKing) != + iDelta) + { + break; + } + } + ASSERT(v != rgCheckers.uCount); +#endif +#endif + return(uReturn); + } + + // + // Phase 2: If we get here there is a lone attacker causing check. + // See if the other pieces can block the check or take the + // checking piece. + // + c = rgCheckers.data[0].cLoc; + for (u = 1; // don't consider the king + u < pos->uNonPawnCount[pos->uToMove][0]; + u++) + { + cDefender = pos->cNonPawns[pos->uToMove][u]; + ASSERT(IS_ON_BOARD(cDefender)); + p = pos->rgSquare[cDefender].pPiece; + ASSERT(p && !IS_PAWN(p)); + ASSERT(GET_COLOR(p) == pos->uToMove); + + (JumpTable[p])(pStack, pos, cDefender, cKing, c); + } + + // Consider all pawns too + if (pos->uToMove == BLACK) + { + for (u = 0; u < pos->uPawnCount[BLACK]; u++) + { + cDefender = pos->cPawns[BLACK][u]; +#ifdef DEBUG + ASSERT(IS_ON_BOARD(cDefender)); + p = pos->rgSquare[cDefender].pPiece; + ASSERT(p && IS_PAWN(p)); + ASSERT(GET_COLOR(p) == pos->uToMove); +#endif + SaveMeBlackPawn(pStack, pos, cDefender, cKing, c); + } + } else { + ASSERT(pos->uToMove == WHITE); + for (u = 0; u < pos->uPawnCount[WHITE]; u++) + { + cDefender = pos->cPawns[WHITE][u]; +#ifdef DEBUG + ASSERT(IS_ON_BOARD(cDefender)); + p = pos->rgSquare[cDefender].pPiece; + ASSERT(p && IS_PAWN(p)); + ASSERT(GET_COLOR(p) == pos->uToMove); +#endif + SaveMeWhitePawn(pStack, pos, cDefender, cKing, c); + } + } + return(uReturn); +} + + +typedef struct _PRECOMP_KILLERS +{ + MOVE mv; + ULONG uBonus; +} +PRECOMP_KILLERS; + +static void +_ScoreAllMoves(IN MOVE_STACK *pStack, + IN SEARCHER_THREAD_CONTEXT *ctx, + IN MOVE mvHash) +/** + +Routine description: + + We have just generated all the moves, now score them. See comments + inline below about order. + +Parameters: + + IN MOVE_STACK *pStack, + IN SEARCHER_THREAD_CONTEXT *ctx, + IN MOVE mvHash, + +Return value: + + static void + +**/ +{ + ULONG uPly = ctx->uPly; + POSITION *pos = &ctx->sPosition; + ULONG u; + MOVE mv; + SCORE s; + MOVE_STACK_MOVE_VALUE_FLAGS mvf; + ULONG uHashMoveLoc = (ULONG)-1; + ULONG uColor = pos->uToMove; + PRECOMP_KILLERS sKillers[4]; + COOR cEnprise = GetEnprisePiece(pos, uColor); + + // + // We have generated all moves here. We also know that we are not + // escaping from check. There can be a hash move -- if there is + // then the search has already tried it and we should not generate + // it again. + // + // White has 218 legal moves in this position: + // 3Q4/1Q4Q1/4Q3/2Q4R/Q4Q2/3Q4/1Q4Rp/1K1BBNNk w - - 0 1 + // + + // + // Pre-populate killer/bonuses + // + sKillers[0].mv = ctx->mvKiller[uPly][0]; + sKillers[0].uBonus = FIRST_KILLER; + sKillers[1].mv.uMove = sKillers[3].mv.uMove = 0; + sKillers[2].mv = ctx->mvKiller[uPly][1]; + sKillers[2].uBonus = THIRD_KILLER; + if (uPly > 1) + { + sKillers[1].mv = ctx->mvKiller[uPly - 2][0]; + sKillers[1].uBonus = SECOND_KILLER; + sKillers[3].mv = ctx->mvKiller[uPly - 2][1]; + sKillers[3].uBonus = FOURTH_KILLER; + } + sKillers[0].uBonus |= + (SORT_THESE_FIRST * (IS_KILLERMATE_MOVE(sKillers[0].mv) != 0)); + sKillers[1].uBonus |= + (SORT_THESE_FIRST * (IS_KILLERMATE_MOVE(sKillers[1].mv) != 0)); + sKillers[2].uBonus |= + (SORT_THESE_FIRST * (IS_KILLERMATE_MOVE(sKillers[2].mv) != 0)); + sKillers[3].uBonus |= + (SORT_THESE_FIRST * (IS_KILLERMATE_MOVE(sKillers[3].mv) != 0)); + + // + // Score moves + // + ASSERT(MOVE_COUNT(ctx, uPly) <= MAX_MOVES_PER_PLY); + for (u = pStack->uBegin[uPly]; + u < pStack->uEnd[uPly]; + u++) + { + mv = pStack->mvf[u].mv; + ASSERT(mv.uMove); + ASSERT(GET_COLOR(mv.pMoved) == uColor); + if (!IS_SAME_MOVE(mv, mvHash)) + { +#ifdef DEBUG + pStack->mvf[u].iValue = -MAX_INT; + pStack->mvf[u].bvFlags = 0; +#endif + // + // 1. Hash move (already handled by search, all we have to + // do here is not generate it) + // 2. Killer mate move, if one exists + // 3. Winning captures & promotions (MVV/LVA to tiebreak) + // 4. Even captures & promotions -- >= SORT_THESE_FIRST + // 5. Killer move 1-4 + // 6. "good" moves (moves away from danger etc...) + // 7. Other non capture moves (using dynamic move ordering scheme) + // 8. Losing captures -- <0 + // + + // + // Captures and promotions, use SEE + // + if (IS_CAPTURE_OR_PROMOTION(mv)) + { + ASSERT((mv.pCaptured) || (mv.pPromoted)); + s = PIECE_VALUE(mv.pCaptured) - + PIECE_VALUE(mv.pMoved); + if ((s <= 0) || mv.pPromoted) + { + s = SEE(pos, mv); + } + + if (s >= 0) + { + s += PIECE_VALUE_OVER_100(mv.pCaptured) + 120; + s += PIECE_VALUE_OVER_100(mv.pPromoted); + s -= PIECE_VALUE_OVER_100(mv.pMoved); + s += SORT_THESE_FIRST; + + // + // IDEA: bonus for capturing opponent's last moved + // piece to encourage quicker fail highs? + // + ASSERT(s >= SORT_THESE_FIRST); + ASSERT(s > 0); + ASSERT((s & STRIP_OFF_FLAGS) < VALUE_KING); + } +#ifdef DEBUG + else + { + ASSERT((s & STRIP_OFF_FLAGS) > -VALUE_KING); + s -= VALUE_KING; + ASSERT(s < 0); + } +#endif + } + + // + // Non-captures/promotes use history/killer + // + else + { + ASSERT((!mv.pCaptured) && (!mv.pPromoted)); + s = g_iPSQT[mv.pMoved][mv.cTo]; // 0..1000 + s |= (IS_SAME_MOVE(sKillers[0].mv, mv) * sKillers[0].uBonus); + s |= (IS_SAME_MOVE(sKillers[1].mv, mv) * sKillers[1].uBonus); + s |= (IS_SAME_MOVE(sKillers[2].mv, mv) * sKillers[2].uBonus); + s |= (IS_SAME_MOVE(sKillers[3].mv, mv) * sKillers[3].uBonus); + s |= ((GOOD_MOVE + PIECE_VALUE(mv.pMoved) / 2) * + (mv.cFrom == cEnprise)); + ASSERT(s >= 0); + } + pStack->mvf[u].iValue = s; + ASSERT(pStack->mvf[u].iValue != -MAX_INT); + } + else + { + ASSERT(uHashMoveLoc == (ULONG)-1); + uHashMoveLoc = u; +#ifdef DEBUG + ASSERT((mv.cFrom == mvHash.cFrom) && (mv.cTo == mvHash.cTo)); + pStack->mvf[u].bvFlags |= MVF_MOVE_SEARCHED; +#endif + } + + } // next move + + // + // If we generated the hash move, stick it at the end and pretend + // we didn't... it was already considered by the search and we + // should not generate it again. + // + if (uHashMoveLoc != (ULONG)-1) + { + ASSERT(MOVE_COUNT(ctx, uPly) >= 1); + ASSERT(uHashMoveLoc >= pStack->uBegin[uPly]); + ASSERT(uHashMoveLoc < pStack->uEnd[uPly]); + mvf = pStack->mvf[uHashMoveLoc]; + pStack->mvf[uHashMoveLoc] = pStack->mvf[pStack->uEnd[uPly] - 1]; +#ifdef DEBUG + pStack->mvf[pStack->uEnd[uPly] - 1] = mvf; +#endif + pStack->uEnd[uPly]--; + } +} + + + +static void +_ScoreAllEscapes(IN MOVE_STACK *pStack, + IN SEARCHER_THREAD_CONTEXT *ctx, + IN MOVE mvHash) +/** + +Routine description: + + We have just generated all the moves, now score them. See comments + inline below about order. + +Parameters: + + IN MOVE_STACK *pStack, + IN SEARCHER_THREAD_CONTEXT *ctx, + IN MOVE mvHash, + +Return value: + + static void + +**/ +{ + ULONG uPly = ctx->uPly; + POSITION *pos = &ctx->sPosition; + ULONG u; + MOVE mv; + SCORE s; + MOVE_STACK_MOVE_VALUE_FLAGS mvf; + ULONG uHashMoveLoc = (ULONG)-1; + COOR c; + ULONG v; + PIECE p; + static SCORE _bonus[2][7] = { + { 0, 2000, 1250, 1500, 1100, 850, 0 }, // friend + { 0, 1600, 100, 100, 50, -1, -1 }, // foe + }; + + // + // We have generated legal escapes from check here. There can be + // a hash move -- if there is then the search has already tried it + // and we should not generate it again. + // + + ASSERT(MOVE_COUNT(ctx, uPly) <= MAX_MOVES_PER_PLY); + for (u = pStack->uBegin[uPly]; + u < pStack->uEnd[uPly]; + u++) + { + mv = pStack->mvf[u].mv; + ASSERT(mv.uMove); + ASSERT(GET_COLOR(mv.pMoved) == pos->uToMove); + if (!IS_SAME_MOVE(mv, mvHash)) + { +#ifdef DEBUG + pStack->mvf[u].iValue = -MAX_INT; + pStack->mvf[u].bvFlags = 0; +#endif + pStack->mvf[u].mv.bvFlags |= MOVE_FLAG_ESCAPING_CHECK; + + // + // 1. Hash move (already handled by search, all we have to + // do here is not generate it) + // 2. Winning captures by pieces other than the checked king + // 3. Winning captures by the king + // 4. Even captures by pieces other than the king + // 5. Killer escapes + // 6. Moves that block the check and are even + // 7. King moves + // 8. Losing captures / blocks + // + + // + // Captures and promotions, use SEE + // + if (IS_CAPTURE_OR_PROMOTION(mv)) + { + ASSERT((mv.pCaptured) || (mv.pPromoted)); + s = PIECE_VALUE(mv.pCaptured) - + PIECE_VALUE(mv.pMoved); + if ((s <= 0) || mv.pPromoted) + { + s = SEE(pos, mv); + } + + if (s > 0) + { + // Winning captures: take with pieces before with king + s += PIECE_VALUE_OVER_100(mv.pPromoted); + s -= PIECE_VALUE_OVER_100(mv.pMoved); + s >>= IS_KING(mv.pMoved); + s |= SORT_THESE_FIRST; + ASSERT(s >= SORT_THESE_FIRST); + ASSERT(s > 0); + ASSERT((s & STRIP_OFF_FLAGS) < VALUE_KING); + } + else if (s == 0) + { + // Even capture -- can't be capturing w/ king + ASSERT(!IS_KING(mv.pMoved)); + s += PIECE_VALUE_OVER_100(mv.pPromoted) + 20; + s -= PIECE_VALUE_OVER_100(mv.pMoved); + s |= FIRST_KILLER; + ASSERT(s > 0); + } +#ifdef DEBUG + else + { + // Losing capture + ASSERT(!IS_KING(mv.pMoved)); + ASSERT((s & STRIP_OFF_FLAGS) > -VALUE_KING); + s -= VALUE_KING; + ASSERT(s < 0); + } +#endif + } + + // + // Non-captures/promotes + // + else + { + ASSERT((!mv.pCaptured) && (!mv.pPromoted)); + if (IS_SAME_MOVE(mv, ctx->mvKillerEscapes[uPly][0]) || + IS_SAME_MOVE(mv, ctx->mvKillerEscapes[uPly][1])) + { + s = SECOND_KILLER; + ASSERT(s >= 0); + } + else + { + s = g_iPSQT[mv.pMoved][mv.cTo]; // 0..1000 + if (!IS_KING(mv.pMoved)) + { + // 0..2400 + s += (VALUE_QUEEN - PIECE_VALUE(mv.pMoved)) * 4; + if (SEE(pos, mv) >= 0) + { + // Non-losing block of check + ASSERT(SEE(pos, mv) == 0); + s |= THIRD_KILLER; + ASSERT(s >= 0); + } + else + { + // Losing block of check + s -= VALUE_KING; + ASSERT(s < 0); + } + } + else + { + // If the king is fleeing, encourage a spot next + // to friendly pieces. + v = 0; + do { + c = mv.cTo + g_iQKDeltas[v++]; + if (IS_ON_BOARD(c)) + { + p = pos->rgSquare[c].pPiece; + s += _bonus[OPPOSITE_COLORS(pos->uToMove, p)] + [PIECE_TYPE(p)]; + ASSERT(_bonus[OPPOSITE_COLORS(pos->uToMove, p)] + [PIECE_TYPE(p)] >= 0); + } + } + while(g_iQKDeltas[v] != 0); + } + } + } + pStack->mvf[u].iValue = s; + ASSERT(pStack->mvf[u].iValue != -MAX_INT); + } + else + { + ASSERT(uHashMoveLoc == (ULONG)-1); + uHashMoveLoc = u; +#ifdef DEBUG + ASSERT((mv.cFrom == mvHash.cFrom) && (mv.cTo == mvHash.cTo)); + pStack->mvf[u].bvFlags |= MVF_MOVE_SEARCHED; +#endif + } + } // next move + + // + // If we generated the hash move, stick it at the end and pretend + // we didn't... it was already considered by the search and we + // should not generate it again. + // + if (uHashMoveLoc != (ULONG)-1) + { + ASSERT(MOVE_COUNT(ctx, uPly) >= 1); + ASSERT(uHashMoveLoc >= pStack->uBegin[uPly]); + ASSERT(uHashMoveLoc < pStack->uEnd[uPly]); + mvf = pStack->mvf[uHashMoveLoc]; + pStack->mvf[uHashMoveLoc] = pStack->mvf[pStack->uEnd[uPly] - 1]; +#ifdef DEBUG + pStack->mvf[pStack->uEnd[uPly] - 1] = mvf; +#endif + pStack->uEnd[uPly]--; + } +} + + + +static void +_ScoreQSearchMovesInclChecks(IN MOVE_STACK *pStack, + IN SEARCHER_THREAD_CONTEXT *ctx) +/** + +Routine description: + + We have just generated all the moves. We were called from the + Qsearch so: + + 1. Unlike _ScoreAllMoves we don't have to think about a hash move + 2. QSearch only cares about winning/even captures/promotes and + checking moves. + + Like _ScoreSearchMoves, this function takes "hints" from the + searcher context about what squares are in danger and tries to + order moves away from those squares sooner. Unlike + _ScoreSearchMoves this function also attempts to capture enemies + that are in danger sooner. + +Parameters: + + IN MOVE_STACK *pStack, + IN SEARCHER_THREAD_CONTEXT *ctx + +Return value: + + static void + +**/ +{ + register POSITION *pos = &ctx->sPosition; + PLY_INFO *pi = &ctx->sPlyInfo[ctx->uPly]; + ULONG uPly = ctx->uPly; + ULONG u, uColor = pos->uToMove; + MOVE mv; + MOVE mvLast = (pi-1)->mv; + SCORE s; + COOR cEnprise = GetEnprisePiece(pos, uColor); + + // + // We have generate all moves or just legal escapes from check + // here. There can be a hash move -- if there is then the search + // has already tried it and we should not generate it again. + // + // White has 218 legal moves in this position: + // 3Q4/1Q4Q1/4Q3/2Q4R/Q4Q2/3Q4/1Q4Rp/1K1BBNNk w - - 0 1 + // + ASSERT(MOVE_COUNT(ctx, uPly) <= MAX_MOVES_PER_PLY); + ASSERT(uPly >= 1); + + for (u = pStack->uBegin[uPly]; + u < pStack->uEnd[uPly]; + u++) + { + mv = pStack->mvf[u].mv; + ASSERT(GET_COLOR(mv.pMoved) == uColor); +#ifdef DEBUG + pStack->mvf[u].iValue = -MAX_INT; + pStack->mvf[u].bvFlags = 0; +#endif + pStack->mvf[u].mv.bvFlags |= WouldGiveCheck(ctx, mv); + + // + // 1. There can't be a hash move so don't worry about it + // 2. Winning captures & promotions + // 3. Even captures & promotions -- >= SORT_THESE_FIRST + // 4. Checking non-capture moves + // 5. Losing captures that check -- > 0 + // 6. Everything else is ignored -- <= 0 + // + + // + // Captures and promotions, use SEE + // + if (IS_CAPTURE_OR_PROMOTION(mv)) + { + ASSERT((mv.pCaptured) || (mv.pPromoted)); + s = PIECE_VALUE(mv.pCaptured) - + PIECE_VALUE(mv.pMoved); + if ((s <= 0) || mv.pPromoted) + { + s = SEE(pos, mv); + } + + if (s >= 0) + { + // + // Winning / even captures / promotes should be >= + // SORT_THESE_FIRST. + // + s += PIECE_VALUE_OVER_100(mv.pCaptured) + 120; + s += PIECE_VALUE_OVER_100(mv.pPromoted); + s -= PIECE_VALUE_OVER_100(mv.pMoved); + s += SORT_THESE_FIRST; + + // + // Bonus if it checks too + // + s += (pStack->mvf[u].mv.bvFlags & MOVE_FLAG_CHECKING) * 4; + + // + // Bonus for capturing last moved enemy piece. + // + s += (mv.cTo == mvLast.cTo) * 64; + ASSERT(s >= SORT_THESE_FIRST); + ASSERT(s > 0); + } + else + { + // + // Make losing captures into either zero scores or + // slightly positive if they check. Qsearch is going + // to bail as soon as it sees the first zero so no + // need to keep real SEE scores on these. + // + s = (pStack->mvf[u].mv.bvFlags & MOVE_FLAG_CHECKING); + ASSERT(s >= 0); + } + } + + // + // Non-captures/promotes -- we don't care unless they check + // + else + { + s = (pStack->mvf[u].mv.bvFlags & MOVE_FLAG_CHECKING) * 2; + ASSERT(s >= 0); + ASSERT(s < SORT_THESE_FIRST); + } + + // + // If this move moves a piece that was in danger, consider it + // sooner. + // + if (s > 0) + { + ASSERT(IS_CAPTURE_OR_PROMOTION(pStack->mvf[u].mv) || + IS_CHECKING_MOVE(pStack->mvf[u].mv)); + s += (mv.cFrom == cEnprise) * (PIECE_VALUE(mv.pMoved) / 4); + ASSERT(s > 0); + } + pStack->mvf[u].iValue = s; + ASSERT(pStack->mvf[u].iValue != -MAX_INT); + + } // next move +} + + +static void +_ScoreQSearchMovesNoChecks(IN MOVE_STACK *pStack, + IN SEARCHER_THREAD_CONTEXT *ctx) +/** + +Routine description: + + We have just generated all the moves. We were called from the + Qsearch so: + + 1. Unlike _ScoreAllMoves we don't have to think about a hash move + 2. QSearch only cares about winning/even captures/promotes. At + this point it is so deep that it doesn't even care about + checks. + + Like _ScoreSearchMoves, this function takes "hints" from the + searcher context about what squares are in danger and tries to + order moves away from those squares sooner. Unlike + _ScoreSearchMoves this function also attempts to capture enemies + that are in danger sooner. + +Parameters: + + IN MOVE_STACK *pStack, + IN SEARCHER_THREAD_CONTEXT *ctx + +Return value: + + static void + +**/ +{ + register POSITION *pos = &(ctx->sPosition); + ULONG uPly = ctx->uPly; + ULONG u, uColor; + MOVE mv; + SCORE s; + + // + // We have generate all moves or just legal escapes from check + // here. There can be a hash move -- if there is then the search + // has already tried it and we should not generate it again. + // + // White has 218 legal moves in this position: + // 3Q4/1Q4Q1/4Q3/2Q4R/Q4Q2/3Q4/1Q4Rp/1K1BBNNk w - - 0 1 + // + ASSERT(MOVE_COUNT(ctx, uPly) <= MAX_MOVES_PER_PLY); + + uColor = pos->uToMove; + for (u = pStack->uBegin[uPly]; + u < pStack->uEnd[uPly]; + u++) + { + mv = pStack->mvf[u].mv; + ASSERT(GET_COLOR(mv.pMoved) == uColor); +#ifdef DEBUG + pStack->mvf[u].iValue = -MAX_INT; + pStack->mvf[u].bvFlags = 0; +#endif + // + // 1. There can't be a hash move so don't worry about it + // 2. Winning captures & promotions + // 3. Even captures & promotions -- >= SORT_THESE_FIRST + // 4. Everything else is ignored -- <= 0 + // + + // + // Captures and promotions, use SEE + // + s = 0; + if (IS_CAPTURE_OR_PROMOTION(mv)) + { + ASSERT((mv.pCaptured) || (mv.pPromoted)); + s = PIECE_VALUE(mv.pCaptured) - + PIECE_VALUE(mv.pMoved); + // + // TODO: how does this handle positions like K *p *k ? + // + if (s <= 0) + { + s = SEE(pos, mv); + } + + if (s >= 0) + { + // + // Winning / even captures / promotes should be >= + // SORT_THESE_FIRST. + // + s += PIECE_VALUE_OVER_100(mv.pCaptured) + 120; + s += PIECE_VALUE_OVER_100(mv.pPromoted); + s -= PIECE_VALUE_OVER_100(mv.pMoved); + s += SORT_THESE_FIRST; + + // + // IDEA: bonus for capturing an enprise enemy piece? + // + ASSERT(s >= SORT_THESE_FIRST); + ASSERT(s > 0); + } + } + pStack->mvf[u].iValue = s; + ASSERT(pStack->mvf[u].iValue != -MAX_INT); + + } // next move +} + + + +void +GenerateMoves(IN SEARCHER_THREAD_CONTEXT *ctx, + IN MOVE mvHash, + IN ULONG uType) +/** + +Routine description: + + This is the entrypoint to the move generator. It invokes the + requested generation code which push moves onto the move stack in + ctx. Once the moves are generated this code optionally will score + the moves. + +Parameters: + + SEARCHER_THREAD_CONTEXT *ctx : a searcher thread's context + + IN: ctx->sPosition.uDangerCount and ctx->sPosition.cDanger + data is used to tweak move scoring. This data MUST be + consistent with the state of the current board. + + OUT: ctx->sMoveStack.uBegin[ctx->uPly] is set, + ctx->sMoveStack.uEnd[ctx->uPly] is set, + ctx->sMoveStack.mvf[begin..end] are populated + + MOVE mvHash : the hash move to not generate + + ULONG uType : what kind of moves to generate + + GENERATE_ALL_MOVES : pseudo-legal generation of all moves; + scored by _ScoreAllMoves. Return value is count of moves + generated. + + GENERATE_ESCAPE: called when stm in check, generate evasions + scored by _ScoreAllMoves. Return value is special code; + see inline comment below. + + GENERATE_CAPTURES_PROMS_CHECKS: caps, promotions, and checks + scored by _ScoreQSearchMoves. Return value is count of + moves generated. + + GENERATE_CAPTURES_PROMS: caps, promotions. Skip the checks. + + GENERATE_DONT_SCORE: pseudo-legal generation of all moves; + not scored to save time. Return value always zero. + +Return value: + + void + +**/ +{ + register ULONG uPly = ctx->uPly; + MOVE_STACK *pStack = &ctx->sMoveStack; + POSITION *pos = &ctx->sPosition; + ULONG uReturn; +#ifdef DEBUG + POSITION board; + ULONG u; + MOVE mv; + PIECE p; + + ASSERT((uPly >= 0) && (uPly < MAX_PLY_PER_SEARCH)); + memcpy(&board, pos, sizeof(POSITION)); + memcpy(&(pStack->board[uPly]), pos, sizeof(POSITION)); + + // + // Make sure the hash move makes sense (if provided) + // + if (mvHash.uMove) + { + p = pos->rgSquare[mvHash.cFrom].pPiece; + ASSERT(p); + ASSERT(GET_COLOR(p) == pos->uToMove); + p = pos->rgSquare[mvHash.cTo].pPiece; + ASSERT(!p || OPPOSITE_COLORS(p, pos->uToMove)); + } +#endif + pStack->uPly = uPly; + pStack->uEnd[uPly] = pStack->uBegin[uPly]; + pStack->sGenFlags[uPly].uAllGenFlags = 0; + + switch(uType) + { + case GENERATE_CAPTURES_PROMS_CHECKS: + ASSERT(!InCheck(pos, pos->uToMove)); + ASSERT(mvHash.uMove == 0); + _FindUnblockedSquares(pStack, pos); + _GenerateAllMoves(pStack, pos); + _ScoreQSearchMovesInclChecks(pStack, ctx); + break; + case GENERATE_CAPTURES_PROMS: + ASSERT(!InCheck(pos, pos->uToMove)); + ASSERT(mvHash.uMove == 0); + _FindUnblockedSquares(pStack, pos); + _GenerateAllMoves(pStack, pos); + _ScoreQSearchMovesNoChecks(pStack, ctx); + break; + case GENERATE_ALL_MOVES: + ASSERT(!InCheck(pos, pos->uToMove)); + _FindUnblockedSquares(pStack, pos); + _GenerateAllMoves(pStack, pos); + _ScoreAllMoves(pStack, ctx, mvHash); + uReturn = MOVE_COUNT(ctx, uPly); + break; + case GENERATE_ESCAPES: + ASSERT(InCheck(pos, pos->uToMove)); + _FindUnblockedSquares(pStack, pos); + uReturn = _GenerateEscapes(pStack, pos); + ASSERT(uReturn); + pStack->sGenFlags[uPly].uKingMoveCount = uReturn >> 16; + pStack->sGenFlags[uPly].uCheckingPieces = uReturn & 0xFF; + _ScoreAllEscapes(pStack, ctx, mvHash); + break; + + // Note: this is just for plytest / seetest. Just generate + // moves, do not score them. + case GENERATE_DONT_SCORE: + if (InCheck(pos, pos->uToMove)) + { + (void)_GenerateEscapes(pStack, pos); + for (uReturn = pStack->uBegin[uPly]; + uReturn < pStack->uEnd[uPly]; + uReturn++) + { + pStack->mvf[uReturn].mv.bvFlags |= + MOVE_FLAG_ESCAPING_CHECK; + } + } + else + { + (void)_GenerateAllMoves(pStack, pos); + } + goto end; +#ifdef DEBUG + default: + uReturn = 0; + ASSERT(FALSE); +#endif + } + +#ifdef DEBUG + // + // Sanity check the move list we just generated... + // + ASSERT(MOVE_COUNT(ctx, uPly) >= 0); + for (u = pStack->uBegin[uPly]; + u < pStack->uEnd[uPly]; + u++) + { + mv = pStack->mvf[u].mv; + ASSERT(!IS_SAME_MOVE(mv, mvHash)); + SanityCheckMove(pos, mv); + + if (WouldGiveCheck(ctx, mv)) + { + if (MakeMove(ctx, mv)) + { + ASSERT(ctx->uPly == (uPly + 1)); + ASSERT(InCheck(pos, pos->uToMove)); + UnmakeMove(ctx, mv); + + // + // Note: this is so that DEBUG and RELEASE builds search + // the same trees. Without this the MakeMove/UnmakeMove + // pair here can affect the order of the pieces in the + // POSITION piece lists which in turn affects the order + // in which moves are generated down the road. + // + memcpy(&ctx->sPosition, &board, sizeof(POSITION)); + } + } + else + { + if (MakeMove(ctx, mv)) + { + ASSERT(ctx->uPly == (uPly + 1)); + ASSERT(!InCheck(pos, pos->uToMove)); + UnmakeMove(ctx, mv); + + // + // Note: this is so that DEBUG and RELEASE builds search + // the same trees. Without this the MakeMove/UnmakeMove + // pair here can affect the order of the pieces in the + // POSITION piece lists which in turn affects the order + // in which moves are generated down the road. + // + memcpy(&ctx->sPosition, &board, sizeof(POSITION)); + } + } + } + ASSERT(PositionsAreEquivalent(&board, pos)); +#endif + end: + pStack->sGenFlags[uPly].uMoveCount = MOVE_COUNT(ctx, uPly); + pStack->uBegin[uPly + 1] = pStack->uEnd[uPly]; +} |