From: Marco Costalba <mcostalba@gmail.com>
Date: Sat, 1 Sep 2012 09:45:14 +0000 (+0200)
Subject: Unroll least valuable attacker loop in SEE
X-Git-Url: https://git.sesse.net/?p=stockfish;a=commitdiff_plain;h=9cdca7516c9397f991b2c0194f5de1ade26622e8;hp=6436e75858f02d42df72243461c8a5f8bc7cb695;ds=inline

Unroll least valuable attacker loop in SEE

This allows to reduce the scanning for new X-ray attacks
according to the capturing piece type.

It seems to be just a very small speed increase in MSVC 64
bit and gcc 32 bit, I guess cache issues value more than some
instruction less to execute (as usual).

No functional change.
---

diff --git a/src/position.cpp b/src/position.cpp
index 1c63f2a9..e8689ea7 100644
--- a/src/position.cpp
+++ b/src/position.cpp
@@ -102,6 +102,37 @@ void init() {
 } // namespace Zobrist
 
 
+/// next_attacker() is an helper function used by see() to locate the least
+/// valuable attacker for the side to move, remove the attacker we just found
+/// from the 'occupied' bitboard and scan for new X-ray attacks behind it.
+
+template<PieceType Pt> static FORCE_INLINE
+PieceType next_attacker(const Bitboard* bb, const Square& to, const Bitboard& stmAttackers,
+                        Bitboard& occupied, Bitboard& attackers) {
+
+  const PieceType NextPt = PieceType((int)Pt + 1);
+
+  if (!(stmAttackers & bb[Pt]))
+      return next_attacker<NextPt>(bb, to, stmAttackers, occupied, attackers);
+
+  Bitboard b = stmAttackers & bb[Pt];
+  occupied ^= b & ~(b - 1);
+
+  if (Pt == PAWN || Pt == BISHOP || Pt == QUEEN)
+      attackers |= attacks_bb<BISHOP>(to, occupied) & (bb[BISHOP] | bb[QUEEN]);
+
+  if (Pt == ROOK || Pt == QUEEN)
+      attackers |= attacks_bb<ROOK>(to, occupied) & (bb[ROOK] | bb[QUEEN]);
+
+  return Pt;
+}
+
+template<> FORCE_INLINE
+PieceType next_attacker<KING>(const Bitboard*, const Square&, const Bitboard&, Bitboard&, Bitboard&) {
+  return KING; // No need to update bitboards, it is the last cycle
+}
+
+
 /// CheckInfo c'tor
 
 CheckInfo::CheckInfo(const Position& pos) {
@@ -1218,7 +1249,7 @@ int Position::see_sign(Move m) const {
 int Position::see(Move m) const {
 
   Square from, to;
-  Bitboard occupied, attackers, stmAttackers, b;
+  Bitboard occupied, attackers, stmAttackers;
   int swapList[32], slIndex = 1;
   PieceType captured;
   Color stm;
@@ -1274,19 +1305,10 @@ int Position::see(Move m) const {
       swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[Mg][captured];
       slIndex++;
 
-      // Locate the least valuable attacker for the side to move. The loop
-      // below looks like it is potentially infinite, but it isn't. We know
-      // that the side to move still has at least one attacker left.
-      for (captured = PAWN; (b = stmAttackers & pieces(captured)) == 0; captured++)
-          assert(captured < KING);
-
-      // Remove the attacker we just found from the 'occupied' bitboard,
-      // and scan for new X-ray attacks behind the attacker.
-      occupied ^= (b & (~b + 1));
-      attackers |=  (attacks_bb<ROOK>(to, occupied)   & pieces(ROOK, QUEEN))
-                  | (attacks_bb<BISHOP>(to, occupied) & pieces(BISHOP, QUEEN));
+      // Locate and remove from 'occupied' the next least valuable attacker
+      captured = next_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
 
-      attackers &= occupied; // Cut out pieces we've already done
+      attackers &= occupied; // Remove the just found attacker
       stm = ~stm;
       stmAttackers = attackers & pieces(stm);