From: Alain SAVARD Date: Sat, 4 Jan 2020 18:54:35 +0000 (-0500) Subject: Use a faster implementation of Static Exchange Evaluation X-Git-Url: https://git.sesse.net/?p=stockfish;a=commitdiff_plain;h=83ecfa7c33ab3e89fcbc506f0f4d5312baa26aeb;hp=44f56e04e22bb449d44475eb054b67c1c22d27ef;ds=sidebyside Use a faster implementation of Static Exchange Evaluation SEE (Static Exchange Evaluation) is a critical component, so we might indulge some tricks to make it faster. Another pull request #2469 showed some speedup by removing templates, this version uses Ronald de Man (@syzygy1) SEE implementation which also unrolls the for loop by suppressing the min_attacker() helper function and exits as soon as the last swap is conclusive. See Ronald de Man version there: https://github.com/syzygy1/Cfish/blob/master/src/position.c Patch testes against pull request #2469: LLR: 2.95 (-2.94,2.94) {-1.00,3.00} Total: 19365 W: 3771 L: 3634 D: 11960 Ptnml(0-2): 241, 1984, 5099, 2092, 255 http://tests.stockfishchess.org/tests/view/5e10eb135e5436dd91b27ba3 And since we are using new SPRT statistics, and that both pull requests finished with less than 20000 games I also tested against master as a speed-up: LLR: 2.99 (-2.94,2.94) {-1.00,3.00} Total: 18878 W: 3674 L: 3539 D: 11665 Ptnml(0-2): 193, 1999, 4966, 2019, 250 http://tests.stockfishchess.org/tests/view/5e10febf12ef906c8b388745 Non functional change --- diff --git a/src/position.cpp b/src/position.cpp index 6336a5ed..9644e02c 100644 --- a/src/position.cpp +++ b/src/position.cpp @@ -50,41 +50,6 @@ const string PieceToChar(" PNBRQK pnbrqk"); constexpr Piece Pieces[] = { W_PAWN, W_KNIGHT, W_BISHOP, W_ROOK, W_QUEEN, W_KING, B_PAWN, B_KNIGHT, B_BISHOP, B_ROOK, B_QUEEN, B_KING }; - -// min_attacker() is a helper function used by see_ge() to locate the least -// valuable attacker for the side to move, remove the attacker we just found -// from the bitboards and scan for new X-ray attacks behind it. - -template -PieceType min_attacker(const Bitboard* byTypeBB, Square to, Bitboard stmAttackers, - Bitboard& occupied, Bitboard& attackers) { - - Bitboard b = stmAttackers & byTypeBB[Pt]; - if (!b) - return min_attacker(byTypeBB, to, stmAttackers, occupied, attackers); - - 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) & (byTypeBB[BISHOP] | byTypeBB[QUEEN]); - - if (Pt == ROOK || Pt == QUEEN) - attackers |= attacks_bb(to, occupied) & (byTypeBB[ROOK] | byTypeBB[QUEEN]); - - // 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 Pt; -} - -template<> -PieceType min_attacker(const Bitboard*, Square, Bitboard, Bitboard&, Bitboard&) { - return KING; // No need to update bitboards: it is the last cycle -} - } // namespace @@ -1052,77 +1017,96 @@ 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 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. - balance = PieceValue[MG][piece_on(to)] - threshold; - if (balance < VALUE_ZERO) + int swap = PieceValue[MG][piece_on(to)] - threshold; + if (swap < 0) return false; - // Now assume the worst possible result: that the opponent can - // capture our piece for free. - balance -= PieceValue[MG][nextVictim]; - - // 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) + swap = PieceValue[MG][piece_on(from)] - swap; + if (swap <= 0) return true; - // 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; + Bitboard occ = pieces() ^ from ^ to; + Color stm = color_of(piece_on(from)); + Bitboard attackers = attackers_to(to, occ); + Bitboard stmAttackers, bb; + int res = 1; while (true) { - stmAttackers = attackers & pieces(stm); + stm = ~stm; + attackers &= occ; + + // If stm has no more attackers then give up: stm loses + if (!(stmAttackers = attackers & pieces(stm))) + break; // Don't allow pinned pieces to attack (except the king) as long as - // any pinners are on their original square. - if (st->pinners[~stm] & occupied) + // there are pinners on their original square. + if (st->pinners[~stm] & occ) stmAttackers &= ~st->blockersForKing[stm]; - // If stm has no more attackers then give up: stm loses if (!stmAttackers) break; + res ^= 1; + // 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); + // the bitboard 'attackers' any X-ray attackers behind it. + if ((bb = stmAttackers & pieces(PAWN))) + { + if ((swap = PawnValueMg - swap) < res) + break; - stm = ~stm; // Switch side to move + occ ^= lsb(bb); + attackers |= attacks_bb(to, occ) & pieces(BISHOP, QUEEN); + } - // Negamax the balance with alpha = balance, beta = balance+1 and - // add nextVictim's value. - // - // (balance, balance+1) -> (-balance-1, -balance) - // - assert(balance < VALUE_ZERO); + else if ((bb = stmAttackers & pieces(KNIGHT))) + { + if ((swap = KnightValueMg - swap) < res) + break; - balance = -balance - 1 - PieceValue[MG][nextVictim]; + occ ^= lsb(bb); + } - // 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) + else if ((bb = stmAttackers & pieces(BISHOP))) { - if (nextVictim == KING && (attackers & pieces(stm))) - stm = ~stm; - break; + if ((swap = BishopValueMg - swap) < res) + break; + + occ ^= lsb(bb); + attackers |= attacks_bb(to, occ) & pieces(BISHOP, QUEEN); + } + + else if ((bb = stmAttackers & pieces(ROOK))) + { + if ((swap = RookValueMg - swap) < res) + break; + + occ ^= lsb(bb); + attackers |= attacks_bb(to, occ) & pieces(ROOK, QUEEN); + } + + else if ((bb = stmAttackers & pieces(QUEEN))) + { + if ((swap = QueenValueMg - swap) < res) + break; + + occ ^= lsb(bb); + attackers |= (attacks_bb(to, occ) & pieces(BISHOP, QUEEN)) + | (attacks_bb(to, occ) & pieces(ROOK , QUEEN)); } - assert(nextVictim != KING); + + else // KING + // If we "capture" with the king but opponent still has attackers, + // reverse the result. + return (attackers & ~pieces(stm)) ? res ^ 1 : res; } - return us != stm; // We break the above loop when stm loses -} + return res; +} /// Position::is_draw() tests whether the position is drawn by 50-move rule /// or by repetition. It does not detect stalemates.