/** 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 (scott.gasch@gmail.com) 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]); } // // board_representation/MOVEGEN_MIGRATION.md section 3 step 1: bitboard // knight generator, the pilot function for the whole migration -- // lowest risk, most precedented (reuses g_KnightAttacksBB, already // built and verified for GetAttacks, no new tables needed). Unlike the // mailbox pair above, one function serves both JumpTable slots // (BLACK_KNIGHT and WHITE_KNIGHT) -- GenerateWhiteKnight's // GET_COLOR(p)==BLACK bit trick was purely a mailbox micro- // optimization exploiting how BLACK happens to be encoded; a bitboard // lookup needs no such color-specific shortcut, it just ANDs off // whichever side's occupancy pos->uToMove identifies. // // Full-board occupancy, both sides -- same formula as see.c's static // _BuildOccupiedBB (a separate copy, not shared, since that one is // file-local to see.c and this module's own convention keeps its // bitboard helpers together). Needed by the slider magic-bitboard // generators (_GenerateRookBB/_GenerateBishopBB) to index into // g_RookAttackTable/g_BishopAttackTable -- see MOVE_STACK's // bbOccupied field comment in chess.h. Non-static so testgenerate.c's // harness can call it directly. BITBOARD _BuildFullOccupiedBB(IN POSITION *pos) /** Routine description: Full-board occupancy bitboard (both colors, every piece including pawns and kings). Parameters: POSITION *pos Return value: BITBOARD **/ { return (pos->bbPieces[WHITE][KNIGHT] | pos->bbPieces[WHITE][BISHOP] | pos->bbPieces[WHITE][ROOK] | pos->bbPieces[WHITE][QUEEN] | pos->bbPieces[BLACK][KNIGHT] | pos->bbPieces[BLACK][BISHOP] | pos->bbPieces[BLACK][ROOK] | pos->bbPieces[BLACK][QUEEN] | pos->bbPawns[WHITE] | pos->bbPawns[BLACK] | COOR_TO_BB(pos->cNonPawns[WHITE][0]) | COOR_TO_BB(pos->cNonPawns[BLACK][0])); } // board_representation/MOVEGEN_MIGRATION.md section 6a Phase 2: raw // magic-table lookups, factored out of _GenerateRookBB/_GenerateBishopBB // so _ComputeCheckTargetMaskBB (below) and the Part B SaveMe*BB // functions can reuse them without duplicating the index arithmetic a // third/fourth time. Non-static (unlike their original file-local // status) so movesup.c's section 6b ExposesCheckBB work can call them // too -- same convention as _BuildFriendlySideBB/_WhoAttacksSquareBB. BITBOARD FORCEINLINE _RookAttacksBB(IN COOR c, IN BITBOARD bbOccupied) { ULONG uMagicIndex = (ULONG) (((bbOccupied & g_RookOccupancyMask[c]) * g_RookMagic[c]) >> g_RookMagicShift[c]); return g_RookAttackTable[c][uMagicIndex]; } BITBOARD FORCEINLINE _BishopAttacksBB(IN COOR c, IN BITBOARD bbOccupied) { ULONG uMagicIndex = (ULONG) (((bbOccupied & g_BishopOccupancyMask[c]) * g_BishopMagic[c]) >> g_BishopMagicShift[c]); return g_BishopAttackTable[c][uMagicIndex]; } // board_representation/MOVEGEN_MIGRATION.md section 6a Phase 2: // bbTargetMask = every square a non-king move could land on to resolve // a lone check -- the checker's own square (a capture always resolves // check) OR, if the checker is a slider, every square strictly between // it and the king (a block also resolves check). The "squares between // two aligned pieces" trick costs nothing new: each square's magic // attack bitboard already reaches exactly to its nearest blocker in // every direction, so ANDing both sides' attack sets together gives // precisely the empty segment between them, excluding both endpoints // (neither piece's own attack set includes its own square). A // diagonally-adjacent pawn checker naturally falls out of the same // bishop-table branch with zero extra bits, since there is nothing // between two adjacent squares -- no separate pawn case needed. A // non-aligned (knight) checker is the only case requiring a branch: // DIRECTION_BETWEEN_SQUARES returns 0 for a knight offset, and there // is no way to block a knight's check regardless. static BITBOARD _ComputeCheckTargetMaskBB(IN COOR cKing, IN COOR cAttacker, IN BITBOARD bbOccupied) { int iDelta = DIRECTION_BETWEEN_SQUARES(cAttacker, cKing); BITBOARD bbBetween = 0; if (0 != iDelta) { if ((16 == iDelta) || (-16 == iDelta) || (1 == iDelta) || (-1 == iDelta)) { bbBetween = _RookAttacksBB(cKing, bbOccupied) & _RookAttacksBB(cAttacker, bbOccupied); } else { bbBetween = _BishopAttacksBB(cKing, bbOccupied) & _BishopAttacksBB(cAttacker, bbOccupied); } } return COOR_TO_BB(cAttacker) | bbBetween; } // Non-static so testgenerate.c's harness can call it directly to set // up MOVE_STACK.bbFriendlyOccupied when calling a _Generate*BB // function outside of _GenerateAllMoves. BITBOARD _BuildFriendlySideBB(IN POSITION *pos, IN ULONG uSide) /** Routine description: Full occupancy bitboard for one side only (all piece types including pawns and king) -- see.c's _BuildOccupiedBB ORs both sides together for a different purpose (SEE's "is this square occupied at all" query); move generation needs just one side's squares, to AND off as illegal (self-occupied) destinations. Parameters: POSITION *pos ULONG uSide Return value: BITBOARD **/ { return (pos->bbPieces[uSide][KNIGHT] | pos->bbPieces[uSide][BISHOP] | pos->bbPieces[uSide][ROOK] | pos->bbPieces[uSide][QUEEN] | pos->bbPawns[uSide] | COOR_TO_BB(pos->cNonPawns[uSide][0])); } // Non-static (unlike a purely-internal helper would be) so // testgenerate.c's speed/correctness harness can call it directly, // same convention _GetAttacksBB (see.c) already uses. void _GenerateKnightBB(IN MOVE_STACK *pStack, IN POSITION *pos, IN COOR cKnight) /** Routine description: Bitboard equivalent of GenerateKnight/GenerateWhiteKnight -- called by GenerateMoves' JumpTable in place of both when GENERATE_KNIGHT_BITBOARD is defined. Produces the exact same pseudo-legal move set (same over-generation behavior, no legal-awareness added) -- see MOVEGEN_MIGRATION.md section 1's explicit non-goal. Relies on pStack->bbFriendlyOccupied already being set by the caller (_GenerateAllMoves computes it once per node, before dispatching to any piece type, precisely so every bitboard-backed generator for that node shares one build instead of each paying for its own -- see MOVE_STACK's field comment in chess.h). A direct caller outside of _GenerateAllMoves (e.g. testgenerate.c's harness) must set it first; the DEBUG-build ASSERT below catches a stale/unset value, but only in a DEBUG build. Parameters: MOVE_STACK *pStack : the move stack (bbFriendlyOccupied must already be set for pos->uToMove) POSITION *pos : the board position COOR cKnight : the knight's location Return value: static void **/ { BITBOARD bbDest = g_KnightAttacksBB[cKnight] & ~pStack->bbFriendlyOccupied; ULONG uBitIndex; COOR c; PIECE p; ASSERT(IS_KNIGHT(pos->rgSquare[cKnight].pPiece)); ASSERT(GET_COLOR(pos->rgSquare[cKnight].pPiece) == pos->uToMove); ASSERT(pStack->bbFriendlyOccupied == _BuildFriendlySideBB(pos, pos->uToMove)); while (bbDest) { uBitIndex = FastFirstBit(bbDest) - 1; bbDest &= (bbDest - 1); c = BIT_NUMBER_TO_COOR(uBitIndex); p = pos->rgSquare[c].pPiece; _AddNormalMove(pStack, pos, cKnight, c, p); } } // // 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]); } // // board_representation/MOVEGEN_MIGRATION.md section 6a Phase 2: // bitboard equivalent of SaveMeKnight -- one AND against a // precomputed bbTargetMask replaces the per-square (c == cAttacker) || // BLOCKS_THE_CHECK(c) test entirely. ExposesCheck (pin detection) // stays exactly as-is, unchanged, called per surviving candidate -- // not in scope to alter, see section 6a's "what does not change." // void _SaveMeKnightBB(IN MOVE_STACK *pStack, IN POSITION *pos, IN COOR cKnight, IN COOR cKing, IN BITBOARD bbTargetMask) /** Routine description: Bitboard equivalent of SaveMeKnight -- called in place of it (via a direct, statically-known call, not JumpTable) when GENERATE_ESCAPES_BLOCK_BITBOARD is defined. Parameters: MOVE_STACK *pStack : the move stack (bbFriendlyOccupied must already be set for pos->uToMove) POSITION *pos : the board position COOR cKnight : the knight's location COOR cKing : the friendly king's location BITBOARD bbTargetMask : squares that resolve the lone check -- see _ComputeCheckTargetMaskBB Return value: void **/ { BITBOARD bbDest = g_KnightAttacksBB[cKnight] & ~pStack->bbFriendlyOccupied & bbTargetMask; ULONG uBitIndex; COOR c, cExposed; PIECE p; ASSERT(InCheck(pos, pos->uToMove)); ASSERT(IS_KNIGHT(pos->rgSquare[cKnight].pPiece)); ASSERT(GET_COLOR(pos->rgSquare[cKnight].pPiece) == pos->uToMove); while (bbDest) { uBitIndex = FastFirstBit(bbDest) - 1; bbDest &= (bbDest - 1); c = BIT_NUMBER_TO_COOR(uBitIndex); cExposed = ExposesCheck(pos, cKnight, cKing); if (!IS_ON_BOARD(cExposed) || (cExposed == c)) { p = pos->rgSquare[c].pPiece; _AddNormalMove(pStack, pos, cKnight, c, p); } } } 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; } } // // board_representation/MOVEGEN_MIGRATION.md section 3 step 3: // magic-bitboard bishop generator -- mechanically identical to // _GenerateRookBB, swapping in the bishop's magic tables. Measured // speed result for rook was parity (not a win) against mailbox at // these small destination counts -- see that finding written up in // MOVEGEN_MIGRATION.md's section 3 entry; expect the same here rather // than a different outcome, since the underlying reason (a mailbox ray // walk's cost is already ~O(destination count), so magic's O(1) // lookup pipeline doesn't out-race it at these distances) applies // identically to diagonals. // void _GenerateBishopBB(IN MOVE_STACK *pStack, IN POSITION *pos, IN COOR cBishop) /** Routine description: Bitboard equivalent of GenerateBishop -- called by GenerateMoves' JumpTable in place of it when GENERATE_BISHOP_BITBOARD is defined. Produces the exact same pseudo-legal move set (same over-generation behavior, no legal-awareness added) -- see MOVEGEN_MIGRATION.md section 1's explicit non-goal. Relies on pStack->bbFriendlyOccupied and pStack->bbOccupied already being set by the caller, same as _GenerateRookBB -- see that function's header comment and MOVE_STACK's field comments in chess.h. Parameters: MOVE_STACK *pStack : the move stack (bbFriendlyOccupied and bbOccupied must already be set) POSITION *pos : the board position COOR cBishop : the bishop's location Return value: void **/ { ULONG uMagicIndex; BITBOARD bbDest; ULONG uBitIndex; COOR c; PIECE p; ASSERT(IS_BISHOP(pos->rgSquare[cBishop].pPiece)); ASSERT(GET_COLOR(pos->rgSquare[cBishop].pPiece) == pos->uToMove); ASSERT(pStack->bbFriendlyOccupied == _BuildFriendlySideBB(pos, pos->uToMove)); ASSERT(pStack->bbOccupied == _BuildFullOccupiedBB(pos)); uMagicIndex = (ULONG) (((pStack->bbOccupied & g_BishopOccupancyMask[cBishop]) * g_BishopMagic[cBishop]) >> g_BishopMagicShift[cBishop]); bbDest = g_BishopAttackTable[cBishop][uMagicIndex] & ~pStack->bbFriendlyOccupied; while (bbDest) { uBitIndex = FastFirstBit(bbDest) - 1; bbDest &= (bbDest - 1); c = BIT_NUMBER_TO_COOR(uBitIndex); p = pos->rgSquare[c].pPiece; _AddNormalMove(pStack, pos, cBishop, c, p); } } 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]); } // // board_representation/MOVEGEN_MIGRATION.md section 6a Phase 2: // bitboard equivalent of SaveMeBishop -- same pattern as // _SaveMeKnightBB, using the magic lookup instead of a ray walk. // void _SaveMeBishopBB(IN MOVE_STACK *pStack, IN POSITION *pos, IN COOR cBishop, IN COOR cKing, IN BITBOARD bbTargetMask) /** Routine description: Bitboard equivalent of SaveMeBishop -- called in place of it (via a direct, statically-known call, not JumpTable) when GENERATE_ESCAPES_BLOCK_BITBOARD is defined. Parameters: MOVE_STACK *pStack : the move stack (bbFriendlyOccupied and bbOccupied must already be set) POSITION *pos : the board position COOR cBishop : the bishop's location COOR cKing : the friendly king's location BITBOARD bbTargetMask : squares that resolve the lone check -- see _ComputeCheckTargetMaskBB Return value: void **/ { BITBOARD bbDest = _BishopAttacksBB(cBishop, pStack->bbOccupied) & ~pStack->bbFriendlyOccupied & bbTargetMask; ULONG uBitIndex; COOR c, cExposed; PIECE p; ASSERT(InCheck(pos, pos->uToMove)); ASSERT(IS_BISHOP(pos->rgSquare[cBishop].pPiece)); ASSERT(GET_COLOR(pos->rgSquare[cBishop].pPiece) == pos->uToMove); while (bbDest) { uBitIndex = FastFirstBit(bbDest) - 1; bbDest &= (bbDest - 1); c = BIT_NUMBER_TO_COOR(uBitIndex); cExposed = ExposesCheck(pos, cBishop, cKing); if (!IS_ON_BOARD(cExposed) || (cExposed == c)) { p = pos->rgSquare[c].pPiece; _AddNormalMove(pStack, pos, cBishop, c, p); } } } 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; } } // // board_representation/MOVEGEN_MIGRATION.md section 3 step 3: magic- // bitboard rook generator -- the first consumer of the InitMagic() // infrastructure (data.c) built ahead of time for exactly this. Unlike // knight/king, this piece type is expected to actually win on speed: // the magic lookup replaces a 4-direction ray walk (up to 7 squares // per direction) with one multiply+shift+table lookup, independent of // how far the rook can see. // void _GenerateRookBB(IN MOVE_STACK *pStack, IN POSITION *pos, IN COOR cRook) /** Routine description: Bitboard equivalent of GenerateRook -- called by GenerateMoves' JumpTable in place of it when GENERATE_ROOK_BITBOARD is defined. Produces the exact same pseudo-legal move set (same over-generation behavior, no legal-awareness added) -- see MOVEGEN_MIGRATION.md section 1's explicit non-goal. Relies on pStack->bbFriendlyOccupied and pStack->bbOccupied already being set by the caller (_GenerateAllMoves computes both once per node, before dispatching to any piece type) -- see MOVE_STACK's field comments in chess.h. A direct caller outside of _GenerateAllMoves (e.g. testgenerate.c's harness) must set both first. Parameters: MOVE_STACK *pStack : the move stack (bbFriendlyOccupied and bbOccupied must already be set) POSITION *pos : the board position COOR cRook : the rook's location Return value: void **/ { ULONG uMagicIndex; BITBOARD bbDest; ULONG uBitIndex; COOR c; PIECE p; ASSERT(IS_ROOK(pos->rgSquare[cRook].pPiece)); ASSERT(GET_COLOR(pos->rgSquare[cRook].pPiece) == pos->uToMove); ASSERT(pStack->bbFriendlyOccupied == _BuildFriendlySideBB(pos, pos->uToMove)); ASSERT(pStack->bbOccupied == _BuildFullOccupiedBB(pos)); uMagicIndex = (ULONG) (((pStack->bbOccupied & g_RookOccupancyMask[cRook]) * g_RookMagic[cRook]) >> g_RookMagicShift[cRook]); bbDest = g_RookAttackTable[cRook][uMagicIndex] & ~pStack->bbFriendlyOccupied; while (bbDest) { uBitIndex = FastFirstBit(bbDest) - 1; bbDest &= (bbDest - 1); c = BIT_NUMBER_TO_COOR(uBitIndex); p = pos->rgSquare[c].pPiece; _AddNormalMove(pStack, pos, cRook, c, p); } } 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]); } // // board_representation/MOVEGEN_MIGRATION.md section 6a Phase 2: // bitboard equivalent of SaveMeRook -- same pattern as // _SaveMeBishopBB, using the rook magic lookup instead of a ray walk. // void _SaveMeRookBB(IN MOVE_STACK *pStack, IN POSITION *pos, IN COOR cRook, IN COOR cKing, IN BITBOARD bbTargetMask) /** Routine description: Bitboard equivalent of SaveMeRook -- called in place of it (via a direct, statically-known call, not JumpTable) when GENERATE_ESCAPES_BLOCK_BITBOARD is defined. Parameters: MOVE_STACK *pStack : the move stack (bbFriendlyOccupied and bbOccupied must already be set) POSITION *pos : the board position COOR cRook : the rook's location COOR cKing : the friendly king's location BITBOARD bbTargetMask : squares that resolve the lone check -- see _ComputeCheckTargetMaskBB Return value: void **/ { BITBOARD bbDest = _RookAttacksBB(cRook, pStack->bbOccupied) & ~pStack->bbFriendlyOccupied & bbTargetMask; ULONG uBitIndex; COOR c, cExposed; PIECE p; ASSERT(InCheck(pos, pos->uToMove)); ASSERT(IS_ROOK(pos->rgSquare[cRook].pPiece)); ASSERT(GET_COLOR(pos->rgSquare[cRook].pPiece) == pos->uToMove); while (bbDest) { uBitIndex = FastFirstBit(bbDest) - 1; bbDest &= (bbDest - 1); c = BIT_NUMBER_TO_COOR(uBitIndex); cExposed = ExposesCheck(pos, cRook, cKing); if (!IS_ON_BOARD(cExposed) || (cExposed == c)) { p = pos->rgSquare[c].pPiece; _AddNormalMove(pStack, pos, cRook, c, p); } } } 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]); } // // board_representation/MOVEGEN_MIGRATION.md section 3 step 4: queen is // just rook-directions OR bishop-directions combined, once step 3 is // solved -- no new design or new tables needed. Two magic lookups (one // rook-table, one bishop-table) ORed together, same // `_EvalQueenOccupancyBB`-flagged caution as the rest of this plan: // a combined single 8-ray table was tried elsewhere (the PoC in data.c // this migration's tables were built alongside) and measured *slower* // than reusing the two-pass rook/bishop structure -- don't rediscover // that, this deliberately does not attempt to unify the two lookups // into one table. // void _GenerateQueenBB(IN MOVE_STACK *pStack, IN POSITION *pos, IN COOR cQueen) /** Routine description: Bitboard equivalent of GenerateQueen -- called by GenerateMoves' JumpTable in place of it when GENERATE_QUEEN_BITBOARD is defined. Produces the exact same pseudo-legal move set (same over-generation behavior, no legal-awareness added) -- see MOVEGEN_MIGRATION.md section 1's explicit non-goal. Relies on pStack->bbFriendlyOccupied and pStack->bbOccupied already being set by the caller, same as _GenerateRookBB/_GenerateBishopBB -- see those functions' header comments and MOVE_STACK's field comments in chess.h. Parameters: MOVE_STACK *pStack : the move stack (bbFriendlyOccupied and bbOccupied must already be set) POSITION *pos : the board position COOR cQueen : the queen's location Return value: void **/ { ULONG uRookMagicIndex, uBishopMagicIndex; BITBOARD bbDest; ULONG uBitIndex; COOR c; PIECE p; ASSERT(IS_QUEEN(pos->rgSquare[cQueen].pPiece)); ASSERT(GET_COLOR(pos->rgSquare[cQueen].pPiece) == pos->uToMove); ASSERT(pStack->bbFriendlyOccupied == _BuildFriendlySideBB(pos, pos->uToMove)); ASSERT(pStack->bbOccupied == _BuildFullOccupiedBB(pos)); uRookMagicIndex = (ULONG) (((pStack->bbOccupied & g_RookOccupancyMask[cQueen]) * g_RookMagic[cQueen]) >> g_RookMagicShift[cQueen]); uBishopMagicIndex = (ULONG) (((pStack->bbOccupied & g_BishopOccupancyMask[cQueen]) * g_BishopMagic[cQueen]) >> g_BishopMagicShift[cQueen]); bbDest = (g_RookAttackTable[cQueen][uRookMagicIndex] | g_BishopAttackTable[cQueen][uBishopMagicIndex]) & ~pStack->bbFriendlyOccupied; while (bbDest) { uBitIndex = FastFirstBit(bbDest) - 1; bbDest &= (bbDest - 1); c = BIT_NUMBER_TO_COOR(uBitIndex); p = pos->rgSquare[c].pPiece; _AddNormalMove(pStack, pos, cQueen, c, p); } } 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]); } // // board_representation/MOVEGEN_MIGRATION.md section 6a Phase 2: // bitboard equivalent of SaveMeQueen -- two magic lookups ORed // together, same as _GenerateQueenBB, ANDed with bbTargetMask. // void _SaveMeQueenBB(IN MOVE_STACK *pStack, IN POSITION *pos, IN COOR cQueen, IN COOR cKing, IN BITBOARD bbTargetMask) /** Routine description: Bitboard equivalent of SaveMeQueen -- called in place of it (via a direct, statically-known call, not JumpTable) when GENERATE_ESCAPES_BLOCK_BITBOARD is defined. Parameters: MOVE_STACK *pStack : the move stack (bbFriendlyOccupied and bbOccupied must already be set) POSITION *pos : the board position COOR cQueen : the queen's location COOR cKing : the friendly king's location BITBOARD bbTargetMask : squares that resolve the lone check -- see _ComputeCheckTargetMaskBB Return value: void **/ { BITBOARD bbDest = (_RookAttacksBB(cQueen, pStack->bbOccupied) | _BishopAttacksBB(cQueen, pStack->bbOccupied)) & ~pStack->bbFriendlyOccupied & bbTargetMask; ULONG uBitIndex; COOR c, cExposed; PIECE p; ASSERT(InCheck(pos, pos->uToMove)); ASSERT(IS_QUEEN(pos->rgSquare[cQueen].pPiece)); ASSERT(GET_COLOR(pos->rgSquare[cQueen].pPiece) == pos->uToMove); while (bbDest) { uBitIndex = FastFirstBit(bbDest) - 1; bbDest &= (bbDest - 1); c = BIT_NUMBER_TO_COOR(uBitIndex); cExposed = ExposesCheck(pos, cQueen, cKing); if (!IS_ON_BOARD(cExposed) || (cExposed == c)) { p = pos->rgSquare[c].pPiece; _AddNormalMove(pStack, pos, cQueen, c, p); } } } 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); } } // // board_representation/MOVEGEN_MIGRATION.md section 3 step 2: bitboard // king generator, normal (non-castling) moves only -- castling stays // mailbox per section 1's explicit non-goal (at most 2 candidate // moves, checked via simple square-emptiness tests, not // ray-walk-shaped, nothing for a bitboard to speed up). Serves both // JumpTable slots the same way _GenerateKnightBB does, for the same // reason (GenerateWhiteKing's GET_COLOR(p)==BLACK bit trick was a // mailbox-only micro-optimization); the castling tail below still // branches on color since CASTLE_BLACK_*/CASTLE_WHITE_* and their // associated squares genuinely differ per side. // void _GenerateKingBB(IN MOVE_STACK *pStack, IN POSITION *pos, IN COOR cKing) /** Routine description: Bitboard equivalent of GenerateBlackKing/GenerateWhiteKing's normal (non-castling) move enumeration -- called by GenerateMoves' JumpTable in place of both when GENERATE_KING_BITBOARD is defined. Produces the exact same pseudo-legal move set as the mailbox pair, castling included (via the same mailbox logic those functions use, verbatim) -- see MOVEGEN_MIGRATION.md section 1's explicit non-goal against changing over-generation behavior. Relies on pStack->bbFriendlyOccupied already being set by the caller, same as _GenerateKnightBB -- see that function's header comment and MOVE_STACK's field comment in chess.h. Parameters: MOVE_STACK *pStack : the move stack (bbFriendlyOccupied must already be set for pos->uToMove) POSITION *pos : the board position COOR cKing : the king's location Return value: void **/ { BITBOARD bbDest = g_KingAttacksBB[cKing] & ~pStack->bbFriendlyOccupied; ULONG uBitIndex; COOR c; PIECE p; ASSERT(IS_KING(pos->rgSquare[cKing].pPiece)); ASSERT(GET_COLOR(pos->rgSquare[cKing].pPiece) == pos->uToMove); ASSERT(pStack->bbFriendlyOccupied == _BuildFriendlySideBB(pos, pos->uToMove)); while (bbDest) { uBitIndex = FastFirstBit(bbDest) - 1; bbDest &= (bbDest - 1); c = BIT_NUMBER_TO_COOR(uBitIndex); p = pos->rgSquare[c].pPiece; _AddNormalMove(pStack, pos, cKing, c, p); } // // Castling: unchanged mailbox logic, copied verbatim from // GenerateBlackKing/GenerateWhiteKing -- see those functions' // comments. Not in scope for a bitboard rewrite (section 1). // if (pos->uToMove == BLACK) { if ((pos->bvCastleInfo & BLACK_CAN_CASTLE) == 0) return; #ifdef DEBUG ASSERT(IS_KING(pos->rgSquare[E8].pPiece)); ASSERT(cKing == E8); #endif 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); } } else { if ((pos->bvCastleInfo & WHITE_CAN_CASTLE) == 0) return; #ifdef DEBUG ASSERT(IS_KING(pos->rgSquare[E1].pPiece)); ASSERT(cKing == E1); #endif 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); } } } } // // board_representation/MOVEGEN_MIGRATION.md section 3 step 5: bulk, // whole-side pawn generator using the classic shift-and-mask technique // (confirmed via ~/crafty/movgen.c to be the standard approach, not a // per-starting-square precomputed mask) rather than a per-square // lookup like the other five migrated piece types. Structurally // different for a real reason: pos->bbPawns[uSide]'s bits already // live in dense rank*8+file space (COOR_TO_BIT_NUMBER), so shifting // the *entire* bitboard by 8 moves every pawn of that side forward one // rank simultaneously -- no per-pawn loop needed to find destinations, // only to emit the resulting moves. // // This engine's square numbering has A8 = bit 0 (COOR_TO_BIT_NUMBER of // 0x88's A8 == 0x00), so rank number increases as the *row* (bits/8) // *decreases* -- opposite of Crafty's convention (confirmed via // GenerateWhitePawn's existing 0x88 deltas: -16 forward, -15/-17 // captures). Concretely, in bit-number space: // WHITE forward = row decreases = bb >> 8 // BLACK forward = row increases = bb << 8 // and the two diagonals per side are +-7/+-9 (one rank plus one file), // each requiring the *opposite* file's edge excluded first so a // same-row wraparound (e.g. an h-file pawn's ">>7" would otherwise // silently land back on the same row's a-file -- a real, silent-wrong- // answer trap, not just an out-of-range index) never happens -- see // each shift's comment below for which file it excludes and why. // // Double-push eligibility (rank 2 for White, rank 7 for Black) is // checked by masking the *already-computed single-push destination* // bitboard against BBRANK[3]/BBRANK[6] (did this pawn's single push // land on rank 3/6, which is only possible starting from rank 2/7) // rather than a per-square starting-rank table -- same technique // Crafty uses (movgen.c's padvances2, masking padvances1_all against // its own rank-3/rank-6 constant before the second shift). // // En passant is deliberately NOT folded into the bulk capture // bitboards -- it is exactly one specific square (pos->cEpSquare) at // most once per node, cheaper and less error-prone to check directly // (does either of the two diagonal-behind squares hold one of this // side's pawns) than to derive and mask a whole extra bitboard for an // event this rare. // void _GenerateAllPawnMovesBB(IN MOVE_STACK *pStack, IN POSITION *pos, IN ULONG uSide) /** Routine description: Bitboard equivalent of the GenerateWhitePawn/GenerateBlackPawn pair -- called in place of the per-pawn mailbox loop when GENERATE_PAWN_BITBOARD is defined, for the entire side's pawns in one call rather than once per pawn. Produces the exact same pseudo-legal move set (same over-generation behavior, no legal-awareness added) -- see MOVEGEN_MIGRATION.md section 1's explicit non-goal. Parameters: MOVE_STACK *pStack : the move stack POSITION *pos : the board position ULONG uSide : which side's pawns to generate for (pos->uToMove) Return value: void **/ { BITBOARD bbPawns = pos->bbPawns[uSide]; BITBOARD bbOccupied = _BuildFullOccupiedBB(pos); BITBOARD bbEmpty = ~bbOccupied; BITBOARD bbEnemy = bbOccupied & ~_BuildFriendlySideBB(pos, uSide); BITBOARD bbSinglePush, bbDoublePush, bbCapLeft, bbCapRight, bb; ULONG uBitIndex; COOR cTo, cFrom, cEp; PIECE p; if (uSide == WHITE) { bbSinglePush = (bbPawns >> 8) & bbEmpty; bbDoublePush = ((bbSinglePush & BBRANK[3]) >> 8) & bbEmpty; // "Left" diagonal (file-1, i.e. 0x88's -17): exclude file A // (file-1 invalid/wraps for an a-file pawn). bbCapLeft = ((bbPawns & ~BBFILE[0]) >> 9) & bbEnemy; // "Right" diagonal (file+1, i.e. 0x88's -15): exclude file H. bbCapRight = ((bbPawns & ~BBFILE[7]) >> 7) & bbEnemy; } else { ASSERT(uSide == BLACK); bbSinglePush = (bbPawns << 8) & bbEmpty; bbDoublePush = ((bbSinglePush & BBRANK[6]) << 8) & bbEmpty; // "Left" diagonal (file-1, 0x88's +15): exclude file A. bbCapLeft = ((bbPawns & ~BBFILE[0]) << 7) & bbEnemy; // "Right" diagonal (file+1, 0x88's +17): exclude file H. bbCapRight = ((bbPawns & ~BBFILE[7]) << 9) & bbEnemy; } // Single push (+ promotion if landing on the far rank). bb = bbSinglePush; while (bb) { uBitIndex = FastFirstBit(bb) - 1; bb &= (bb - 1); cTo = BIT_NUMBER_TO_COOR(uBitIndex); cFrom = (uSide == WHITE) ? BIT_NUMBER_TO_COOR(uBitIndex + 8) : BIT_NUMBER_TO_COOR(uBitIndex - 8); ASSERT(IS_PAWN(pos->rgSquare[cFrom].pPiece)); if (RANK8(cTo) || RANK1(cTo)) { _AddPromote(pStack, pos, cFrom, cTo); } else { _AddNormalMove(pStack, pos, cFrom, cTo, 0); } } // Double push -- never a promotion (rank 4/5 destination only). bb = bbDoublePush; while (bb) { uBitIndex = FastFirstBit(bb) - 1; bb &= (bb - 1); cTo = BIT_NUMBER_TO_COOR(uBitIndex); cFrom = (uSide == WHITE) ? BIT_NUMBER_TO_COOR(uBitIndex + 16) : BIT_NUMBER_TO_COOR(uBitIndex - 16); ASSERT(IS_PAWN(pos->rgSquare[cFrom].pPiece)); _AddDoubleJump(pStack, pos, cFrom, cTo); } // Capture left (+ promotion if landing on the far rank). bb = bbCapLeft; while (bb) { uBitIndex = FastFirstBit(bb) - 1; bb &= (bb - 1); cTo = BIT_NUMBER_TO_COOR(uBitIndex); cFrom = (uSide == WHITE) ? BIT_NUMBER_TO_COOR(uBitIndex + 9) : BIT_NUMBER_TO_COOR(uBitIndex - 7); ASSERT(IS_PAWN(pos->rgSquare[cFrom].pPiece)); p = pos->rgSquare[cTo].pPiece; ASSERT(!IS_EMPTY(p) && OPPOSITE_COLORS(p, pos->rgSquare[cFrom].pPiece)); if (RANK8(cTo) || RANK1(cTo)) { _AddPromote(pStack, pos, cFrom, cTo); } else { _AddNormalMove(pStack, pos, cFrom, cTo, p); } } // Capture right (+ promotion if landing on the far rank). bb = bbCapRight; while (bb) { uBitIndex = FastFirstBit(bb) - 1; bb &= (bb - 1); cTo = BIT_NUMBER_TO_COOR(uBitIndex); cFrom = (uSide == WHITE) ? BIT_NUMBER_TO_COOR(uBitIndex + 7) : BIT_NUMBER_TO_COOR(uBitIndex - 9); ASSERT(IS_PAWN(pos->rgSquare[cFrom].pPiece)); p = pos->rgSquare[cTo].pPiece; ASSERT(!IS_EMPTY(p) && OPPOSITE_COLORS(p, pos->rgSquare[cFrom].pPiece)); if (RANK8(cTo) || RANK1(cTo)) { _AddPromote(pStack, pos, cFrom, cTo); } else { _AddNormalMove(pStack, pos, cFrom, cTo, p); } } // En passant -- deliberately not bulk (see block comment above): // check the (at most 2) squares diagonally behind pos->cEpSquare // for one of this side's pawns, exactly like the mailbox // functions' cTo == pos->cEpSquare check, just run once per side // per node instead of once per pawn. cEp = pos->cEpSquare; if (IS_ON_BOARD(cEp)) { int iBehindDelta = (uSide == WHITE) ? 16 : -16; cFrom = cEp + iBehindDelta - 1; if (IS_ON_BOARD(cFrom) && IS_PAWN(pos->rgSquare[cFrom].pPiece) && (GET_COLOR(pos->rgSquare[cFrom].pPiece) == uSide)) { _AddEnPassant(pStack, pos, cFrom, cEp); } cFrom = cEp + iBehindDelta + 1; if (IS_ON_BOARD(cFrom) && IS_PAWN(pos->rgSquare[cFrom].pPiece) && (GET_COLOR(pos->rgSquare[cFrom].pPiece) == uSide)) { _AddEnPassant(pStack, pos, cFrom, cEp); } } } 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); } } } } // // board_representation/MOVEGEN_MIGRATION.md section 6a Phase 2: bulk // whole-side pawn escape generator, same shift-and-mask technique as // _GenerateAllPawnMovesBB, with each move-category bitboard ANDed // against bbTargetMask before extraction and an ExposesCheck filter // added per surviving candidate (the mailbox SaveMeWhitePawn/ // SaveMeBlackPawn pair calls ExposesCheck per move too -- see section // 6a's "what does not change"). En passant is NOT covered by // bbTargetMask (a between-squares/capture-square mask has no way to // express "the checking pawn happens to be capturable en passant") -- // kept as the same narrow direct special case the mailbox functions // use: only relevant when the double-jumping pawn *is* the checker. // void _SaveMeAllPawnMovesBB(IN MOVE_STACK *pStack, IN POSITION *pos, IN ULONG uSide, IN COOR cKing, IN COOR cAttacker, IN BITBOARD bbTargetMask) /** Routine description: Bitboard equivalent of the SaveMeWhitePawn/SaveMeBlackPawn pair -- called in place of the per-pawn mailbox loop when GENERATE_ESCAPES_BLOCK_BITBOARD is defined, for the entire side's pawns in one call. Parameters: MOVE_STACK *pStack : the move stack POSITION *pos : the board position ULONG uSide : which side's pawns to generate for (pos->uToMove) COOR cKing : the friendly king's location COOR cAttacker : the lone checker's location BITBOARD bbTargetMask : squares that resolve the lone check -- see _ComputeCheckTargetMaskBB Return value: void **/ { BITBOARD bbPawns = pos->bbPawns[uSide]; BITBOARD bbOccupied = _BuildFullOccupiedBB(pos); BITBOARD bbEmpty = ~bbOccupied; BITBOARD bbEnemy = bbOccupied & ~_BuildFriendlySideBB(pos, uSide); BITBOARD bbSinglePush, bbDoublePush, bbCapLeft, bbCapRight, bb; ULONG uBitIndex; COOR cTo, cFrom, cExposed; PIECE p; if (uSide == WHITE) { bbSinglePush = (bbPawns >> 8) & bbEmpty; bbDoublePush = ((bbSinglePush & BBRANK[3]) >> 8) & bbEmpty; bbCapLeft = ((bbPawns & ~BBFILE[0]) >> 9) & bbEnemy; bbCapRight = ((bbPawns & ~BBFILE[7]) >> 7) & bbEnemy; } else { ASSERT(uSide == BLACK); bbSinglePush = (bbPawns << 8) & bbEmpty; bbDoublePush = ((bbSinglePush & BBRANK[6]) << 8) & bbEmpty; bbCapLeft = ((bbPawns & ~BBFILE[0]) << 7) & bbEnemy; bbCapRight = ((bbPawns & ~BBFILE[7]) << 9) & bbEnemy; } // Every move category is ANDed against bbTargetMask -- see this // function's header comment for why that's sufficient (a push // destination is only ever in bbTargetMask if it's a genuine block // square, since bbTargetMask's non-capture bits are, by // construction, empty squares; a capture destination is only ever // in bbTargetMask if it's the checker's own square, since // between-squares are empty and captures already require bbEnemy). bbSinglePush &= bbTargetMask; bbDoublePush &= bbTargetMask; bbCapLeft &= bbTargetMask; bbCapRight &= bbTargetMask; bb = bbSinglePush; while (bb) { uBitIndex = FastFirstBit(bb) - 1; bb &= (bb - 1); cTo = BIT_NUMBER_TO_COOR(uBitIndex); cFrom = (uSide == WHITE) ? BIT_NUMBER_TO_COOR(uBitIndex + 8) : BIT_NUMBER_TO_COOR(uBitIndex - 8); cExposed = ExposesCheck(pos, cFrom, cKing); if (!IS_ON_BOARD(cExposed) || (cExposed == cTo)) { if (RANK8(cTo) || RANK1(cTo)) { _AddPromote(pStack, pos, cFrom, cTo); } else { _AddNormalMove(pStack, pos, cFrom, cTo, 0); } } } bb = bbDoublePush; while (bb) { uBitIndex = FastFirstBit(bb) - 1; bb &= (bb - 1); cTo = BIT_NUMBER_TO_COOR(uBitIndex); cFrom = (uSide == WHITE) ? BIT_NUMBER_TO_COOR(uBitIndex + 16) : BIT_NUMBER_TO_COOR(uBitIndex - 16); cExposed = ExposesCheck(pos, cFrom, cKing); if (!IS_ON_BOARD(cExposed) || (cExposed == cTo)) { _AddDoubleJump(pStack, pos, cFrom, cTo); } } bb = bbCapLeft; while (bb) { uBitIndex = FastFirstBit(bb) - 1; bb &= (bb - 1); cTo = BIT_NUMBER_TO_COOR(uBitIndex); cFrom = (uSide == WHITE) ? BIT_NUMBER_TO_COOR(uBitIndex + 9) : BIT_NUMBER_TO_COOR(uBitIndex - 7); cExposed = ExposesCheck(pos, cFrom, cKing); if (!IS_ON_BOARD(cExposed) || (cExposed == cAttacker)) { p = pos->rgSquare[cTo].pPiece; if (RANK8(cTo) || RANK1(cTo)) { _AddPromote(pStack, pos, cFrom, cTo); } else { _AddNormalMove(pStack, pos, cFrom, cTo, p); } } } bb = bbCapRight; while (bb) { uBitIndex = FastFirstBit(bb) - 1; bb &= (bb - 1); cTo = BIT_NUMBER_TO_COOR(uBitIndex); cFrom = (uSide == WHITE) ? BIT_NUMBER_TO_COOR(uBitIndex + 7) : BIT_NUMBER_TO_COOR(uBitIndex - 9); cExposed = ExposesCheck(pos, cFrom, cKing); if (!IS_ON_BOARD(cExposed) || (cExposed == cAttacker)) { p = pos->rgSquare[cTo].pPiece; if (RANK8(cTo) || RANK1(cTo)) { _AddPromote(pStack, pos, cFrom, cTo); } else { _AddNormalMove(pStack, pos, cFrom, cTo, p); } } } // // En passant: only relevant when the double-jumping enemy pawn // *is* the checker -- there is no way to block check with an en // passant capture (see SaveMeWhitePawn/SaveMeBlackPawn's identical // comment). White defender: cAttacker == cEpSquare + 16. Black // defender: cAttacker == cEpSquare - 16. // if (IS_ON_BOARD(pos->cEpSquare)) { COOR cEp = pos->cEpSquare; int iBehindDelta = (uSide == WHITE) ? 16 : -16; FLAG fEpResolvesCheck = (uSide == WHITE) ? (cAttacker == cEp + 16) : (cAttacker == cEp - 16); if (fEpResolvesCheck) { cFrom = cEp + iBehindDelta - 1; if (IS_ON_BOARD(cFrom) && IS_PAWN(pos->rgSquare[cFrom].pPiece) && (GET_COLOR(pos->rgSquare[cFrom].pPiece) == uSide)) { _AddEnPassant(pStack, pos, cFrom, cEp); } cFrom = cEp + iBehindDelta + 1; if (IS_ON_BOARD(cFrom) && IS_PAWN(pos->rgSquare[cFrom].pPiece) && (GET_COLOR(pos->rgSquare[cFrom].pPiece) == uSide)) { _AddEnPassant(pStack, pos, cFrom, cEp); } } } } 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__); } // Non-static (unlike its historical internal-only status) so // testgenerate.c's whole-node dispatch benchmark can call it directly // by name -- see _GenerateAllMovesBB's block comment for why that // comparison needs both functions callable under their real names in // a toggle-free build. 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) // MOVEGEN_MIGRATION.md section 6 toggle -- one #define per // piece type, independent of the others. _GenerateKnightBB // serves both slots; see its header comment for why the // mailbox pair's color split doesn't carry over to bitboards. #if defined(GENERATE_KNIGHT_BITBOARD) _GenerateKnightBB, // 4 (BLACK_KNIGHT) _GenerateKnightBB, // 5 (WHITE_KNIGHT) #else GenerateKnight, // 4 (BLACK_KNIGHT) GenerateWhiteKnight, // 5 (WHITE_KNIGHT) #endif #if defined(GENERATE_BISHOP_BITBOARD) _GenerateBishopBB, // 6 (BLACK_BISHOP) _GenerateBishopBB, // 7 (WHITE_BISHOP) #else GenerateBishop, // 6 (BLACK_BISHOP) GenerateBishop, // 7 (WHITE_BISHOP) #endif #if defined(GENERATE_ROOK_BITBOARD) _GenerateRookBB, // 8 (BLACK_ROOK) _GenerateRookBB, // 9 (WHITE_ROOK) #else GenerateRook, // 8 (BLACK_ROOK) GenerateRook, // 9 (WHITE_ROOK) #endif #if defined(GENERATE_QUEEN_BITBOARD) _GenerateQueenBB, // 10 (BLACK_QUEEN) _GenerateQueenBB, // 11 (WHITE_QUEEN) #else GenerateQueen, // 10 (BLACK_QUEEN) GenerateQueen, // 11 (WHITE_QUEEN) #endif #if defined(GENERATE_KING_BITBOARD) _GenerateKingBB, // 12 (BLACK_KING) _GenerateKingBB // 13 (WHITE_KING) #else GenerateBlackKing, // 12 (BLACK_KING) GenerateWhiteKing // 13 (WHITE_KING) #endif }; ULONG u; #ifdef DEBUG PIECE p; #endif // See MOVE_STACK's bbFriendlyOccupied field comment (chess.h) and // _GenerateKnightBB's header comment: computed once per node here, // before any piece-type dispatch, so every bitboard-backed // generator invoked below shares this build instead of each // recomputing it -- extend this #if with each new // GENERATE_*_BITBOARD toggle as piece types migrate. #if defined(GENERATE_KNIGHT_BITBOARD) || defined(GENERATE_KING_BITBOARD) || \ defined(GENERATE_ROOK_BITBOARD) || defined(GENERATE_BISHOP_BITBOARD) || \ defined(GENERATE_QUEEN_BITBOARD) pStack->bbFriendlyOccupied = _BuildFriendlySideBB(pos, pos->uToMove); #endif #if defined(GENERATE_ROOK_BITBOARD) || defined(GENERATE_BISHOP_BITBOARD) || \ defined(GENERATE_QUEEN_BITBOARD) pStack->bbOccupied = _BuildFullOccupiedBB(pos); #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 defined(GENERATE_PAWN_BITBOARD) _GenerateAllPawnMovesBB(pStack, pos, pos->uToMove); #else 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); } } #endif } // // board_representation/MOVEGEN_MIGRATION.md section 3: fully // bitboard-driven alternative to _GenerateAllMoves, forked at this // level (not folded into _GenerateAllMoves's own JumpTable-based body // via an #if) specifically to eliminate _GenerateAllMoves's own // indirect-call dispatch, not just to swap which per-piece-type // function gets called. // // _GenerateAllMoves's cNonPawns[side][] loop is a flat list mixing all // non-pawn piece types together (pieces are added/removed via // swap-with-last, so there is no contiguous per-type range to slice) // -- that mixed ordering is *why* it needs // JumpTable[pos->rgSquare[c].pPiece], an indirect call whose target // changes almost every iteration as the loop walks across different // piece types, close to the worst case for a CPU's indirect-branch // predictor. Every per-piece-type speed benchmark in this migration // (testgenerate.c's TestGenerateKnightSpeed and friends) called its // _Generate*BB function directly, bypassing JumpTable entirely -- so // none of those numbers ever measured, or could benefit from // removing, this dispatch cost. This function is the piece that // actually exercises that question: pos->bbPieces[side][KNIGHT/ // BISHOP/ROOK/QUEEN] already partitions squares by type (unlike // cNonPawns), so each piece type gets its own bit-extraction loop // calling its specific _Generate*BB function BY NAME -- a // statically-known, likely-inlinable direct call, no function pointer // anywhere in this function. // // Only exists (and is only substituted in for _GenerateAllMoves, see // the #define below) when every non-pawn, non-castling piece type's // bitboard toggle is defined -- a partial-rollout mix (e.g. knight and // king migrated, rook/bishop/queen not yet) still needs // _GenerateAllMoves's cNonPawns/JumpTable path, since that path is the // only one that knows how to fall back to a still-mailbox piece type // while also correctly finding already-migrated ones by iterating the // same mixed list. This function does not attempt to support that // mixed case -- see MOVEGEN_MIGRATION.md for why an all-or-nothing // fork was chosen over threading partial-rollout support through this // function too. // void _GenerateAllMovesBB(IN MOVE_STACK *pStack, IN POSITION *pos) /** Routine description: Fully bitboard-driven equivalent of _GenerateAllMoves -- see the block comment above. Produces the exact same pseudo-legal move set (same over-generation behavior, no legal-awareness added, and no change to which moves are generated, only how the dispatch to each piece type's generator happens) -- see MOVEGEN_MIGRATION.md section 1's explicit non-goal. Parameters: MOVE_STACK *pStack : the move stack POSITION *pos : the board position Return value: static void **/ { ULONG uSide = pos->uToMove; BITBOARD bb; ULONG uBitIndex; COOR c; #if !defined(GENERATE_PAWN_BITBOARD) ULONG u; #endif #if defined(DEBUG) && !defined(GENERATE_PAWN_BITBOARD) PIECE p; #endif pStack->bbFriendlyOccupied = _BuildFriendlySideBB(pos, uSide); pStack->bbOccupied = _BuildFullOccupiedBB(pos); bb = pos->bbPieces[uSide][KNIGHT]; while (bb) { uBitIndex = FastFirstBit(bb) - 1; bb &= (bb - 1); c = BIT_NUMBER_TO_COOR(uBitIndex); ASSERT(IS_KNIGHT(pos->rgSquare[c].pPiece)); _GenerateKnightBB(pStack, pos, c); } bb = pos->bbPieces[uSide][BISHOP]; while (bb) { uBitIndex = FastFirstBit(bb) - 1; bb &= (bb - 1); c = BIT_NUMBER_TO_COOR(uBitIndex); ASSERT(IS_BISHOP(pos->rgSquare[c].pPiece)); _GenerateBishopBB(pStack, pos, c); } bb = pos->bbPieces[uSide][ROOK]; while (bb) { uBitIndex = FastFirstBit(bb) - 1; bb &= (bb - 1); c = BIT_NUMBER_TO_COOR(uBitIndex); ASSERT(IS_ROOK(pos->rgSquare[c].pPiece)); _GenerateRookBB(pStack, pos, c); } bb = pos->bbPieces[uSide][QUEEN]; while (bb) { uBitIndex = FastFirstBit(bb) - 1; bb &= (bb - 1); c = BIT_NUMBER_TO_COOR(uBitIndex); ASSERT(IS_QUEEN(pos->rgSquare[c].pPiece)); _GenerateQueenBB(pStack, pos, c); } // King has no bitboard of its own (a single square, cNonPawns[ // side][0] -- see POSITION's bbPieces field comment in chess.h for // why a bitboard would add nothing here); still a direct, // statically-known call, same as the four loops above. c = pos->cNonPawns[uSide][0]; ASSERT(IS_KING(pos->rgSquare[c].pPiece)); _GenerateKingBB(pStack, pos, c); // Pawns: unchanged from _GenerateAllMoves -- not in scope for this // migration (section 3 step 5's pawn note) unless // GENERATE_PAWN_BITBOARD is also defined, in which case pawns get // the same bulk treatment via _GenerateAllPawnMovesBB -- pawns' // own toggle is independent of the five above (section 6). #if defined(GENERATE_PAWN_BITBOARD) _GenerateAllPawnMovesBB(pStack, pos, uSide); #else if (uSide == 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) == uSide); #endif GenerateBlackPawn(pStack, pos, c); } } else { ASSERT(uSide == 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) == uSide); #endif GenerateWhitePawn(pStack, pos, c); } } #endif } // Whole-dispatch fork -- see _GenerateAllMovesBB's block comment for // why this is a #define swap of the entire function (matching // chess.h's GetAttacks precedent) rather than a branch nested inside // _GenerateAllMoves. Only fires when every non-pawn, non-castling // piece type is bitboard-backed; any partial mix still uses // _GenerateAllMoves's cNonPawns/JumpTable path unchanged. #if defined(GENERATE_KNIGHT_BITBOARD) && defined(GENERATE_KING_BITBOARD) && \ defined(GENERATE_ROOK_BITBOARD) && defined(GENERATE_BISHOP_BITBOARD) && \ defined(GENERATE_QUEEN_BITBOARD) #define _GenerateAllMoves _GenerateAllMovesBB #endif 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 **/ { #if !defined(GENERATE_ESCAPES_KING_BITBOARD) || !defined(GENERATE_ESCAPES_BLOCK_BITBOARD) ULONG u; #endif #if !defined(GENERATE_ESCAPES_KING_BITBOARD) ULONG v; #endif COOR c; #if !defined(GENERATE_ESCAPES_BLOCK_BITBOARD) COOR cDefender; #endif PIECE p; PIECE pKing; COOR cKing = pos->cNonPawns[pos->uToMove][0]; #if !defined(GENERATE_ESCAPES_KING_BITBOARD) int iIndex; #endif SEE_LIST rgCheckers; #if !defined(GENERATE_ESCAPES_KING_BITBOARD) int iDelta; #endif ULONG uReturn = 0; #if !defined(GENERATE_ESCAPES_BLOCK_BITBOARD) 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 }; #endif 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)); #if defined(GENERATE_ESCAPES_KING_BITBOARD) // // board_representation/MOVEGEN_MIGRATION.md section 6a Phase 1: // g_KingAttacksBB gives every candidate flight square in one // lookup (already excludes friendly-occupied squares); the // mailbox version's manual per-checker x-ray loop below is // replaced entirely by testing _WhoAttacksSquareBB against // occupancy with the king itself removed -- a slider whose ray // was only blocked by the king's own (pre-move) body now correctly // shows up as attacking a candidate square still on that ray, // exactly the case the manual loop existed to catch by hand. // Pawns are checked separately since _WhoAttacksSquareBB // deliberately excludes them (see its header comment). { ULONG uEnemy = FLIP(pos->uToMove); // pKing is only used inside ASSERTs below, which vanish in a // non-DEBUG build -- silence the resulting "set but not used" // warning explicitly rather than leave it looking accidental. (void)pKing; BITBOARD bbFriendly = _BuildFriendlySideBB(pos, pos->uToMove); BITBOARD bbOccupiedWithoutKing = _BuildFullOccupiedBB(pos) & ~COOR_TO_BB(cKing); BITBOARD bbDest = g_KingAttacksBB[cKing] & ~bbFriendly; ULONG uBitIndex; while (bbDest) { uBitIndex = FastFirstBit(bbDest) - 1; bbDest &= (bbDest - 1); c = BIT_NUMBER_TO_COOR(uBitIndex); p = pos->rgSquare[c].pPiece; ASSERT(IS_EMPTY(p) || OPPOSITE_COLORS(p, pKing)); if ((0 == _WhoAttacksSquareBB(pos, c, uEnemy, bbOccupiedWithoutKing)) && (0 == (g_PawnAttackOriginBB[uEnemy][c] & pos->bbPawns[uEnemy]))) { _AddNormalMove(pStack, pos, cKing, c, p); uReturn += 0x00010000; } } } #else 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: ; } #endif // // 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; #if defined(GENERATE_ESCAPES_BLOCK_BITBOARD) // // board_representation/MOVEGEN_MIGRATION.md section 6a Phase 2: // pos->cNonPawns[side][] mixes every non-pawn piece type together // (same reason as _GenerateAllMoves's own loop -- no contiguous // per-type range to slice), which is why the mailbox path above // needs JumpTable[p], an indirect call whose target changes almost // every iteration -- close to the worst case for a CPU's // indirect-branch predictor. pos->bbPieces[side][KNIGHT/BISHOP/ // ROOK/QUEEN] sidesteps this exactly like _GenerateAllMovesBB did: // each piece type gets its own bit-extraction loop calling its // specific _SaveMe*BB function BY NAME, no function pointer // anywhere in this block. { BITBOARD bbTargetMask; BITBOARD bb; ULONG uBitIndex; COOR cDef; // Unlike _GenerateAllMoves, GENERATE_ESCAPES's call site never // precomputes these -- set them here, once, for every // _SaveMe*BB call below to share (same amortization reasoning // as _GenerateAllMoves's own precompute block). pStack->bbFriendlyOccupied = _BuildFriendlySideBB(pos, pos->uToMove); pStack->bbOccupied = _BuildFullOccupiedBB(pos); bbTargetMask = _ComputeCheckTargetMaskBB(cKing, c, pStack->bbOccupied); bb = pos->bbPieces[pos->uToMove][KNIGHT]; while (bb) { uBitIndex = FastFirstBit(bb) - 1; bb &= (bb - 1); cDef = BIT_NUMBER_TO_COOR(uBitIndex); _SaveMeKnightBB(pStack, pos, cDef, cKing, bbTargetMask); } bb = pos->bbPieces[pos->uToMove][BISHOP]; while (bb) { uBitIndex = FastFirstBit(bb) - 1; bb &= (bb - 1); cDef = BIT_NUMBER_TO_COOR(uBitIndex); _SaveMeBishopBB(pStack, pos, cDef, cKing, bbTargetMask); } bb = pos->bbPieces[pos->uToMove][ROOK]; while (bb) { uBitIndex = FastFirstBit(bb) - 1; bb &= (bb - 1); cDef = BIT_NUMBER_TO_COOR(uBitIndex); _SaveMeRookBB(pStack, pos, cDef, cKing, bbTargetMask); } bb = pos->bbPieces[pos->uToMove][QUEEN]; while (bb) { uBitIndex = FastFirstBit(bb) - 1; bb &= (bb - 1); cDef = BIT_NUMBER_TO_COOR(uBitIndex); _SaveMeQueenBB(pStack, pos, cDef, cKing, bbTargetMask); } _SaveMeAllPawnMovesBB(pStack, pos, pos->uToMove, cKing, c, bbTargetMask); } #else 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); } } #endif 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. Full move-ordering hierarchy for a normal (not-in-check) node, from highest-scored to lowest -- "vNext", the dynamic-move-ordering overhaul from the 2026-08-29 session (see CLAUDE.md's "Dynamic move ordering experiments" section for the methodology behind it): 1. Hash move -- already handled by Search(), never (re)generated here; excluded from this list entirely. 2. Killer that also threatens/delivers mate -- FIRST_KILLER (or whichever killer slot matched) OR'd with SORT_THESE_FIRST. 3. Winning/even captures & promotions -- SORT_THESE_FIRST, MVV/LVA tiebreak; strictly-winning-by-raw-material trades skip SEE, an even or ambiguous trade (or any promotion) gets the full exchange walk. 4. Killers, this ply's slot 0/1, then ply-2's slot 0/1 (Crafty-style ordering, this ply's own pair before either ply-2-back one) -- FIRST_KILLER/SECOND_KILLER/THIRD_KILLER/FOURTH_KILLER. 5. A countermove-table match (exact move, keyed by whatever the opponent just played) *whose own accumulated history+ continuation-history evidence clears COUNTERMOVE_EVIDENCE_ THRESHOLD* -- COUNTERMOVE_TIER_BONUS, placed below both ply-2 killer slots (conservative default; never validated as deserving to outrank them). An *unevidenced* match gets no special treatment at all and falls through to tier 6 -- see chess.h's COUNTERMOVE_TIER_BONUS/COUNTERMOVE_EVIDENCE_THRESHOLD comments for why the promotion is evidence-gated rather than automatic on a bare match. 6. GOOD_MOVE boundary. Below this, "leftover" (see search.c's fIsLeftoverMove) -- eligible for EFP pruning, but every leftover is still fully ranked via SelectBestWithHistory (movesup.c); the old NumLeftoverMovesToSelect depth-indexed selection budget was retired once evidence showed the leftover pool has real, findable signal a bailout was discarding. An ordinary leftover quiet move's score is: PSQT (g_iPSQT[piece][to], 0..1000) + g_HistoryCounters[piece][to] (classic butterfly history, (depth+1)^2 growth on fail-high, decays on a miss or global aging pass) + CONTINUATION_SCALE * g_ContinuationHistory[(prev move, this move)] (same growth/decay math as history, additionally keyed by the previous move -- self-calibrating, no magic constant needed; CONTINUATION_SCALE=1 found flat/sufficient across a 256x sweep) + FLEE_BONUS if this move's origin square is currently en prise (flat same-tier nudge; the old unconditional GOOD_ MOVE-tier promotion for these moves was retired after evidence-calibration showed most such moves, unbacked by real track record, perform identically to an ordinary leftover -- see the RETIRED comment below). 7. Losing captures -- negative, SEE-verified. 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; #ifdef DEBUG MOVE_STACK_MOVE_VALUE_FLAGS mvf; #endif ULONG uHashMoveLoc = (ULONG)-1; #ifdef DEBUG ULONG uColor = pos->uToMove; #endif PRECOMP_KILLERS sKillers[4]; ULONG uCounterMoveIdx = 0; ULONG uCounterMoveContKey = 0; FLAG fHaveCounterMove = FALSE; // // 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. Crafty-style ordering: both of this // ply's own killers before either ply-2-back one. (Reverted twice // before -- see git history -- but this pass is on top of both // NumLeftoverMovesToSelect and the mvNullmoveQuietRefutations fix // (dynamic.c/searchsup.c), and beats the interleaved order (this // ply's killer1, ply-2's killer1, this ply's killer2, ply-2's // killer2) head-to-head on every metric with the fix applied to // both: more solves, fewer nodes, equal-or-higher first-move beta // cutoff on 2 of 3 curated suites. Both orderings lose first-move // cutoff rate vs. head_reference once the backfill is added -- that // appears to be a cost of the backfill itself, not of tier order -- // but Crafty order is the one where the backfilled data lands in a // tier (this ply's own killer[1], promoted to SECOND_KILLER here) // that's otherwise structurally almost always empty, so it's pure // upside there; under interleaved order the same backfill instead // lands in THIRD_KILLER, behind two already-real proven killers, // where it appears to cost more (misordering) than it gives.) // sKillers[0].mv = ctx->mvKiller[uPly][0]; sKillers[0].uBonus = FIRST_KILLER; sKillers[1].mv = ctx->mvKiller[uPly][1]; sKillers[1].uBonus = SECOND_KILLER; sKillers[2].mv.uMove = sKillers[3].mv.uMove = 0; if (uPly > 1) { sKillers[2].mv = ctx->mvKiller[uPly - 2][0]; sKillers[2].uBonus = THIRD_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)); // EXPERIMENT: countermove-match tier. Precompute the previous // move's countermove-table index once per node (mirrors killer // precompute above) so the per-move loop below is just an // IS_SAME_MOVE check, not a recompute. fHaveCounterMove = FALSE; if ((uPly > 0) && (0 != (ctx->sPlyInfo[uPly - 1]).mv.uMove)) { uCounterMoveIdx = MOVE_TO_INDEX((ctx->sPlyInfo[uPly - 1]).mv); uCounterMoveContKey = MOVE_TO_CONT_KEY((ctx->sPlyInfo[uPly - 1]).mv); fHaveCounterMove = TRUE; } // // 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 // pStack->mvf[u].bvFlags &= ~(MVF_SEE_KNOWN | MVF_SEE_NONNEGATIVE); 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); pStack->mvf[u].bvFlags |= MVF_SEE_KNOWN | ((s >= 0) ? MVF_SEE_NONNEGATIVE : 0); } 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); // RETIRED: hung-piece-escape used to get an unconditional // (GOOD_MOVE + PIECE_VALUE/2) promotion here for any move // whose origin square was flagged en-prise, regardless of // any track record. Evidence-calibration data showed the // overwhelming majority of triggers (the "zero accumulated // history/continuation evidence" bucket -- 250-1000x more // populous than the equivalent countermove-match bucket) // had a fail-high rate statistically identical to an // ordinary, unprivileged leftover move (~0.22-0.25% vs. // ~0.19-0.21% baseline). The escape motif alone, with no // verification the destination is actually safe or the // threat was real, isn't a trustworthy enough signal to // justify an unconditional tier promotion -- unlike // killers (self-evidencing by construction) or a // sufficiently-evidenced countermove match. Retired // rather than evidence-gated: a well-evidenced escape // still gets ranked via the existing, already-validated // history/continuation scoring below, same as any other // leftover -- no separate mechanism needed for that case. // Countermove-match tier, evidence-gated -- see chess.h's // COUNTERMOVE_TIER_BONUS/COUNTERMOVE_EVIDENCE_THRESHOLD // comment. Calibration data showed a raw match, with no // track record, performs identically to an ordinary // leftover (~0.6-0.85% FH) -- promoting on match alone // repeats hung-piece-escape's mistake. Only promote once // the same history+continuation evidence already used // to score ordinary leftovers clears a threshold where // it demonstrably beats killer-ply2's own average. // Written into iValue itself (not a selection-time-only // nudge) so a qualifying match actually escapes // GOOD_MOVE/leftover classification. if ((TRUE == fHaveCounterMove) && (IS_SAME_MOVE(mv, ctx->mvCounter[uCounterMoveIdx][0]) || IS_SAME_MOVE(mv, ctx->mvCounter[uCounterMoveIdx][1]))) { ULONG uCMEvidence = g_HistoryCounters[mv.pMoved][mv.cTo] + g_ContinuationHistory[(uCounterMoveContKey * CONT_KEY_RANGE) + MOVE_TO_CONT_KEY(mv)]; if (uCMEvidence >= COUNTERMOVE_EVIDENCE_THRESHOLD) { s |= COUNTERMOVE_TIER_BONUS; } } 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]); #ifdef DEBUG mvf = pStack->mvf[uHashMoveLoc]; #endif 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; #ifdef DEBUG MOVE_STACK_MOVE_VALUE_FLAGS mvf; #endif 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 // pStack->mvf[u].bvFlags &= ~(MVF_SEE_KNOWN | MVF_SEE_NONNEGATIVE); 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); pStack->mvf[u].bvFlags |= MVF_SEE_KNOWN | ((s >= 0) ? MVF_SEE_NONNEGATIVE : 0); } 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]); #ifdef DEBUG mvf = pStack->mvf[uHashMoveLoc]; #endif 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 = FindEnprisePiece(ctx, 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; #ifdef DEBUG ULONG uColor; #endif 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); #ifdef DEBUG uColor = pos->uToMove; #endif 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]; }