- // Step 12. Futility pruning (omitted at root)
- // Step 13. Make the move
- pos.do_move(move, st, ci, moveIsCheck);
-
- // Step extra. pv search
- // We do pv search for PV moves
- if (isPvMove)
- {
- // Aspiration window is disabled in multi-pv case
- if (MultiPV > 1)
- alpha = -VALUE_INFINITE;
-
- // Full depth PV search, done on first move or after a fail high
- value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, 1);
- }
- else
- {
- // Step 14. Reduced search
- // if the move fails high will be re-searched at full depth
- bool doFullDepthSearch = true;
-
- if ( depth >= 3 * ONE_PLY
- && !captureOrPromotion
- && !dangerous
- && !move_is_castle(move)
- && ss->killers[0] != move
- && ss->killers[1] != move)
- {
- ss->reduction = reduction<PV>(depth, moveCount - MultiPV + 1);
-
- if (ss->reduction)
- {
- Depth d = newDepth - ss->reduction;
- value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, d, 1);
-
- doFullDepthSearch = (value > alpha);
- }
- ss->reduction = DEPTH_ZERO; // Restore original reduction
- }
-
- // Step 15. Full depth search
- if (doFullDepthSearch)
- {
- // Full depth non-pv search using alpha as upperbound
- value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth, 1);
-
- // If we are above alpha then research at same depth but as PV
- // to get a correct score or eventually a fail high above beta.
- if (value > alpha)
- value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, 1);
- }
- }
-
- // Step 16. Undo move
- pos.undo_move(move);
-
- assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
-
- // Finished searching the move. If StopRequest is true, the search
- // was aborted because the user interrupted the search or because we
- // ran out of time. In this case, the return value of the search cannot
- // be trusted, and we break out of the loop without updating the best
- // move and/or PV.
- if (StopRequest)
- break;
-
- // Remember searched nodes counts for this move
- rm->nodes += pos.nodes_searched() - nodes;
-
- // Step 17. Check for new best move
- if (!isPvMove && value <= alpha)
- rm->pv_score = -VALUE_INFINITE;
- else
- {
- // PV move or new best move!
-
- // Update PV
- ss->bestMove = move;
- rm->pv_score = value;
- rm->extract_pv_from_tt(pos);
-
- // 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 (!isPvMove && MultiPV == 1)
- BestMoveChangesByIteration[Iteration]++;
-
- // Inform GUI that PV has changed, in case of multi-pv UCI protocol
- // requires we send all the PV lines properly sorted.
- rml.sort_multipv(moveCount);
-
- for (int j = 0; j < Min(MultiPV, (int)rml.size()); j++)
- cout << rml[j].pv_info_to_uci(pos, alpha, beta, j) << endl;
-
- // Update alpha. In multi-pv we don't use aspiration window
- if (MultiPV == 1)
- {
- // Raise alpha to setup proper non-pv search upper bound
- if (value > alpha)
- alpha = bestValue = value;
- }
- else // Set alpha equal to minimum score among the PV lines
- alpha = bestValue = rml[Min(moveCount, MultiPV) - 1].pv_score; // FIXME why moveCount?
-
- } // PV move or new best move
-
- ++rm;
-
- } // Root moves loop
-
- // Step 20. Update tables
- // If the search is not aborted, update the transposition table,
- // history counters, and killer moves.
- if (!StopRequest)
- {
- move = bestValue <= oldAlpha ? MOVE_NONE : ss->bestMove;
- vt = bestValue <= oldAlpha ? VALUE_TYPE_UPPER
- : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT;
-
- TT.store(posKey, value_to_tt(bestValue, 0), vt, depth, move, ss->eval, ss->evalMargin);
-
- // Update killers and history only for non capture moves that fails high
- if ( bestValue >= beta
- && !pos.move_is_capture_or_promotion(move))
- {
- update_history(pos, move, depth, movesSearched, moveCount);
- update_killers(move, ss->killers);
- }
- }
-
- assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
-
- return bestValue;
- }
-
-
- // search<>() is the main search function for both PV and non-PV nodes and for
- // normal and SplitPoint nodes. When called just after a split point the search
- // is 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 again. 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.
-
- template <NodeType PvNode, bool SpNode>
- Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply) {
-
- assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
- assert(beta > alpha && beta <= VALUE_INFINITE);
- assert(PvNode || alpha == beta - 1);
- assert(ply > 0 && ply < PLY_MAX);
- assert(pos.thread() >= 0 && pos.thread() < ThreadsMgr.active_threads());
-
- Move movesSearched[MOVES_MAX];
- StateInfo st;
- const TTEntry *tte;
- Key posKey;
- Move ttMove, move, excludedMove, threatMove;
- Depth ext, newDepth;
- ValueType vt;
- Value bestValue, value, oldAlpha;
- Value refinedValue, nullValue, futilityBase, futilityValueScaled; // Non-PV specific
- bool isCheck, singleEvasion, singularExtensionNode, moveIsCheck, captureOrPromotion, dangerous;
- bool mateThreat = false;
- int moveCount = 0;
- int threadID = pos.thread();
- SplitPoint* sp = NULL;
- refinedValue = bestValue = value = -VALUE_INFINITE;
- oldAlpha = alpha;
- isCheck = pos.is_check();
-
- if (SpNode)
- {
- sp = ss->sp;
- tte = NULL;
- ttMove = excludedMove = MOVE_NONE;
- threatMove = sp->threatMove;
- mateThreat = sp->mateThreat;
- goto split_point_start;
- }
- else {} // Hack to fix icc's "statement is unreachable" warning
-
- // Step 1. Initialize node and poll. Polling can abort search
- ss->currentMove = ss->bestMove = threatMove = MOVE_NONE;
- (ss+2)->killers[0] = (ss+2)->killers[1] = (ss+2)->mateKiller = MOVE_NONE;
-
- if (threadID == 0 && ++NodesSincePoll > NodesBetweenPolls)
- {
- NodesSincePoll = 0;
- poll(pos);
- }
-
- // Step 2. Check for aborted search and immediate draw
- if ( StopRequest
- || ThreadsMgr.cutoff_at_splitpoint(threadID)
- || pos.is_draw()
- || ply >= PLY_MAX - 1)
- return VALUE_DRAW;
-
- // Step 3. Mate distance pruning
- alpha = Max(value_mated_in(ply), alpha);
- beta = Min(value_mate_in(ply+1), beta);
- if (alpha >= beta)
- return alpha;
-
- // Step 4. Transposition table lookup
-
- // We don't want the score of a partial search to overwrite a previous full search
- // TT value, so we use a different position key in case of an excluded move exists.
- excludedMove = ss->excludedMove;
- posKey = excludedMove ? pos.get_exclusion_key() : pos.get_key();
-
- tte = TT.retrieve(posKey);
- ttMove = tte ? tte->move() : MOVE_NONE;
-
- // At PV nodes, we don't use the TT for pruning, but only for move ordering.
- // This is to avoid problems in the following areas:
- //
- // * Repetition draw detection
- // * Fifty move rule detection
- // * Searching for a mate
- // * Printing of full PV line
- if (!PvNode && tte && ok_to_use_TT(tte, depth, beta, ply))
- {
- TT.refresh(tte);
- ss->bestMove = ttMove; // Can be MOVE_NONE
- return value_from_tt(tte->value(), ply);
- }
-
- // Step 5. Evaluate the position statically and
- // update gain statistics of parent move.
- if (isCheck)
- ss->eval = ss->evalMargin = VALUE_NONE;
- else if (tte)
- {
- assert(tte->static_value() != VALUE_NONE);
-
- ss->eval = tte->static_value();
- ss->evalMargin = tte->static_value_margin();
- refinedValue = refine_eval(tte, ss->eval, ply);
- }
- else
- {
- refinedValue = ss->eval = evaluate(pos, ss->evalMargin);
- TT.store(posKey, VALUE_NONE, VALUE_TYPE_NONE, DEPTH_NONE, MOVE_NONE, ss->eval, ss->evalMargin);
- }
-
- // Save gain for the parent non-capture move
- update_gains(pos, (ss-1)->currentMove, (ss-1)->eval, ss->eval);