From 27ba611a3da37423a3502e49beeebe11c9a11d8e Mon Sep 17 00:00:00 2001 From: Marco Costalba Date: Sun, 4 Jun 2017 11:03:23 +0200 Subject: [PATCH] Better naming in endgame code And small clean-up of magic bitboards code. No functional change. Closes #1138 --- src/Makefile | 2 +- src/bitboard.cpp | 61 +++++++++++++++++++++--------------------- src/bitboard.h | 48 ++++++++++++++------------------- src/endgame.cpp | 8 ------ src/endgame.h | 40 +++++++++++++-------------- src/material.cpp | 2 +- src/search.cpp | 2 +- src/syzygy/tbprobe.cpp | 4 +-- 8 files changed, 75 insertions(+), 92 deletions(-) diff --git a/src/Makefile b/src/Makefile index e56ea54c..fd928384 100644 --- a/src/Makefile +++ b/src/Makefile @@ -452,7 +452,7 @@ install: #clean all clean: objclean profileclean - @rm -f .depend *~ core + @rm -f .depend *~ core # clean binaries and objects objclean: diff --git a/src/bitboard.cpp b/src/bitboard.cpp index 99070ef2..555cd13c 100644 --- a/src/bitboard.cpp +++ b/src/bitboard.cpp @@ -26,9 +26,6 @@ uint8_t PopCnt16[1 << 16]; int SquareDistance[SQUARE_NB][SQUARE_NB]; -Magic RookMagics[SQUARE_NB]; -Magic BishopMagics[SQUARE_NB]; - Bitboard SquareBB[SQUARE_NB]; Bitboard FileBB[FILE_NB]; Bitboard RankBB[RANK_NB]; @@ -43,6 +40,9 @@ Bitboard PawnAttackSpan[COLOR_NB][SQUARE_NB]; Bitboard PseudoAttacks[PIECE_TYPE_NB][SQUARE_NB]; Bitboard PawnAttacks[COLOR_NB][SQUARE_NB]; +Magic RookMagics[SQUARE_NB]; +Magic BishopMagics[SQUARE_NB]; + namespace { // De Bruijn sequences. See chessprogramming.wikispaces.com/BitScan @@ -54,7 +54,7 @@ namespace { Bitboard RookTable[0x19000]; // To store rook attacks Bitboard BishopTable[0x1480]; // To store bishop attacks - typedef unsigned (Fn)(Square, Bitboard); + typedef unsigned (Fn)(const Magic&, Bitboard); void init_magics(Bitboard table[], Magic magics[], Square deltas[], Fn index); @@ -204,8 +204,8 @@ void Bitboards::init() { Square RookDeltas[] = { NORTH, EAST, SOUTH, WEST }; Square BishopDeltas[] = { NORTH_EAST, SOUTH_EAST, SOUTH_WEST, NORTH_WEST }; - init_magics(RookTable, RookMagics, RookDeltas, magic_index); - init_magics(BishopTable, BishopMagics, BishopDeltas, magic_index); + init_magics(RookTable, RookMagics, RookDeltas, magic_index); + init_magics(BishopTable, BishopMagics, BishopDeltas, magic_index); for (Square s1 = SQ_A1; s1 <= SQ_H8; ++s1) { @@ -257,10 +257,7 @@ namespace { { 728, 10316, 55013, 32803, 12281, 15100, 16645, 255 } }; Bitboard occupancy[4096], reference[4096], edges, b; - int age[4096] = {0}, current = 0, i, size; - - // attacks[s] is a pointer to the beginning of the attacks table for square 's' - magics[SQ_A1].attacks = table; + int epoch[4096] = {}, cnt = 0, size = 0; for (Square s = SQ_A1; s <= SQ_H8; ++s) { @@ -272,8 +269,13 @@ namespace { // all the attacks for each possible subset of the mask and so is 2 power // the number of 1s of the mask. Hence we deduce the size of the shift to // apply to the 64 or 32 bits word to get the index. - magics[s].mask = sliding_attack(deltas, s, 0) & ~edges; - magics[s].shift = (Is64Bit ? 64 : 32) - popcount(magics[s].mask); + Magic& m = magics[s]; + m.mask = sliding_attack(deltas, s, 0) & ~edges; + m.shift = (Is64Bit ? 64 : 32) - popcount(m.mask); + + // Set the offset for the attacks table of the square. We have individual + // table sizes for each square with "Fancy Magic Bitboards". + m.attacks = s == SQ_A1 ? table : magics[s - 1].attacks + size; // Use Carry-Rippler trick to enumerate all subsets of masks[s] and // store the corresponding sliding attack bitboard in reference[]. @@ -283,17 +285,12 @@ namespace { reference[size] = sliding_attack(deltas, s, b); if (HasPext) - magics[s].attacks[pext(b, magics[s].mask)] = reference[size]; + m.attacks[pext(b, m.mask)] = reference[size]; size++; - b = (b - magics[s].mask) & magics[s].mask; + b = (b - m.mask) & m.mask; } while (b); - // Set the offset for the table of the next square. We have individual - // table sizes for each square with "Fancy Magic Bitboards". - if (s < SQ_H8) - magics[s + 1].attacks = magics[s].attacks + size; - if (HasPext) continue; @@ -301,28 +298,30 @@ namespace { // Find a magic for square 's' picking up an (almost) random number // until we find the one that passes the verification test. - do { - do - magics[s].magic = rng.sparse_rand(); - while (popcount((magics[s].magic * magics[s].mask) >> 56) < 6); + for (int i = 0; i < size; ) + { + for (m.magic = 0; popcount((m.magic * m.mask) >> 56) < 6; ) + m.magic = rng.sparse_rand(); // A good magic must map every possible occupancy to an index that // looks up the correct sliding attack in the attacks[s] database. // Note that we build up the database for square 's' as a side - // effect of verifying the magic. - for (++current, i = 0; i < size; ++i) + // effect of verifying the magic. Keep track of the attempt count + // and save it in epoch[], little speed-up trick to avoid resetting + // m.attacks[] after every failed attempt. + for (++cnt, i = 0; i < size; ++i) { - unsigned idx = index(s, occupancy[i]); + unsigned idx = index(m, occupancy[i]); - if (age[idx] < current) + if (epoch[idx] < cnt) { - age[idx] = current; - magics[s].attacks[idx] = reference[i]; + epoch[idx] = cnt; + m.attacks[idx] = reference[i]; } - else if (magics[s].attacks[idx] != reference[i]) + else if (m.attacks[idx] != reference[i]) break; } - } while (i < size); + } } } } diff --git a/src/bitboard.h b/src/bitboard.h index 3ea92bdf..38870a2b 100644 --- a/src/bitboard.h +++ b/src/bitboard.h @@ -76,6 +76,18 @@ extern Bitboard PseudoAttacks[PIECE_TYPE_NB][SQUARE_NB]; extern Bitboard PawnAttacks[COLOR_NB][SQUARE_NB]; +/// Magic holds all magic bitboards relevant data for a single square +struct Magic { + Bitboard mask; + Bitboard magic; + Bitboard* attacks; + unsigned shift; +}; + +extern Magic RookMagics[SQUARE_NB]; +extern Magic BishopMagics[SQUARE_NB]; + + /// Overloads of bitwise operators between a Bitboard and a Square for testing /// whether a given bit is set in a bitboard, and for setting and clearing bits. @@ -209,47 +221,27 @@ template<> inline int distance(Square x, Square y) { return distance(file_ template<> inline int distance(Square x, Square y) { return distance(rank_of(x), rank_of(y)); } -/// Magic holds all magic relevant data for a single square -struct Magic { - - Bitboard mask; - Bitboard magic; - Bitboard* attacks; - unsigned shift; -}; - /// attacks_bb() returns a bitboard representing all the squares attacked by a /// piece of type Pt (bishop or rook) placed on 's'. The helper magic_index() /// looks up the index using the 'magic bitboards' approach. -template -inline unsigned magic_index(Square s, Bitboard occupied) { - - extern Magic RookMagics[SQUARE_NB]; - extern Magic BishopMagics[SQUARE_NB]; - - const Magic* Magics = Pt == ROOK ? RookMagics : BishopMagics; - Bitboard mask = Magics[s].mask; - Bitboard magic = Magics[s].magic; - unsigned shift = Magics[s].shift; +inline unsigned magic_index(const Magic& m, Bitboard occupied) { if (HasPext) - return unsigned(pext(occupied, mask)); + return unsigned(pext(occupied, m.mask)); if (Is64Bit) - return unsigned(((occupied & mask) * magic) >> shift); + return unsigned(((occupied & m.mask) * m.magic) >> m.shift); - unsigned lo = unsigned(occupied) & unsigned(mask); - unsigned hi = unsigned(occupied >> 32) & unsigned(mask >> 32); - return (lo * unsigned(magic) ^ hi * unsigned(magic >> 32)) >> shift; + unsigned lo = unsigned(occupied) & unsigned(m.mask); + unsigned hi = unsigned(occupied >> 32) & unsigned(m.mask >> 32); + return (lo * unsigned(m.magic) ^ hi * unsigned(m.magic >> 32)) >> m.shift; } template inline Bitboard attacks_bb(Square s, Bitboard occupied) { - extern Magic RookMagics[SQUARE_NB]; - extern Magic BishopMagics[SQUARE_NB]; - - return (Pt == ROOK ? RookMagics : BishopMagics)[s].attacks[magic_index(s, occupied)]; + const Magic& M = Pt == ROOK ? RookMagics[s] : BishopMagics[s]; + return M.attacks[magic_index(M, occupied)]; } inline Bitboard attacks_bb(PieceType pt, Square s, Bitboard occupied) { diff --git a/src/endgame.cpp b/src/endgame.cpp index 136ee0f6..b64b75cb 100644 --- a/src/endgame.cpp +++ b/src/endgame.cpp @@ -110,14 +110,6 @@ Endgames::Endgames() { } -template -void Endgames::add(const string& code) { - StateInfo st; - map()[Position().set(code, WHITE, &st).material_key()] = std::unique_ptr>(new Endgame(WHITE)); - map()[Position().set(code, BLACK, &st).material_key()] = std::unique_ptr>(new Endgame(BLACK)); -} - - /// Mate with KX vs K. This function is used to evaluate positions with /// king and plenty of material vs a lone king. It simply gives the /// attacking side a bonus for driving the defending king towards the edge diff --git a/src/endgame.h b/src/endgame.h index 509e8d4c..5e181526 100644 --- a/src/endgame.h +++ b/src/endgame.h @@ -31,12 +31,11 @@ #include "types.h" -/// EndgameType lists all supported endgames +/// EndgameCode lists all supported endgame functions by corresponding codes -enum EndgameType { - - // Evaluation functions +enum EndgameCode { + EVALUATION_FUNCTIONS, KNNK, // KNN vs K KXK, // Generic "mate lone king" eval KBNK, // KBN vs K @@ -47,10 +46,7 @@ enum EndgameType { KQKP, // KQ vs KP KQKR, // KQ vs KR - - // Scaling functions SCALING_FUNCTIONS, - KBPsK, // KB and pawns vs K KQKRPs, // KQ vs KR and pawns KRPKR, // KRP vs KR @@ -68,30 +64,28 @@ enum EndgameType { /// Endgame functions can be of two types depending on whether they return a /// Value or a ScaleFactor. -template using +template using eg_type = typename std::conditional<(E < SCALING_FUNCTIONS), Value, ScaleFactor>::type; -/// Base and derived templates for endgame evaluation and scaling functions +/// Base and derived functors for endgame evaluation and scaling functions template struct EndgameBase { + explicit EndgameBase(Color c) : strongSide(c), weakSide(~c) {} virtual ~EndgameBase() = default; - virtual Color strong_side() const = 0; virtual T operator()(const Position&) const = 0; + + const Color strongSide, weakSide; }; -template> +template> struct Endgame : public EndgameBase { - explicit Endgame(Color c) : strongSide(c), weakSide(~c) {} - Color strong_side() const { return strongSide; } + explicit Endgame(Color c) : EndgameBase(c) {} T operator()(const Position&) const; - -private: - Color strongSide, weakSide; }; @@ -101,16 +95,22 @@ private: class Endgames { - template using Map = std::map>>; - - template> - void add(const std::string& code); + template using Ptr = std::unique_ptr>; + template using Map = std::map>; template Map& map() { return std::get::value>(maps); } + template, typename P = Ptr> + void add(const std::string& code) { + + StateInfo st; + map()[Position().set(code, WHITE, &st).material_key()] = P(new Endgame(WHITE)); + map()[Position().set(code, BLACK, &st).material_key()] = P(new Endgame(BLACK)); + } + std::pair, Map> maps; public: diff --git a/src/material.cpp b/src/material.cpp index e5b8ddf2..dc2a3a3b 100644 --- a/src/material.cpp +++ b/src/material.cpp @@ -155,7 +155,7 @@ Entry* probe(const Position& pos) { if ((sf = pos.this_thread()->endgames.probe(key)) != nullptr) { - e->scalingFunction[sf->strong_side()] = sf; // Only strong color assigned + e->scalingFunction[sf->strongSide] = sf; // Only strong color assigned return e; } diff --git a/src/search.cpp b/src/search.cpp index 4f943b4c..51d3ae8c 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -335,7 +335,7 @@ void Thread::search() { MainThread* mainThread = (this == Threads.main() ? Threads.main() : nullptr); std::memset(ss-4, 0, 7 * sizeof(Stack)); - for(int i = 4; i > 0; i--) + for (int i = 4; i > 0; i--) (ss-i)->history = &this->counterMoveHistory[NO_PIECE][0]; // Use as sentinel bestValue = delta = alpha = -VALUE_INFINITE; diff --git a/src/syzygy/tbprobe.cpp b/src/syzygy/tbprobe.cpp index 5d08549e..48c448fd 100644 --- a/src/syzygy/tbprobe.cpp +++ b/src/syzygy/tbprobe.cpp @@ -531,14 +531,14 @@ int decompress_pairs(PairsData* d, uint64_t idx) { // // I(k) = k * d->span + d->span / 2 (1) - // First step is to get the 'k' of the I(k) nearest to our idx, using defintion (1) + // First step is to get the 'k' of the I(k) nearest to our idx, using definition (1) uint32_t k = idx / d->span; // Then we read the corresponding SparseIndex[] entry uint32_t block = number(&d->sparseIndex[k].block); int offset = number(&d->sparseIndex[k].offset); - // Now compute the difference idx - I(k). From defintion of k we know that + // Now compute the difference idx - I(k). From definition of k we know that // // idx = k * d->span + idx % d->span (2) // -- 2.39.2