/** 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" // See eval.c's identical comment: CoorFromBitBoardRank8ToRank1 // (bitboard.c) is a real out-of-line extern call; this routes the // bitboard-scan loops added during the cNonPawns/cPawns retirement // (dead mailbox-fallback paths under this build's *_BITBOARD toggles, // but still worth keeping fast for other toggle combinations) to the // inlined FastCoorFromBitBoardRank8ToRank1 (chess.h) instead. #ifndef CROUTINES #define CoorFromBitBoardRank8ToRank1 FastCoorFromBitBoardRank8ToRank1 #endif // // Note: this order is important because of how EvalQueen works // const INT g_iQKDeltas[] = { -17, -16, -15, -1, +1, +17, +15, +16, 0 }; // board_representation/MOVEGEN_MIGRATION.md's never-started // _FindUnblockedSquares/WouldGiveCheck candidate. Membership (is this // square unblocked for the opposing king) is exactly the set of // squares the rook+bishop magic tables already reach from the king's // square, stopping at (and including) the first blocker in each of // the 8 directions -- precisely the queen-ray walk the mailbox // version does by hand, one lookup+OR instead of an 8-direction loop. // The direction-back-to-king half of the old table needs no storage // at all: generate.c's own ASSERT two lines below (mailbox version) // proves DIR_FROM_SQ_TO_KING(c) is always identical to // DIRECTION_BETWEEN_SQUARES(c, xKing), which is a g_pVectorDelta[] // table lookup in release builds (see chess.h), not a divide/branch // chain -- so recomputing it on demand costs the same as reading a // stored value would have, with no table to populate up front. void _FindUnblockedSquaresBB(IN MOVE_STACK *pStack, IN POSITION *pos) /** Routine description: Bitboard replacement for _FindUnblockedSquares -- see that function's header comment for what "unblocked" means. Builds pStack->bbUnblocked[uPly], one bit per square unblocked for the king of the side not on move. Parameters: MOVE_STACK *pStack : move stack pointer POSITION *pos : position pointer Return value: void **/ { COOR cKing = KingPosition(pos, FLIP(pos->uToMove)); ULONG uPly = pStack->uPly; ASSERT(IS_ON_BOARD(cKing)); ASSERT(IS_KING(pos->rgSquare[cKing].pPiece)); ASSERT(GET_COLOR(pos->rgSquare[cKing].pPiece) != pos->uToMove); pStack->bbUnblocked[uPly] = _RookAttacksBB(cKing, pos->bbOccupied) | _BishopAttacksBB(cKing, pos->bbOccupied); } // GenerateMoves no longer builds bbUnblocked[uPly] eagerly -- it just // bumps this ply's generation ticket (uUnblockedKeyValue[uPly], see // its comment in chess.h) so WouldGiveCheck's own lazy check (below) // knows a new node has arrived here and the cached bbUnblocked[uPly] // (built for some earlier generation, if ever) is no longer trusted. // The real build is deferred to WouldGiveCheck's first call this // generation, if there is one -- a node whose every candidate gets // rejected before ever needing WouldGiveCheck now never pays for it. #define MARK_UNBLOCKED_SQUARES_STALE(pStack, pos, uPly) \ ((void)(pos), (pStack)->uUnblockedKeyValue[(uPly)]++) #define SQUARE_IS_UNBLOCKED(c) \ (0 != (pStack->bbUnblocked[ctx->uPly] & COOR_TO_BB(c))) #define DIR_FROM_SQ_TO_KING(c) \ DIRECTION_BETWEEN_SQUARES((c), xKing) FLAG FORCEINLINE WouldGiveCheck(IN SEARCHER_THREAD_CONTEXT *ctx, IN MOVE mv) /** Routine description: Determine whether a move is a checking move or not. Self-sufficient -- builds bbUnblocked[ctx->uPly] itself, lazily, on the first call for a given generation (see the lazy-rebuild block below and chess.h's uUnblockedBuiltFor comment). GenerateMoves no longer builds it eagerly, only marks the generation stale (MARK_UNBLOCKED_SQUARES_STALE); callers no longer need to remember to call _FindUnblockedSquaresBB first. 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 = KingPosition(pos, FLIP(GET_COLOR(pPiece))); 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); // Lazy rebuild: GenerateMoves only bumps uUnblockedKeyValue[uPly] // (MARK_UNBLOCKED_SQUARES_STALE above) instead of building // bbUnblocked[uPly] eagerly. The first WouldGiveCheck call for a // given generation discovers its mismatch here and does the real // build; every later call this same node/generation matches and // skips straight to SQUARE_IS_UNBLOCKED/DIR_FROM_SQ_TO_KING below. // A node whose every candidate gets rejected before ever calling // WouldGiveCheck (e.g. every capture futility-pruned in QSearch) // now never pays for the build at all -- see chess.h's // uUnblockedBuiltFor comment for why this needs its own field // rather than reusing uUnblockedKeyValue for both jobs. Measured // cost of the added branch itself (mock A/B, same shape as this // one, three curated suites): within this box's own run-to-run // noise band, no consistent direction -- see conversation. if (pStack->uUnblockedBuiltFor[ctx->uPly] != pStack->uUnblockedKeyValue[ctx->uPly]) { _FindUnblockedSquaresBB(pStack, pos); pStack->uUnblockedBuiltFor[ctx->uPly] = pStack->uUnblockedKeyValue[ctx->uPly]; } // // 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)); } // // 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. Callers should prefer reading // pos->bbOccupied directly (incrementally maintained, see chess.h and // board_representation/EVAL.md section 0) -- this from-scratch // rebuild now exists mainly as the ground truth used to verify that // field stays in sync (VerifyPositionConsistency, board.c; the // ASSERT(pStack->bbOccupied == _BuildFullOccupiedBB(pos)) calls // below) and for testgenerate.c's benchmark harness. Non-static so // both of those can call it directly. BITBOARD FORCEINLINE _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(KingPosition(pos, WHITE)) | COOR_TO_BB(KingPosition(pos, BLACK))); } // 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 FORCEINLINE _BuildFriendlySideBB(IN POSITION *pos, IN ULONG uSide) /** Routine description: Full occupancy bitboard for one side only (all piece types including pawns and king) -- pos->bbOccupied ORs both sides together for a different purpose (SEE's/generation's "is this square occupied at all" query); move generation also needs just one side's squares here, to AND off as illegal (self-occupied) destinations. Parameters: POSITION *pos ULONG uSide Return value: BITBOARD **/ { // 2026-09-06: was a 6-term OR of bbPieces+bbPawns+king every call -- // pos->bbOccupiedSide[uSide] is now incrementally maintained (move.c, // same treatment as pos->bbOccupied) so this is just a field read. return pos->bbOccupiedSide[uSide]; } // 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); } } // // 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); } } } // // 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); } } // // 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); } } } // // 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); } } // // 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); } } } // // 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); } } // // 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); } } } // // 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); } } } // // 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 = pos->bbOccupied; 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); } } } // // 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 = pos->bbOccupied; 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__); } // -------------------------------------------------------------------- // Captures/promotions-only generators (QSearch's GENERATE_CAPTURES_PROMS // path). QSearch's _ScoreQSearchMovesNoChecks assigns a score of 0 to // every quiet non-promoting move, and search.c's QSearch loop bails out // of its move loop on the first move it sees scored <= 0 -- so a quiet // move that _GenerateAllMoves would have produced for this uType was // always going to be generated, scored 0, and never searched. These // generators skip producing it in the first place: same mask-and- // serialize shape as the normal _Generate*BB functions, but masking the // attack bitboard with the ENEMY-occupied bitboard instead of the // complement of the friendly one, so quiet destinations never reach // _AddNormalMove at all. Bitboard-only (no mailbox fallback) -- every // piece type's GENERATE_*_BITBOARD flag is on in this project's only // build profile (GNUmakefile's PROFILE), and the mailbox generators this // would otherwise have to mirror are slated for removal separately. // // Castling is skipped entirely (a castle is never a capture or // promotion). Quiet pawn pushes are skipped except the single push onto // the back rank, which is a (quiet) promotion and still must be scored. // // These must stay pseudo-legal-equivalent to _GenerateAllMoves filtered // to IS_CAPTURE_OR_PROMOTION(mv), as a set -- see testgenerate.c's // TestCapturesAndPromotionsGenerator for the TEST=1 gate that checks // exactly this, over a corpus of positions, before any piece type here // is trusted. // -------------------------------------------------------------------- // CAPTURES_PROMS_BITBOARD_PATH is declared in chess.h (not defined // here) so every translation unit that needs to know whether this path // exists sees the same answer -- see its comment there. #if defined(CAPTURES_PROMS_BITBOARD_PATH) void _GenerateKnightCapturesBB(IN MOVE_STACK *pStack, IN POSITION *pos, IN COOR cKnight) /** Routine description: Captures-only sibling of _GenerateKnightBB: masks the knight's attack bitboard with the enemy-occupied bitboard instead of the complement of the friendly one, so only captures are serialized. Knights never promote, so this is the whole move set this piece type can contribute to GENERATE_CAPTURES_PROMS. Parameters: MOVE_STACK *pStack : the move stack POSITION *pos : the board position COOR cKnight : the knight's location Return value: void **/ { BITBOARD bbDest = g_KnightAttacksBB[cKnight] & pos->bbOccupiedSide[FLIP(pos->uToMove)]; ULONG uBitIndex; COOR c; PIECE p; 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); p = pos->rgSquare[c].pPiece; ASSERT(!IS_EMPTY(p) && OPPOSITE_COLORS(p, pos->rgSquare[cKnight].pPiece)); _AddNormalMove(pStack, pos, cKnight, c, p); } } void _GenerateKingCapturesBB(IN MOVE_STACK *pStack, IN POSITION *pos, IN COOR cKing) /** Routine description: Captures-only sibling of _GenerateKingBB. No castling here -- a castle can never be a capture. Parameters: MOVE_STACK *pStack : the move stack POSITION *pos : the board position COOR cKing : the king's location Return value: void **/ { BITBOARD bbDest = g_KingAttacksBB[cKing] & pos->bbOccupiedSide[FLIP(pos->uToMove)]; ULONG uBitIndex; COOR c; PIECE p; ASSERT(IS_KING(pos->rgSquare[cKing].pPiece)); ASSERT(GET_COLOR(pos->rgSquare[cKing].pPiece) == pos->uToMove); 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, pos->rgSquare[cKing].pPiece)); _AddNormalMove(pStack, pos, cKing, c, p); } } void _GenerateBishopCapturesBB(IN MOVE_STACK *pStack, IN POSITION *pos, IN COOR cBishop) /** Routine description: Captures-only sibling of _GenerateBishopBB. Parameters: MOVE_STACK *pStack : the move stack (bbOccupied must already be set, same precondition as _GenerateBishopBB) 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->bbOccupied == _BuildFullOccupiedBB(pos)); uMagicIndex = (ULONG) (((pStack->bbOccupied & g_BishopOccupancyMask[cBishop]) * g_BishopMagic[cBishop]) >> g_BishopMagicShift[cBishop]); bbDest = g_BishopAttackTable[cBishop][uMagicIndex] & pos->bbOccupiedSide[FLIP(pos->uToMove)]; 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, pos->rgSquare[cBishop].pPiece)); _AddNormalMove(pStack, pos, cBishop, c, p); } } void _GenerateRookCapturesBB(IN MOVE_STACK *pStack, IN POSITION *pos, IN COOR cRook) /** Routine description: Captures-only sibling of _GenerateRookBB. Parameters: MOVE_STACK *pStack : the move stack (bbOccupied must already be set, same precondition as _GenerateRookBB) 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->bbOccupied == _BuildFullOccupiedBB(pos)); uMagicIndex = (ULONG) (((pStack->bbOccupied & g_RookOccupancyMask[cRook]) * g_RookMagic[cRook]) >> g_RookMagicShift[cRook]); bbDest = g_RookAttackTable[cRook][uMagicIndex] & pos->bbOccupiedSide[FLIP(pos->uToMove)]; 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, pos->rgSquare[cRook].pPiece)); _AddNormalMove(pStack, pos, cRook, c, p); } } void _GenerateQueenCapturesBB(IN MOVE_STACK *pStack, IN POSITION *pos, IN COOR cQueen) /** Routine description: Captures-only sibling of _GenerateQueenBB. Parameters: MOVE_STACK *pStack : the move stack (bbOccupied must already be set, same precondition as _GenerateQueenBB) 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->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]) & pos->bbOccupiedSide[FLIP(pos->uToMove)]; 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, pos->rgSquare[cQueen].pPiece)); _AddNormalMove(pStack, pos, cQueen, c, p); } } void _GenerateCapturesAndPromotionsPawnsBB(IN MOVE_STACK *pStack, IN POSITION *pos, IN ULONG uSide) /** Routine description: Captures/promotions-only sibling of _GenerateAllPawnMovesBB: both diagonal captures (promoting or not), en passant, and the single quiet push onto the back rank (a promotion, so it still must be scored) -- but never a double push or a non-promoting single push, neither of which can be a capture or promotion. 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 bbEmpty = ~pos->bbOccupied; BITBOARD bbEnemy = pos->bbOccupiedSide[FLIP(uSide)]; BITBOARD bbPushPromote, bbCapLeft, bbCapRight, bb; ULONG uBitIndex; COOR cTo, cFrom, cEp; PIECE p; if (uSide == WHITE) { bbPushPromote = ((bbPawns & BBRANK[7]) >> 8) & bbEmpty; bbCapLeft = ((bbPawns & ~BBFILE[0]) >> 9) & bbEnemy; bbCapRight = ((bbPawns & ~BBFILE[7]) >> 7) & bbEnemy; } else { ASSERT(uSide == BLACK); bbPushPromote = ((bbPawns & BBRANK[2]) << 8) & bbEmpty; bbCapLeft = ((bbPawns & ~BBFILE[0]) << 7) & bbEnemy; bbCapRight = ((bbPawns & ~BBFILE[7]) << 9) & bbEnemy; } // Quiet promotions only -- the single push from the 7th/2nd rank. bb = bbPushPromote; 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)); ASSERT(RANK8(cTo) || RANK1(cTo)); _AddPromote(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 -- same per-side-per-node (not per-pawn) check as // _GenerateAllPawnMovesBB. 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); } } } // Non-static so testgenerate.c's correctness/speed harness can call it // directly by name, same convention as _GenerateAllMoves below. void _GenerateCapturesAndPromotions(IN MOVE_STACK *pStack, IN POSITION *pos) /** Routine description: Generates exactly the pseudo-legal moves that are captures or promotions in this position -- the subset of _GenerateAllMoves' output that IS_CAPTURE_OR_PROMOTION(mv) is true for, produced directly rather than generated-then-filtered. Used by GenerateMoves for GENERATE_CAPTURES_PROMS (QSearch's no-checks path) in place of _GenerateAllMoves, since every quiet move _GenerateAllMoves would have produced there is scored 0 by _ScoreQSearchMovesNoChecks and never searched. Relies on pStack->bbOccupied being set by the caller for the sliding-piece magic lookups, same precondition as _GenerateAllMoves itself. Parameters: MOVE_STACK *pStack : the move stack POSITION *pos : the board position Return value: void **/ { COOR c; static void (*JumpTable[])(MOVE_STACK *, POSITION *, COOR) = { InvalidGenerator, // EMPTY InvalidGenerator, // EMPTY | WHITE InvalidGenerator, // 2 (BLACK_PAWN) InvalidGenerator, // 3 (WHITE_PAWN) _GenerateKnightCapturesBB, // 4 (BLACK_KNIGHT) _GenerateKnightCapturesBB, // 5 (WHITE_KNIGHT) _GenerateBishopCapturesBB, // 6 (BLACK_BISHOP) _GenerateBishopCapturesBB, // 7 (WHITE_BISHOP) _GenerateRookCapturesBB, // 8 (BLACK_ROOK) _GenerateRookCapturesBB, // 9 (WHITE_ROOK) _GenerateQueenCapturesBB, // 10 (BLACK_QUEEN) _GenerateQueenCapturesBB, // 11 (WHITE_QUEEN) _GenerateKingCapturesBB, // 12 (BLACK_KING) _GenerateKingCapturesBB // 13 (WHITE_KING) }; pStack->bbOccupied = pos->bbOccupied; { BITBOARD bbNonPawns = NON_KING_PIECES_BB(pos, pos->uToMove) | COOR_TO_BB(KingPosition(pos, pos->uToMove)); while (IS_ON_BOARD(c = CoorFromBitBoardRank8ToRank1(&bbNonPawns))) { (JumpTable[pos->rgSquare[c].pPiece])(pStack, pos, c); } } _GenerateCapturesAndPromotionsPawnsBB(pStack, pos, pos->uToMove); } #endif // captures/promotions bitboard path // 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) // _GenerateKnightBB serves both slots; see its header comment // for why the mailbox pair's old color split doesn't carry // over to bitboards. _GenerateKnightBB, // 4 (BLACK_KNIGHT) _GenerateKnightBB, // 5 (WHITE_KNIGHT) _GenerateBishopBB, // 6 (BLACK_BISHOP) _GenerateBishopBB, // 7 (WHITE_BISHOP) _GenerateRookBB, // 8 (BLACK_ROOK) _GenerateRookBB, // 9 (WHITE_ROOK) _GenerateQueenBB, // 10 (BLACK_QUEEN) _GenerateQueenBB, // 11 (WHITE_QUEEN) _GenerateKingBB, // 12 (BLACK_KING) _GenerateKingBB // 13 (WHITE_KING) }; #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. pStack->bbFriendlyOccupied = _BuildFriendlySideBB(pos, pos->uToMove); pStack->bbOccupied = pos->bbOccupied; { BITBOARD bbNonPawns = NON_KING_PIECES_BB(pos, pos->uToMove) | COOR_TO_BB(KingPosition(pos, pos->uToMove)); while (IS_ON_BOARD(c = CoorFromBitBoardRank8ToRank1(&bbNonPawns))) { #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); } } _GenerateAllPawnMovesBB(pStack, pos, pos->uToMove); } // // 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; pStack->bbFriendlyOccupied = _BuildFriendlySideBB(pos, uSide); pStack->bbOccupied = pos->bbOccupied; 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 = KingPosition(pos, uSide); ASSERT(IS_KING(pos->rgSquare[c].pPiece)); _GenerateKingBB(pStack, pos, c); // Pawns get the same bulk treatment via _GenerateAllPawnMovesBB. _GenerateAllPawnMovesBB(pStack, pos, uSide); } // 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. _GenerateAllMoves itself (the JumpTable/cNonPawns // version above) is kept only as testgenerate.c's named comparison // point -- production always goes through this redirect. #define _GenerateAllMoves _GenerateAllMovesBB 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 **/ { COOR c; PIECE p; PIECE pKing; COOR cKing = KingPosition(pos, pos->uToMove); SEE_LIST rgCheckers; ULONG uReturn = 0; 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)); // // 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 = pos->bbOccupied & ~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; } } } // // 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; // // board_representation/MOVEGEN_MIGRATION.md section 6a Phase 2: // pos->cNonPawns[side][] mixed every non-pawn piece type together, // which is why the old mailbox path needed JumpTable[p], an // indirect call whose target changed 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 does: 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 = pos->bbOccupied; 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); } 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 LMP 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; ctx->sPlyInfo[uPly].eMoveScoringScheme = MOVE_SCORING_NORMAL; // // 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[0].uBonus |= (SORT_THESE_FIRST * (IS_KILLERMATE_MOVE(sKillers[0].mv) != 0)); sKillers[1].mv = ctx->mvKiller[uPly][1]; sKillers[1].uBonus = SECOND_KILLER; sKillers[1].uBonus |= (SORT_THESE_FIRST * (IS_KILLERMATE_MOVE(sKillers[1].mv) != 0)); sKillers[2].mv.uMove = sKillers[3].mv.uMove = 0; // uBonus must be initialized unconditionally too, matching .mv // above -- at uPly<=1 the "if" below never runs, but the move- // scoring code further down reads both fields unconditionally // (IS_SAME_MOVE(sKillers[2].mv, mv) * sKillers[2].uBonus). Harmless // today (sKillers[2].mv is zeroed, so that match is always false // and 0 * garbage still yields 0), but a real uninitialised-stack // read that valgrind correctly flags -- caught chasing an // unrelated report that turned out to trace back to this exact // stack slot via register/value propagation under LTO. sKillers[2].uBonus = sKillers[3].uBonus = 0; if (uPly > 1) { sKillers[2].mv = ctx->mvKiller[uPly - 2][0]; sKillers[2].uBonus = THIRD_KILLER; sKillers[2].uBonus |= (SORT_THESE_FIRST * (IS_KILLERMATE_MOVE(sKillers[2].mv) != 0)); sKillers[3].mv = ctx->mvKiller[uPly - 2][1]; sKillers[3].uBonus = FOURTH_KILLER; 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. MOVE mvLast = (ctx->sPlyInfo[uPly - 1]).mv; fHaveCounterMove = (0 != mvLast.uMove); uCounterMoveIdx = MOVE_TO_INDEX(mvLast); uCounterMoveContKey = MOVE_TO_CONT_KEY(mvLast); } // 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); } else { // s > 0 here: the captured piece is worth strictly // more than the piece making the capture. The real // SEE(pos, mv) is mathematically guaranteed >= this // material floor (the side to move can always stop // the exchange right after this capture), so its // sign is already known to be nonnegative without // paying for the actual exchange walk -- avoids a // later GetMoveSee() cache miss (and a redundant // SEE() call) on exactly the most common "good // capture" case. pStack->mvf[u].bvFlags |= MVF_SEE_KNOWN | MVF_SEE_NONNEGATIVE; } 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; // DROPPED: recapture bonus (MOVE_ORDERING_IDEAS.md // item 4) -- a real, well-calibrated FH% signal // (64-65% vs. a 49-52% all-captures-at-the-same- // SEE-sign baseline) that never converted into a // tree-size win at two magnitudes tried (50: a // dominant override of MVV/LVA's own ~16-unit // spread, confirmed real tactical loss on // ecm_hard_quick; 4: fixed the regression but // still no node-count improvement on any suite). // See chess.h's DROPPED comment near // COUNTERMOVE_EVIDENCE_THRESHOLD for the full // backlog history. ASSERT(s >= SORT_THESE_FIRST); ASSERT(s > 0); ASSERT((s & STRIP_OFF_FLAGS) < VALUE_KING); } } // // 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; } } // DROPPED: flee-to-safety tier (MOVE_ORDERING_IDEAS.md // item 6) -- a real, well-calibrated FH% signal // (56-68% vs. ~1.35-1.54% baseline at evidence >= // 10000) that turned out to fire too rarely (2,444- // 9,209 qualifying tries across an entire suite run) // to register any measurable node-count or solve-count // effect either way. See chess.h's DROPPED comment // near COUNTERMOVE_EVIDENCE_THRESHOLD for the full // backlog history. // DROPPED: ply-2 move-pair match (MOVE_ORDERING_IDEAS.md // item 3) -- a real, well-calibrated signal (53-66% FH // vs. ~1.2-1.4% baseline) that never converted into a // tree-size win across three mechanisms tried (tier // escape, dominant nudge, proportionate nudge). See // chess.h's DROPPED comment near COUNTERMOVE_EVIDENCE_ // THRESHOLD for the full history. 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. // ctx->sPlyInfo[uPly].eMoveScoringScheme = MOVE_SCORING_ESCAPE; 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); } else { // Same reasoning as _ScoreAllMoves' identical // shortcut: s > 0 here is a guaranteed floor on the // real SEE, so its sign is already known. pStack->mvf[u].bvFlags |= MVF_SEE_KNOWN | MVF_SEE_NONNEGATIVE; } 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); } } // // 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 (SeeFastSign(pos, mv)) { // 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. // // TODO: does this matter enough for how slow it is? 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. 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 generated 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); ctx->sPlyInfo[uPly].eMoveScoringScheme = MOVE_SCORING_QSEARCH_CHECKS; // uLiveEnd shrinks as moves are rejected, instead of leaving them in // place scored <= 0 for QSearch's move loop (search.c) to discover // and bail on. Every move QSearch's loop will ever consider calls // SelectBestNoHistory, which rescans the WHOLE remaining [u, // uEnd[uPly]) range -- so a quiet, non-checking move sitting in // that range gets rescanned by every single one of those calls // until the bail, not generated/scored once and ignored. Instead, // a rejected move (iValue <= 0) is swapped with the last live // element and uLiveEnd drops by one -- same whole-struct-swap // idiom GenerateMoves already uses to retire a found hash move // (see its comment above) -- and pStack->uEnd[uPly] is written // once at the end, after every move has been classified. The // index being examined is NOT advanced on a reject, since the // element just swapped into that slot hasn't been scored yet. // // Net effect: every move left in [uBegin[uPly], uEnd[uPly]) after // this function returns has iValue > 0, so search.c's QSearch loop // will never actually hit its own `iValue <= 0` bail for this // scoring scheme -- that check stays (it's shared with // _ScoreQSearchMovesNoChecks, which still needs it), it just // becomes unreachable here, which is harmless. ULONG uLiveEnd = pStack->uEnd[uPly]; u = pStack->uBegin[uPly]; while (u < uLiveEnd) { 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); } else { // // Reject: this move will never be searched (QSearch's // caller would bail on it the moment it became the best // remaining candidate) -- drop it from the live range now // instead of leaving it for SelectBestNoHistory to keep // rescanning. Swap the last live element into this slot // and shrink uLiveEnd; u is deliberately NOT advanced so // the freshly-swapped-in element gets classified on the // next iteration. // uLiveEnd--; if (u != uLiveEnd) { pStack->mvf[u] = pStack->mvf[uLiveEnd]; } continue; } pStack->mvf[u].iValue = s; ASSERT(pStack->mvf[u].iValue != -MAX_INT); u++; } // next move pStack->uEnd[uPly] = uLiveEnd; } 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); ctx->sPlyInfo[uPly].eMoveScoringScheme = MOVE_SCORING_QSEARCH_NO_CHECKS; #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); MARK_UNBLOCKED_SQUARES_STALE(pStack, pos, uPly); _GenerateAllMoves(pStack, pos); _ScoreQSearchMovesInclChecks(pStack, ctx); break; case GENERATE_CAPTURES_PROMS: ASSERT(!InCheck(pos, pos->uToMove)); ASSERT(mvHash.uMove == 0); // The unblocked-squares table itself is no longer built // here -- see WouldGiveCheck's lazy rebuild (generate.c): // this just marks the ply's generation ticket so the // first WouldGiveCheck call this node (if any) knows to // build it. search.c's QSearch loop calls WouldGiveCheck // itself, deferred, on whichever single move it selects // and decides to search (see fIncludeChecks == FALSE // there) -- most nodes whose candidates are all futility- // pruned away never reach that call at all, and now never // pay for the table either. MARK_UNBLOCKED_SQUARES_STALE(pStack, pos, uPly); #if defined(CAPTURES_PROMS_BITBOARD_PATH) _GenerateCapturesAndPromotions(pStack, pos); #else _GenerateAllMoves(pStack, pos); #endif _ScoreQSearchMovesNoChecks(pStack, ctx); break; case GENERATE_ALL_MOVES: ASSERT(!InCheck(pos, pos->uToMove)); MARK_UNBLOCKED_SQUARES_STALE(pStack, pos, uPly); _GenerateAllMoves(pStack, pos); _ScoreAllMoves(pStack, ctx, mvHash); uReturn = MOVE_COUNT(ctx, uPly); break; case GENERATE_ESCAPES: ASSERT(InCheck(pos, pos->uToMove)); MARK_UNBLOCKED_SQUARES_STALE(pStack, pos, uPly); uReturn = _GenerateEscapes(pStack, pos); ASSERT(uReturn); pStack->sGenFlags[uPly].uKingMoveCount = uReturn >> 16; pStack->sGenFlags[uPly].uCheckingPieces = uReturn & 0xFF; // Snapshot the true legal-escape count before // _ScoreAllEscapes shrinks uEnd[uPly] to exclude an // already-tried hash move -- see uTrueEscapeCount's // comment in chess.h. pStack->sGenFlags[uPly].uTrueEscapeCount = (UCHAR)MOVE_COUNT(ctx, uPly); _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]; }