And small clean-up of magic bitboards code.
No functional change.
Closes #1138
#clean all
clean: objclean profileclean
- @rm -f .depend *~ core
+ @rm -f .depend *~ core
# clean binaries and objects
objclean:
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];
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
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);
Square RookDeltas[] = { NORTH, EAST, SOUTH, WEST };
Square BishopDeltas[] = { NORTH_EAST, SOUTH_EAST, SOUTH_WEST, NORTH_WEST };
- init_magics(RookTable, RookMagics, RookDeltas, magic_index<ROOK>);
- init_magics(BishopTable, BishopMagics, BishopDeltas, magic_index<BISHOP>);
+ init_magics(RookTable, RookMagics, RookDeltas, magic_index);
+ init_magics(BishopTable, BishopMagics, BishopDeltas, magic_index);
for (Square s1 = SQ_A1; s1 <= SQ_H8; ++s1)
{
{ 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)
{
// 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[].
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;
// 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<Bitboard>();
- 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<Bitboard>();
// 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);
+ }
}
}
}
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.
template<> inline int distance<Rank>(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<PieceType Pt>
-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<PieceType Pt>
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<Pt>(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) {
}
-template<EndgameType E, typename T>
-void Endgames::add(const string& code) {
- StateInfo st;
- map<T>()[Position().set(code, WHITE, &st).material_key()] = std::unique_ptr<EndgameBase<T>>(new Endgame<E>(WHITE));
- map<T>()[Position().set(code, BLACK, &st).material_key()] = std::unique_ptr<EndgameBase<T>>(new Endgame<E>(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
#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
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
/// Endgame functions can be of two types depending on whether they return a
/// Value or a ScaleFactor.
-template<EndgameType E> using
+template<EndgameCode E> 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<typename T>
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<EndgameType E, typename T = eg_type<E>>
+template<EndgameCode E, typename T = eg_type<E>>
struct Endgame : public EndgameBase<T> {
- explicit Endgame(Color c) : strongSide(c), weakSide(~c) {}
- Color strong_side() const { return strongSide; }
+ explicit Endgame(Color c) : EndgameBase<T>(c) {}
T operator()(const Position&) const;
-
-private:
- Color strongSide, weakSide;
};
class Endgames {
- template<typename T> using Map = std::map<Key, std::unique_ptr<EndgameBase<T>>>;
-
- template<EndgameType E, typename T = eg_type<E>>
- void add(const std::string& code);
+ template<typename T> using Ptr = std::unique_ptr<EndgameBase<T>>;
+ template<typename T> using Map = std::map<Key, Ptr<T>>;
template<typename T>
Map<T>& map() {
return std::get<std::is_same<T, ScaleFactor>::value>(maps);
}
+ template<EndgameCode E, typename T = eg_type<E>, typename P = Ptr<T>>
+ void add(const std::string& code) {
+
+ StateInfo st;
+ map<T>()[Position().set(code, WHITE, &st).material_key()] = P(new Endgame<E>(WHITE));
+ map<T>()[Position().set(code, BLACK, &st).material_key()] = P(new Endgame<E>(BLACK));
+ }
+
std::pair<Map<Value>, Map<ScaleFactor>> maps;
public:
if ((sf = pos.this_thread()->endgames.probe<ScaleFactor>(key)) != nullptr)
{
- e->scalingFunction[sf->strong_side()] = sf; // Only strong color assigned
+ e->scalingFunction[sf->strongSide] = sf; // Only strong color assigned
return e;
}
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;
//
// 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<uint32_t, LittleEndian>(&d->sparseIndex[k].block);
int offset = number<uint16_t, LittleEndian>(&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)
//