/** Copyright (c) Scott Gasch Module Name: movesup.c Abstract: Functions to support MakeMove and UnmakeMove along with some other miscellanious move support functions. Author: Scott Gasch (scott.gasch@gmail.com) 13 May 2004 Revision History: $Id: movesup.c 345 2007-12-02 22:56:42Z scott $ **/ #include "chess.h" // Unlike GetAttacks (a real asm symbol in a different file, so // chess.h's macro-swap never touches its own definition), // ExposesCheck/FasterExposesCheck/ExposesCheckEp's mailbox // implementations live in *this* file, right below their BB // counterparts -- chess.h's #define would otherwise rename these // functions' own definitions too, colliding with the real // ExposesCheckBB/etc. symbols. #undef restores the real names for // this file's own definitions; every other translation unit that // includes chess.h still sees the macro-renamed calls. #if defined(EXPOSESCHECK_BITBOARD) #undef ExposesCheck #undef FasterExposesCheck #undef ExposesCheckEp #endif #if defined(ISATTACKED_BITBOARD) #undef IsAttacked #undef InCheck #endif // board_representation/MOVEGEN_MIGRATION.md section 6b: bitboard // equivalents of ExposesCheck/FasterExposesCheck/ExposesCheckEp. // ExposesCheck is called from MakeMove (move.c) on essentially every // move actually played during search -- the pin-legality safety net // every generator's header comment references -- making it a much // hotter target than anything in generate.c's own Part A/B work. // // Design: keep the mailbox version's own O(1) alignment pre-check // (CHECK_VECTOR_WITH_INDEX -- already a table lookup, nothing to // improve) to bail out on the common "not even aligned" case before // paying for any bitboard work at all. Only when aligned: exclude the // hypothetically-removed square(s) from occupancy, magic-lookup the // attack set from cLocation against that occupancy, and mask to the // single ray through cRemove via g_RookRayToEdge/g_BishopRayToEdge // (so an unrelated attacker on a *different* ray through cLocation // can't falsely register) -- then apply the same enemy-color/ // piece-type check the mailbox version does on whatever single square // survives. // Finds the single nearest occupied square along one specific // direction from c, or ILLEGAL_COOR if that ray is empty all the way // to the edge. This is *not* "magic attack bitboard ANDed with a ray // mask" -- that was tried first and is wrong: an unblocked ray's magic // attack set contains every empty square out to the edge, and // FastFirstBit on that intersection picks the lowest square index // overall, which is not necessarily the square nearest c (bit index // order and "distance from c" only coincide for one of the two // possible directions along any given ray). The correct technique, // mirrored exactly from _WhoAttacksSquareBB (see.c): isolate the // lowest set bit for a "positive" direction (bb & -bb, no bit-scan // needed) or the highest set bit for a "negative" direction // (1ULL << (FastLastBit-1)) -- g_RookRayPositiveDir/ // g_BishopRayPositiveDir already record which is which per direction. static COOR _NearestBlockerAlongRayBB(IN COOR c, IN int iDeltaFromC, IN BITBOARD bbOccupied) /** Routine description: Nearest occupied square from c along the single queen-direction iDeltaFromC, or ILLEGAL_COOR if none. Parameters: COOR c int iDeltaFromC : one of g_iQKDeltas's 8 values BITBOARD bbOccupied Return value: COOR **/ { BITBOARD bbRay; BITBOARD bbBlockers; BITBOARD bbBlockerBit; FLAG fPositiveDir; ULONG uBitIndex; switch (iDeltaFromC) { case 16: bbRay = g_RookRayToEdge[0][c]; fPositiveDir = g_RookRayPositiveDir[0]; break; case -16: bbRay = g_RookRayToEdge[1][c]; fPositiveDir = g_RookRayPositiveDir[1]; break; case 1: bbRay = g_RookRayToEdge[2][c]; fPositiveDir = g_RookRayPositiveDir[2]; break; case -1: bbRay = g_RookRayToEdge[3][c]; fPositiveDir = g_RookRayPositiveDir[3]; break; case 17: bbRay = g_BishopRayToEdge[0][c]; fPositiveDir = g_BishopRayPositiveDir[0]; break; case -17: bbRay = g_BishopRayToEdge[1][c]; fPositiveDir = g_BishopRayPositiveDir[1]; break; case 15: bbRay = g_BishopRayToEdge[2][c]; fPositiveDir = g_BishopRayPositiveDir[2]; break; case -15: bbRay = g_BishopRayToEdge[3][c]; fPositiveDir = g_BishopRayPositiveDir[3]; break; default: ASSERT(FALSE); return(ILLEGAL_COOR); } bbBlockers = bbRay & bbOccupied; if (0 == bbBlockers) { return(ILLEGAL_COOR); } bbBlockerBit = fPositiveDir ? (bbBlockers & (0ULL - bbBlockers)) : (1ULL << (FastLastBit(bbBlockers) - 1)); uBitIndex = FastFirstBit(bbBlockerBit) - 1; return BIT_NUMBER_TO_COOR(uBitIndex); } // Shared tail: given a candidate blocker square, apply the same // enemy-color / piece-type-can-reach-us check the mailbox versions do, // and return it (or ILLEGAL_COOR). static COOR _ValidateExposedBlockerBB(IN POSITION *pos, IN COOR cBlocker, IN COOR cLocation) { PIECE xPiece; int iIndex; if (!IS_ON_BOARD(cBlocker)) { return(ILLEGAL_COOR); } xPiece = pos->rgSquare[cBlocker].pPiece; ASSERT(!IS_EMPTY(xPiece)); if (OPPOSITE_COLORS(xPiece, pos->rgSquare[cLocation].pPiece)) { iIndex = (int)cBlocker - (int)cLocation; if (0 != (CHECK_VECTOR_WITH_INDEX(iIndex, GET_COLOR(xPiece)) & (1 << (PIECE_TYPE(xPiece))))) { return(cBlocker); } } return(ILLEGAL_COOR); } COOR FasterExposesCheckBB(IN POSITION *pos, IN COOR cRemove, IN COOR cLocation) /** Routine description: Bitboard equivalent of FasterExposesCheck -- see that function's comment. Caller already knows exposure is geometrically possible (skips the alignment pre-check FasterExposesCheck also skips). Parameters: POSITION *pos, COOR cRemove, COOR cLocation Return value: COOR **/ { int iIndex = (int)cLocation - (int)cRemove; int iDelta; BITBOARD bbOccupiedWithoutRemove; COOR cBlocker; ASSERT(IS_KING(pos->rgSquare[cLocation].pPiece)); ASSERT(IS_ON_BOARD(cRemove)); ASSERT(IS_ON_BOARD(cLocation)); ASSERT(!IS_EMPTY(pos->rgSquare[cLocation].pPiece)); ASSERT(0 != (CHECK_VECTOR_WITH_INDEX(iIndex, BLACK) & (1 << QUEEN))); iDelta = CHECK_DELTA_WITH_INDEX(iIndex); ASSERT(iDelta != 0); bbOccupiedWithoutRemove = _BuildFullOccupiedBB(pos) & ~COOR_TO_BB(cRemove); cBlocker = _NearestBlockerAlongRayBB(cLocation, iDelta, bbOccupiedWithoutRemove); return _ValidateExposedBlockerBB(pos, cBlocker, cLocation); } COOR ExposesCheckBB(IN POSITION *pos, IN COOR cRemove, IN COOR cLocation) /** Routine description: Bitboard equivalent of ExposesCheck -- see that function's comment. Parameters: POSITION *pos : the board COOR cRemove : the square where a piece hypothetically removed from COOR cLocation : the square where the attackee is sitting Return value: COOR : the location of an attacker piece or 0x88 (!IS_ON_BOARD) if the removal of cRemove does not expose check. **/ { int iIndex = (int)cLocation - (int)cRemove; int iDelta; BITBOARD bbOccupiedWithoutRemove; COOR cBlocker; ASSERT(IS_ON_BOARD(cRemove)); ASSERT(IS_ON_BOARD(cLocation)); ASSERT(!IS_EMPTY(pos->rgSquare[cLocation].pPiece)); // // If there is no way for a queen sitting at the square removed to // reach the square we are testing (i.e. the two squares are not // on the same rank, file, or diagonal) then there is no way // removing it can expose cLocation to check. // if (0 == (CHECK_VECTOR_WITH_INDEX(iIndex, BLACK) & (1 << QUEEN))) { return(ILLEGAL_COOR); } iDelta = CHECK_DELTA_WITH_INDEX(iIndex); bbOccupiedWithoutRemove = _BuildFullOccupiedBB(pos) & ~COOR_TO_BB(cRemove); cBlocker = _NearestBlockerAlongRayBB(cLocation, iDelta, bbOccupiedWithoutRemove); return _ValidateExposedBlockerBB(pos, cBlocker, cLocation); } COOR ExposesCheckEpBB(IN POSITION *pos, IN COOR cTest, IN COOR cIgnore, IN COOR cBlock, IN COOR cKing) /** Routine description: Bitboard equivalent of ExposesCheckEp -- see that function's comment. Two squares are excluded from occupancy (cTest, the captured pawn; cIgnore, the capturing pawn's origin) and one is forced occupied (cBlock, the capturing pawn's destination) -- matching the mailbox version's own "pretend the en passant capture already happened" bookkeeping. Parameters: POSITION *pos, COOR cTest : the square the attack would come from COOR cIgnore : ignore this square, the pawn moved COOR cBlock : this square is where the pawn moved to and now blocks COOR cKing : the square under attack Return value: COOR **/ { int iIndex = (int)cKing - (int)cTest; int iDelta; BITBOARD bbOccupied; COOR cBlocker; ASSERT(IS_ON_BOARD(cTest)); ASSERT(IS_ON_BOARD(cIgnore)); ASSERT(IS_ON_BOARD(cBlock)); ASSERT(IS_ON_BOARD(cKing)); if (0 == (CHECK_VECTOR_WITH_INDEX(iIndex, BLACK) & (1 << QUEEN))) { return(ILLEGAL_COOR); } iDelta = CHECK_DELTA_WITH_INDEX(iIndex); bbOccupied = (_BuildFullOccupiedBB(pos) & ~COOR_TO_BB(cTest) & ~COOR_TO_BB(cIgnore)) | COOR_TO_BB(cBlock); cBlocker = _NearestBlockerAlongRayBB(cKing, iDelta, bbOccupied); // cBlock is forced-occupied above purely to stop the ray there -- // it may not really hold a piece yet (pre-move state), so it must // be recognized and treated as "safe" directly, not run through // pos->rgSquare's real (stale) contents, exactly like the mailbox // version's explicit early check. if (cBlocker == cBlock) { return(ILLEGAL_COOR); } return _ValidateExposedBlockerBB(pos, cBlocker, cKing); } COOR FasterExposesCheck(POSITION *pos, COOR cRemove, COOR cLocation) /** Routine description: This is just like ExposesCheck (see below) but it does not bother checking whether its possible to expose check with the piece at cRemove because we already know it is. Parameters: POSITION *pos, COOR cRemove, COOR cLocation Return value: COOR **/ { register int iDelta; register COOR cBlockIndex; int iIndex; PIECE xPiece; ULONG uColor = GET_COLOR(pos->rgSquare[cLocation].pPiece); ASSERT(IS_KING(pos->rgSquare[cLocation].pPiece)); iIndex = (int)cLocation - (int)cRemove; ASSERT(IS_ON_BOARD(cRemove)); ASSERT(IS_ON_BOARD(cLocation)); ASSERT(!IS_EMPTY(pos->rgSquare[cLocation].pPiece)); ASSERT(0 != (CHECK_VECTOR_WITH_INDEX(iIndex, BLACK) & (1 << QUEEN))); iDelta = CHECK_DELTA_WITH_INDEX(iIndex); ASSERT(iDelta != 0); for (cBlockIndex = cRemove + iDelta; IS_ON_BOARD(cBlockIndex); cBlockIndex += iDelta) { ASSERT(cBlockIndex != cRemove); ASSERT(cBlockIndex != cLocation); xPiece = pos->rgSquare[cBlockIndex].pPiece; if (!IS_EMPTY(xPiece)) { // // Is it an enemy? // if (OPPOSITE_COLORS(xPiece, uColor)) { // // Does it move the right way to attack? // iIndex = (int)cBlockIndex - (int)cLocation; if (0 != (CHECK_VECTOR_WITH_INDEX(iIndex, WHITE) & (1 << (PIECE_TYPE(xPiece))))) { return(cBlockIndex); } } // // Either we found another friendly piece or an enemy piece // that was unable to reach us. Either way we are safe. // return(ILLEGAL_COOR); } } // // We fell off the board without seeing another piece. // return(ILLEGAL_COOR); } COOR ExposesCheck(POSITION *pos, COOR cRemove, COOR cLocation) /** Routine description: Test if removing the piece at cRemove exposes the piece at cLocation to attack by the other side. Note: there must be a piece at cLocation because the color of that piece is used to determine what side is "checking" and what side is "being checked". Parameters: POSITION *pos : the board COOR cRemove : the square where a piece hypothetically removed from COOR cLocation : the square where the attackee is sitting Return value: COOR : the location of an attacker piece or 0x88 (!IS_ON_BOARD) if the removal of cRemove does not expose check. **/ { register int iDelta; register COOR cBlockIndex; int iIndex; PIECE xPiece; ASSERT(IS_ON_BOARD(cRemove)); ASSERT(IS_ON_BOARD(cLocation)); ASSERT(!IS_EMPTY(pos->rgSquare[cLocation].pPiece)); iIndex = (int)cLocation - (int)cRemove; // // If there is no way for a queen sitting at the square removed to // reach the square we are testing (i.e. the two squares are not // on the same rank, file, or diagonal) then there is no way // removing it can expose cLocation to check. // if (0 == (CHECK_VECTOR_WITH_INDEX(iIndex, BLACK) & (1 << QUEEN))) { return(ILLEGAL_COOR); } iDelta = CHECK_DELTA_WITH_INDEX(iIndex); for (cBlockIndex = cLocation + iDelta; IS_ON_BOARD(cBlockIndex); cBlockIndex += iDelta) { if (cBlockIndex == cRemove) { continue; } xPiece = pos->rgSquare[cBlockIndex].pPiece; if (!IS_EMPTY(xPiece)) { // // Is it an enemy? // if (OPPOSITE_COLORS(xPiece, pos->rgSquare[cLocation].pPiece)) { // // Does it move the right way to attack? // iIndex = (int)cBlockIndex - (int)cLocation; if (0 != (CHECK_VECTOR_WITH_INDEX(iIndex, GET_COLOR(xPiece)) & (1 << (PIECE_TYPE(xPiece))))) { return(cBlockIndex); } } // // Either we found another friendly piece or an enemy piece // that was unable to reach us. Either way we are safe. // return(ILLEGAL_COOR); } } // // We fell off the board without seeing another piece. // return(ILLEGAL_COOR); } COOR ExposesCheckEp(POSITION *pos, COOR cTest, COOR cIgnore, COOR cBlock, COOR cKing) /** Routine description: Parameters: POSITION *pos, COOR cTest : The square from whence the attack comes COOR cIgnore : Ignore this square, the pawn moved COOR cBlock : This square is where the pawn moved to and now blocks COOR cKing : The square under attack Return value: COOR **/ { register int iDelta; register COOR cBlockIndex; int iIndex; PIECE xPiece; ASSERT(IS_ON_BOARD(cTest)); ASSERT(IS_ON_BOARD(cIgnore)); ASSERT(IS_ON_BOARD(cBlock)); ASSERT(IS_ON_BOARD(cKing)); iIndex = (int)cKing - (int)cTest; // // If there is no way for a queen sitting at the square removed to // reach the square we are testing (i.e. the two squares are not // on the same rank, file, or diagonal) then no problemo. // if (0 == (CHECK_VECTOR_WITH_INDEX(iIndex, BLACK) & (1 << QUEEN))) { return(ILLEGAL_COOR); } iDelta = CHECK_DELTA_WITH_INDEX(iIndex); for (cBlockIndex = cKing + iDelta; IS_ON_BOARD(cBlockIndex); cBlockIndex += iDelta) { if (cBlockIndex == cTest) continue; if (cBlockIndex == cIgnore) continue; if (cBlockIndex == cBlock) return(ILLEGAL_COOR); xPiece = pos->rgSquare[cBlockIndex].pPiece; if (!IS_EMPTY(xPiece)) { if (OPPOSITE_COLORS(xPiece, pos->rgSquare[cKing].pPiece)) { // // Does it move the right way to attack? // iIndex = (int)cBlockIndex - (int)cKing; if (0 != (CHECK_VECTOR_WITH_INDEX(iIndex, GET_COLOR(xPiece)) & (1 << (PIECE_TYPE(xPiece))))) { return(cBlockIndex); } } // // Either we found another friendly piece or an enemy piece // that was unable to reach us. Either way we are safe. // return(ILLEGAL_COOR); } } // // We fell off the board without seeing another piece. // return(ILLEGAL_COOR); } // // board_representation/MOVEGEN_MIGRATION.md section 6b: bitboard // equivalent of IsAttacked/InCheck. IsAttacked's own direct callers // (move.c/san.c castling-through-check legality) are cold, but InCheck // -- a thin wrapper around it -- has ~70 call sites across // search.c/move.c/eval.c/root.c/dynamic.c, called constantly through // search; this is a much hotter target than its direct-caller count // alone would suggest. // // Design: _WhoAttacksSquareBB (see.c, already exposed) already answers // "which of uSide's knight/bishop/rook/queen/king pieces attack this // square" via the same magic-table substrate as everything else in // this migration -- IsAttackedBB is just that function reduced to a // boolean, plus a separate pawn-attack check via g_PawnAttackOriginBB // (since _WhoAttacksSquareBB deliberately excludes pawns -- see its // own header comment). // FLAG IsAttackedBB(IN COOR cTest, IN POSITION *pos, IN ULONG uSide) /** Routine description: Bitboard equivalent of IsAttacked -- see that function's comment. Parameters: COOR cTest : the square we want to determine if is under attack POSITION *pos : the board ULONG uSide : the side we want to see if is attacking cTest Return value: FLAG : TRUE if uSide attacks cTest, FALSE otherwise **/ { BITBOARD bbOccupied; ASSERT(IS_ON_BOARD(cTest)); ASSERT(IS_VALID_COLOR(uSide)); bbOccupied = _BuildFullOccupiedBB(pos); if (0 != _WhoAttacksSquareBB(pos, cTest, uSide, bbOccupied)) { return(TRUE); } return(0 != (g_PawnAttackOriginBB[uSide][cTest] & pos->bbPawns[uSide])); } FLAG InCheckBB(IN POSITION *pos, IN ULONG uSide) /** Routine description: Bitboard equivalent of InCheck -- see that function's comment. Parameters: POSITION *pos : the board ULONG uSide : the side we want to determine if is in check Return value: FLAG : TRUE if side is in check, FALSE otherwise. **/ { COOR cKingLoc = pos->cNonPawns[uSide][0]; ASSERT(IS_VALID_COLOR(uSide)); ASSERT(IS_KING(pos->rgSquare[cKingLoc].pPiece)); ASSERT(GET_COLOR(pos->rgSquare[cKingLoc].pPiece) == uSide); return IsAttackedBB(cKingLoc, pos, FLIP(uSide)); } FLAG IsAttacked(COOR cTest, POSITION *pos, ULONG uSide) /** Routine description: Determine whether the square cTest is attacked by the side uSide. Parameters: COOR cTest : the square we want to determine if is under attack POSITION *pos : the board ULONG uSide : the side we want to see if is attacking cTest Return value: FLAG : TRUE if uSide attacks cTest, FALSE otherwise **/ { ULONG u; PIECE pPiece; COOR cLocation; COOR cBlockIndex; int iIndex; int iDelta; static int iPawnLoc[2] = { -17, +15 }; static PIECE pPawn[2] = { BLACK_PAWN, WHITE_PAWN }; ASSERT(IS_ON_BOARD(cTest)); ASSERT(IS_VALID_COLOR(uSide)); ASSERT((pos->uNonPawnCount[uSide][0] - 1) < 16); // // Begin at the end because the king is the 0th item in the list and // we want to consider king moves last. // for (u = pos->uNonPawnCount[uSide][0] - 1; u != (ULONG)-1; u--) { cLocation = pos->cNonPawns[uSide][u]; ASSERT(IS_ON_BOARD(cLocation)); pPiece = pos->rgSquare[cLocation].pPiece; ASSERT(!IS_EMPTY(pPiece)); ASSERT(!IS_PAWN(pPiece)); ASSERT(GET_COLOR(pPiece) == uSide); iIndex = (int)cLocation - (int)cTest; if (!(CHECK_VECTOR_WITH_INDEX(iIndex, uSide) & (1 << (PIECE_TYPE(pPiece))))) { continue; } // // These pieces do not slide, we don't need to look for // blockers. If they can get there then there is nothing // we can do to stop them. // if (IS_KNIGHT(pPiece) || IS_KING(pPiece)) { return(TRUE); } // // Well, here we have a sliding piece (bishop, rook or queen) // that is on the same line (file, rank or diagonal) as the // cTest. We now have to see if the attacker (pPiece) is // blocked or is free to attack cTest. // iDelta = NEG_DELTA_WITH_INDEX(iIndex); for (cBlockIndex = cTest + iDelta; cBlockIndex != cLocation; cBlockIndex += iDelta) { if (!IS_EMPTY(pos->rgSquare[cBlockIndex].pPiece)) { break; } } if (cBlockIndex == cLocation) { return(TRUE); } } // // Check the locations a pawn could attack cTest from. // cLocation = cTest + iPawnLoc[uSide]; if (IS_ON_BOARD(cLocation) && (pos->rgSquare[cLocation].pPiece == pPawn[uSide])) { return(TRUE); } cLocation += 2; if (IS_ON_BOARD(cLocation) && (pos->rgSquare[cLocation].pPiece == pPawn[uSide])) { return(TRUE); } return(FALSE); } FLAG InCheck(POSITION *pos, ULONG uSide) /** Routine description: Determine if a side is in check or not. Parameters: POSITION *pos : the board ULONG uSide : the side we want to determine if is in check Return value: FLAG : TRUE if side is in check, FALSE otherwise. **/ { COOR cKingLoc; #ifdef DEBUG PIECE pKing; #endif ASSERT(IS_VALID_COLOR(uSide)); cKingLoc = pos->cNonPawns[uSide][0]; #ifdef DEBUG pKing = pos->rgSquare[cKingLoc].pPiece; ASSERT(IS_KING(pKing)); ASSERT(IS_VALID_COLOR(uSide)); ASSERT(GET_COLOR(pKing) == uSide); #endif return(IsAttacked(cKingLoc, pos, FLIP(uSide))); } static FLAG _SanityCheckPawnMove(POSITION *pos, MOVE mv) /** Routine description: Parameters: POSITION *pos, MOVE mv Return value: FLAG **/ { PIECE p = mv.pMoved; COOR cFrom = mv.cFrom; COOR cTo = mv.cTo; ASSERT(mv.uMove); ASSERT(IS_PAWN(p)); // // General sanity checking... // if (!IS_ON_BOARD(cFrom) || !IS_ON_BOARD(cTo)) { return(FALSE); } // // Sanity check promotions. // if (mv.pPromoted) { if (GET_COLOR(p) == WHITE) { if ((RANK(cTo) != 8) && (RANK(cFrom) != 7)) return(FALSE); } else { if ((RANK(cTo) != 1) && (RANK(cFrom) != 2)) return(FALSE); } if (!IS_KNIGHT(mv.pPromoted) && !IS_BISHOP(mv.pPromoted) && !IS_ROOK(mv.pPromoted) && !IS_QUEEN(mv.pPromoted)) { return(FALSE); } } // // Handle capture moves. // if (mv.pCaptured) { // // Must be capturing something // if (IS_SPECIAL_MOVE(mv) && (!mv.pPromoted)) { // // en passant // if (!IS_EMPTY(pos->rgSquare[cTo].pPiece)) return(FALSE); } else { // // normal capture // if (IS_EMPTY(pos->rgSquare[cTo].pPiece)) return(FALSE); if (!OPPOSITE_COLORS(mv.pMoved, mv.pCaptured)) return(FALSE); } // // Must be in the capturing position. // if (WHITE == GET_COLOR(p)) { if (((cFrom - 17) != cTo) && ((cFrom - 15) != cTo)) return(FALSE); } else { if (((cFrom + 17) != cTo) && ((cFrom + 15) != cTo)) return(FALSE); } if ((IS_SPECIAL_MOVE(mv)) && (!mv.pPromoted) && (pos->cEpSquare != cTo)) return(FALSE); return(TRUE); } else { // // If the pawn is not capturing, the TO square better be empty. // if (!IS_EMPTY(pos->rgSquare[cTo].pPiece)) return(FALSE); // // A non-capturing pawn can only push forward. One or two squares // based on whether or not its the initial move. // if (WHITE == GET_COLOR(p)) { if (cTo == cFrom - 16) return(TRUE); if ((cTo == cFrom - 32) && (RANK2(cFrom)) && (IS_EMPTY(pos->rgSquare[cFrom - 16].pPiece))) return(TRUE); } else { if (cTo == cFrom + 16) return(TRUE); if ((cTo == cFrom + 32) && (RANK7(cFrom)) && (IS_EMPTY(pos->rgSquare[cFrom + 16].pPiece))) return(TRUE); } } return(FALSE); } static FLAG _SanityCheckPieceMove(POSITION *pos, MOVE mv) /** Routine description: Parameters: POSITION *pos, MOVE mv Return value: static **/ { PIECE p = mv.pMoved; PIECE pPieceType = p >> 1; int iIndex; COOR cFrom = mv.cFrom; COOR cTo = mv.cTo; COOR cBlock; COOR cAttack; COOR cKing; int iDelta; ASSERT(!IS_PAWN(p)); // // Handle castling // if (IS_CASTLE(mv)) { ASSERT(IS_KING(mv.pMoved)); ASSERT(IS_SPECIAL_MOVE(mv)); return(TRUE); } // // Make sure the piece moves in the way the move describes. // iIndex = (int)cFrom - (int)cTo; if (0 == (CHECK_VECTOR_WITH_INDEX(iIndex, BLACK) & (1 << pPieceType))) { return(FALSE); } // // If we get here the piece can move in the way described by the // move but we still have to check to see if there are any other // pieces in the way if the piece moved is not a king or knight // (pawns handled in their own routine, see above). // if ((pPieceType == QUEEN) || (pPieceType == ROOK) || (pPieceType == BISHOP)) { iDelta = CHECK_DELTA_WITH_INDEX(iIndex); for (cBlock = cFrom + iDelta; cBlock != cTo; cBlock += iDelta) { if (!IS_EMPTY(pos->rgSquare[cBlock].pPiece)) { break; } } if (cBlock != cTo) return(FALSE); } // // Ok the piece can move the way they asked and there are no other // pieces in the way... but it cannot expose its own king to check // by doing so! // cKing = pos->cNonPawns[pos->uToMove][0]; cAttack = ExposesCheck(pos, cFrom, cKing); if ((ILLEGAL_COOR != cAttack) && (cTo != cAttack)) { // // Ok if we are here then removing this piece from the from square // does expose the king to check and the move does not capture the // checking piece. But it's still ok as long as the TO location // still blocks the checking piece. // iIndex = cAttack - cKing; iDelta = CHECK_DELTA_WITH_INDEX(iIndex); for (cBlock = cAttack + iDelta; cBlock != cKing; cBlock += iDelta) { if ((cBlock == cTo) || !IS_EMPTY(pos->rgSquare[cBlock].pPiece)) break; } if (cBlock == cKing) return(FALSE); } // // Legal! // return(TRUE); } FLAG SanityCheckMove(POSITION *pos, MOVE mv) /** Routine description: Sanity check a move -- Note: Not a strict chess legality checker! Parameters: POSITION *pos, MOVE mv Return value: FLAG **/ { register PIECE p = mv.pMoved; if (0 == mv.uMove) { return(FALSE); } else if (mv.cTo == mv.cFrom) { return(FALSE); } else if (IS_EMPTY(pos->rgSquare[mv.cFrom].pPiece)) { return(FALSE); } else if (GET_COLOR(mv.pMoved) != pos->uToMove) { return(FALSE); } else if ((!IS_EMPTY(pos->rgSquare[mv.cTo].pPiece)) && (0 == mv.pCaptured)) { return(FALSE); } if (!IS_SPECIAL_MOVE(mv)) { if (mv.pCaptured) { if (IS_EMPTY(pos->rgSquare[mv.cTo].pPiece)) { return(FALSE); } if (((pos->rgSquare[mv.cTo].pPiece) != mv.pCaptured) || (!OPPOSITE_COLORS(mv.pCaptured, mv.pMoved))) { return(FALSE); } } if (!IS_EMPTY(pos->rgSquare[mv.cTo].pPiece) && !mv.pCaptured) { return(FALSE); } } else { if (!IS_PAWN(p) && !IS_KING(p)) { return(FALSE); } } if (IS_PAWN(p)) { return(_SanityCheckPawnMove(pos, mv)); } else { return(_SanityCheckPieceMove(pos, mv)); } } FLAG LooksLikeFile(CHAR c) /** Routine description: Does some char look like a file (i.e. 'a' <= char <= 'h') Parameters: CHAR c Return value: FLAG **/ { if ((toupper(c) >= 'A') && (toupper(c) <= 'H')) { return(TRUE); } return(FALSE); } FLAG LooksLikeRank(CHAR c) /** Routine description: Does char look like a coor rank (i.e. '1' <= char <= '8') Parameters: CHAR c Return value: FLAG **/ { if (((c - '0') >= 1) && ((c - '0') <= 8)) { return(TRUE); } return(FALSE); } FLAG LooksLikeCoor(char *szData) /** Routine description: Do the first two chars in szData look like a file/rank? Parameters: char *szData Return value: FLAG **/ { char f = szData[0]; char r = szData[1]; if (LooksLikeFile(f) && LooksLikeRank(r)) { return(TRUE); } return(FALSE); } CHAR * StripMove(CHAR *szMove) /** Routine description: Strip decoration punctuation marks out of a move. Parameters: CHAR *szMove Return value: CHAR **/ { CHAR cIgnore[] = "?!x+#-=\r\n"; // chars stripped from szMove static CHAR szStripped[10]; ULONG y; CHAR *p; memset(szStripped, 0, sizeof(szStripped)); p = szMove; y = 0; while (*p != '\0') { if (NULL == strchr(cIgnore, *p)) { szStripped[y++] = *p; if (y >= 8) break; } p++; } return(szStripped); } ULONG LooksLikeMove(char *szData) /** Routine description: Does some char pointer point at some text that looks like a move? If so, does the move look like SAN or ICS style? Parameters: char *szData Return value: ULONG **/ { CHAR *szStripped = StripMove(szData); ULONG u; static CHAR cPieces[] = { 'P', 'N', 'B', 'R', 'Q', 'K', '\0' }; // // A (stripped) move must be at least two characters long even in // SAN. // if ((strlen(szStripped) < 2) || (strlen(szStripped) > 7)) { return(NOT_MOVE); } // // O-O, O-O-O // if (!STRNCMPI(szStripped, "OOO", 3) || !STRNCMPI(szStripped, "OO", 2) || !STRNCMPI(szStripped, "00", 2) || // duh !STRNCMPI(szStripped, "000", 3)) { return(MOVE_SAN); } // // COOR COOR (d2d4) // if (LooksLikeCoor(szStripped) && LooksLikeCoor(szStripped + 2)) { return(MOVE_ICS); } // // COOR (d4) // if (LooksLikeCoor(szStripped) && strlen(szStripped) == 2) { return(MOVE_SAN); } // // RANK COOR // if ((LooksLikeRank(szStripped[0]) || LooksLikeFile(szStripped[0])) && LooksLikeCoor(&szStripped[1])) { return(MOVE_SAN); } // // PIECE COOR COOR // PIECE COOR // PIECE FILE COOR // PIECE RANK COOR // for (u = 0; u < ARRAY_LENGTH(cPieces); u++) { if (szStripped[0] == cPieces[u]) // must be uppercase! { if (LooksLikeCoor(&szStripped[1])) { return(MOVE_SAN); } if (LooksLikeFile(szStripped[1]) && LooksLikeCoor(&szStripped[2])) { return(MOVE_SAN); } if (LooksLikeRank(szStripped[1]) && LooksLikeCoor(&szStripped[2])) { return(MOVE_SAN); } } } // // (COORD)=(PIECE) // if ((strlen(szStripped) == 4) && LooksLikeCoor(szStripped) && szStripped[2] == '=') { if (NULL != strchr(cPieces, szStripped[3])) { return(MOVE_SAN); } } // // (COOR)(PIECE) // if ((strlen(szStripped) == 3) && LooksLikeCoor(szStripped) && (NULL != strchr(cPieces, szStripped[2]))) { return(MOVE_SAN); } return(NOT_MOVE); } void FASTCALL SelectBestWithHistory(SEARCHER_THREAD_CONTEXT *ctx, ULONG u) /** Routine description: Pick the best (i.e. move with the highest "score" assigned to it at generation time) that has not been played yet this ply and move it to the front of the move list to be played next. Parameters: SEARCHER_THREAD_CONTEXT *ctx, ULONG u Return value: void FASTCALL **/ { register ULONG v; register ULONG uEnd = ctx->sMoveStack.uEnd[ctx->uPly]; register SCORE iBestVal; ULONG uLoc; SCORE iVal; MOVE mv; MOVE_STACK_MOVE_VALUE_FLAGS mvfTemp; MOVE mvLast; ULONG uPrevContKey = 0; FLAG fHaveContinuation = FALSE; COOR cEnprise; ASSERT(ctx->sMoveStack.uBegin[ctx->uPly] <= uEnd); ASSERT(u >= ctx->sMoveStack.uBegin[ctx->uPly]); ASSERT(u < uEnd); // Continuation history: "did a move like this tend to fail high // right after a move like that?", keyed by (previous move, this // move) at the same [piece][to] coarseness g_HistoryCounters // already uses. Same accumulation/decay math as g_HistoryCounters // (see _IncrementContinuationCounter/_DecrementContinuationCounter, // dynamic.c) so its magnitude is empirically self-calibrated rather // than a hand-picked constant -- a pair seen once contributes // almost nothing, a pair that's fail-highed repeatedly at real // depth naturally grows to compete with PSQT+history. if ((ctx->uPly > 0) && (0 != (mvLast = (ctx->sPlyInfo[ctx->uPly - 1]).mv).uMove)) { uPrevContKey = MOVE_TO_CONT_KEY(mvLast); fHaveContinuation = TRUE; } // Flee-to-safety: a small, same-tier selection-time nudge (not a // GOOD_MOVE promotion -- that class was retired, see generate.c's // RETIRED comment) for a quiet move whose origin square is // currently en prise. cEnprise = FindEnprisePiece(ctx, ctx->sPosition.uToMove); // // Linear search from u..ctx->sMoveStack.uEnd[ctx->uPly] for the // move with the best value. // iBestVal = ctx->sMoveStack.mvf[u].iValue; mv = ctx->sMoveStack.mvf[u].mv; if (!IS_CAPTURE_OR_PROMOTION(mv)) { iBestVal += g_HistoryCounters[mv.pMoved][mv.cTo]; if (TRUE == fHaveContinuation) { iBestVal += CONTINUATION_SCALE * g_ContinuationHistory[(uPrevContKey * CONT_KEY_RANGE) + MOVE_TO_CONT_KEY(mv)]; } if (mv.cFrom == cEnprise) { iBestVal += FLEE_BONUS; } } uLoc = u; for (v = u + 1; v < uEnd; v++) { iVal = ctx->sMoveStack.mvf[v].iValue; mv = ctx->sMoveStack.mvf[v].mv; if (!IS_CAPTURE_OR_PROMOTION(mv)) { iVal += g_HistoryCounters[mv.pMoved][mv.cTo]; if (TRUE == fHaveContinuation) { iVal += g_ContinuationHistory[(uPrevContKey * CONT_KEY_RANGE) + MOVE_TO_CONT_KEY(mv)]; } if (mv.cFrom == cEnprise) { iVal += FLEE_BONUS; } } if (iVal > iBestVal) { iBestVal = iVal; uLoc = v; } } // // Note: the if here slows down the code, just swap em. // mvfTemp = ctx->sMoveStack.mvf[u]; ctx->sMoveStack.mvf[u] = ctx->sMoveStack.mvf[uLoc]; ctx->sMoveStack.mvf[uLoc] = mvfTemp; } void FASTCALL SelectBestNoHistory(SEARCHER_THREAD_CONTEXT *ctx, ULONG u) /** Routine description: Pick the best (i.e. move with the highest "score" assigned to it at generation time) that has not been played yet this ply and move it to the front of the move list to be played next. Parameters: SEARCHER_THREAD_CONTEXT *ctx, ULONG u Return value: void FASTCALL **/ { register ULONG v; register ULONG uEnd = ctx->sMoveStack.uEnd[ctx->uPly]; register SCORE iBestVal; ULONG uLoc; SCORE iVal; MOVE_STACK_MOVE_VALUE_FLAGS mvfTemp; ASSERT(ctx->sMoveStack.uBegin[ctx->uPly] <= uEnd); ASSERT(u >= ctx->sMoveStack.uBegin[ctx->uPly]); ASSERT(u < uEnd); // // Linear search from u..ctx->sMoveStack.uEnd[ctx->uPly] for the // move with the best value. // iBestVal = ctx->sMoveStack.mvf[u].iValue; uLoc = u; for (v = u + 1; v < uEnd; v++) { iVal = ctx->sMoveStack.mvf[v].iValue; if (iVal > iBestVal) { iBestVal = iVal; uLoc = v; } } // // Note: the if here slows down the code, just swap em. // mvfTemp = ctx->sMoveStack.mvf[u]; ctx->sMoveStack.mvf[u] = ctx->sMoveStack.mvf[uLoc]; ctx->sMoveStack.mvf[uLoc] = mvfTemp; } void FASTCALL SelectMoveAtRoot(SEARCHER_THREAD_CONTEXT *ctx, ULONG u) /** Routine description: Parameters: SEARCHER_THREAD_CONTEXT *ctx, ULONG u Return value: void FASTCALL **/ { ULONG v = u; ULONG uEnd = ctx->sMoveStack.uEnd[ctx->uPly]; SCORE iBestVal = -INFINITY; ULONG uLoc = v; SCORE iVal; MOVE_STACK_MOVE_VALUE_FLAGS mvfTemp; ASSERT(ctx->sMoveStack.uBegin[ctx->uPly] <= uEnd); ASSERT(u >= ctx->sMoveStack.uBegin[ctx->uPly]); ASSERT(u < uEnd); ASSERT(MOVE_COUNT(ctx, ctx->uPly) >= 1); // // Find the first move that we have not already searched. It will // provide our initial iBestVal. // do { if (!(ctx->sMoveStack.mvf[v].bvFlags & MVF_MOVE_SEARCHED)) { iBestVal = ctx->sMoveStack.mvf[v].iValue; uLoc = v; break; } v++; } while(v < uEnd); if (v >= uEnd) return; // // Search the rest of the moves that have not yet been tried by // RootSearch and find the one with the best value. // for (v = uLoc + 1; v < uEnd; v++) { if (!(ctx->sMoveStack.mvf[v].bvFlags & MVF_MOVE_SEARCHED)) { iVal = ctx->sMoveStack.mvf[v].iValue; if (iVal > iBestVal) { iBestVal = iVal; uLoc = v; } } } // // Move the best move we found into position u. // mvfTemp = ctx->sMoveStack.mvf[u]; ctx->sMoveStack.mvf[u] = ctx->sMoveStack.mvf[uLoc]; ctx->sMoveStack.mvf[uLoc] = mvfTemp; } static UINT64 g_uPerftNodeCount; static UINT64 g_uPerftTotalNodes; static UINT64 g_uPerftGenerates; void Perft(SEARCHER_THREAD_CONTEXT *ctx, ULONG uDepth) { MOVE mv; ULONG u; ULONG uPly; g_uPerftTotalNodes += 1; ASSERT(uDepth < MAX_PLY_PER_SEARCH); if (uDepth == 0) { g_uPerftNodeCount += 1; return; } mv.uMove = 0; g_uPerftGenerates += 1; GenerateMoves(ctx, mv, GENERATE_DONT_SCORE); uPly = ctx->uPly; for (u = ctx->sMoveStack.uBegin[uPly]; u < ctx->sMoveStack.uEnd[uPly]; u++) { mv = ctx->sMoveStack.mvf[u].mv; if (MakeMove(ctx, mv)) { Perft(ctx, uDepth - 1); UnmakeMove(ctx, mv); } } } COMMAND(PerftCommand) /** Routine description: This function implements the 'perft' engine command. I have no idea what 'perft' means but some people use this command to benchmark the speed of the move generator code. Note: the way this is implemented here does nothing whatsoever with the move scoring code (i.e. the SEE) Usage: perft Parameters: The COMMAND macro hides four arguments from the input parser: CHAR *szInput : the full line of input ULONG argc : number of argument chunks CHAR *argv[] : array of ptrs to each argument chunk POSITION *pos : a POSITION pointer to operate on Return value: void **/ { LIGHTWEIGHT_SEARCHER_CONTEXT ctx; ULONG u; ULONG uDepth; double dBegin, dTime; double dNps; if (argc < 2) { Trace("Usage: perft \n"); return; } uDepth = atoi(argv[1]); if (uDepth >= MAX_DEPTH_PER_SEARCH) { Trace("Error: invalid depth.\n"); return; } InitializeLightweightSearcherContext(pos, &ctx); g_uPerftTotalNodes = g_uPerftGenerates = 0ULL; dBegin = SystemTimeStamp(); for (u = 1; u <= uDepth; u++) { g_uPerftNodeCount = 0ULL; Perft((SEARCHER_THREAD_CONTEXT *)&ctx, u); Trace("%u. %" COMPILER_LONGLONG_UNSIGNED_FORMAT " node%s, " "%" COMPILER_LONGLONG_UNSIGNED_FORMAT " generate%s.\n", u, g_uPerftNodeCount, (g_uPerftNodeCount > 1) ? "s" : "", g_uPerftGenerates, (g_uPerftGenerates > 1) ? "s" : ""); } dTime = SystemTimeStamp() - dBegin; dNps = (double)g_uPerftTotalNodes; dNps /= dTime; Trace("%" COMPILER_LONGLONG_UNSIGNED_FORMAT " total nodes, " "%" COMPILER_LONGLONG_UNSIGNED_FORMAT " total generates " "in %6.2f seconds.\n", g_uPerftTotalNodes, g_uPerftGenerates, dTime); Trace("That's approx %.0f moves/sec\n", dNps); }