it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
-
+
Glaurung is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
-
+
You should have received a copy of the GNU General Public License
along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
// root move, we store a score, a node count, and a PV (really a refutation
// in the case of moves which fail low).
- class RootMove {
+ struct RootMove {
- public:
RootMove();
+ bool operator<(const RootMove&); // used to sort
+
Move move;
Value score;
int64_t nodes, cumulativeNodes;
int64_t get_move_cumulative_nodes(int moveNum);
int move_count() const;
Move scan_for_easy_move() const;
- void sort();
+ inline void sort();
void sort_multipv(int n);
private:
- static int compare_root_moves(const RootMove &rm1, const RootMove &rm2);
static const int MaxRootMoves = 500;
RootMove moves[MaxRootMoves];
int count;
#else
DWORD WINAPI init_thread(LPVOID threadID);
#endif
-
+
}
Depth(get_option_value_int("Pawn Push to 7th Extension (non-PV nodes)"));
PassedPawnExtension[1] =
Depth(get_option_value_int("Passed Pawn Extension (PV nodes)"));
- PassedPawnExtension[0] =
+ PassedPawnExtension[0] =
Depth(get_option_value_int("Passed Pawn Extension (non-PV nodes)"));
PawnEndgameExtension[1] =
Depth(get_option_value_int("Pawn Endgame Extension (PV nodes)"));
get_option_value_int("Maximum Number of Threads per Split Point");
read_weights(pos.side_to_move());
-
+
int newActiveThreads = get_option_value_int("Threads");
if(newActiveThreads != ActiveThreads) {
ActiveThreads = newActiveThreads;
if(UseLogFile)
LogFile.close();
-
+
if(Quit) {
OpeningBook.close();
stop_threads();
lock_init(&IOLock, NULL);
init_split_point_stack();
-
+
#if !defined(_MSC_VER)
pthread_mutex_init(&WaitLock, NULL);
pthread_cond_init(&WaitCond, NULL);
void id_loop(const Position &pos, Move searchMoves[]) {
Position p(pos);
- RootMoveList rml(p, searchMoves);
SearchStack ss[PLY_MAX_PLUS_2];
+ // searchMoves are verified, copied, scored and sorted
+ RootMoveList rml(p, searchMoves);
+
// Initialize
TT.new_search();
H.clear();
}
}
- // Write PV to transposition table, in case the relevant entries have
+ // Write PV to transposition table, in case the relevant entries have
// been overwritten during the search:
TT.insert_pv(p, ss[0].pv);
if(current_search_time() >= 1000)
std::cout << "info currmove " << move
<< " currmovenumber " << i + 1 << std::endl;
-
+
// Decide search depth for this move:
ext = extension(pos, move, true, pos.move_is_check(move), false, false);
newDepth = (Iteration-2)*OnePly + ext + InitialDepth;
else {
value = -search(pos, ss, -alpha, newDepth, 1, true, 0);
if(value > alpha) {
- // Fail high! Set the boolean variable FailHigh to true, and
+ // Fail high! Set the boolean variable FailHigh to true, and
// re-search the move with a big window. The variable FailHigh is
// used for time managment: We try to avoid aborting the search
// prematurely during a fail high research.
if(AbortSearch)
break;
- // Remember the node count for this move. The node counts are used to
+ // Remember the node count for this move. The node counts are used to
// sort the root moves at the next iteration.
rml.set_move_nodes(i, nodes_searched() - nodes);
rml.set_move_pv(i, ss[0].pv);
if(MultiPV == 1) {
- // We record how often the best move has been changed in each
+ // We record how often the best move has been changed in each
// iteration. This information is used for time managment: When
// the best move changes frequently, we allocate some more time.
if(i > 0)
return alpha;
// Transposition table lookup. At PV nodes, we don't use the TT for
- // pruning, but only for move ordering.
+ // pruning, but only for move ordering.
Value ttValue;
Depth ttDepth;
Move ttMove = MOVE_NONE;
bool moveIsCheck = pos.move_is_check(move, dcCandidates);
bool moveIsCapture = pos.move_is_capture(move);
bool moveIsPassedPawnPush = pos.move_is_passed_pawn_push(move);
-
+
assert(move_is_ok(move));
movesSearched[moveCount++] = ss[ply].currentMove = move;
// Make and search the move.
pos.do_move(move, u, dcCandidates);
-
- if(moveCount == 1)
+
+ if(moveCount == 1)
value = -search_pv(pos, ss, -beta, -alpha, newDepth, ply+1, threadID);
else {
if(depth >= 2*OnePly && ext == Depth(0) && moveCount >= LMRPVMoves
&& !moveIsPassedPawnPush && !move_is_castle(move)
&& move != ss[ply].killer1 && move != ss[ply].killer2) {
ss[ply].reduction = OnePly;
- value = -search(pos, ss, -alpha, newDepth-OnePly, ply+1, true,
+ value = -search(pos, ss, -alpha, newDepth-OnePly, ply+1, true,
threadID);
}
else value = alpha + 1;
// such cases, because resolving the fail high at ply 1 could
// result in a big drop in score at the root.
Threads[threadID].failHighPly1 = true;
- value = -search_pv(pos, ss, -beta, -alpha, newDepth, ply+1,
+ value = -search_pv(pos, ss, -beta, -alpha, newDepth, ply+1,
threadID);
Threads[threadID].failHighPly1 = false;
}
pos.undo_move(move, u);
assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
-
+
// New best move?
if(value > bestValue) {
bestValue = value;
return VALUE_DRAW;
}
- // If the search is not aborted, update the transposition table,
+ // If the search is not aborted, update the transposition table,
// history counters, and killer moves. This code is somewhat messy,
// and definitely needs to be cleaned up. FIXME
if(!AbortSearch && !thread_should_stop(threadID)) {
movesSearched[i]);
H.success(pos.piece_on(move_from(m)), m, depth);
-
+
if(m != ss[ply].killer1) {
ss[ply].killer2 = ss[ply].killer1;
ss[ply].killer1 = m;
return bestValue;
}
-
+
// search() is the search function for zero-width nodes.
// Futility pruning
if(useFutilityPruning && ext == Depth(0) && !moveIsCapture &&
!moveIsPassedPawnPush && !move_promotion(move)) {
-
+
if(moveCount >= 2 + int(depth)
&& ok_to_prune(pos, move, ss[ply].threatMove, depth))
continue;
// Make and search the move.
pos.do_move(move, u, dcCandidates);
-
+
if(depth >= 2*OnePly && ext == Depth(0) && moveCount >= LMRNonPVMoves
&& !moveIsCapture && !move_promotion(move) && !moveIsPassedPawnPush
&& !move_is_castle(move)
pos.undo_move(move, u);
assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
-
+
// New best move?
if(value > bestValue) {
bestValue = value;
VALUE_TYPE_UPPER);
else {
Move m = ss[ply].pv[ply];
-
+
if(pos.square_is_empty(move_to(m)) && !move_promotion(m) &&
!move_is_ep(m)) {
for(int i = 0; i < moveCount - 1; i++)
H.failure(pos.piece_on(move_from(movesSearched[i])),
movesSearched[i]);
H.success(pos.piece_on(move_from(m)), m, depth);
-
+
if(m != ss[ply].killer1) {
ss[ply].killer2 = ss[ply].killer1;
ss[ply].killer1 = m;
return bestValue;
}
-
+
// qsearch() is the quiescence search function, which is called by the main
// search function when the remaining depth is zero (or, to be more precise,
assert(ply >= 0 && ply < PLY_MAX);
assert(threadID >= 0 && threadID < ActiveThreads);
- // Initialize, and make an early exit in case of an aborted search,
+ // Initialize, and make an early exit in case of an aborted search,
// an instant draw, maximum ply reached, etc.
if(AbortSearch || thread_should_stop(threadID))
return Value(0);
Bitboard dcCandidates = mp.discovered_check_candidates();
bool isCheck = pos.is_check();
- // Loop through the moves until no moves remain or a beta cutoff
+ // Loop through the moves until no moves remain or a beta cutoff
// occurs.
while(alpha < beta && ((move = mp.get_next_move()) != MOVE_NONE)) {
UndoInfo u;
ss[ply].currentMove = move;
// Futility pruning
- if(UseQSearchFutilityPruning && !isCheck && !moveIsCheck &&
- !move_promotion(move) && !moveIsPassedPawnPush &&
+ if(UseQSearchFutilityPruning && !isCheck && !moveIsCheck &&
+ !move_promotion(move) && !moveIsPassedPawnPush &&
beta - alpha == 1 &&
pos.non_pawn_material(pos.side_to_move()) > RookValueMidgame) {
Value futilityValue =
- staticValue
+ staticValue
+ Max(pos.midgame_value_of_piece_on(move_to(move)),
pos.endgame_value_of_piece_on(move_to(move)))
+ FutilityMargin0
+ ei.futilityMargin;
if(futilityValue < alpha) {
- if(futilityValue > bestValue)
+ if(futilityValue > bestValue)
bestValue = futilityValue;
continue;
}
}
// All legal moves have been searched. A special case: If we're in check
- // and no legal moves were found, it is checkmate:
+ // and no legal moves were found, it is checkmate:
if(pos.is_check() && moveCount == 0) // Mate!
return value_mated_in(ply);
// splitting, we don't have to repeat all this work in sp_search(). We
// also don't need to store anything to the hash table here: This is taken
// care of after we return from the split point.
-
+
void sp_search(SplitPoint *sp, int threadID) {
assert(threadID >= 0 && threadID < ActiveThreads);
assert(ActiveThreads > 1);
-
+
Position pos = Position(sp->pos);
SearchStack *ss = sp->sstack[threadID];
Value value;
if(thread_should_stop(threadID))
break;
-
+
// New best move?
lock_grab(&(sp->lock));
if(value > sp->bestValue && !thread_should_stop(threadID)) {
// don't have to repeat all this work in sp_search_pv(). We also don't
// need to store anything to the hash table here: This is taken care of
// after we return from the split point.
-
+
void sp_search_pv(SplitPoint *sp, int threadID) {
assert(threadID >= 0 && threadID < ActiveThreads);
assert(ActiveThreads > 1);
-
+
Position pos = Position(sp->pos);
SearchStack *ss = sp->sstack[threadID];
Value value;
lock_release(&(sp->lock));
ss[sp->ply].currentMove = move;
-
+
// Decide the new search depth.
ext = extension(pos, move, true, moveIsCheck, false, false);
newDepth = sp->depth - OnePly + ext;
if(thread_should_stop(threadID))
break;
-
+
// New best move?
lock_grab(&(sp->lock));
if(value > sp->bestValue && !thread_should_stop(threadID)) {
sp->slaves[threadID] = 0;
lock_release(&(sp->lock));
- }
+ }
/// The RootMove class
RootMove::RootMove() {
nodes = cumulativeNodes = 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) {
+
+ if (score != m.score)
+ return (score < m.score);
+
+ return nodes <= m.nodes;
+ }
/// The RootMoveList class
// Constructor
- RootMoveList::RootMoveList(Position &pos, Move searchMoves[]) {
+ RootMoveList::RootMoveList(Position& pos, Move searchMoves[]) : count(0) {
+
MoveStack mlist[MaxRootMoves];
bool includeAllMoves = (searchMoves[0] == MOVE_NONE);
- int i, j = 0, k;
// Generate all legal moves
- count = generate_legal_moves(pos, mlist);
+ int lm_count = generate_legal_moves(pos, mlist);
// Add each move to the moves[] array
- for(i = 0; i < count; i++) {
- UndoInfo u;
- SearchStack ss[PLY_MAX_PLUS_2];
- bool includeMove;
-
- if(includeAllMoves)
- includeMove = true;
- else {
- includeMove = false;
- for(k = 0; searchMoves[k] != MOVE_NONE; k++)
- if(searchMoves[k] == mlist[i].move) {
- includeMove = true;
- break;
- }
- }
-
- if(includeMove) {
- moves[j].move = mlist[i].move;
- moves[j].nodes = 0ULL;
- pos.do_move(moves[j].move, u);
- moves[j].score = -qsearch(pos, ss, -VALUE_INFINITE, VALUE_INFINITE,
- Depth(0), 1, 0);
- pos.undo_move(moves[j].move, u);
- moves[j].pv[0] = moves[i].move;
- moves[j].pv[1] = MOVE_NONE; // FIXME
- j++;
- }
+ for (int i = 0; i < lm_count; i++)
+ {
+ bool includeMove = includeAllMoves;
+
+ for (int k = 0; !includeMove && searchMoves[k] != MOVE_NONE; k++)
+ includeMove = (searchMoves[k] == mlist[i].move);
+
+ if (includeMove)
+ {
+ // Find a quick score for the move
+ UndoInfo u;
+ SearchStack ss[PLY_MAX_PLUS_2];
+
+ moves[count].move = mlist[i].move;
+ moves[count].nodes = 0ULL;
+ pos.do_move(moves[count].move, u);
+ moves[count].score = -qsearch(pos, ss, -VALUE_INFINITE, VALUE_INFINITE,
+ Depth(0), 1, 0);
+ pos.undo_move(moves[count].move, u);
+ moves[count].pv[0] = moves[i].move;
+ moves[count].pv[1] = MOVE_NONE; // FIXME
+ count++;
+ }
}
- count = j;
- this->sort();
+ sort();
}
void RootMoveList::set_move_score(int moveNum, Value score) {
moves[moveNum].score = score;
}
-
+
void RootMoveList::set_move_nodes(int moveNum, int64_t nodes) {
moves[moveNum].nodes = nodes;
moves[moveNum].cumulativeNodes += nodes;
int64_t RootMoveList::get_move_cumulative_nodes(int moveNum) {
return moves[moveNum].cumulativeNodes;
}
-
+
int RootMoveList::move_count() const {
return count;
}
// is returned, otherwise the function returns MOVE_NONE. It is very
// important that this function is called at the right moment: The code
// assumes that the first iteration has been completed and the moves have
- // been sorted.
+ // been sorted. This is done in RootMoveList c'tor.
Move RootMoveList::scan_for_easy_move() const {
- Value bestMoveValue = this->get_move_score(0);
- for(int i = 1; i < this->move_count(); i++)
- if(this->get_move_score(i) >= bestMoveValue - EasyMoveMargin)
- return MOVE_NONE;
- return this->get_move(0);
- }
+ assert(count);
+
+ if (count == 1)
+ return get_move(0);
+
+ // moves are sorted so just consider the best and the second one
+ if (get_move_score(0) > get_move_score(1) + EasyMoveMargin)
+ return get_move(0);
+
+ return MOVE_NONE;
+ }
// RootMoveList::sort() sorts the root move list at the beginning of a new
// iteration.
- void RootMoveList::sort() {
- for(int i = 1; i < count; i++) {
- RootMove rm = moves[i];
- int j;
- for(j = i; j > 0 && compare_root_moves(moves[j-1], rm); j--)
- moves[j] = moves[j-1];
- moves[j] = rm;
- }
+ inline void RootMoveList::sort() {
+
+ sort_multipv(count - 1); // all items
}
// RootMoveList::sort_multipv() sorts the first few moves in the root move
- // list by their scores and depths. It is used to order the different PVs
+ // list by their scores and depths. It is used to order the different PVs
// correctly in MultiPV mode.
void RootMoveList::sort_multipv(int n) {
- for(int i = 1; i <= n; i++) {
+
+ for (int i = 1; i <= n; i++)
+ {
RootMove rm = moves[i];
int j;
- for(j = i; j > 0 && moves[j-1].score < rm.score; j--)
- moves[j] = moves[j-1];
+ for (j = i; j > 0 && moves[j-1] < rm; j--)
+ moves[j] = moves[j-1];
moves[j] = rm;
}
}
- // RootMoveList::compare_root_moves() is the comparison function used by
- // RootMoveList::sort 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.
-
- int RootMoveList::compare_root_moves(const RootMove &rm1,
- const RootMove &rm2) {
- if(rm1.score < rm2.score) return 1;
- else if(rm1.score > rm2.score) return 0;
- else if(rm1.nodes < rm2.nodes) return 1;
- else if(rm1.nodes > rm2.nodes) return 0;
- else return 1;
- }
-
-
// init_search_stack() initializes a search stack at the beginning of a
// new search from the root.
// 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);
return false;
}
-
-
+
+
// extension() decides whether a move should be searched with normal depth,
// or with extended depth. Certain classes of moves (checking moves, in
// particular) are searched with bigger depth than ordinary moves.
// Case 4: Don't prune moves with good history.
if(!H.ok_to_prune(pos.piece_on(move_from(m)), m, d))
return false;
-
+
// Case 5: 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
return true;
}
-
+
// 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.
-
+
bool fail_high_ply_1() {
for(int i = 0; i < ActiveThreads; i++)
if(Threads[i].failHighPly1)
else if(strncmp(input, "ponderhit", 9) == 0)
ponderhit();
}
-
+
// Print search information
if(t < 1000)
lastInfoTime = 0;
std::cout << "info nodes " << nodes_searched() << " nps " << nps()
<< " time " << t << " hashfull " << TT.full() << std::endl;
lock_release(&IOLock);
- if(ShowCurrentLine)
+ if(ShowCurrentLine)
Threads[0].printCurrentLine = true;
}
// print_current_line() prints the current line of search for a given
// thread. Called when the UCI option UCI_ShowCurrLine is 'true'.
-
+
void print_current_line(SearchStack ss[], int ply, int threadID) {
assert(ply >= 0 && ply < PLY_MAX);
assert(threadID >= 0 && threadID < ActiveThreads);
// "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()).
-
+
void wait_for_stop_or_ponderhit() {
std::string command;
while(true) {
if(!std::getline(std::cin, command))
command = "quit";
-
+
if(command == "quit") {
OpeningBook.close();
stop_threads();
}
}
-
+
// idle_loop() is where the threads are parked when they have no work to do.
// The parameter "waitSp", if non-NULL, is a pointer to an active SplitPoint
// 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;
+ Threads[threadID].running = true;
while(true) {
if(AllThreadsShouldExit && threadID != 0)
for(int i = 0; i < THREAD_MAX; i++)
for(int j = 0; j < MaxActiveSplitPoints; j++)
lock_destroy(&(SplitPointStack[i][j].lock));
- }
+ }
// thread_should_stop() checks whether the thread with a given threadID has
bool thread_should_stop(int threadID) {
assert(threadID >= 0 && threadID < ActiveThreads);
-
+
SplitPoint *sp;
if(Threads[threadID].stop)
return true;
}
return false;
- }
+ }
// thread_is_available() checks whether the thread with threadID "slave" is
assert(slave >= 0 && slave < ActiveThreads);
assert(master >= 0 && master < ActiveThreads);
assert(ActiveThreads > 1);
-
+
if(!Threads[slave].idle || slave == master)
return false;
return false;
}
-
+
// idle_thread_exists() tries to find an idle thread which is available as
// 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;
#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.
-
+
#if !defined(_MSC_VER)
void *init_thread(void *threadID) {
idle_loop(*(int *)threadID, NULL);
return NULL;
}
-
+
#else
DWORD WINAPI init_thread(LPVOID threadID) {
projects / stockfish / blobdiff