Line data Source code
1 : #include "dynamicConfig.hpp"
2 : #include "moveApply.hpp"
3 : #include "searcher.hpp"
4 :
5 1 : ScoreType Searcher::qsearchNoPruning(ScoreType alpha, ScoreType beta, const Position& p, DepthType height, DepthType& seldepth, PVList* pv) {
6 : // is updated recursively in pvs and qsearch calls but also affected to Searcher data in order to be available inside eval.
7 1 : height_ = height;
8 :
9 1 : EvalData evalData;
10 1 : ++stats.counters[Stats::sid_qnodes];
11 1 : const ScoreType evalScore = eval(p, evalData, *this);
12 :
13 1 : if (evalScore >= beta) return evalScore;
14 1 : if (evalScore > alpha) alpha = evalScore;
15 :
16 1 : const bool isInCheck = isPosInCheck(p);
17 1 : ScoreType bestScore = isInCheck ? matedScore(height) : evalScore;
18 :
19 : CMHPtrArray cmhPtr;
20 1 : getCMHPtr(p.halfmoves, cmhPtr);
21 :
22 1 : MoveList moves;
23 : //if ( isInCheck ) MoveGen::generate<MoveGen::GP_all>(p,moves); ///@todo generate only evasion !
24 1 : /*else*/ MoveGen::generate<MoveGen::GP_cap>(p, moves);
25 1 : MoveSorter::scoreAndSort(*this, moves, p, evalData.gp, height, cmhPtr, false, isInCheck);
26 :
27 1 : for (const auto & it : moves) {
28 0 : Position p2 = p;
29 0 : const MoveInfo moveInfo(p2,it);
30 0 : if (!applyMove(p2, moveInfo, true)) continue;
31 : #ifdef WITH_NNUE
32 0 : NNUEEvaluator newEvaluator = p.evaluator();
33 : p2.associateEvaluator(newEvaluator);
34 0 : applyMoveNNUEUpdate(p2, moveInfo);
35 : #endif
36 0 : PVList childPV;
37 0 : const ScoreType score = -qsearchNoPruning(-beta, -alpha, p2, height + 1, seldepth, pv ? &childPV : nullptr);
38 0 : if (score > bestScore) {
39 : bestScore = score;
40 0 : if (score > alpha) {
41 0 : if (pv) updatePV(*pv, it, childPV);
42 0 : if (score >= beta) return score;
43 : alpha = score;
44 : }
45 : }
46 0 : }
47 : return bestScore;
48 : }
49 :
50 : FORCE_FINLINE ScoreType bestCapture(const Position &p){
51 : return p.pieces_const(~p.c,P_wq) ? value(P_wq) : value(P_wr);
52 : /*p.pieces_const(~p.c,P_wr) ? value(P_wr) :
53 : p.pieces_const(~p.c,P_wb) ? value(P_wb) :
54 : p.pieces_const(~p.c,P_wn) ? value(P_wn) :
55 : p.pieces_const(~p.c,P_wp) ? value(P_wp) : 0;*/
56 : }
57 :
58 : FORCE_FINLINE ScoreType qDeltaMargin(const Position& p) {
59 : const ScoreType delta = (p.pieces_const(p.c, P_wp) & BB::seventhRank[p.c]) ? value(P_wq) : value(P_wp);
60 : return delta + bestCapture(p);
61 : }
62 :
63 3116925 : ScoreType Searcher::qsearch(ScoreType alpha,
64 : ScoreType beta,
65 : const Position& p,
66 : DepthType height,
67 : DepthType& seldepth,
68 : DepthType qply,
69 : bool qRoot,
70 : bool pvnode,
71 : int8_t isInCheckHint) {
72 :
73 : ///@todo more validation !!
74 3116925 : assert(p.halfmoves - 1 < MAX_PLY && p.halfmoves - 1 >= 0);
75 :
76 : // is updated recursively in pvs and qsearch calls but also affected to Searcher data in order to be available inside eval.
77 3116925 : height_ = height;
78 :
79 : // some evaluation are used inside search
80 3116925 : EvalData evalData;
81 :
82 : // we cannot search deeper than MAX_DEPTH, if so just return static evaluation in this case
83 3116925 : if (height >= MAX_DEPTH - 1 ) return eval(p, evalData, *this);
84 :
85 : // no time verification in qsearch, too slow
86 3116925 : if (stopFlag) return STOPSCORE;
87 :
88 : // update nodes count as soon as we enter a node
89 3116924 : ++stats.counters[Stats::sid_qnodes];
90 : //std::cout << GetFEN(p) << std::endl;
91 :
92 3116924 : alpha = std::max(alpha, matedScore(height));
93 3116924 : beta = std::min(beta, matingScore(height + 1));
94 3116924 : if (alpha >= beta) return alpha;
95 :
96 : // update selective depth
97 3116794 : seldepth = std::max(seldepth,height);
98 :
99 : Move bestMove = INVALIDMOVE;
100 :
101 3116794 : debug_king_cap(p);
102 :
103 : // probe TT
104 : TT::Entry e;
105 3116794 : const Hash pHash = computeHash(p);
106 3116794 : const bool ttDepthOk = TT::getEntry(*this, p, pHash, -2, e);
107 3116794 : const TT::Bound bound = static_cast<TT::Bound>(e.b & ~TT::B_allFlags);
108 3116794 : const bool ttHit = e.h != nullHash;
109 3116794 : const bool validTTmove = ttHit && e.m != INVALIDMINIMOVE;
110 3116794 : const bool ttPV = pvnode || (validTTmove && (e.b & TT::B_ttPVFlag));
111 405761 : const bool ttIsInCheck = validTTmove && (e.b & TT::B_isInCheckFlag);
112 3234579 : const bool isInCheck = isInCheckHint != -1 ? isInCheckHint : ttIsInCheck || isPosInCheck(p);;
113 3116794 : const bool specialQSearch = isInCheck || qRoot;
114 3116794 : const DepthType hashDepth = specialQSearch ? 0 : -1;
115 :
116 : // if depth of TT entry is enough
117 3116794 : if (ttDepthOk && e.d >= hashDepth) {
118 : // if not at a pvnode, we verify bound and not shuffling with quiet moves
119 : // in this case we can "safely" return hash score
120 452992 : if (!pvnode && p.fifty < SearchConfig::ttMaxFiftyValideDepth && ((bound == TT::B_alpha && e.s <= alpha) || (bound == TT::B_beta && e.s >= beta) || (bound == TT::B_exact))) {
121 391715 : return TT::adjustHashScore(e.s, height);
122 : }
123 : }
124 :
125 : // set TT move as current best, this allows to re-insert it in pv in case there is no capture, or no move incrases alpha
126 2725079 : const bool usableTTmove = validTTmove && (isInCheck || isCapture(e.m));
127 56042 : if (usableTTmove) bestMove = e.m;
128 :
129 : // get a static score for that position.
130 : ScoreType evalScore;
131 : // do not eval position when in check, we won't use it (won't forward prune)
132 2725079 : if (isInCheck){
133 : evalScore = matedScore(height);
134 : stats.incr(Stats::sid_qsearchInCheck);
135 : }
136 : // skip eval if nullmove just applied, we can hack using opposite of opponent score corrected by tempo
137 : // But this may don't work well with (a too) asymetric HalfKA NNUE
138 2370562 : else if (!DynamicConfig::useNNUE && p.lastMove == NULLMOVE && height > 0){
139 0 : evalScore = 2 * EvalConfig::tempo - stack[p.halfmoves - 1].eval;
140 : #ifdef DEBUG_STATICEVAL
141 : checkEval(p,evalScore,*this,"null move trick (qsearch)");
142 : #endif
143 : stats.incr(Stats::sid_qEvalNullMoveTrick);
144 : }
145 : else {
146 : // if we had a TT hit (with or without associated move), we can use its eval instead of calling eval()
147 2370562 : if (ttHit) {
148 : stats.incr(Stats::sid_ttschits);
149 579632 : evalScore = e.e;
150 : #ifdef DEBUG_STATICEVAL
151 : checkEval(p,evalScore,*this,"from TT (qsearch)");
152 : #endif
153 : // in this case we force mid game value in sorting ...
154 : // anyway, this affects only quiet move sorting, so here only for check evasion ...
155 579632 : evalData.gp = 0.5;
156 : }
157 : else {
158 : // we tried everthing ... now this position must be evaluated
159 : stats.incr(Stats::sid_ttscmiss);
160 1790930 : evalScore = eval(p, evalData, *this);
161 : #ifdef DEBUG_STATICEVAL
162 : checkEval(p,evalScore,*this,"from eval (qsearch)");
163 : #endif
164 : }
165 : }
166 : // backup this score as the "static" one
167 : const ScoreType staticScore = evalScore;
168 :
169 2725079 : if (!isInCheck && !ttHit){
170 : // Be carefull here, _data in Entry is always (INVALIDMOVE,B_none,-2) here, so that collisions are a lot more likely
171 : // depth -2 is used to ensure this will never be used directly (only evaluation score is of interest here...)
172 1790930 : TT::setEntry(*this, pHash, INVALIDMOVE, TT::createHashScore(staticScore, height), TT::createHashScore(staticScore, height), TT::B_none, -2, isMainThread());
173 : }
174 :
175 : // early cut-off based on staticScore score
176 2725079 : if (staticScore >= beta) return staticScore;
177 1290370 : else if (staticScore > alpha) alpha = staticScore;
178 :
179 : // maybe we can use tt score (instead of static evaluation) as a better draft if possible and not in check ?
180 : bool evalScoreIsHashScore = false;
181 :
182 1290370 : if (!isInCheck) {
183 935853 : if (ttHit && ((bound == TT::B_alpha && e.s <= evalScore) || (bound == TT::B_beta && e.s >= evalScore) || (bound == TT::B_exact))){
184 53286 : evalScore = TT::adjustHashScore(e.s, height);
185 : evalScoreIsHashScore = true;
186 : }
187 : }
188 :
189 : TT::Bound b = TT::B_alpha;
190 : ScoreType bestScore = evalScore;
191 1290370 : const ScoreType alphaInit = alpha;
192 : int validMoveCount = 0;
193 :
194 : // we try the tt move before move generation
195 1290370 : if (usableTTmove) {
196 46207 : Position p2 = p;
197 46207 : if (const MoveInfo moveInfo(p2,e.m); applyMove(p2, moveInfo, true)) {
198 : #ifdef WITH_NNUE
199 46207 : NNUEEvaluator newEvaluator = p.evaluator();
200 : p2.associateEvaluator(newEvaluator);
201 46207 : applyMoveNNUEUpdate(p2, moveInfo);
202 : #endif
203 : ++validMoveCount;
204 : //stack[p2.halfmoves].p = p2; ///@todo another expensive copy !!!!
205 : //stack[p2.halfmoves].h = p2.h;
206 46207 : TT::prefetch(computeHash(p2));
207 46207 : const ScoreType score = -qsearch(-beta, -alpha, p2, height + 1, seldepth, isInCheck ? 0 : qply + 1, false, false);
208 46207 : if (score > bestScore) {
209 28628 : bestMove = e.m;
210 : bestScore = score;
211 28628 : if (score > alpha) {
212 7545 : if (score >= beta) {
213 : b = TT::B_beta;
214 : stats.incr(Stats::sid_qttbeta);
215 6989 : TT::setEntry(*this, pHash, bestMove, TT::createHashScore(bestScore, height), TT::createHashScore(evalScore, height),
216 6989 : static_cast<TT::Bound>(b |
217 13978 : (ttPV ? TT::B_ttPVFlag : TT::B_none) |
218 6989 : (isInCheck ? TT::B_isInCheckFlag : TT::B_none)),
219 : hashDepth,
220 6989 : isMainThread());
221 6989 : return bestScore;
222 : }
223 : b = TT::B_exact;
224 556 : alpha = score;
225 : stats.incr(Stats::sid_qttalpha);
226 : }
227 : }
228 : }
229 46207 : }
230 :
231 : // generate move list
232 1283381 : MoveList moves;
233 1283381 : if (isInCheck) MoveGen::generate<MoveGen::GP_evasion>(p, moves);
234 : else
235 931152 : MoveGen::generate<MoveGen::GP_cap>(p, moves); ///@todo generate only recapture if qly > 5
236 :
237 : //std::cout << "=========================" << std::endl;
238 : //std::cout << ToString(p) << std::endl;
239 : CMHPtrArray cmhPtr;
240 1283381 : getCMHPtr(p.halfmoves, cmhPtr);
241 :
242 : #ifdef USE_PARTIAL_SORT
243 2517469 : MoveSorter ms(*this, p, evalData.gp, height, cmhPtr, false, isInCheck, validTTmove ? &e : nullptr); ///@todo warning gp is often = 0.5 here !
244 1283381 : ms.score(moves);
245 1283381 : size_t offset = 0;
246 : const Move* it = nullptr;
247 3152182 : while ((it = ms.pickNext/*Lazy*/(moves, offset, false/*, SearchConfig::lazySortThresholdQS*/))) {
248 : #else
249 : MoveSorter::scoreAndSort(*this, moves, p, evalData.gp, height, cmhPtr, false, isInCheck,
250 : validTTmove ? &e : nullptr); ///@todo warning gp is often = 0.5 here !
251 : for (auto it = moves.begin(); it != moves.end(); ++it) {
252 : #endif
253 3520535 : if (validTTmove && sameMove(e.m, *it)) continue; // already tried
254 2292284 : if (!isInCheck) {
255 1522198 : if (qply > 5){
256 309 : const Square recapture = (isValidMove(p.lastMove) && isCapture(p.lastMove)) ? Move2To(p.lastMove) : INVALIDSQUARE;
257 309 : if (recapture != INVALIDSQUARE && Move2To(*it) != recapture) continue; // only recapture now ...
258 : }
259 : if (SearchConfig::doQFutility && validMoveCount &&
260 : staticScore + SearchConfig::qfutilityMargin[evalScoreIsHashScore]
261 : + (isPromotionCap(*it) ? (value(P_wq) - value(P_wp)) : 0)
262 : + (Move2Type(*it) == T_ep ? value(P_wp) : PieceTools::getAbsValue(p, Move2To(*it))) <= alphaInit) {
263 : stats.incr(Stats::sid_qfutility);
264 : continue;
265 : }
266 1521953 : const ScoreType seeValue = SEE(p,*it);
267 : // prune all bad captures
268 1521953 : if (seeValue < SearchConfig::seeQThreshold) {
269 : stats.incr(Stats::sid_qsee);
270 803825 : continue;
271 : }
272 : // neutral captures are pruned if move can't raise alpha (idea origin from Seer)
273 718128 : if (SearchConfig::doQDeltaPruning && !ttPV
274 717039 : && seeValue <= SearchConfig::deltaBadSEEThreshold && staticScore + SearchConfig::deltaBadMargin < alpha){
275 : stats.incr(Stats::sid_deltaAlpha);
276 141759 : continue;
277 : }
278 : // return beta early if a good capture sequence is found and static eval was not far from beta (idea origin from Seer)
279 : if (SearchConfig::doQDeltaPruning && !ttPV
280 575280 : && seeValue >= SearchConfig::deltaGoodSEEThreshold && staticScore + SearchConfig::deltaGoodMargin > beta){
281 : stats.incr(Stats::sid_deltaBeta);
282 15525 : return beta;
283 : }
284 : }
285 1330930 : Position p2 = p;
286 1330930 : const MoveInfo moveInfo(p2,*it);
287 1330930 : if (!applyMove(p2, moveInfo, true)) continue;
288 : // prefetch as soon as possible
289 1087726 : TT::prefetch(computeHash(p2));
290 1087726 : ++validMoveCount;
291 : #ifdef WITH_NNUE
292 1087726 : NNUEEvaluator newEvaluator = p.evaluator();
293 : p2.associateEvaluator(newEvaluator);
294 1087726 : applyMoveNNUEUpdate(p2, moveInfo);
295 : #endif
296 : //stack[p2.halfmoves].p = p2;
297 : //stack[p2.halfmoves].h = p2.h;
298 1087726 : const ScoreType score = -qsearch(-beta, -alpha, p2, height + 1, seldepth, isInCheck ? 0 : qply + 1, false, false);
299 1087726 : if (score > bestScore) {
300 810097 : bestMove = *it;
301 : bestScore = score;
302 810097 : if (score > alpha) {
303 447611 : if (score >= beta) {
304 : b = TT::B_beta;
305 : stats.incr(Stats::sid_qbeta);
306 : break;
307 : }
308 : b = TT::B_exact;
309 435 : alpha = score;
310 : stats.incr(Stats::sid_qalpha);
311 : }
312 : }
313 1330930 : }
314 :
315 1267856 : if (alphaInit == alpha ) stats.incr(Stats::sid_qalphanoupdate);
316 :
317 1267856 : if (validMoveCount == 0 && isInCheck) bestScore = matedScore(height);
318 1265060 : else if (is50moves(p,false)) return drawScore(p, height); // post move loop version
319 :
320 1267856 : TT::setEntry(*this, pHash, bestMove, TT::createHashScore(bestScore, height), TT::createHashScore(evalScore, height),
321 1267856 : static_cast<TT::Bound>(b |
322 2535712 : (ttPV ? TT::B_ttPVFlag : TT::B_none) |
323 1267856 : (isInCheck ? TT::B_isInCheckFlag : TT::B_none)),
324 : hashDepth,
325 1267856 : isMainThread());
326 :
327 : return bestScore;
328 : }
|
