From: Marco Costalba Date: Fri, 23 Feb 2018 21:02:10 +0000 (+0100) Subject: Reformat SEE to better document the function X-Git-Url: https://git.sesse.net/?p=stockfish;a=commitdiff_plain;h=a09eee579810fe446e34d0004e5716191310f4e4;ds=sidebyside Reformat SEE to better document the function This is one of the most difficult to understand but also most important and speed critical functions of SF. This patch rewrites some part of it to hopefully make it clearer and drop some redundant variables in the process. Same speed than master (or even a bit more). Thanks to Chris Cain for useful feedback. No functional change. --- diff --git a/src/bitboard.h b/src/bitboard.h index 5cafcfcc..cf948afc 100644 --- a/src/bitboard.h +++ b/src/bitboard.h @@ -160,15 +160,17 @@ constexpr Bitboard shift(Bitboard b) { : 0; } + /// pawn_attacks_bb() returns the pawn attacks for the given color from the /// squares in the given bitboard. -template +template constexpr Bitboard pawn_attacks_bb(Bitboard b) { - return c == WHITE ? shift(b) | shift(b) + return C == WHITE ? shift(b) | shift(b) : shift(b) | shift(b); } + /// adjacent_files_bb() returns a bitboard representing all the squares on the /// adjacent files of the given one. @@ -187,9 +189,9 @@ inline Bitboard between_bb(Square s1, Square s2) { } -/// forward_ranks_bb() returns a bitboard representing all the squares on all the ranks -/// in front of the given one, from the point of view of the given color. For -/// instance, forward_ranks_bb(BLACK, SQ_D3) will return the 16 squares on ranks 1 and 2. +/// forward_ranks_bb() returns a bitboard representing the squares on all the ranks +/// in front of the given one, from the point of view of the given color. For instance, +/// forward_ranks_bb(BLACK, SQ_D3) will return the 16 squares on ranks 1 and 2. inline Bitboard forward_ranks_bb(Color c, Square s) { return ForwardRanksBB[c][rank_of(s)]; diff --git a/src/evaluate.cpp b/src/evaluate.cpp index 0022ae4c..884b1d85 100644 --- a/src/evaluate.cpp +++ b/src/evaluate.cpp @@ -510,9 +510,9 @@ namespace { template template Score Evaluation::threats() const { - const Color Them = (Us == WHITE ? BLACK : WHITE); - const Direction Up = (Us == WHITE ? NORTH : SOUTH); - const Bitboard TRank3BB = (Us == WHITE ? Rank3BB : Rank6BB); + const Color Them = (Us == WHITE ? BLACK : WHITE); + const Direction Up = (Us == WHITE ? NORTH : SOUTH); + const Bitboard TRank3BB = (Us == WHITE ? Rank3BB : Rank6BB); Bitboard b, weak, defended, nonPawnEnemies, stronglyProtected, safeThreats; Score score = SCORE_ZERO; diff --git a/src/pawns.cpp b/src/pawns.cpp index 01e9632c..a1b53325 100644 --- a/src/pawns.cpp +++ b/src/pawns.cpp @@ -88,8 +88,8 @@ namespace { template Score evaluate(const Position& pos, Pawns::Entry* e) { - const Color Them = (Us == WHITE ? BLACK : WHITE); - const Direction Up = (Us == WHITE ? NORTH : SOUTH); + const Color Them = (Us == WHITE ? BLACK : WHITE); + const Direction Up = (Us == WHITE ? NORTH : SOUTH); Bitboard b, neighbours, stoppers, doubled, supported, phalanx; Bitboard lever, leverPush; diff --git a/src/position.cpp b/src/position.cpp index 7e12fdcc..fdae0ae0 100644 --- a/src/position.cpp +++ b/src/position.cpp @@ -60,22 +60,27 @@ const Piece Pieces[] = { W_PAWN, W_KNIGHT, W_BISHOP, W_ROOK, W_QUEEN, W_KING, // from the bitboards and scan for new X-ray attacks behind it. template -PieceType min_attacker(const Bitboard* bb, Square to, Bitboard stmAttackers, +PieceType min_attacker(const Bitboard* byTypeBB, Square to, Bitboard stmAttackers, Bitboard& occupied, Bitboard& attackers) { - Bitboard b = stmAttackers & bb[Pt]; + Bitboard b = stmAttackers & byTypeBB[Pt]; if (!b) - return min_attacker(bb, to, stmAttackers, occupied, attackers); + return min_attacker(byTypeBB, to, stmAttackers, occupied, attackers); - occupied ^= b & ~(b - 1); + occupied ^= lsb(b); // Remove the attacker from occupied + // Add any X-ray attack behind the just removed piece. For instance with + // rooks in a8 and a7 attacking a1, after removing a7 we add rook in a8. + // Note that new added attackers can be of any color. if (Pt == PAWN || Pt == BISHOP || Pt == QUEEN) - attackers |= attacks_bb(to, occupied) & (bb[BISHOP] | bb[QUEEN]); + attackers |= attacks_bb(to, occupied) & (byTypeBB[BISHOP] | byTypeBB[QUEEN]); if (Pt == ROOK || Pt == QUEEN) - attackers |= attacks_bb(to, occupied) & (bb[ROOK] | bb[QUEEN]); + attackers |= attacks_bb(to, occupied) & (byTypeBB[ROOK] | byTypeBB[QUEEN]); - attackers &= occupied; // After X-ray that may add already processed pieces + // X-ray may add already processed pieces because byTypeBB[] is constant: in + // the rook example, now attackers contains _again_ rook in a7, so remove it. + attackers &= occupied; return (PieceType)Pt; } @@ -997,11 +1002,12 @@ bool Position::see_ge(Move m, Value threshold) const { if (type_of(m) != NORMAL) return VALUE_ZERO >= threshold; + Bitboard stmAttackers; Square from = from_sq(m), to = to_sq(m); PieceType nextVictim = type_of(piece_on(from)); - Color stm = ~color_of(piece_on(from)); // First consider opponent's move - Value balance; // Values of the pieces taken by us minus opponent's ones - Bitboard occupied, stmAttackers; + Color us = color_of(piece_on(from)); + Color stm = ~us; // First consider opponent's move + Value balance; // Values of the pieces taken by us minus opponent's ones // The opponent may be able to recapture so this is the best result // we can hope for. @@ -1014,65 +1020,57 @@ bool Position::see_ge(Move m, Value threshold) const { // capture our piece for free. balance -= PieceValue[MG][nextVictim]; - if (balance >= VALUE_ZERO) // Always true if nextVictim == KING + // If it is enough (like in PxQ) then return immediately. Note that + // in case nextVictim == KING we always return here, this is ok + // if the given move is legal. + if (balance >= VALUE_ZERO) return true; - bool opponentToMove = true; - occupied = pieces() ^ from ^ to; - - // Find all attackers to the destination square, with the moving piece removed, - // but possibly an X-ray attacker added behind it. + // Find all attackers to the destination square, with the moving piece + // removed, but possibly an X-ray attacker added behind it. + Bitboard occupied = pieces() ^ from ^ to; Bitboard attackers = attackers_to(to, occupied) & occupied; while (true) { - // The balance is negative only because we assumed we could win - // the last piece for free. We are truly winning only if we can - // win the last piece _cheaply enough_. Test if we can actually - // do this otherwise "give up". - assert(balance < VALUE_ZERO); - stmAttackers = attackers & pieces(stm); - // Don't allow pinned pieces to attack pieces except the king as long all - // pinners are on their original square. + // Don't allow pinned pieces to attack (except the king) as long as + // all pinners are on their original square. if (!(st->pinnersForKing[stm] & ~occupied)) stmAttackers &= ~st->blockersForKing[stm]; - // If we have no more attackers we must give up + // If stm has no more attackers then give up: stm loses if (!stmAttackers) break; - // Locate and remove the next least valuable attacker + // Locate and remove the next least valuable attacker, and add to + // the bitboard 'attackers' the possibly X-ray attackers behind it. nextVictim = min_attacker(byTypeBB, to, stmAttackers, occupied, attackers); - if (nextVictim == KING) - { - // Our only attacker is the king. If the opponent still has - // attackers we must give up. Otherwise we make the move and - // (having no more attackers) the opponent must give up. - if (!(attackers & pieces(~stm))) - opponentToMove = !opponentToMove; - break; - } + stm = ~stm; // Switch side to move - // Assume the opponent can win the next piece for free and switch sides - balance += PieceValue[MG][nextVictim]; - opponentToMove = !opponentToMove; + // Negamax the balance with alpha = balance, beta = balance+1 and + // add nextVictim's value. + // + // (balance, balance+1) -> (-balance-1, -balance) + // + assert(balance < VALUE_ZERO); - // If balance is negative after receiving a free piece then give up - if (balance < VALUE_ZERO) - break; + balance = -balance - 1 - PieceValue[MG][nextVictim]; - // Complete the process of switching sides. The first line swaps - // all negative numbers with non-negative numbers. The compiler - // probably knows that it is just the bitwise negation ~balance. - balance = -balance-1; - stm = ~stm; + // If balance is still non-negative after giving away nextVictim then we + // win. The only thing to be careful about it is that we should revert + // stm if we captured with the king when the opponent still has attackers. + if (balance >= VALUE_ZERO) + { + if (nextVictim == KING && (attackers & pieces(stm))) + stm = ~stm; + break; + } + assert(nextVictim != KING); } - - // If the opponent gave up we win, otherwise we lose. - return opponentToMove; + return us != stm; // We break the above loop when stm loses }