*/
#include <cassert>
+#include <vector>
#include "bitboard.h"
#include "types.h"
namespace {
+ // The possible pawns squares are 24, the first 4 files and ranks from 2 to 7
+ const unsigned IndexMax = 2*24*64*64; // stm * psq * wksq * bksq = 196608
+
+ // Each uint32_t stores results of 32 positions, one per bit
+ uint32_t KPKBitbase[IndexMax / 32];
+
+ // A KPK bitbase index is an integer in [0, IndexMax] range
+ //
+ // Information is mapped in a way that minimizes number of iterations:
+ //
+ // bit 0- 5: white king square (from SQ_A1 to SQ_H8)
+ // bit 6-11: black king square (from SQ_A1 to SQ_H8)
+ // bit 12: side to move (WHITE or BLACK)
+ // bit 13-14: white pawn file (from FILE_A to FILE_D)
+ // bit 15-17: white pawn 6 - rank (from 6 - RANK_7 to 6 - RANK_2)
+ unsigned index(Color us, Square bksq, Square wksq, Square psq) {
+ return wksq + (bksq << 6) + (us << 12) + (file_of(psq) << 13) + ((6 - rank_of(psq)) << 15);
+ }
+
enum Result {
INVALID = 0,
UNKNOWN = 1,
struct KPKPosition {
- Result classify_leaf(int idx);
- Result classify(int idx, Result db[]);
+ operator Result() const { return res; }
+ Result classify_leaf(unsigned idx);
+ Result classify(const std::vector<KPKPosition>& db)
+ { return us == WHITE ? classify<WHITE>(db) : classify<BLACK>(db); }
private:
- template<Color Us> Result classify(const Result db[]) const;
-
- template<Color Us> Bitboard k_attacks() const {
- return Us == WHITE ? StepAttacksBB[W_KING][wksq] : StepAttacksBB[B_KING][bksq];
- }
-
- Bitboard p_attacks() const { return StepAttacksBB[W_PAWN][psq]; }
- void decode_index(int idx);
+ template<Color Us> Result classify(const std::vector<KPKPosition>& db);
- Square wksq, bksq, psq;
- Color stm;
+ Color us;
+ Square bksq, wksq, psq;
+ Result res;
};
- // The possible pawns squares are 24, the first 4 files and ranks from 2 to 7
- const int IndexMax = 2 * 24 * 64 * 64; // stm * wp_sq * wk_sq * bk_sq = 196608
-
- // Each uint32_t stores results of 32 positions, one per bit
- uint32_t KPKBitbase[IndexMax / 32];
+} // namespace
- int index(Square wksq, Square bksq, Square psq, Color stm);
-}
+bool Bitbases::probe_kpk(Square wksq, Square wpsq, Square bksq, Color us) {
-uint32_t Bitbases::probe_kpk(Square wksq, Square wpsq, Square bksq, Color stm) {
+ assert(file_of(wpsq) <= FILE_D);
- int idx = index(wksq, bksq, wpsq, stm);
- return KPKBitbase[idx / 32] & (1 << (idx & 31));
+ unsigned idx = index(us, bksq, wksq, wpsq);
+ return KPKBitbase[idx / 32] & (1 << (idx & 0x1F));
}
void Bitbases::init_kpk() {
- Result* db = new Result[IndexMax]; // Avoid to hit stack limit on some platforms
- KPKPosition pos;
- int idx, bit, repeat = 1;
+ unsigned idx, repeat = 1;
+ std::vector<KPKPosition> db(IndexMax);
- // Initialize table with known win / draw positions
+ // Initialize db with known win / draw positions
for (idx = 0; idx < IndexMax; idx++)
- db[idx] = pos.classify_leaf(idx);
+ db[idx].classify_leaf(idx);
- // Iterate until all positions are classified (30 cycles needed)
+ // Iterate until all positions are classified (15 cycles needed)
while (repeat)
for (repeat = idx = 0; idx < IndexMax; idx++)
- if (db[idx] == UNKNOWN && (db[idx] = pos.classify(idx, db)) != UNKNOWN)
+ if (db[idx] == UNKNOWN && db[idx].classify(db) != UNKNOWN)
repeat = 1;
- // Map 32 position results into one KPKBitbase[] entry
- for (idx = 0; idx < IndexMax / 32; idx++)
- for (bit = 0; bit < 32; bit++)
- if (db[32 * idx + bit] == WIN)
- KPKBitbase[idx] |= 1 << bit;
-
- delete [] db;
+ // Map 32 results into one KPKBitbase[] entry
+ for (idx = 0; idx < IndexMax; idx++)
+ if (db[idx] == WIN)
+ KPKBitbase[idx / 32] |= 1 << (idx & 0x1F);
}
namespace {
- // A KPK bitbase index is an integer in [0, IndexMax] range
- //
- // Information is mapped in this way
- //
- // bit 0: side to move (WHITE or BLACK)
- // bit 1- 6: black king square (from SQ_A1 to SQ_H8)
- // bit 7-12: white king square (from SQ_A1 to SQ_H8)
- // bit 13-14: white pawn file (from FILE_A to FILE_D)
- // bit 15-17: white pawn rank - 1 (from RANK_2 - 1 to RANK_7 - 1)
-
- int index(Square w, Square b, Square p, Color c) {
-
- assert(file_of(p) <= FILE_D);
-
- return c + (b << 1) + (w << 7) + (file_of(p) << 13) + ((rank_of(p) - 1) << 15);
- }
-
- void KPKPosition::decode_index(int idx) {
+ Result KPKPosition::classify_leaf(unsigned idx) {
- stm = Color(idx & 1);
- bksq = Square((idx >> 1) & 63);
- wksq = Square((idx >> 7) & 63);
- psq = File((idx >> 13) & 3) | Rank((idx >> 15) + 1);
- }
-
- Result KPKPosition::classify_leaf(int idx) {
-
- decode_index(idx);
+ wksq = Square((idx >> 0) & 0x3F);
+ bksq = Square((idx >> 6) & 0x3F);
+ us = Color((idx >> 12) & 0x01);
+ psq = File((idx >> 13) & 3) | Rank(6 - (idx >> 15));
// Check if two pieces are on the same square or if a king can be captured
if ( wksq == psq || wksq == bksq || bksq == psq
- || (k_attacks<WHITE>() & bksq)
- || (stm == WHITE && (p_attacks() & bksq)))
- return INVALID;
-
- // The position is an immediate win if it is white to move and the white
- // pawn can be promoted without getting captured.
- if ( rank_of(psq) == RANK_7
- && stm == WHITE
- && wksq != psq + DELTA_N
- && ( square_distance(bksq, psq + DELTA_N) > 1
- ||(k_attacks<WHITE>() & (psq + DELTA_N))))
- return WIN;
-
- // Check for known draw positions
- //
- // Case 1: Stalemate
- if ( stm == BLACK
- && !(k_attacks<BLACK>() & ~(k_attacks<WHITE>() | p_attacks())))
- return DRAW;
-
- // Case 2: King can capture undefended pawn
- if ( stm == BLACK
- && (k_attacks<BLACK>() & psq & ~k_attacks<WHITE>()))
- return DRAW;
-
- // Case 3: Black king in front of white pawn
- if ( bksq == psq + DELTA_N
- && rank_of(psq) < RANK_7)
- return DRAW;
-
- // Case 4: White king in front of pawn and black has opposition
- if ( stm == WHITE
- && wksq == psq + DELTA_N
- && bksq == wksq + DELTA_N + DELTA_N
- && rank_of(psq) < RANK_5)
- return DRAW;
-
- // Case 5: Stalemate with rook pawn
- if ( bksq == SQ_A8
- && file_of(psq) == FILE_A)
- return DRAW;
-
- // Case 6: White king trapped on the rook file
- if ( file_of(wksq) == FILE_A
- && file_of(psq) == FILE_A
- && rank_of(wksq) > rank_of(psq)
- && bksq == wksq + 2)
- return DRAW;
-
- return UNKNOWN;
+ || (StepAttacksBB[KING][wksq] & bksq)
+ || (us == WHITE && (StepAttacksBB[PAWN][psq] & bksq)))
+ return res = INVALID;
+
+ if (us == WHITE)
+ {
+ // Immediate win if pawn can be promoted without getting captured
+ if ( rank_of(psq) == RANK_7
+ && wksq != psq + DELTA_N
+ && ( square_distance(bksq, psq + DELTA_N) > 1
+ ||(StepAttacksBB[KING][wksq] & (psq + DELTA_N))))
+ return res = WIN;
+ }
+ // Immediate draw if is stalemate or king captures undefended pawn
+ else if ( !(StepAttacksBB[KING][bksq] & ~(StepAttacksBB[KING][wksq] | StepAttacksBB[PAWN][psq]))
+ || (StepAttacksBB[KING][bksq] & psq & ~StepAttacksBB[KING][wksq]))
+ return res = DRAW;
+
+ return res = UNKNOWN;
}
template<Color Us>
- Result KPKPosition::classify(const Result db[]) const {
+ Result KPKPosition::classify(const std::vector<KPKPosition>& db) {
- // White to Move: If one move leads to a position classified as RESULT_WIN,
- // the result of the current position is RESULT_WIN. If all moves lead to
- // positions classified as RESULT_DRAW, the current position is classified
- // RESULT_DRAW otherwise the current position is classified as RESULT_UNKNOWN.
+ // White to Move: If one move leads to a position classified as WIN, the result
+ // of the current position is WIN. If all moves lead to positions classified
+ // as DRAW, the current position is classified DRAW otherwise the current
+ // position is classified as UNKNOWN.
//
- // Black to Move: If one move leads to a position classified as RESULT_DRAW,
- // the result of the current position is RESULT_DRAW. If all moves lead to
- // positions classified as RESULT_WIN, the position is classified RESULT_WIN.
- // Otherwise, the current position is classified as RESULT_UNKNOWN.
+ // Black to Move: If one move leads to a position classified as DRAW, the result
+ // of the current position is DRAW. If all moves lead to positions classified
+ // as WIN, the position is classified WIN otherwise the current position is
+ // classified UNKNOWN.
Result r = INVALID;
- Bitboard b = k_attacks<Us>();
+ Bitboard b = StepAttacksBB[KING][Us == WHITE ? wksq : bksq];
while (b)
- {
- r |= Us == WHITE ? db[index(pop_lsb(&b), bksq, psq, BLACK)]
- : db[index(wksq, pop_lsb(&b), psq, WHITE)];
-
- if (Us == WHITE && (r & WIN))
- return WIN;
-
- if (Us == BLACK && (r & DRAW))
- return DRAW;
- }
+ r |= Us == WHITE ? db[index(~Us, bksq, pop_lsb(&b), psq)]
+ : db[index(~Us, pop_lsb(&b), wksq, psq)];
if (Us == WHITE && rank_of(psq) < RANK_7)
{
Square s = psq + DELTA_N;
- r |= db[index(wksq, bksq, s, BLACK)]; // Single push
+ r |= db[index(BLACK, bksq, wksq, s)]; // Single push
if (rank_of(s) == RANK_3 && s != wksq && s != bksq)
- r |= db[index(wksq, bksq, s + DELTA_N, BLACK)]; // Double push
-
- if (r & WIN)
- return WIN;
+ r |= db[index(BLACK, bksq, wksq, s + DELTA_N)]; // Double push
}
- return r & UNKNOWN ? UNKNOWN : Us == WHITE ? DRAW : WIN;
+ if (Us == WHITE)
+ return res = r & WIN ? WIN : r & UNKNOWN ? UNKNOWN : DRAW;
+ else
+ return res = r & DRAW ? DRAW : r & UNKNOWN ? UNKNOWN : WIN;
}
- Result KPKPosition::classify(int idx, Result db[]) {
-
- decode_index(idx);
- return stm == WHITE ? classify<WHITE>(db) : classify<BLACK>(db);
- }
-
-}
+} // namespace
namespace Bitbases {
void init_kpk();
-uint32_t probe_kpk(Square wksq, Square wpsq, Square bksq, Color stm);
+bool probe_kpk(Square wksq, Square wpsq, Square bksq, Color us);
}
assert(pos.piece_count(weakerSide, PAWN) == 0);
Square wksq, bksq, wpsq;
- Color stm;
+ Color us;
if (strongerSide == WHITE)
{
wksq = pos.king_square(WHITE);
bksq = pos.king_square(BLACK);
wpsq = pos.piece_list(WHITE, PAWN)[0];
- stm = pos.side_to_move();
+ us = pos.side_to_move();
}
else
{
wksq = ~pos.king_square(BLACK);
bksq = ~pos.king_square(WHITE);
wpsq = ~pos.piece_list(BLACK, PAWN)[0];
- stm = ~pos.side_to_move();
+ us = ~pos.side_to_move();
}
if (file_of(wpsq) >= FILE_E)
wpsq = mirror(wpsq);
}
- if (!Bitbases::probe_kpk(wksq, wpsq, bksq, stm))
+ if (!Bitbases::probe_kpk(wksq, wpsq, bksq, us))
return VALUE_DRAW;
Value result = VALUE_KNOWN_WIN + PawnValueEg + Value(rank_of(wpsq));
return SCALE_FACTOR_DRAW;
}
}
+
+ // All pawns on same B or G file? Then potential draw
+ if ( (pawnFile == FILE_B || pawnFile == FILE_G)
+ && !(pos.pieces(PAWN) & ~file_bb(pawnFile))
+ && pos.non_pawn_material(weakerSide) == 0
+ && pos.piece_count(weakerSide, PAWN) >= 1)
+ {
+ // Get weaker pawn closest to opponent's queening square
+ Bitboard wkPawns = pos.pieces(weakerSide, PAWN);
+ Square weakerPawnSq = strongerSide == WHITE ? msb(wkPawns) : lsb(wkPawns);
+
+ Square strongerKingSq = pos.king_square(strongerSide);
+ Square weakerKingSq = pos.king_square(weakerSide);
+ Square bishopSq = pos.piece_list(strongerSide, BISHOP)[0];
+
+ // Draw if weaker pawn is on rank 7, bishop can't attack the pawn, and
+ // weaker king can stop opposing opponent's king from penetrating.
+ if ( relative_rank(strongerSide, weakerPawnSq) == RANK_7
+ && opposite_colors(bishopSq, weakerPawnSq)
+ && square_distance(weakerPawnSq, weakerKingSq) <= square_distance(weakerPawnSq, strongerKingSq))
+ return SCALE_FACTOR_DRAW;
+ }
+
return SCALE_FACTOR_NONE;
}
Square wksq = pos.king_square(strongerSide);
Square bksq = pos.king_square(weakerSide);
Square wpsq = pos.piece_list(strongerSide, PAWN)[0];
- Color stm = pos.side_to_move();
+ Color us = pos.side_to_move();
if (strongerSide == BLACK)
{
wksq = ~wksq;
bksq = ~bksq;
wpsq = ~wpsq;
- stm = ~stm;
+ us = ~us;
}
if (file_of(wpsq) >= FILE_E)
// Probe the KPK bitbase with the weakest side's pawn removed. If it's a draw,
// it's probably at least a draw even with the pawn.
- return Bitbases::probe_kpk(wksq, wpsq, bksq, stm) ? SCALE_FACTOR_NONE : SCALE_FACTOR_DRAW;
+ return Bitbases::probe_kpk(wksq, wpsq, bksq, us) ? SCALE_FACTOR_NONE : SCALE_FACTOR_DRAW;
}
STOP
};
+ // Our insertion sort, guaranteed to be stable, as is needed
+ void insertion_sort(MoveStack* begin, MoveStack* end)
+ {
+ MoveStack tmp, *p, *q;
+
+ for (p = begin + 1; p < end; ++p)
+ {
+ tmp = *p;
+ for (q = p; q != begin && *(q-1) < tmp; --q)
+ *q = *(q-1);
+ *q = tmp;
+ }
+ }
+
// Unary predicate used by std::partition to split positive scores from remaining
// ones so to sort separately the two sets, and with the second sort delayed.
inline bool has_positive_score(const MoveStack& ms) { return ms.score > 0; }
endQuiets = end = generate<QUIETS>(pos, moves);
score<QUIETS>();
end = std::partition(cur, end, has_positive_score);
- sort<MoveStack>(cur, end);
+ insertion_sort(cur, end);
return;
case QUIETS_2_S1:
cur = end;
end = endQuiets;
if (depth >= 3 * ONE_PLY)
- sort<MoveStack>(cur, end);
+ insertion_sort(cur, end);
return;
case BAD_CAPTURES_S1:
assert(MoveList<LEGAL>(pos).contains(m));
- Bitboard attackers;
- bool ambiguousMove, ambiguousFile, ambiguousRank;
+ Bitboard others, b;
string san;
Color us = pos.side_to_move();
Square from = from_sq(m);
{
san = PieceToChar[WHITE][pt]; // Upper case
- // Disambiguation if we have more then one piece with destination 'to'
- // note that for pawns is not needed because starting file is explicit.
- ambiguousMove = ambiguousFile = ambiguousRank = false;
+ // Disambiguation if we have more then one piece of type 'pt' that can
+ // reach 'to' with a legal move.
+ others = b = (pos.attacks_from(pc, to) & pos.pieces(us, pt)) ^ from;
- attackers = (pos.attacks_from(pc, to) & pos.pieces(us, pt)) ^ from;
-
- while (attackers)
+ while (b)
{
- Square sq = pop_lsb(&attackers);
-
- // If the move is illegal, the piece is not included in the sub-set
- if (!pos.pl_move_is_legal(make_move(sq, to), pos.pinned_pieces()))
- continue;
-
- ambiguousFile |= file_of(sq) == file_of(from);
- ambiguousRank |= rank_of(sq) == rank_of(from);
- ambiguousMove = true;
+ Move move = make_move(pop_lsb(&b), to);
+ if (!pos.pl_move_is_legal(move, pos.pinned_pieces()))
+ others ^= from_sq(move);
}
- if (ambiguousMove)
+ if (others)
{
- if (!ambiguousFile)
+ if (!(others & file_bb(from)))
san += file_to_char(file_of(from));
- else if (!ambiguousRank)
+ else if (!(others & rank_bb(from)))
san += rank_to_char(rank_of(from));
else
// Update piece list, move the last piece at index[capsq] position and
// shrink the list.
//
- // WARNING: This is a not revresible operation. When we will reinsert the
+ // WARNING: This is a not reversible operation. When we will reinsert the
// captured piece in undo_move() we will put it at the end of the list and
// not in its original place, it means index[] and pieceList[] are not
// guaranteed to be invariant to a do_move() + undo_move() sequence.
void id_loop(Position& pos);
Value value_to_tt(Value v, int ply);
Value value_from_tt(Value v, int ply);
- bool check_is_dangerous(Position& pos, Move move, Value futilityBase, Value beta);
+ bool check_is_dangerous(const Position& pos, Move move, Value futilityBase, Value beta);
bool allows(const Position& pos, Move first, Move second);
bool refutes(const Position& pos, Move first, Move second);
string uci_pv(const Position& pos, int depth, Value alpha, Value beta);
// we want to keep the same order for all the moves but the new
// PV that goes to the front. Note that in case of MultiPV search
// the already searched PV lines are preserved.
- sort<RootMove>(RootMoves.begin() + PVIdx, RootMoves.end());
+ std::stable_sort(RootMoves.begin() + PVIdx, RootMoves.end());
// Write PV back to transposition table in case the relevant
// entries have been overwritten during the search.
}
// Sort the PV lines searched so far and update the GUI
- sort<RootMove>(RootMoves.begin(), RootMoves.begin() + PVIdx + 1);
+ std::stable_sort(RootMoves.begin(), RootMoves.begin() + PVIdx + 1);
if (PVIdx + 1 == PVSize || Time::now() - SearchTime > 3000)
sync_cout << uci_pv(pos, depth, alpha, beta) << sync_endl;
else if (tte)
{
// Never assume anything on values stored in TT
- if ( (ss->staticEval = eval = tte->static_value()) == VALUE_NONE
- ||(ss->evalMargin = tte->static_value_margin()) == VALUE_NONE)
+ if ( (ss->staticEval = eval = tte->eval_value()) == VALUE_NONE
+ ||(ss->evalMargin = tte->eval_margin()) == VALUE_NONE)
eval = ss->staticEval = evaluate(pos, ss->evalMargin);
// Can ttValue be used as a better position evaluation?
// Step 19. Check for splitting the search
if ( !SpNode
&& depth >= Threads.minimumSplitDepth
- && Threads.slave_available(thisThread)
+ && Threads.available_slave(thisThread)
&& thisThread->splitPointsSize < MAX_SPLITPOINTS_PER_THREAD)
{
assert(bestValue < beta);
if (tte)
{
// Never assume anything on values stored in TT
- if ( (ss->staticEval = bestValue = tte->static_value()) == VALUE_NONE
- ||(ss->evalMargin = tte->static_value_margin()) == VALUE_NONE)
+ if ( (ss->staticEval = bestValue = tte->eval_value()) == VALUE_NONE
+ ||(ss->evalMargin = tte->eval_margin()) == VALUE_NONE)
ss->staticEval = bestValue = evaluate(pos, ss->evalMargin);
}
else
// check_is_dangerous() tests if a checking move can be pruned in qsearch()
- bool check_is_dangerous(Position& pos, Move move, Value futilityBase, Value beta)
+ bool check_is_dangerous(const Position& pos, Move move, Value futilityBase, Value beta)
{
Piece pc = pos.piece_moved(move);
Square from = from_sq(move);
sp->mutex.lock();
- assert(sp->slavesPositions[idx] == NULL);
+ assert(activePosition == NULL);
- sp->slavesPositions[idx] = &pos;
+ activePosition = &pos;
switch (sp->nodeType) {
case Root:
assert(searching);
searching = false;
- sp->slavesPositions[idx] = NULL;
+ activePosition = NULL;
sp->slavesMask &= ~(1ULL << idx);
sp->nodes += pos.nodes_searched();
nodes = RootPos.nodes_searched();
// Loop across all split points and sum accumulated SplitPoint nodes plus
- // all the currently active slaves positions.
+ // all the currently active positions nodes.
for (size_t i = 0; i < Threads.size(); i++)
for (int j = 0; j < Threads[i]->splitPointsSize; j++)
{
Bitboard sm = sp.slavesMask;
while (sm)
{
- Position* pos = sp.slavesPositions[pop_lsb(&sm)];
- nodes += pos ? pos->nodes_searched() : 0;
+ Position* pos = Threads[pop_lsb(&sm)]->activePosition;
+ if (pos)
+ nodes += pos->nodes_searched();
}
sp.mutex.unlock();
/// all non-pv moves.
struct RootMove {
- RootMove(){} // Needed by sort()
RootMove(Move m) : score(-VALUE_INFINITE), prevScore(-VALUE_INFINITE) {
pv.push_back(m); pv.push_back(MOVE_NONE);
}
- bool operator<(const RootMove& m) const { return score < m.score; }
+ bool operator<(const RootMove& m) const { return score > m.score; } // Ascending sort
bool operator==(const Move& m) const { return pv[0] == m; }
void extract_pv_from_tt(Position& pos);
// Thread c'tor starts a newly-created thread of execution that will call
// the the virtual function idle_loop(), going immediately to sleep.
-Thread::Thread() : splitPoints() {
+Thread::Thread() /* : splitPoints() */ { // Value-initialization bug in MSVC
searching = exit = false;
maxPly = splitPointsSize = 0;
activeSplitPoint = NULL;
+ activePosition = NULL;
idx = Threads.size();
if (!thread_create(handle, start_routine, this))
// slave_available() tries to find an idle thread which is available as a slave
// for the thread 'master'.
-bool ThreadPool::slave_available(Thread* master) const {
+Thread* ThreadPool::available_slave(Thread* master) const {
for (const_iterator it = begin(); it != end(); ++it)
if ((*it)->is_available_to(master))
- return true;
+ return *it;
- return false;
+ return NULL;
}
splitPointsSize++;
activeSplitPoint = &sp;
+ activePosition = NULL;
size_t slavesCnt = 1; // This thread is always included
+ Thread* slave;
- for (ThreadPool::iterator it = Threads.begin(); it != Threads.end() && !Fake; ++it)
+ while ( (slave = Threads.available_slave(this)) != NULL
+ && ++slavesCnt <= Threads.maxThreadsPerSplitPoint && !Fake)
{
- Thread* slave = *it;
-
- if (slave->is_available_to(this) && ++slavesCnt <= Threads.maxThreadsPerSplitPoint)
- {
- sp.slavesMask |= 1ULL << slave->idx;
- slave->activeSplitPoint = &sp;
- slave->searching = true; // Slave leaves idle_loop()
- slave->notify_one(); // Could be sleeping
- }
+ sp.slavesMask |= 1ULL << slave->idx;
+ slave->activeSplitPoint = &sp;
+ slave->searching = true; // Slave leaves idle_loop()
+ slave->notify_one(); // Could be sleeping
}
sp.mutex.unlock();
// In helpful master concept a master can help only a sub-tree of its split
// point, and because here is all finished is not possible master is booked.
assert(!searching);
+ assert(!activePosition);
}
// We have returned from the idle loop, which means that all threads are
searching = true;
splitPointsSize--;
activeSplitPoint = sp.parentSplitPoint;
+ activePosition = &pos;
pos.set_nodes_searched(pos.nodes_searched() + sp.nodes);
*bestMove = sp.bestMove;
*bestValue = sp.bestValue;
// Shared data
Mutex mutex;
- Position* slavesPositions[MAX_THREADS];
volatile uint64_t slavesMask;
volatile int64_t nodes;
volatile Value alpha;
Material::Table materialTable;
Endgames endgames;
Pawns::Table pawnsTable;
+ Position* activePosition;
size_t idx;
int maxPly;
Mutex mutex;
MainThread* main_thread() { return static_cast<MainThread*>((*this)[0]); }
void read_uci_options();
- bool slave_available(Thread* master) const;
+ Thread* available_slave(Thread* master) const;
void wait_for_think_finished();
void start_thinking(const Position&, const Search::LimitsType&,
const std::vector<Move>&, Search::StateStackPtr&);
TranspositionTable TT; // Our global transposition table
-TranspositionTable::TranspositionTable() {
-
- size = generation = 0;
- entries = NULL;
-}
-
-TranspositionTable::~TranspositionTable() {
-
- delete [] entries;
-}
-
/// TranspositionTable::set_size() sets the size of the transposition table,
-/// measured in megabytes. Transposition table consists of a power of 2 number of
-/// TTCluster and each cluster consists of ClusterSize number of TTEntries. Each
-/// non-empty entry contains information of exactly one position.
+/// measured in megabytes. Transposition table consists of a power of 2 number
+/// of clusters and each cluster consists of ClusterSize number of TTEntry.
void TranspositionTable::set_size(size_t mbSize) {
- size_t newSize = 1ULL << msb((mbSize << 20) / sizeof(TTCluster));
+ assert(msb((mbSize << 20) / sizeof(TTEntry)) < 32);
- if (newSize == size)
+ uint32_t size = ClusterSize << msb((mbSize << 20) / sizeof(TTEntry[ClusterSize]));
+
+ if (hashMask == size - ClusterSize)
return;
- size = newSize;
- delete [] entries;
- entries = new (std::nothrow) TTCluster[size];
+ hashMask = size - ClusterSize;
+ delete [] table;
+ table = new (std::nothrow) TTEntry[size];
- if (!entries)
+ if (!table)
{
std::cerr << "Failed to allocate " << mbSize
<< "MB for transposition table." << std::endl;
void TranspositionTable::clear() {
- memset(entries, 0, size * sizeof(TTCluster));
+ memset(table, 0, (hashMask + ClusterSize) * sizeof(TTEntry));
}
/// more valuable than a TTEntry t2 if t1 is from the current search and t2 is from
/// a previous search, or if the depth of t1 is bigger than the depth of t2.
-void TranspositionTable::store(const Key posKey, Value v, Bound t, Depth d, Move m, Value statV, Value kingD) {
+void TranspositionTable::store(const Key key, Value v, Bound t, Depth d, Move m, Value statV, Value kingD) {
int c1, c2, c3;
TTEntry *tte, *replace;
- uint32_t posKey32 = posKey >> 32; // Use the high 32 bits as key inside the cluster
+ uint32_t key32 = key >> 32; // Use the high 32 bits as key inside the cluster
- tte = replace = first_entry(posKey);
+ tte = replace = first_entry(key);
- for (int i = 0; i < ClusterSize; i++, tte++)
+ for (unsigned i = 0; i < ClusterSize; i++, tte++)
{
- if (!tte->key() || tte->key() == posKey32) // Empty or overwrite old
+ if (!tte->key() || tte->key() == key32) // Empty or overwrite old
{
// Preserve any existing ttMove
if (m == MOVE_NONE)
m = tte->move();
- tte->save(posKey32, v, t, d, m, generation, statV, kingD);
+ tte->save(key32, v, t, d, m, generation, statV, kingD);
return;
}
if (c1 + c2 + c3 > 0)
replace = tte;
}
- replace->save(posKey32, v, t, d, m, generation, statV, kingD);
+ replace->save(key32, v, t, d, m, generation, statV, kingD);
}
/// transposition table. Returns a pointer to the TTEntry or NULL if
/// position is not found.
-TTEntry* TranspositionTable::probe(const Key posKey) const {
+TTEntry* TranspositionTable::probe(const Key key) const {
- uint32_t posKey32 = posKey >> 32;
- TTEntry* tte = first_entry(posKey);
+ TTEntry* tte = first_entry(key);
+ uint32_t key32 = key >> 32;
- for (int i = 0; i < ClusterSize; i++, tte++)
- if (tte->key() == posKey32)
+ for (unsigned i = 0; i < ClusterSize; i++, tte++)
+ if (tte->key() == key32)
return tte;
return NULL;
}
-
-
-/// TranspositionTable::new_search() is called at the beginning of every new
-/// search. It increments the "generation" variable, which is used to
-/// distinguish transposition table entries from previous searches from
-/// entries from the current search.
-
-void TranspositionTable::new_search() {
- generation++;
-}
class TTEntry {
public:
- void save(uint32_t k, Value v, Bound b, Depth d, Move m, int g, Value statV, Value statM) {
+ void save(uint32_t k, Value v, Bound b, Depth d, Move m, int g, Value ev, Value em) {
key32 = (uint32_t)k;
move16 = (uint16_t)m;
generation8 = (uint8_t)g;
value16 = (int16_t)v;
depth16 = (int16_t)d;
- staticValue = (int16_t)statV;
- staticMargin = (int16_t)statM;
+ evalValue = (int16_t)ev;
+ evalMargin = (int16_t)em;
}
void set_generation(int g) { generation8 = (uint8_t)g; }
- uint32_t key() const { return key32; }
- Depth depth() const { return (Depth)depth16; }
- Move move() const { return (Move)move16; }
- Value value() const { return (Value)value16; }
- Bound type() const { return (Bound)bound; }
- int generation() const { return (int)generation8; }
- Value static_value() const { return (Value)staticValue; }
- Value static_value_margin() const { return (Value)staticMargin; }
+ uint32_t key() const { return key32; }
+ Depth depth() const { return (Depth)depth16; }
+ Move move() const { return (Move)move16; }
+ Value value() const { return (Value)value16; }
+ Bound type() const { return (Bound)bound; }
+ int generation() const { return (int)generation8; }
+ Value eval_value() const { return (Value)evalValue; }
+ Value eval_margin() const { return (Value)evalMargin; }
private:
uint32_t key32;
uint16_t move16;
uint8_t bound, generation8;
- int16_t value16, depth16, staticValue, staticMargin;
+ int16_t value16, depth16, evalValue, evalMargin;
};
-/// This is the number of TTEntry slots for each cluster
-const int ClusterSize = 4;
-
-
-/// TTCluster consists of ClusterSize number of TTEntries. Size of TTCluster
-/// must not be bigger than a cache line size. In case it is less, it should
-/// be padded to guarantee always aligned accesses.
-
-struct TTCluster {
- TTEntry data[ClusterSize];
-};
-
-
-/// The transposition table class. This is basically just a huge array containing
-/// TTCluster objects, and a few methods for writing and reading entries.
+/// A TranspositionTable consists of a power of 2 number of clusters and each
+/// cluster consists of ClusterSize number of TTEntry. Each non-empty entry
+/// contains information of exactly one position. Size of a cluster shall not be
+/// bigger than a cache line size. In case it is less, it should be padded to
+/// guarantee always aligned accesses.
class TranspositionTable {
- TranspositionTable(const TranspositionTable&);
- TranspositionTable& operator=(const TranspositionTable&);
+ static const unsigned ClusterSize = 4; // A cluster is 64 Bytes
public:
- TranspositionTable();
- ~TranspositionTable();
+ ~TranspositionTable() { delete [] table; }
+ void new_search() { generation++; }
+
+ TTEntry* probe(const Key key) const;
+ TTEntry* first_entry(const Key key) const;
+ void refresh(const TTEntry* tte) const;
void set_size(size_t mbSize);
void clear();
- void store(const Key posKey, Value v, Bound type, Depth d, Move m, Value statV, Value kingD);
- TTEntry* probe(const Key posKey) const;
- void new_search();
- TTEntry* first_entry(const Key posKey) const;
- void refresh(const TTEntry* tte) const;
+ void store(const Key key, Value v, Bound type, Depth d, Move m, Value statV, Value kingD);
private:
- size_t size;
- TTCluster* entries;
+ uint32_t hashMask;
+ TTEntry* table;
uint8_t generation; // Size must be not bigger then TTEntry::generation8
};
/// a cluster given a position. The lowest order bits of the key are used to
/// get the index of the cluster.
-inline TTEntry* TranspositionTable::first_entry(const Key posKey) const {
+inline TTEntry* TranspositionTable::first_entry(const Key key) const {
- return entries[((uint32_t)posKey) & (size - 1)].data;
+ return table + ((uint32_t)key & hashMask);
}
return ch;
}
-/// Our insertion sort implementation, works with pointers and iterators and is
-/// guaranteed to be stable, as is needed.
-template<typename T, typename K>
-void sort(K begin, K end)
-{
- T tmp;
- K p, q;
-
- for (p = begin + 1; p < end; p++)
- {
- tmp = *p;
- for (q = p; q != begin && *(q-1) < tmp; --q)
- *q = *(q-1);
- *q = tmp;
- }
-}
-
#endif // !defined(TYPES_H_INCLUDED)
void set_option(istringstream& up);
void set_position(Position& pos, istringstream& up);
- void go(Position& pos, istringstream& up);
+ void go(const Position& pos, istringstream& up);
}
// the thinking time and other parameters from the input string, and starts
// the search.
- void go(Position& pos, istringstream& is) {
+ void go(const Position& pos, istringstream& is) {
Search::LimitsType limits;
vector<Move> searchMoves;
projects / stockfish / commitdiff