- // Don't search moves with negative SEE values
- if ( (!isCheck || evasionPrunable)
- && move != ttMove
- && !move_is_promotion(move)
- && pos.see_sign(move) < 0)
- continue;
-
- // Make and search the move
- pos.do_move(move, st, ci, moveIsCheck);
- value = -qsearch(pos, ss, -beta, -alpha, depth-OnePly, ply+1, threadID);
- pos.undo_move(move);
-
- assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
-
- // New best move?
- if (value > bestValue)
- {
- bestValue = value;
- if (value > alpha)
- {
- alpha = value;
- update_pv(ss, ply);
- }
- }
- }
-
- // All legal moves have been searched. A special case: If we're in check
- // and no legal moves were found, it is checkmate.
- if (!moveCount && pos.is_check()) // Mate!
- return value_mated_in(ply);
-
- // Update transposition table
- Depth d = (depth == Depth(0) ? Depth(0) : Depth(-1));
- if (bestValue <= oldAlpha)
- {
- // If bestValue isn't changed it means it is still the static evaluation
- // of the node, so keep this info to avoid a future evaluation() call.
- ValueType type = (bestValue == staticValue && !ei.futilityMargin[pos.side_to_move()] ? VALUE_TYPE_EV_UP : VALUE_TYPE_UPPER);
- TT.store(pos.get_key(), value_to_tt(bestValue, ply), type, d, MOVE_NONE);
- }
- else if (bestValue >= beta)
- {
- move = ss[ply].pv[ply];
- TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, d, move);
-
- // Update killers only for good checking moves
- if (!pos.move_is_capture_or_promotion(move))
- update_killers(move, ss[ply]);
- }
- else
- TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_EXACT, d, ss[ply].pv[ply]);
-
- assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
-
- return bestValue;
- }
-
-
- // sp_search() is used to search from a split point. This function is called
- // by each thread working at the split point. It is similar to the normal
- // search() function, but simpler. Because we have already probed the hash
- // table, done a null move search, and searched the first move before
- // 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(*sp->pos);
- CheckInfo ci(pos);
- SearchStack* ss = sp->sstack[threadID];
- Value value = -VALUE_INFINITE;
- Move move;
- int moveCount;
- bool isCheck = pos.is_check();
- bool useFutilityPruning = sp->depth < 7 * OnePly //FIXME: sync with search
- && !isCheck;
-
- while ( lock_grab_bool(&(sp->lock))
- && sp->bestValue < sp->beta
- && !thread_should_stop(threadID)
- && (move = sp->mp->get_next_move()) != MOVE_NONE)
- {
- moveCount = ++sp->moves;
- lock_release(&(sp->lock));
-
- assert(move_is_ok(move));
-
- bool moveIsCheck = pos.move_is_check(move, ci);
- bool captureOrPromotion = pos.move_is_capture_or_promotion(move);
-
- ss[sp->ply].currentMove = move;
-
- // Decide the new search depth
- bool dangerous;
- Depth ext = extension(pos, move, false, captureOrPromotion, moveIsCheck, false, false, &dangerous);
- Depth newDepth = sp->depth - OnePly + ext;
-
- // Prune?
- if ( useFutilityPruning
- && !dangerous
- && !captureOrPromotion)
- {
- // Move count based pruning
- if ( moveCount >= futility_move_count(sp->depth)
- && ok_to_prune(pos, move, ss[sp->ply].threatMove)
- && sp->bestValue > value_mated_in(PLY_MAX))
- continue;
-
- // Value based pruning
- Value futilityValueScaled = sp->futilityValue - moveCount * 8; //FIXME: sync with search
-
- if (futilityValueScaled < sp->beta)
- {
- if (futilityValueScaled > sp->bestValue) // Less then 1% of cases
- {
- lock_grab(&(sp->lock));
- if (futilityValueScaled > sp->bestValue)
- sp->bestValue = futilityValueScaled;
- lock_release(&(sp->lock));
- }
- continue;
- }
- }
-
- // Make and search the move.
- StateInfo st;
- 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.
- bool doFullDepthSearch = true;
-
- if ( !dangerous
- && !captureOrPromotion
- && !move_is_castle(move)
- && !move_is_killer(move, ss[sp->ply]))
- {
- ss[sp->ply].reduction = nonpv_reduction(sp->depth, moveCount);
- if (ss[sp->ply].reduction)
- {
- value = -search(pos, ss, -(sp->beta-1), newDepth-ss[sp->ply].reduction, sp->ply+1, true, threadID);
- doFullDepthSearch = (value >= sp->beta);
- }
- }
-
- if (doFullDepthSearch) // Go with full depth non-pv search
- {
- ss[sp->ply].reduction = Depth(0);
- value = -search(pos, ss, -(sp->beta - 1), newDepth, sp->ply+1, true, threadID);
- }
- pos.undo_move(move);
-
- assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
-
- if (thread_should_stop(threadID))
- {
- lock_grab(&(sp->lock));
- break;
- }
-
- // New best move?
- if (value > sp->bestValue) // Less then 2% of cases
- {
- lock_grab(&(sp->lock));
- if (value > sp->bestValue && !thread_should_stop(threadID))
- {
- sp->bestValue = value;
- if (sp->bestValue >= sp->beta)
- {
- sp_update_pv(sp->parentSstack, ss, sp->ply);
- for (int i = 0; i < ActiveThreads; i++)
- if (i != threadID && (i == sp->master || sp->slaves[i]))
- Threads[i].stop = true;
-
- sp->finished = true;
- }
- }
- lock_release(&(sp->lock));
- }
- }
-
- /* Here we have the lock still grabbed */
-
- // If this is the master thread and we have been asked to stop because of
- // a beta cutoff higher up in the tree, stop all slave threads.
- if (sp->master == threadID && thread_should_stop(threadID))
- for (int i = 0; i < ActiveThreads; i++)
- if (sp->slaves[i])
- Threads[i].stop = true;
-
- sp->cpus--;
- sp->slaves[threadID] = 0;
-
- lock_release(&(sp->lock));
- }
-
-
- // sp_search_pv() is used to search from a PV split point. This function
- // is called by each thread working at the split point. It is similar to
- // the normal search_pv() function, but simpler. Because we have already
- // probed the hash table and searched the first move before splitting, we
- // 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(*sp->pos);
- CheckInfo ci(pos);
- SearchStack* ss = sp->sstack[threadID];
- Value value = -VALUE_INFINITE;
- int moveCount;
- Move move;
-
- while ( lock_grab_bool(&(sp->lock))
- && sp->alpha < sp->beta
- && !thread_should_stop(threadID)
- && (move = sp->mp->get_next_move()) != MOVE_NONE)
- {
- moveCount = ++sp->moves;
- lock_release(&(sp->lock));
-
- assert(move_is_ok(move));
-
- bool moveIsCheck = pos.move_is_check(move, ci);
- bool captureOrPromotion = pos.move_is_capture_or_promotion(move);
-
- ss[sp->ply].currentMove = move;
-
- // Decide the new search depth
- bool dangerous;
- Depth ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, false, false, &dangerous);
- Depth newDepth = sp->depth - OnePly + ext;
-
- // Make and search the move.
- StateInfo st;
- 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.
- bool doFullDepthSearch = true;
-
- if ( !dangerous
- && !captureOrPromotion
- && !move_is_castle(move)
- && !move_is_killer(move, ss[sp->ply]))
- {
- ss[sp->ply].reduction = pv_reduction(sp->depth, moveCount);
- if (ss[sp->ply].reduction)
- {
- Value localAlpha = sp->alpha;
- value = -search(pos, ss, -localAlpha, newDepth-ss[sp->ply].reduction, sp->ply+1, true, threadID);
- doFullDepthSearch = (value > localAlpha);
- }
- }
-
- if (doFullDepthSearch) // Go with full depth non-pv search
- {
- Value localAlpha = sp->alpha;
- ss[sp->ply].reduction = Depth(0);
- value = -search(pos, ss, -localAlpha, newDepth, sp->ply+1, true, threadID);
-
- if (value > localAlpha && value < sp->beta)
- {
- // If another thread has failed high then sp->alpha has been increased
- // to be higher or equal then beta, if so, avoid to start a PV search.
- localAlpha = sp->alpha;
- if (localAlpha < sp->beta)
- value = -search_pv(pos, ss, -sp->beta, -localAlpha, newDepth, sp->ply+1, threadID);
- else
- assert(thread_should_stop(threadID));
- }
- }
- pos.undo_move(move);
-
- assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
-
- if (thread_should_stop(threadID))
- {
- lock_grab(&(sp->lock));
- break;
- }
-
- // New best move?
- if (value > sp->bestValue) // Less then 2% of cases
- {
- lock_grab(&(sp->lock));
- if (value > sp->bestValue && !thread_should_stop(threadID))
- {
- sp->bestValue = value;
- if (value > sp->alpha)
- {
- // Ask threads to stop before to modify sp->alpha
- if (value >= sp->beta)
- {
- for (int i = 0; i < ActiveThreads; i++)
- if (i != threadID && (i == sp->master || sp->slaves[i]))
- Threads[i].stop = true;
-
- sp->finished = true;
- }
-
- sp->alpha = value;
-
- sp_update_pv(sp->parentSstack, ss, sp->ply);
- if (value == value_mate_in(sp->ply + 1))
- ss[sp->ply].mateKiller = move;
- }
- }
- lock_release(&(sp->lock));
- }
- }
-
- /* Here we have the lock still grabbed */
-
- // If this is the master thread and we have been asked to stop because of
- // a beta cutoff higher up in the tree, stop all slave threads.
- if (sp->master == threadID && thread_should_stop(threadID))
- for (int i = 0; i < ActiveThreads; i++)
- if (sp->slaves[i])
- Threads[i].stop = true;
-
- sp->cpus--;
- sp->slaves[threadID] = 0;
-
- lock_release(&(sp->lock));
- }
-
- /// The BetaCounterType class
-
- BetaCounterType::BetaCounterType() { clear(); }
-
- void BetaCounterType::clear() {
-
- for (int i = 0; i < THREAD_MAX; i++)
- Threads[i].betaCutOffs[WHITE] = Threads[i].betaCutOffs[BLACK] = 0ULL;
- }
-
- void BetaCounterType::add(Color us, Depth d, int threadID) {
-
- // Weighted count based on depth
- Threads[threadID].betaCutOffs[us] += unsigned(d);
- }
-
- void BetaCounterType::read(Color us, int64_t& our, int64_t& their) {
-
- our = their = 0UL;
- for (int i = 0; i < THREAD_MAX; i++)
- {
- our += Threads[i].betaCutOffs[us];
- their += Threads[i].betaCutOffs[opposite_color(us)];
- }
- }
-
-
- /// The RootMoveList class
-
- // RootMoveList c'tor
-
- RootMoveList::RootMoveList(Position& pos, Move searchMoves[]) : count(0) {
-
- SearchStack ss[PLY_MAX_PLUS_2];
- MoveStack mlist[MaxRootMoves];
- StateInfo st;
- bool includeAllMoves = (searchMoves[0] == MOVE_NONE);
-
- // Generate all legal moves
- MoveStack* last = generate_moves(pos, mlist);
-
- // Add each move to the moves[] array
- for (MoveStack* cur = mlist; cur != last; cur++)
- {
- bool includeMove = includeAllMoves;
-
- for (int k = 0; !includeMove && searchMoves[k] != MOVE_NONE; k++)
- includeMove = (searchMoves[k] == cur->move);
-
- if (!includeMove)
- continue;
-
- // Find a quick score for the move
- init_ss_array(ss);
- pos.do_move(cur->move, st);
- moves[count].move = cur->move;
- moves[count].score = -qsearch(pos, ss, -VALUE_INFINITE, VALUE_INFINITE, Depth(0), 1, 0);
- moves[count].pv[0] = cur->move;
- moves[count].pv[1] = MOVE_NONE;
- pos.undo_move(cur->move);
- count++;
- }
- sort();
- }
-
-
- // RootMoveList simple methods definitions
-
- void RootMoveList::set_move_nodes(int moveNum, int64_t nodes) {
-
- moves[moveNum].nodes = nodes;
- moves[moveNum].cumulativeNodes += nodes;
- }
-
- 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;
- }
-
-
- // RootMoveList::sort() sorts the root move list at the beginning of a new
- // iteration.
-
- void RootMoveList::sort() {
-
- sort_multipv(count - 1); // Sort 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
- // correctly in MultiPV mode.
-
- void RootMoveList::sort_multipv(int n) {
-
- int i,j;
-
- for (i = 1; i <= n; i++)
- {
- 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
- // NodesBetweenPolls nodes, init_node() also calls poll(), which polls
- // for user input and checks whether it is time to stop the search.
-
- void init_node(SearchStack ss[], int ply, int threadID) {
-
- assert(ply >= 0 && ply < PLY_MAX);
- assert(threadID >= 0 && threadID < ActiveThreads);
-
- Threads[threadID].nodes++;