+template<int Pt>
+PieceType min_attacker(const Bitboard* byTypeBB, Square to, Bitboard stmAttackers,
+ Bitboard& occupied, Bitboard& attackers) {
+
+ Bitboard b = stmAttackers & byTypeBB[Pt];
+ if (!b)
+ return min_attacker<Pt + 1>(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<BISHOP>(to, occupied) & (byTypeBB[BISHOP] | byTypeBB[QUEEN]);
+
+ if (Pt == ROOK || Pt == QUEEN)
+ attackers |= attacks_bb<ROOK>(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 (PieceType)Pt;
+}
+
+template<>
+PieceType min_attacker<KING>(const Bitboard*, Square, Bitboard, Bitboard&, Bitboard&) {
+ return KING; // No need to update bitboards: it is the last cycle
+}
+
+} // namespace
+
+
+/// operator<<(Position) returns an ASCII representation of the position
+
+std::ostream& operator<<(std::ostream& os, const Position& pos) {
+
+ os << "\n +---+---+---+---+---+---+---+---+\n";
+
+ for (Rank r = RANK_8; r >= RANK_1; --r)
+ {
+ for (File f = FILE_A; f <= FILE_H; ++f)
+ os << " | " << PieceToChar[pos.piece_on(make_square(f, r))];
+
+ os << " |\n +---+---+---+---+---+---+---+---+\n";
+ }
+
+ os << "\nFen: " << pos.fen() << "\nKey: " << std::hex << std::uppercase
+ << std::setfill('0') << std::setw(16) << pos.key()
+ << std::setfill(' ') << std::dec << "\nCheckers: ";
+
+ for (Bitboard b = pos.checkers(); b; )
+ os << UCI::square(pop_lsb(&b)) << " ";
+
+ if ( int(Tablebases::MaxCardinality) >= popcount(pos.pieces())
+ && !pos.can_castle(ANY_CASTLING))
+ {
+ StateInfo st;
+ Position p;
+ p.set(pos.fen(), pos.is_chess960(), &st, pos.this_thread());
+ Tablebases::ProbeState s1, s2;
+ Tablebases::WDLScore wdl = Tablebases::probe_wdl(p, &s1);
+ int dtz = Tablebases::probe_dtz(p, &s2);
+ os << "\nTablebases WDL: " << std::setw(4) << wdl << " (" << s1 << ")"
+ << "\nTablebases DTZ: " << std::setw(4) << dtz << " (" << s2 << ")";
+ }
+
+ return os;
+}
+
+
+// Marcel van Kervinck's cuckoo algorithm for fast detection of "upcoming repetition"
+// situations. Description of the algorithm in the following paper:
+// https://marcelk.net/2013-04-06/paper/upcoming-rep-v2.pdf
+
+// First and second hash functions for indexing the cuckoo tables
+inline int H1(Key h) { return h & 0x1fff; }
+inline int H2(Key h) { return (h >> 16) & 0x1fff; }
+
+// Cuckoo tables with Zobrist hashes of valid reversible moves, and the moves themselves
+Key cuckoo[8192];
+Move cuckooMove[8192];
+
+
+/// Position::init() initializes at startup the various arrays used to compute
+/// hash keys.
+
+void Position::init() {
+
+ PRNG rng(1070372);
+
+ for (Piece pc : Pieces)
+ for (Square s = SQ_A1; s <= SQ_H8; ++s)
+ Zobrist::psq[pc][s] = rng.rand<Key>();
+
+ for (File f = FILE_A; f <= FILE_H; ++f)
+ Zobrist::enpassant[f] = rng.rand<Key>();
+
+ for (int cr = NO_CASTLING; cr <= ANY_CASTLING; ++cr)
+ {
+ Zobrist::castling[cr] = 0;
+ Bitboard b = cr;
+ while (b)
+ {
+ Key k = Zobrist::castling[1ULL << pop_lsb(&b)];
+ Zobrist::castling[cr] ^= k ? k : rng.rand<Key>();
+ }
+ }
+
+ Zobrist::side = rng.rand<Key>();
+ Zobrist::noPawns = rng.rand<Key>();
+
+ // Prepare the cuckoo tables
+ std::memset(cuckoo, 0, sizeof(cuckoo));
+ std::memset(cuckooMove, 0, sizeof(cuckooMove));
+ int count = 0;
+ for (Piece pc : Pieces)
+ for (Square s1 = SQ_A1; s1 <= SQ_H8; ++s1)
+ for (Square s2 = Square(s1 + 1); s2 <= SQ_H8; ++s2)
+ if (PseudoAttacks[type_of(pc)][s1] & s2)
+ {
+ Move move = make_move(s1, s2);
+ Key key = Zobrist::psq[pc][s1] ^ Zobrist::psq[pc][s2] ^ Zobrist::side;
+ int i = H1(key);
+ while (true)
+ {
+ std::swap(cuckoo[i], key);
+ std::swap(cuckooMove[i], move);
+ if (move == 0) // Arrived at empty slot ?
+ break;
+ i = (i == H1(key)) ? H2(key) : H1(key); // Push victim to alternative slot
+ }
+ count++;
+ }
+ assert(count == 3668);