struct RootMove {
- RootMove();
- bool operator<(const RootMove&) const; // Used to sort
+ RootMove() { nodes = cumulativeNodes = ourBeta = theirBeta = 0ULL; }
+
+ // RootMove::operator<() is the comparison function used when
+ // sorting the moves. A move m1 is considered to be better
+ // than a move m2 if it has a higher score, or if the moves
+ // have equal score but m1 has the higher node count.
+ bool operator<(const RootMove& m) const {
+
+ return score != m.score ? score < m.score : theirBeta <= m.theirBeta;
+ }
Move move;
Value score;
public:
RootMoveList(Position& pos, Move searchMoves[]);
- inline Move get_move(int moveNum) const;
- inline Value get_move_score(int moveNum) const;
- inline void set_move_score(int moveNum, Value score);
- inline void set_move_nodes(int moveNum, int64_t nodes);
- inline void set_beta_counters(int moveNum, int64_t our, int64_t their);
+
+ int move_count() const { return count; }
+ Move get_move(int moveNum) const { return moves[moveNum].move; }
+ Value get_move_score(int moveNum) const { return moves[moveNum].score; }
+ void set_move_score(int moveNum, Value score) { moves[moveNum].score = score; }
+ Move get_move_pv(int moveNum, int i) const { return moves[moveNum].pv[i]; }
+ int64_t get_move_cumulative_nodes(int moveNum) const { return moves[moveNum].cumulativeNodes; }
+
+ void set_move_nodes(int moveNum, int64_t nodes);
+ void set_beta_counters(int moveNum, int64_t our, int64_t their);
void set_move_pv(int moveNum, const Move pv[]);
- inline Move get_move_pv(int moveNum, int i) const;
- inline int64_t get_move_cumulative_nodes(int moveNum) const;
- inline int move_count() const;
- inline void sort();
+ void sort();
void sort_multipv(int n);
private:
// evaluation of the position is more than NullMoveMargin below beta.
const Value NullMoveMargin = Value(0x300);
- // Pruning criterions. See the code and comments in ok_to_prune() to
- // understand their precise meaning.
- const bool PruneEscapeMoves = false;
- const bool PruneDefendingMoves = false;
- const bool PruneBlockingMoves = false;
-
// If the TT move is at least SingleReplyMargin better then the
// remaining ones we will extend it.
const Value SingleReplyMargin = Value(0x20);
Lock MPLock;
Lock IOLock;
bool AllThreadsShouldExit = false;
- const int MaxActiveSplitPoints = 8; // FIXME, sync with UCI Option
- SplitPoint SplitPointStack[THREAD_MAX][MaxActiveSplitPoints];
+ SplitPoint SplitPointStack[THREAD_MAX][ACTIVE_SPLIT_POINTS_MAX];
bool Idle = true;
#if !defined(_MSC_VER)
bool ok_to_do_nullmove(const Position& pos);
bool ok_to_prune(const Position& pos, Move m, Move threat);
bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply);
- void update_history(const Position& pos, Move m, Depth depth, Move movesSearched[], int moveCount);
+ Value refine_eval(const TTEntry* tte, Value defaultEval, int ply);
+ void update_history(const Position& pos, Move move, Depth depth, Move movesSearched[], int moveCount);
void update_killers(Move m, SearchStack& ss);
bool fail_high_ply_1();
//// Functions
////
+//FIXME: HACK
+static double lnArray[512];
+
+inline double ln(int i)
+{
+ return lnArray[i];
+}
/// perft() is our utility to verify move generation is bug free. All the legal
/// moves up to given depth are generated and counted and the sum returned.
/// and initializes the split point stack and the global locks and condition
/// objects.
+#include <cmath> //FIXME: HACK
+
void init_threads() {
+ // FIXME: HACK!!
+ for (int i = 0; i < 512; i++)
+ lnArray[i] = log(double(i));
+
volatile int i;
#if !defined(_MSC_VER)
}
// Launch the helper threads
- for(i = 1; i < THREAD_MAX; i++)
+ for (i = 1; i < THREAD_MAX; i++)
{
#if !defined(_MSC_VER)
pthread_create(pthread, NULL, init_thread, (void*)(&i));
for (int i = 1; i < THREAD_MAX; i++)
{
Threads[i].stop = true;
- while(Threads[i].running);
+ while (Threads[i].running);
}
destroy_split_point_stack();
}
int64_t nodes;
Move move;
StateInfo st;
- Depth ext, newDepth;
+ Depth depth, ext, newDepth;
RootMoveNumber = i + 1;
FailHigh = false;
bool moveIsCheck = pos.move_is_check(move);
bool captureOrPromotion = pos.move_is_capture_or_promotion(move);
bool dangerous;
+ depth = (Iteration - 2) * OnePly + InitialDepth;
ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, false, false, &dangerous);
- newDepth = (Iteration - 2) * OnePly + ext + InitialDepth;
+ newDepth = depth + ext;
// Make the move, and search it
pos.do_move(move, st, ci, moveIsCheck);
{
// Try to reduce non-pv search depth by one ply if move seems not problematic,
// if the move fails high will be re-searched at full depth.
- if ( newDepth >= 3*OnePly
- && i >= MultiPV + LMRPVMoves
+ if ( depth >= 3*OnePly // FIXME was newDepth
&& !dangerous
&& !captureOrPromotion
&& !move_is_castle(move))
{
- ss[0].reduction = OnePly;
- value = -search(pos, ss, -alpha, newDepth-OnePly, 1, true, 0);
+ double red = 0.5 + ln(RootMoveNumber - MultiPV + 1) * ln(depth / 2) / 6.0;
+ if (red >= 1.0)
+ {
+ ss[0].reduction = Depth(int(floor(red * int(OnePly))));
+ value = -search(pos, ss, -alpha, newDepth-ss[0].reduction, 1, true, 0);
+ }
+ else
+ value = alpha + 1; // Just to trigger next condition
} else
value = alpha + 1; // Just to trigger next condition
// Try to reduce non-pv search depth by one ply if move seems not problematic,
// if the move fails high will be re-searched at full depth.
if ( depth >= 3*OnePly
- && moveCount >= LMRPVMoves
&& !dangerous
&& !captureOrPromotion
&& !move_is_castle(move)
&& !move_is_killer(move, ss[ply]))
{
- ss[ply].reduction = OnePly;
- value = -search(pos, ss, -alpha, newDepth-OnePly, ply+1, true, threadID);
+ double red = 0.5 + ln(moveCount) * ln(depth / 2) / 6.0;
+ if (red >= 1.0)
+ {
+ ss[ply].reduction = Depth(int(floor(red * int(OnePly))));
+ value = -search(pos, ss, -alpha, newDepth-ss[ply].reduction, ply+1, true, threadID);
+ }
+ else
+ value = alpha + 1; // Just to trigger next condition
}
else
value = alpha + 1; // Just to trigger next condition
return value_from_tt(tte->value(), ply);
}
- approximateEval = quick_evaluate(pos);
+ approximateEval = refine_eval(tte, quick_evaluate(pos), ply);
isCheck = pos.is_check();
// Null move search
pos.do_null_move(st);
// Null move dynamic reduction based on depth
- int R = (depth >= 5 * OnePly ? 4 : 3);
+ int R = 3 + (depth >= 5 * OnePly ? depth / 8 : 0);
// Null move dynamic reduction based on value
if (approximateEval - beta > PawnValueMidgame)
// Try to reduce non-pv search depth by one ply if move seems not problematic,
// if the move fails high will be re-searched at full depth.
if ( depth >= 3*OnePly
- && moveCount >= LMRNonPVMoves
&& !dangerous
&& !captureOrPromotion
&& !move_is_castle(move)
- && !move_is_killer(move, ss[ply]))
+ && !move_is_killer(move, ss[ply])
+ /* && move != ttMove*/)
{
- ss[ply].reduction = OnePly;
- value = -search(pos, ss, -(beta-1), newDepth-OnePly, ply+1, true, threadID);
+ double red = 0.5 + ln(moveCount) * ln(depth / 2) / 3.0;
+ if (red >= 1.0)
+ {
+ ss[ply].reduction = Depth(int(floor(red * int(OnePly))));
+ value = -search(pos, ss, -(beta-1), newDepth-ss[ply].reduction, ply+1, true, threadID);
+ }
+ else
+ value = beta; // Just to trigger next condition
}
else
value = beta; // Just to trigger next condition
// Try to reduce non-pv search depth by one ply if move seems not problematic,
// if the move fails high will be re-searched at full depth.
if ( !dangerous
- && moveCount >= LMRNonPVMoves
&& !captureOrPromotion
&& !move_is_castle(move)
&& !move_is_killer(move, ss[sp->ply]))
{
- ss[sp->ply].reduction = OnePly;
- value = -search(pos, ss, -(sp->beta-1), newDepth - OnePly, sp->ply+1, true, threadID);
+ double red = 0.5 + ln(moveCount) * ln(sp->depth / 2) / 3.0;
+ if (red >= 1.0)
+ {
+ ss[sp->ply].reduction = Depth(int(floor(red * int(OnePly))));
+ value = -search(pos, ss, -(sp->beta-1), newDepth-ss[sp->ply].reduction, sp->ply+1, true, threadID);
+ }
+ else
+ value = sp->beta; // Just to trigger next condition
}
else
value = sp->beta; // Just to trigger next condition
// Try to reduce non-pv search depth by one ply if move seems not problematic,
// if the move fails high will be re-searched at full depth.
if ( !dangerous
- && moveCount >= LMRPVMoves
&& !captureOrPromotion
&& !move_is_castle(move)
&& !move_is_killer(move, ss[sp->ply]))
{
- ss[sp->ply].reduction = OnePly;
- value = -search(pos, ss, -sp->alpha, newDepth - OnePly, sp->ply+1, true, threadID);
+ double red = 0.5 + ln(moveCount) * ln(sp->depth / 2) / 6.0;
+ if (red >= 1.0)
+ {
+ ss[sp->ply].reduction = Depth(int(floor(red * int(OnePly))));
+ value = -search(pos, ss, -sp->alpha, newDepth-ss[sp->ply].reduction, sp->ply+1, true, threadID);
+ }
+ else
+ value = sp->alpha + 1; // Just to trigger next condition
}
else
value = sp->alpha + 1; // Just to trigger next condition
}
- /// The RootMove class
-
- // Constructor
-
- RootMove::RootMove() {
- nodes = cumulativeNodes = ourBeta = theirBeta = 0ULL;
- }
-
- // RootMove::operator<() is the comparison function used when
- // sorting the moves. A move m1 is considered to be better
- // than a move m2 if it has a higher score, or if the moves
- // have equal score but m1 has the higher node count.
-
- bool RootMove::operator<(const RootMove& m) const {
-
- if (score != m.score)
- return (score < m.score);
-
- return theirBeta <= m.theirBeta;
- }
-
/// The RootMoveList class
- // Constructor
+ // RootMoveList c'tor
RootMoveList::RootMoveList(Position& pos, Move searchMoves[]) : count(0) {
}
- // Simple accessor methods for the RootMoveList class
-
- inline Move RootMoveList::get_move(int moveNum) const {
- return moves[moveNum].move;
- }
-
- inline Value RootMoveList::get_move_score(int moveNum) const {
- return moves[moveNum].score;
- }
+ // RootMoveList simple methods definitions
- inline void RootMoveList::set_move_score(int moveNum, Value score) {
- moves[moveNum].score = score;
- }
+ void RootMoveList::set_move_nodes(int moveNum, int64_t nodes) {
- inline void RootMoveList::set_move_nodes(int moveNum, int64_t nodes) {
moves[moveNum].nodes = nodes;
moves[moveNum].cumulativeNodes += nodes;
}
- inline void RootMoveList::set_beta_counters(int moveNum, int64_t our, int64_t their) {
+ void RootMoveList::set_beta_counters(int moveNum, int64_t our, int64_t their) {
+
moves[moveNum].ourBeta = our;
moves[moveNum].theirBeta = their;
}
void RootMoveList::set_move_pv(int moveNum, const Move pv[]) {
- int j;
- for(j = 0; pv[j] != MOVE_NONE; j++)
- moves[moveNum].pv[j] = pv[j];
- moves[moveNum].pv[j] = MOVE_NONE;
- }
- inline Move RootMoveList::get_move_pv(int moveNum, int i) const {
- return moves[moveNum].pv[i];
- }
+ int j;
- inline int64_t RootMoveList::get_move_cumulative_nodes(int moveNum) const {
- return moves[moveNum].cumulativeNodes;
- }
+ for (j = 0; pv[j] != MOVE_NONE; j++)
+ moves[moveNum].pv[j] = pv[j];
- inline int RootMoveList::move_count() const {
- return count;
+ moves[moveNum].pv[j] = MOVE_NONE;
}
// RootMoveList::sort() sorts the root move list at the beginning of a new
// iteration.
- inline void RootMoveList::sort() {
+ void RootMoveList::sort() {
- sort_multipv(count - 1); // all items
+ sort_multipv(count - 1); // Sort all items
}
void RootMoveList::sort_multipv(int n) {
- for (int i = 1; i <= n; i++)
+ int i,j;
+
+ for (i = 1; i <= n; i++)
{
- RootMove rm = moves[i];
- int j;
- for (j = i; j > 0 && moves[j-1] < rm; j--)
- moves[j] = moves[j-1];
- moves[j] = rm;
+ RootMove rm = moves[i];
+ for (j = i; j > 0 && moves[j - 1] < rm; j--)
+ moves[j] = moves[j - 1];
+
+ moves[j] = rm;
}
}
// init_node() is called at the beginning of all the search functions
- // (search(), search_pv(), qsearch(), and so on) and initializes the search
- // stack object corresponding to the current node. Once every
+ // (search(), search_pv(), qsearch(), and so on) and initializes the
+ // search stack object corresponding to the current node. Once every
// NodesBetweenPolls nodes, init_node() also calls poll(), which polls
// for user input and checks whether it is time to stop the search.
}
}
ss[ply].init(ply);
- ss[ply+2].initKillers();
+ ss[ply + 2].initKillers();
if (Threads[threadID].printCurrentLine)
print_current_line(ss, ply, threadID);
}
- // update_pv() is called whenever a search returns a value > alpha. It
- // updates the PV in the SearchStack object corresponding to the current
- // node.
+ // update_pv() is called whenever a search returns a value > alpha.
+ // It updates the PV in the SearchStack object corresponding to the
+ // current node.
void update_pv(SearchStack ss[], int ply) {
+
assert(ply >= 0 && ply < PLY_MAX);
- ss[ply].pv[ply] = ss[ply].currentMove;
int p;
- for(p = ply + 1; ss[ply+1].pv[p] != MOVE_NONE; p++)
- ss[ply].pv[p] = ss[ply+1].pv[p];
+
+ ss[ply].pv[ply] = ss[ply].currentMove;
+
+ for (p = ply + 1; ss[ply + 1].pv[p] != MOVE_NONE; p++)
+ ss[ply].pv[p] = ss[ply + 1].pv[p];
+
ss[ply].pv[p] = MOVE_NONE;
}
- // sp_update_pv() is a variant of update_pv for use at split points. The
+ // sp_update_pv() is a variant of update_pv for use at split points. The
// difference between the two functions is that sp_update_pv also updates
// the PV at the parent node.
void sp_update_pv(SearchStack* pss, SearchStack ss[], int ply) {
+
assert(ply >= 0 && ply < PLY_MAX);
- ss[ply].pv[ply] = pss[ply].pv[ply] = ss[ply].currentMove;
int p;
- for(p = ply + 1; ss[ply+1].pv[p] != MOVE_NONE; p++)
- ss[ply].pv[p] = pss[ply].pv[p] = ss[ply+1].pv[p];
+
+ ss[ply].pv[ply] = pss[ply].pv[ply] = ss[ply].currentMove;
+
+ for (p = ply + 1; ss[ply + 1].pv[p] != MOVE_NONE; p++)
+ ss[ply].pv[p] = pss[ply].pv[p] = ss[ply + 1].pv[p];
+
ss[ply].pv[p] = pss[ply].pv[p] = MOVE_NONE;
}
// connected_moves() tests whether two moves are 'connected' in the sense
// that the first move somehow made the second move possible (for instance
- // if the moving piece is the same in both moves). The first move is
- // assumed to be the move that was made to reach the current position, while
- // the second move is assumed to be a move from the current position.
+ // if the moving piece is the same in both moves). The first move is assumed
+ // to be the move that was made to reach the current position, while the
+ // second move is assumed to be a move from the current position.
bool connected_moves(const Position& pos, Move m1, Move m2) {
&& bit_is_set(squares_between(f2, t2), f1))
return true;
- // Case 4: The destination square for m2 is attacked by the moving piece in m1
+ // Case 4: The destination square for m2 is defended by the moving piece in m1
p = pos.piece_on(t1);
if (bit_is_set(pos.attacks_from(p, t1), t2))
return true;
// Case 5: Discovered check, checking piece is the piece moved in m1
- if ( piece_is_slider(p)
- && bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), f2)
+ if ( piece_is_slider(p)
+ && bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), f2)
&& !bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), t2))
{
- Bitboard occ = pos.occupied_squares();
- Color us = pos.side_to_move();
- Square ksq = pos.king_square(us);
- clear_bit(&occ, f2);
- if (type_of_piece(p) == BISHOP)
- {
- if (bit_is_set(bishop_attacks_bb(ksq, occ), t1))
- return true;
- }
- else if (type_of_piece(p) == ROOK)
- {
- if (bit_is_set(rook_attacks_bb(ksq, occ), t1))
- return true;
- }
- else
- {
- assert(type_of_piece(p) == QUEEN);
- if (bit_is_set(queen_attacks_bb(ksq, occ), t1))
- return true;
- }
+ // discovered_check_candidates() works also if the Position's side to
+ // move is the opposite of the checking piece.
+ Color them = opposite_color(pos.side_to_move());
+ Bitboard dcCandidates = pos.discovered_check_candidates(them);
+
+ if (bit_is_set(dcCandidates, f2))
+ return true;
}
return false;
}
// extension() decides whether a move should be searched with normal depth,
- // or with extended depth. Certain classes of moves (checking moves, in
+ // or with extended depth. Certain classes of moves (checking moves, in
// particular) are searched with bigger depth than ordinary moves and in
// any case are marked as 'dangerous'. Note that also if a move is not
// extended, as example because the corresponding UCI option is set to zero,
// ok_to_do_nullmove() looks at the current position and decides whether
- // doing a 'null move' should be allowed. In order to avoid zugzwang
+ // doing a 'null move' should be allowed. In order to avoid zugzwang
// problems, null moves are not allowed when the side to move has very
- // little material left. Currently, the test is a bit too simple: Null
- // moves are avoided only when the side to move has only pawns left. It's
- // probably a good idea to avoid null moves in at least some more
+ // little material left. Currently, the test is a bit too simple: Null
+ // moves are avoided only when the side to move has only pawns left.
+ // It's probably a good idea to avoid null moves in at least some more
// complicated endgames, e.g. KQ vs KR. FIXME
bool ok_to_do_nullmove(const Position& pos) {
}
- // ok_to_prune() tests whether it is safe to forward prune a move. Only
+ // ok_to_prune() tests whether it is safe to forward prune a move. Only
// non-tactical moves late in the move list close to the leaves are
// candidates for pruning.
Square mfrom, mto, tfrom, tto;
+ // Prune if there isn't any threat move and
+ // is not a castling move (common case).
+ if (threat == MOVE_NONE && !move_is_castle(m))
+ return true;
+
mfrom = move_from(m);
mto = move_to(m);
tfrom = move_from(threat);
return false;
// Case 2: Don't prune moves which move the threatened piece
- if (!PruneEscapeMoves && threat != MOVE_NONE && mfrom == tto)
+ if (mfrom == tto)
return false;
// Case 3: If the threatened piece has value less than or equal to the
// value of the threatening piece, don't prune move which defend it.
- if ( !PruneDefendingMoves
- && threat != MOVE_NONE
- && pos.move_is_capture(threat)
+ if ( pos.move_is_capture(threat)
&& ( pos.midgame_value_of_piece_on(tfrom) >= pos.midgame_value_of_piece_on(tto)
|| pos.type_of_piece_on(tfrom) == KING)
&& pos.move_attacks_square(m, tto))
// Case 4: If the moving piece in the threatened move is a slider, don't
// prune safe moves which block its ray.
- if ( !PruneBlockingMoves
- && threat != MOVE_NONE
- && piece_is_slider(pos.piece_on(tfrom))
+ if ( piece_is_slider(pos.piece_on(tfrom))
&& bit_is_set(squares_between(tfrom, tto), mto)
&& pos.see_sign(m) >= 0)
return false;
}
+ // refine_eval() returns the transposition table score if
+ // possible otherwise falls back on static position evaluation.
+
+ Value refine_eval(const TTEntry* tte, Value defaultEval, int ply) {
+
+ if (!tte)
+ return defaultEval;
+
+ Value v = value_from_tt(tte->value(), ply);
+
+ if ( (is_lower_bound(tte->type()) && v >= defaultEval)
+ || (is_upper_bound(tte->type()) && v < defaultEval))
+ return v;
+
+ return defaultEval;
+ }
+
// update_history() registers a good move that produced a beta-cutoff
// in history and marks as failures all the other moves of that ply.
- void update_history(const Position& pos, Move m, Depth depth,
+ void update_history(const Position& pos, Move move, Depth depth,
Move movesSearched[], int moveCount) {
- H.success(pos.piece_on(move_from(m)), move_to(m), depth);
+ Move m;
+
+ H.success(pos.piece_on(move_from(move)), move_to(move), depth);
for (int i = 0; i < moveCount - 1; i++)
{
- assert(m != movesSearched[i]);
- if (!pos.move_is_capture_or_promotion(movesSearched[i]))
- H.failure(pos.piece_on(move_from(movesSearched[i])), move_to(movesSearched[i]), depth);
+ m = movesSearched[i];
+
+ assert(m != move);
+
+ if (!pos.move_is_capture_or_promotion(m))
+ H.failure(pos.piece_on(move_from(m)), move_to(m), depth);
}
}
// fail_high_ply_1() checks if some thread is currently resolving a fail
// high at ply 1 at the node below the first root node. This information
- // is used for time managment.
+ // is used for time management.
bool fail_high_ply_1() {
- for(int i = 0; i < ActiveThreads; i++)
+ for (int i = 0; i < ActiveThreads; i++)
if (Threads[i].failHighPly1)
return true;
// since the beginning of the current search.
int current_search_time() {
+
return get_system_time() - SearchStartTime;
}
// nps() computes the current nodes/second count.
int nps() {
+
int t = current_search_time();
- return (t > 0)? int((nodes_searched() * 1000) / t) : 0;
+ return (t > 0 ? int((nodes_searched() * 1000) / t) : 0);
}
- // poll() performs two different functions: It polls for user input, and it
+ // poll() performs two different functions: It polls for user input, and it
// looks at the time consumed so far and decides if it's time to abort the
// search.
{
// We are line oriented, don't read single chars
std::string command;
+
if (!std::getline(std::cin, command))
command = "quit";
else if (command == "ponderhit")
ponderhit();
}
+
// Print search information
if (t < 1000)
lastInfoTime = 0;
{
lastInfoTime = t;
lock_grab(&IOLock);
+
if (dbg_show_mean)
dbg_print_mean();
cout << "info nodes " << nodes_searched() << " nps " << nps()
<< " time " << t << " hashfull " << TT.full() << endl;
+
lock_release(&IOLock);
+
if (ShowCurrentLine)
Threads[0].printCurrentLine = true;
}
+
// Should we stop the search?
if (PonderSearch)
return;
- bool overTime = t > AbsoluteMaxSearchTime
- || (RootMoveNumber == 1 && t > MaxSearchTime + ExtraSearchTime && !FailLow) //FIXME: We are not checking any problem flags, BUG?
- || ( !FailHigh && !FailLow && !fail_high_ply_1() && !Problem
- && t > 6*(MaxSearchTime + ExtraSearchTime));
+ bool stillAtFirstMove = RootMoveNumber == 1
+ && !FailLow
+ && t > MaxSearchTime + ExtraSearchTime;
- if ( (Iteration >= 3 && (!InfiniteSearch && overTime))
+ bool noProblemFound = !FailHigh
+ && !FailLow
+ && !fail_high_ply_1()
+ && !Problem
+ && t > 6 * (MaxSearchTime + ExtraSearchTime);
+
+ bool noMoreTime = t > AbsoluteMaxSearchTime
+ || stillAtFirstMove //FIXME: We are not checking any problem flags, BUG?
+ || noProblemFound;
+
+ if ( (Iteration >= 3 && !InfiniteSearch && noMoreTime)
|| (ExactMaxTime && t >= ExactMaxTime)
|| (Iteration >= 3 && MaxNodes && nodes_searched() >= MaxNodes))
AbortSearch = true;
int t = current_search_time();
PonderSearch = false;
- if (Iteration >= 3 &&
- (!InfiniteSearch && (StopOnPonderhit ||
- t > AbsoluteMaxSearchTime ||
- (RootMoveNumber == 1 &&
- t > MaxSearchTime + ExtraSearchTime && !FailLow) ||
- (!FailHigh && !FailLow && !fail_high_ply_1() && !Problem &&
- t > 6*(MaxSearchTime + ExtraSearchTime)))))
- AbortSearch = true;
+
+ bool stillAtFirstMove = RootMoveNumber == 1
+ && !FailLow
+ && t > MaxSearchTime + ExtraSearchTime;
+
+ bool noProblemFound = !FailHigh
+ && !FailLow
+ && !fail_high_ply_1()
+ && !Problem
+ && t > 6 * (MaxSearchTime + ExtraSearchTime);
+
+ bool noMoreTime = t > AbsoluteMaxSearchTime
+ || stillAtFirstMove
+ || noProblemFound;
+
+ if (Iteration >= 3 && !InfiniteSearch && (noMoreTime || StopOnPonderhit))
+ AbortSearch = true;
}
// print_current_line() prints the current line of search for a given
- // thread. Called when the UCI option UCI_ShowCurrLine is 'true'.
+ // thread. Called when the UCI option UCI_ShowCurrLine is 'true'.
void print_current_line(SearchStack ss[], int ply, int threadID) {
// wait_for_stop_or_ponderhit() is called when the maximum depth is reached
- // while the program is pondering. The point is to work around a wrinkle in
- // the UCI protocol: When pondering, the engine is not allowed to give a
+ // while the program is pondering. The point is to work around a wrinkle in
+ // the UCI protocol: When pondering, the engine is not allowed to give a
// "bestmove" before the GUI sends it a "stop" or "ponderhit" command.
// We simply wait here until one of these commands is sent, and return,
// after which the bestmove and pondermove will be printed (in id_loop()).
// object for which the current thread is the master.
void idle_loop(int threadID, SplitPoint* waitSp) {
+
assert(threadID >= 0 && threadID < THREAD_MAX);
Threads[threadID].running = true;
- while(true) {
- if(AllThreadsShouldExit && threadID != 0)
- break;
+ while (true)
+ {
+ if (AllThreadsShouldExit && threadID != 0)
+ break;
+
+ // If we are not thinking, wait for a condition to be signaled
+ // instead of wasting CPU time polling for work.
+ while (threadID != 0 && (Idle || threadID >= ActiveThreads))
+ {
- // If we are not thinking, wait for a condition to be signaled instead
- // of wasting CPU time polling for work:
- while(threadID != 0 && (Idle || threadID >= ActiveThreads)) {
#if !defined(_MSC_VER)
- pthread_mutex_lock(&WaitLock);
- if(Idle || threadID >= ActiveThreads)
- pthread_cond_wait(&WaitCond, &WaitLock);
- pthread_mutex_unlock(&WaitLock);
+ pthread_mutex_lock(&WaitLock);
+ if (Idle || threadID >= ActiveThreads)
+ pthread_cond_wait(&WaitCond, &WaitLock);
+
+ pthread_mutex_unlock(&WaitLock);
#else
- WaitForSingleObject(SitIdleEvent[threadID], INFINITE);
+ WaitForSingleObject(SitIdleEvent[threadID], INFINITE);
#endif
- }
+ }
// If this thread has been assigned work, launch a search
- if(Threads[threadID].workIsWaiting) {
- Threads[threadID].workIsWaiting = false;
- if(Threads[threadID].splitPoint->pvNode)
- sp_search_pv(Threads[threadID].splitPoint, threadID);
- else
- sp_search(Threads[threadID].splitPoint, threadID);
- Threads[threadID].idle = true;
+ if (Threads[threadID].workIsWaiting)
+ {
+ Threads[threadID].workIsWaiting = false;
+ if (Threads[threadID].splitPoint->pvNode)
+ sp_search_pv(Threads[threadID].splitPoint, threadID);
+ else
+ sp_search(Threads[threadID].splitPoint, threadID);
+
+ Threads[threadID].idle = true;
}
// If this thread is the master of a split point and all threads have
// finished their work at this split point, return from the idle loop.
- if(waitSp != NULL && waitSp->cpus == 0)
- return;
+ if (waitSp != NULL && waitSp->cpus == 0)
+ return;
}
Threads[threadID].running = false;
// initializes all split point objects.
void init_split_point_stack() {
- for(int i = 0; i < THREAD_MAX; i++)
- for(int j = 0; j < MaxActiveSplitPoints; j++) {
- SplitPointStack[i][j].parent = NULL;
- lock_init(&(SplitPointStack[i][j].lock), NULL);
- }
+
+ for (int i = 0; i < THREAD_MAX; i++)
+ for (int j = 0; j < ACTIVE_SPLIT_POINTS_MAX; j++)
+ {
+ SplitPointStack[i][j].parent = NULL;
+ lock_init(&(SplitPointStack[i][j].lock), NULL);
+ }
}
// destroys all locks in the precomputed split point objects.
void destroy_split_point_stack() {
- for(int i = 0; i < THREAD_MAX; i++)
- for(int j = 0; j < MaxActiveSplitPoints; j++)
- lock_destroy(&(SplitPointStack[i][j].lock));
+
+ for (int i = 0; i < THREAD_MAX; i++)
+ for (int j = 0; j < ACTIVE_SPLIT_POINTS_MAX; j++)
+ lock_destroy(&(SplitPointStack[i][j].lock));
}
// thread_should_stop() checks whether the thread with a given threadID has
- // been asked to stop, directly or indirectly. This can happen if a beta
- // cutoff has occured in thre thread's currently active split point, or in
+ // been asked to stop, directly or indirectly. This can happen if a beta
+ // cutoff has occurred in the thread's currently active split point, or in
// some ancestor of the current split point.
bool thread_should_stop(int threadID) {
+
assert(threadID >= 0 && threadID < ActiveThreads);
SplitPoint* sp;
- if(Threads[threadID].stop)
- return true;
- if(ActiveThreads <= 2)
- return false;
- for(sp = Threads[threadID].splitPoint; sp != NULL; sp = sp->parent)
- if(sp->finished) {
- Threads[threadID].stop = true;
+ if (Threads[threadID].stop)
return true;
- }
+ if (ActiveThreads <= 2)
+ return false;
+ for (sp = Threads[threadID].splitPoint; sp != NULL; sp = sp->parent)
+ if (sp->finished)
+ {
+ Threads[threadID].stop = true;
+ return true;
+ }
return false;
}
// thread_is_available() checks whether the thread with threadID "slave" is
- // available to help the thread with threadID "master" at a split point. An
- // obvious requirement is that "slave" must be idle. With more than two
+ // available to help the thread with threadID "master" at a split point. An
+ // obvious requirement is that "slave" must be idle. With more than two
// threads, this is not by itself sufficient: If "slave" is the master of
// some active split point, it is only available as a slave to the other
// threads which are busy searching the split point at the top of "slave"'s
// split point stack (the "helpful master concept" in YBWC terminology).
bool thread_is_available(int slave, int master) {
+
assert(slave >= 0 && slave < ActiveThreads);
assert(master >= 0 && master < ActiveThreads);
assert(ActiveThreads > 1);
- if(!Threads[slave].idle || slave == master)
- return false;
+ if (!Threads[slave].idle || slave == master)
+ return false;
- if(Threads[slave].activeSplitPoints == 0)
- // No active split points means that the thread is available as a slave
- // for any other thread.
- return true;
+ if (Threads[slave].activeSplitPoints == 0)
+ // No active split points means that the thread is available as
+ // a slave for any other thread.
+ return true;
- if(ActiveThreads == 2)
- return true;
+ if (ActiveThreads == 2)
+ return true;
- // Apply the "helpful master" concept if possible.
- if(SplitPointStack[slave][Threads[slave].activeSplitPoints-1].slaves[master])
- return true;
+ // Apply the "helpful master" concept if possible
+ if (SplitPointStack[slave][Threads[slave].activeSplitPoints - 1].slaves[master])
+ return true;
return false;
}
// a slave for the thread with threadID "master".
bool idle_thread_exists(int master) {
+
assert(master >= 0 && master < ActiveThreads);
assert(ActiveThreads > 1);
- for(int i = 0; i < ActiveThreads; i++)
- if(thread_is_available(i, master))
- return true;
+ for (int i = 0; i < ActiveThreads; i++)
+ if (thread_is_available(i, master))
+ return true;
+
return false;
}
// split() does the actual work of distributing the work at a node between
- // several threads at PV nodes. If it does not succeed in splitting the
+ // several threads at PV nodes. If it does not succeed in splitting the
// node (because no idle threads are available, or because we have no unused
- // split point objects), the function immediately returns false. If
+ // split point objects), the function immediately returns false. If
// splitting is possible, a SplitPoint object is initialized with all the
// data that must be copied to the helper threads (the current position and
// search stack, alpha, beta, the search depth, etc.), and we tell our
- // helper threads that they have been assigned work. This will cause them
- // to instantly leave their idle loops and call sp_search_pv(). When all
+ // helper threads that they have been assigned work. This will cause them
+ // to instantly leave their idle loops and call sp_search_pv(). When all
// threads have returned from sp_search_pv (or, equivalently, when
// splitPoint->cpus becomes 0), split() returns true.
// If no other thread is available to help us, or if we have too many
// active split points, don't split.
- if(!idle_thread_exists(master) ||
- Threads[master].activeSplitPoints >= MaxActiveSplitPoints) {
- lock_release(&MPLock);
- return false;
+ if ( !idle_thread_exists(master)
+ || Threads[master].activeSplitPoints >= ACTIVE_SPLIT_POINTS_MAX)
+ {
+ lock_release(&MPLock);
+ return false;
}
// Pick the next available split point object from the split point stack
splitPoint = SplitPointStack[master] + Threads[master].activeSplitPoints;
Threads[master].activeSplitPoints++;
- // Initialize the split point object
+ // Initialize the split point object and copy current position
splitPoint->parent = Threads[master].splitPoint;
splitPoint->finished = false;
splitPoint->ply = ply;
splitPoint->depth = depth;
- splitPoint->alpha = pvNode? *alpha : (*beta - 1);
+ splitPoint->alpha = pvNode ? *alpha : (*beta - 1);
splitPoint->beta = *beta;
splitPoint->pvNode = pvNode;
splitPoint->bestValue = *bestValue;
splitPoint->cpus = 1;
splitPoint->pos.copy(p);
splitPoint->parentSstack = sstck;
- for(i = 0; i < ActiveThreads; i++)
- splitPoint->slaves[i] = 0;
+ for (i = 0; i < ActiveThreads; i++)
+ splitPoint->slaves[i] = 0;
- // Copy the current position and the search stack to the master thread
- memcpy(splitPoint->sstack[master], sstck, (ply+1)*sizeof(SearchStack));
+ // Copy the current search stack to the master thread
+ memcpy(splitPoint->sstack[master], sstck, (ply+1) * sizeof(SearchStack));
Threads[master].splitPoint = splitPoint;
// Make copies of the current position and search stack for each thread
- for(i = 0; i < ActiveThreads && splitPoint->cpus < MaxThreadsPerSplitPoint;
- i++)
- if(thread_is_available(i, master)) {
- memcpy(splitPoint->sstack[i], sstck, (ply+1)*sizeof(SearchStack));
- Threads[i].splitPoint = splitPoint;
- splitPoint->slaves[i] = 1;
- splitPoint->cpus++;
- }
+ for (i = 0; i < ActiveThreads && splitPoint->cpus < MaxThreadsPerSplitPoint; i++)
+ if (thread_is_available(i, master))
+ {
+ memcpy(splitPoint->sstack[i], sstck, (ply+1) * sizeof(SearchStack));
+ Threads[i].splitPoint = splitPoint;
+ splitPoint->slaves[i] = 1;
+ splitPoint->cpus++;
+ }
- // Tell the threads that they have work to do. This will make them leave
+ // Tell the threads that they have work to do. This will make them leave
// their idle loop.
- for(i = 0; i < ActiveThreads; i++)
- if(i == master || splitPoint->slaves[i]) {
- Threads[i].workIsWaiting = true;
- Threads[i].idle = false;
- Threads[i].stop = false;
- }
+ for (i = 0; i < ActiveThreads; i++)
+ if (i == master || splitPoint->slaves[i])
+ {
+ Threads[i].workIsWaiting = true;
+ Threads[i].idle = false;
+ Threads[i].stop = false;
+ }
lock_release(&MPLock);
- // Everything is set up. The master thread enters the idle loop, from
+ // Everything is set up. The master thread enters the idle loop, from
// which it will instantly launch a search, because its workIsWaiting
// slot is 'true'. We send the split point as a second parameter to the
// idle loop, which means that the main thread will return from the idle
// loop when all threads have finished their work at this split point
- // (i.e. when // splitPoint->cpus == 0).
+ // (i.e. when splitPoint->cpus == 0).
idle_loop(master, splitPoint);
// We have returned from the idle loop, which means that all threads are
- // finished. Update alpha, beta and bestvalue, and return.
+ // finished. Update alpha, beta and bestValue, and return.
lock_grab(&MPLock);
- if(pvNode) *alpha = splitPoint->alpha;
+
+ if (pvNode)
+ *alpha = splitPoint->alpha;
+
*beta = splitPoint->beta;
*bestValue = splitPoint->bestValue;
Threads[master].stop = false;
Threads[master].idle = false;
Threads[master].activeSplitPoints--;
Threads[master].splitPoint = splitPoint->parent;
- lock_release(&MPLock);
+ lock_release(&MPLock);
return true;
}
// to start a new search from the root.
void wake_sleeping_threads() {
- if(ActiveThreads > 1) {
- for(int i = 1; i < ActiveThreads; i++) {
- Threads[i].idle = true;
- Threads[i].workIsWaiting = false;
- }
+
+ if (ActiveThreads > 1)
+ {
+ for (int i = 1; i < ActiveThreads; i++)
+ {
+ Threads[i].idle = true;
+ Threads[i].workIsWaiting = false;
+ }
+
#if !defined(_MSC_VER)
pthread_mutex_lock(&WaitLock);
pthread_cond_broadcast(&WaitCond);
pthread_mutex_unlock(&WaitLock);
#else
- for(int i = 1; i < THREAD_MAX; i++)
- SetEvent(SitIdleEvent[i]);
+ for (int i = 1; i < THREAD_MAX; i++)
+ SetEvent(SitIdleEvent[i]);
#endif
}
}
// init_thread() is the function which is called when a new thread is
- // launched. It simply calls the idle_loop() function with the supplied
- // threadID. There are two versions of this function; one for POSIX threads
- // and one for Windows threads.
+ // launched. It simply calls the idle_loop() function with the supplied
+ // threadID. There are two versions of this function; one for POSIX
+ // threads and one for Windows threads.
#if !defined(_MSC_VER)
- void *init_thread(void *threadID) {
- idle_loop(*(int *)threadID, NULL);
+ void* init_thread(void *threadID) {
+
+ idle_loop(*(int*)threadID, NULL);
return NULL;
}
#else
DWORD WINAPI init_thread(LPVOID threadID) {
- idle_loop(*(int *)threadID, NULL);
+
+ idle_loop(*(int*)threadID, NULL);
return NULL;
}
projects / stockfish / blobdiff