Line data Source code
1 : #pragma once
2 :
3 : #include "definition.hpp"
4 : #include "distributed.h"
5 : #include "dynamicConfig.hpp"
6 : #include "egt.hpp"
7 : #include "evalConfig.hpp"
8 : #include "evalTools.hpp"
9 : #include "moveApply.hpp"
10 : #include "moveGen.hpp"
11 : #include "movePseudoLegal.hpp"
12 : #include "moveSort.hpp"
13 : #include "positionTools.hpp"
14 : #include "searchConfig.hpp"
15 : #include "timeMan.hpp"
16 : #include "tools.hpp"
17 : #include "transposition.hpp"
18 :
19 : #define PERIODICCHECK uint64_t(1024)
20 :
21 : // be carefull isBadCap shall only be used on moves already detected as capture !
22 400989 : [[nodiscard]] inline bool isBadCap(const Move m) { return badCapScore(m) < DynamicConfig::badCapLimit; }
23 :
24 : FORCE_FINLINE void Searcher::updateStatBetaCut(const Position & p, const Move m, const DepthType height){
25 : const MType t = Move2Type(m);
26 : assert(isValidMoveType(t));
27 :
28 : if (isCapture(t) && !isPromotion(t)) {
29 : if(isBadCap(m)) stats.incr(Stats::sid_beta_bc);
30 : else stats.incr(Stats::sid_beta_gc);
31 : }
32 : else if (isPromotion(t)){
33 : stats.incr(Stats::sid_beta_p);
34 : }
35 : else if (t == T_std || isCastling(m)) {
36 : if (sameMove(m, killerT.killers[height][0])) stats.incr(Stats::sid_beta_k1);
37 : else if (sameMove(m, killerT.killers[height][1])) stats.incr(Stats::sid_beta_k2);
38 : else if (height > 1 && sameMove(m, killerT.killers[height - 2][0])) stats.incr(Stats::sid_beta_k3);
39 : else if (height > 1 && sameMove(m, killerT.killers[height - 2][1])) stats.incr(Stats::sid_beta_k4);
40 : else if (isValidMove(p.lastMove) && sameMove(counterT.counter[Move2From(p.lastMove)][correctedMove2ToKingDest(p.lastMove)], m)) stats.incr(Stats::sid_beta_c);
41 : else stats.incr(Stats::sid_beta_q);
42 : }
43 : else{
44 : assert(false);
45 : }
46 : }
47 :
48 : FORCE_FINLINE std::tuple<DepthType, DepthType, DepthType>
49 : Searcher::depthPolicy( [[maybe_unused]] const Position & p,
50 : [[maybe_unused]] DepthType depth,
51 : [[maybe_unused]] DepthType height,
52 : [[maybe_unused]] Move m,
53 : [[maybe_unused]] const PVSData & pvsData,
54 : [[maybe_unused]] const EvalData & evalData,
55 : [[maybe_unused]] ScoreType evalScore,
56 : [[maybe_unused]] DepthType extensions,
57 : [[maybe_unused]] bool isReductible) const{
58 :
59 : // Extension toggles.
60 : constexpr bool enableCheckQuietExtension = false;
61 : constexpr bool enableInCheckExtension = false;
62 : constexpr bool enableBMExtension = false;
63 : constexpr bool enableMateThreatExtension = false;
64 : constexpr bool enableQueenThreatExtension = false;
65 : constexpr bool enableCastlingExtension = false;
66 : constexpr bool enableRecaptureExtension = false;
67 : constexpr bool enableGoodHistoryExtension = false;
68 : constexpr bool enableCMHExtension = false;
69 :
70 : int extension = 0;
71 :
72 : const auto tryExtension = [&](const bool condition, const Stats::StatId statId){
73 : if (extension == 0 && condition) {
74 : stats.incr(statId);
75 : ++extension;
76 : }
77 : };
78 :
79 : if (!pvsData.validTTmove){
80 : if constexpr (enableCheckQuietExtension) {
81 : // correspond to first move (not being the TT one) or quiet with very good score (like killers)
82 : const bool weakEarlyMove = pvsData.earlyMove || (pvsData.isQuiet && Move2Score(m) >= HISTORY_MAX);
83 : tryExtension(weakEarlyMove && pvsData.isCheck, Stats::sid_checkExtension2);
84 : }
85 : if constexpr (enableInCheckExtension) {
86 : tryExtension(pvsData.earlyMove && pvsData.isInCheck, Stats::sid_checkExtension);
87 : }
88 : if constexpr (enableBMExtension) {
89 : tryExtension(pvsData.BMextension, Stats::sid_BMExtension);
90 : }
91 : if constexpr (enableMateThreatExtension) {
92 : tryExtension(pvsData.earlyMove && pvsData.mateThreat, Stats::sid_mateThreatExtension);
93 : }
94 : if constexpr (enableQueenThreatExtension) {
95 : tryExtension(pvsData.earlyMove &&
96 : p.pieces_const<P_wq>(p.c) &&
97 : pvsData.isQuiet && PieceTools::getPieceType(p, Move2From(m)) == P_wq &&
98 : isAttacked(p, BBTools::SquareFromBitBoard(p.pieces_const<P_wq>(p.c))) &&
99 : SEE_GE(p, m, -80),
100 : Stats::sid_queenThreatExtension);
101 : }
102 : if constexpr (enableCastlingExtension) {
103 : tryExtension(isCastling(m), Stats::sid_castlingExtension);
104 : }
105 : if constexpr (enableRecaptureExtension) {
106 : tryExtension(isValidMove(p.lastMove) &&
107 : Move2Type(p.lastMove) == T_capture &&
108 : !isBadCap(m) &&
109 : correctedMove2ToKingDest(m) == correctedMove2ToKingDest(p.lastMove),
110 : Stats::sid_recaptureExtension);
111 : }
112 : if constexpr (enableGoodHistoryExtension) {
113 : tryExtension(pvsData.isQuiet &&
114 : Move2Score(m) <= HISTORY_MAX &&
115 : Move2Score(m) > SearchConfig::historyExtensionThreshold,
116 : Stats::sid_goodHistoryExtension);
117 : }
118 : if constexpr (enableCMHExtension) {
119 : tryExtension(pvsData.isQuiet &&
120 : isCMHGood(p, Move2From(m), correctedMove2ToKingDest(m), pvsData.cmhPtr, 3 * HISTORY_MAX / 4),
121 : Stats::sid_CMHExtension);
122 : }
123 : }
124 :
125 : // Reduction toggles
126 : constexpr bool enableThreadBaseReduction = false;
127 : constexpr bool enableAggressiveRandomReduction = false;
128 : constexpr bool enableMobilityBasedReduction = false;
129 : constexpr bool enableReduceLessWhenInCheck = false;
130 : constexpr bool enableReduceLessWhenGivingCheck = false;
131 : constexpr bool enableReduceLessAtPVNode = false;
132 : constexpr bool enableReduceLessAfterAlphaUpdateAll = false;
133 : constexpr bool enableReduceLessOnSingularTT = false;
134 : constexpr bool enableReduceLessOnTheirTurn = false;
135 : constexpr bool enableReduceLessOnEmergencyDefence = false;
136 : constexpr bool enableReduceLessOnAdvancedPawnPush = false;
137 :
138 : constexpr bool enableCaptureBadCapExtraReduction = true;
139 : constexpr bool enableCaptureReduceLessIfTTMoveIsCap = false;
140 : constexpr bool enableCaptureReduceLessOnFormerPV = false;
141 : constexpr bool enableCaptureReduceLessOnAdvancedPawn = false;
142 :
143 : constexpr bool enableStdBaseLMRReduction = true;
144 : constexpr bool enableStdNotImprovingReduction = true;
145 : constexpr bool enableStdTTMoveIsCaptureReduction = true;
146 : constexpr bool enableStdFailHighReduction = true;
147 : constexpr bool enableStdHistoryReduction = true;
148 : constexpr bool enableStdFormerPVPrudence = true;
149 : constexpr bool enableStdKnownEndgamePrudence = true;
150 :
151 : constexpr bool enableCapBaseLMRReduction = true;
152 : constexpr bool enableCapHistoryReduction = true;
153 : constexpr bool enableCapPVNodePrudence = true;
154 : constexpr bool enableCapImprovingPrudence = true;
155 :
156 : int reduction = 0;
157 :
158 3318687 : if (isReductible) {
159 2978679 : const int depthIdx = std::min(static_cast<int>(depth), MAX_DEPTH - 1);
160 :
161 2978679 : if (Move2Type(m) == T_std){
162 : stats.incr(Stats::sid_lmr);
163 :
164 : const int threadReductionIdx = 0;
165 2581778 : const int moveIdx = std::min(pvsData.validMoveCount + threadReductionIdx, MAX_MOVE - 1);
166 :
167 : if constexpr (enableStdBaseLMRReduction) {
168 2581778 : reduction += SearchConfig::lmrReduction[depthIdx][moveIdx];
169 : }
170 : if constexpr (enableStdNotImprovingReduction) {
171 2581778 : reduction += static_cast<int>(!pvsData.improving);
172 : }
173 : if constexpr (enableStdTTMoveIsCaptureReduction) {
174 2581778 : reduction += static_cast<int>(pvsData.ttMoveIsCapture);
175 : }
176 :
177 : if constexpr (enableStdFailHighReduction) {
178 2581778 : const bool likelyFailHigh = pvsData.cutNode &&
179 1450704 : evalScore - SearchConfig::failHighReductionCoeff.threshold(
180 725352 : pvsData.marginDepth, evalData.gp, pvsData.evalScoreIsHashScore, pvsData.improving) > pvsData.beta;
181 2581778 : reduction += static_cast<int>(likelyFailHigh);
182 : }
183 :
184 : if constexpr (enableStdHistoryReduction) {
185 2581778 : const int hScore = HISTORY_DIV(2 * Move2Score(m));
186 2581778 : reduction -= std::min(3, hScore);
187 : }
188 :
189 : if constexpr (enableThreadBaseReduction) {
190 : reduction += static_cast<int>(id() % 2);
191 : }
192 :
193 : if constexpr (enableAggressiveRandomReduction) {
194 : constexpr int randomAggressiveReductionFactor = 0;
195 : const ScoreType randomShot = (stats.counters[Stats::sid_nodes] + stats.counters[Stats::sid_qnodes]) % 128;
196 : if (randomShot > 128 -
197 : randomAggressiveReductionFactor * pvsData.validQuietMoveCount) {
198 : stats.incr(Stats::sid_lmrAR);
199 : ++reduction;
200 : }
201 : }
202 :
203 : if constexpr (enableMobilityBasedReduction) {
204 : if (!pvsData.isInCheck) {
205 : const int16_t mobilityBalance = evalData.mobility[~p.c] - evalData.mobility[p.c];
206 : reduction += static_cast<int>(mobilityBalance / 16 < 0);
207 : }
208 : }
209 :
210 : if constexpr (enableReduceLessWhenInCheck) {
211 : reduction -= static_cast<int>(pvsData.isInCheck);
212 : }
213 : if constexpr (enableReduceLessWhenGivingCheck) {
214 : reduction -= static_cast<int>(pvsData.isCheck);
215 : }
216 :
217 : if constexpr (enableStdFormerPVPrudence) {
218 2581778 : reduction -= static_cast<int>(pvsData.formerPV || pvsData.ttPV);
219 : }
220 :
221 : if constexpr (enableReduceLessAtPVNode) {
222 : reduction -= static_cast<int>(pvsData.pvnode);
223 : }
224 : if constexpr (enableReduceLessAfterAlphaUpdateAll) {
225 : reduction -= static_cast<int>(!pvsData.cutNode && pvsData.alphaUpdated);
226 : }
227 : if constexpr (enableReduceLessOnSingularTT) {
228 : reduction -= static_cast<int>(pvsData.ttMoveSingularExt);
229 : }
230 : if constexpr (enableReduceLessOnTheirTurn) {
231 : reduction -= static_cast<int>(pvsData.theirTurn);
232 : }
233 : if constexpr (enableReduceLessOnEmergencyDefence) {
234 : reduction -= static_cast<int>(pvsData.isEmergencyDefence);
235 : }
236 :
237 : if constexpr (enableStdKnownEndgamePrudence) {
238 2581778 : reduction -= static_cast<int>(pvsData.isKnownEndGame);
239 : }
240 :
241 : if constexpr (enableReduceLessOnAdvancedPawnPush) {
242 : reduction -= static_cast<int>(2 * pvsData.isAdvancedPawnPush);
243 : }
244 : }
245 396901 : else if (Move2Type(m) == T_capture){
246 : stats.incr(Stats::sid_lmrcap);
247 :
248 : if constexpr (enableCapBaseLMRReduction) {
249 395554 : const int moveIdx = std::min(static_cast<int>(pvsData.validMoveCount), MAX_MOVE - 1);
250 395554 : reduction += SearchConfig::lmrReduction[depthIdx][moveIdx];
251 : }
252 :
253 : if constexpr (enableCapHistoryReduction) {
254 395554 : const Square to = Move2To(m); // ok this is a std capture (no ep)
255 791108 : const int hScore = HISTORY_DIV(SearchConfig::lmrCapHistoryFactor *
256 395554 : historyT.historyCap[PieceIdx(p.board_const(Move2From(m)))][to][Abs(p.board_const(to)) - 1]);
257 825832 : reduction -= std::max(-2, std::min(2, hScore));
258 : }
259 :
260 : if constexpr (enableCaptureBadCapExtraReduction) {
261 395554 : reduction += static_cast<int>(isBadCap(m) && reduction > 1);
262 : }
263 :
264 : if constexpr (enableCapPVNodePrudence) {
265 395554 : reduction -= static_cast<int>(pvsData.pvnode);
266 : }
267 :
268 : if constexpr (enableCaptureReduceLessIfTTMoveIsCap) {
269 : reduction -= static_cast<int>(pvsData.ttMoveIsCapture);
270 : }
271 : if constexpr (enableCaptureReduceLessOnFormerPV) {
272 : reduction -= static_cast<int>(pvsData.formerPV || pvsData.ttPV);
273 : }
274 :
275 : if constexpr (enableCapImprovingPrudence) {
276 395554 : reduction -= static_cast<int>(pvsData.improving);
277 : }
278 :
279 : if constexpr (enableCaptureReduceLessOnAdvancedPawn) {
280 : reduction -= static_cast<int>(2 * pvsData.isAdvancedPawnPush);
281 : }
282 : }
283 :
284 : // never extend more than reduce (to avoid search explosion)
285 : // except for first move when no TT hit where a +1 extension is possible
286 2978679 : if (extension - reduction > 0) reduction = extension;
287 : // clamp to depth = 0
288 2978679 : if (static_cast<int>(depth) - 1 + extension - reduction <= 0) reduction = static_cast<int>(depth) - 1 + extension;
289 : }
290 :
291 4123755 : const DepthType nextDepth = static_cast<DepthType>(static_cast<int>(depth) - 1 + extension - reduction);
292 :
293 3318687 : return {nextDepth, static_cast<DepthType>(extension), static_cast<DepthType>(reduction)};
294 : }
295 :
296 : #pragma GCC diagnostic push
297 : #pragma GCC diagnostic ignored "-Wconversion"
298 :
299 : FORCE_FINLINE void evalFeatures(const Position & p,
300 : array2d<BitBoard,2,6> & attFromPiece,
301 : colored<BitBoard> & att,
302 : colored<BitBoard> & att2,
303 : array2d<BitBoard,2,6> & checkers,
304 : colored<ScoreType> & kdanger,
305 : EvalScore & mobilityScore,
306 : colored<uint16_t> & mobility){
307 :
308 : const bool kingIsMandatory = DynamicConfig::isKingMandatory();
309 : const colored<BitBoard> pawns = {p.whitePawn(), p.blackPawn()};
310 2366863 : const colored<BitBoard> nonPawnMat = {p.allPieces[Co_White] & ~pawns[Co_White],
311 2366863 : p.allPieces[Co_Black] & ~pawns[Co_Black]};
312 2366863 : const colored<BitBoard> kingZone = {isValidSquare(p.king[Co_White]) ? BBTools::mask[p.king[Co_White]].kingZone : emptyBitBoard,
313 2366863 : isValidSquare(p.king[Co_Black]) ? BBTools::mask[p.king[Co_Black]].kingZone : emptyBitBoard};
314 2366863 : const BitBoard occupancy = p.occupancy();
315 :
316 7100589 : for (Color c = Co_White ; c <= Co_Black ; ++c){
317 33136082 : for (Piece pp = P_wp ; pp <= P_wk ; ++pp){
318 56804712 : BB::applyOn(p.pieces_const(c,pp), [&](const Square & k) {
319 : // aligned threats removing own piece (not pawn) in occupancy
320 44770503 : const BitBoard shadowTarget = BBTools::pfCoverage[pp - 1](k, occupancy ^ nonPawnMat[c], c);
321 44770503 : if (shadowTarget) {
322 44770503 : kdanger[~c] += BB::countBit(shadowTarget & kingZone[~c]) * EvalConfig::kingAttWeight[EvalConfig::katt_attack][pp - 1];
323 44770503 : const BitBoard target = BBTools::pfCoverage[pp - 1](k, occupancy, c); // real targets
324 44770503 : if (target) {
325 44770503 : attFromPiece[c][pp - 1] |= target;
326 44770503 : att2[c] |= att[c] & target;
327 44770503 : att[c] |= target;
328 44770503 : if (target & p.pieces_const<P_wk>(~c)) checkers[c][pp - 1] |= SquareToBitboard(k);
329 44770503 : kdanger[c] -= BB::countBit(target & kingZone[c]) * EvalConfig::kingAttWeight[EvalConfig::katt_defence][pp - 1];
330 : }
331 : }
332 44770503 : });
333 : }
334 : }
335 :
336 2366863 : if (kingIsMandatory){
337 2366863 : const File wkf = SQFILE(p.king[Co_White]);
338 2366863 : const File bkf = SQFILE(p.king[Co_Black]);
339 :
340 2366863 : const colored<BitBoard> semiOpenFiles = {BBTools::fillFile(pawns[Co_White]) & ~BBTools::fillFile(pawns[Co_Black]),
341 2366863 : BBTools::fillFile(pawns[Co_Black]) & ~BBTools::fillFile(pawns[Co_White])};
342 2366863 : const BitBoard openFiles = BBTools::openFiles(pawns[Co_White], pawns[Co_Black]);
343 :
344 2366863 : kdanger[Co_White] += EvalConfig::kingAttOpenfile * BB::countBit(BB::kingFlank[wkf] & openFiles) / 8;
345 2366863 : kdanger[Co_White] += EvalConfig::kingAttSemiOpenfileOpp * BB::countBit(BB::kingFlank[wkf] & semiOpenFiles[Co_White]) / 8;
346 2366863 : kdanger[Co_White] += EvalConfig::kingAttSemiOpenfileOur * BB::countBit(BB::kingFlank[wkf] & semiOpenFiles[Co_Black]) / 8;
347 2366863 : kdanger[Co_Black] += EvalConfig::kingAttOpenfile * BB::countBit(BB::kingFlank[bkf] & openFiles) / 8;
348 2366863 : kdanger[Co_Black] += EvalConfig::kingAttSemiOpenfileOpp * BB::countBit(BB::kingFlank[bkf] & semiOpenFiles[Co_Black]) / 8;
349 2366863 : kdanger[Co_Black] += EvalConfig::kingAttSemiOpenfileOur * BB::countBit(BB::kingFlank[bkf] & semiOpenFiles[Co_White]) / 8;
350 : }
351 :
352 2366863 : const colored<BitBoard> weakSquare = { att[Co_Black] & ~att2[Co_White] & (~att[Co_White] | attFromPiece[Co_White][P_wk - 1] | attFromPiece[Co_White][P_wq - 1]),
353 2366863 : att[Co_White] & ~att2[Co_Black] & (~att[Co_Black] | attFromPiece[Co_Black][P_wk - 1] | attFromPiece[Co_Black][P_wq - 1])};
354 :
355 2366863 : const colored<BitBoard> safeSquare = { ~att[Co_Black] | (weakSquare[Co_Black] & att2[Co_White]),
356 2366863 : ~att[Co_White] | (weakSquare[Co_White] & att2[Co_Black])};
357 :
358 : // reward safe checks
359 2366863 : kdanger[Co_White] += EvalConfig::kingAttSafeCheck[0] * BB::countBit(checkers[Co_Black][0] & att[Co_Black]);
360 2366863 : kdanger[Co_Black] += EvalConfig::kingAttSafeCheck[0] * BB::countBit(checkers[Co_White][0] & att[Co_White]);
361 11834315 : for (Piece pp = P_wn; pp < P_wk; ++pp) {
362 9467452 : kdanger[Co_White] += EvalConfig::kingAttSafeCheck[pp - 1] * BB::countBit(checkers[Co_Black][pp - 1] & safeSquare[Co_Black]);
363 9467452 : kdanger[Co_Black] += EvalConfig::kingAttSafeCheck[pp - 1] * BB::countBit(checkers[Co_White][pp - 1] & safeSquare[Co_White]);
364 : }
365 :
366 : // pieces mobility (second attack loop needed, knowing safeSquare ...)
367 : const colored<BitBoard> knights = {p.whiteKnight(), p.blackKnight()};
368 : const colored<BitBoard> bishops = {p.whiteBishop(), p.blackBishop()};
369 : const colored<BitBoard> rooks = {p.whiteRook(), p.blackRook()};
370 : const colored<BitBoard> queens = {p.whiteQueen(), p.blackQueen()};
371 : const colored<BitBoard> kings = {p.whiteKing(), p.blackKing()};
372 :
373 2366863 : evalMob<P_wn, Co_White>(p, knights[Co_White], mobilityScore, safeSquare[Co_White], occupancy, mobility[Co_White]);
374 2366863 : evalMob<P_wb, Co_White>(p, bishops[Co_White], mobilityScore, safeSquare[Co_White], occupancy, mobility[Co_White]);
375 2366863 : evalMob<P_wr, Co_White>(p, rooks [Co_White], mobilityScore, safeSquare[Co_White], occupancy, mobility[Co_White]);
376 2366863 : evalMobQ< Co_White>(p, queens [Co_White], mobilityScore, safeSquare[Co_White], occupancy, mobility[Co_White]);
377 2366863 : evalMobK< Co_White>(p, kings [Co_White], mobilityScore, ~att[Co_Black] , occupancy, mobility[Co_White]);
378 2366863 : evalMob<P_wn, Co_Black>(p, knights[Co_Black], mobilityScore, safeSquare[Co_Black], occupancy, mobility[Co_Black]);
379 2366863 : evalMob<P_wb, Co_Black>(p, bishops[Co_Black], mobilityScore, safeSquare[Co_Black], occupancy, mobility[Co_Black]);
380 2366863 : evalMob<P_wr, Co_Black>(p, rooks [Co_Black], mobilityScore, safeSquare[Co_Black], occupancy, mobility[Co_Black]);
381 2366863 : evalMobQ< Co_Black>(p, queens [Co_Black], mobilityScore, safeSquare[Co_Black], occupancy, mobility[Co_Black]);
382 2366863 : evalMobK< Co_Black>(p, kings [Co_Black], mobilityScore, ~att[Co_White] , occupancy, mobility[Co_Black]);
383 : }
384 :
385 : #pragma GCC diagnostic pop
386 :
387 : // this function shall be used on the initial position state before move is applied
388 : [[nodiscard]] FORCE_FINLINE bool isNoisy(const Position & /*p*/, const Move & m){
389 : return Move2Type(m) != T_std;
390 : /*
391 : if ( Move2Type(m) != T_std ) return true;
392 : const Square from = Move2From(m);
393 : const Square to = Move2To(m);
394 : const Piece pp = p.board_const(from);
395 : if (pp == P_wp){
396 : const BitBoard pAtt = p.c == Co_White ? BBTools::pawnAttacks<Co_White>(SquareToBitboard(to)) & p.allPieces[~p.c]:
397 : BBTools::pawnAttacks<Co_Black>(SquareToBitboard(to)) & p.allPieces[~p.c];
398 : if ( BB::countBit(pAtt) > 1 ) return true; ///@todo verify if the pawn is protected and/or not attacked ?
399 : }
400 : else if (pp == P_wn){
401 : const BitBoard nAtt = BBTools::coverage<P_wn>(to, p.occupancy(), p.c) & p.allPieces[~p.c];
402 : if ( BB::countBit(nAtt) > 1 ) return true; ///@todo verify if the knight is protected and/or not attacked ?
403 : }
404 : return false;
405 : */
406 : }
407 :
408 : FORCE_FINLINE void Searcher::timeCheck(){
409 : static uint64_t periodicCheck = 0ull; ///@todo this is slow because of guard variable
410 4947677 : if (periodicCheck == 0ull) {
411 4834 : periodicCheck = (TimeMan::maxNodes > 0) ? std::min(TimeMan::maxNodes, PERIODICCHECK) : PERIODICCHECK;
412 9668 : const Counter nodeCount = isStoppableCoSearcher ? stats.counters[Stats::sid_nodes] + stats.counters[Stats::sid_qnodes]
413 4834 : : ThreadPool::instance().counter(Stats::sid_nodes) + ThreadPool::instance().counter(Stats::sid_qnodes);
414 4834 : if (TimeMan::maxNodes > 0 && nodeCount > TimeMan::maxNodes) {
415 0 : stopFlag = true;
416 0 : Logging::LogIt(Logging::logInfo) << "stopFlag triggered (nodes limits) in thread " << id();
417 : }
418 4834 : if (getTimeDiff(startTime) > getCurrentMoveMs()) {
419 0 : stopFlag = true;
420 0 : Logging::LogIt(Logging::logInfo) << "stopFlag triggered in thread " << id();
421 : }
422 : Distributed::pollStat();
423 :
424 : if (!Distributed::isMainProcess()) {
425 : bool masterStopFlag;
426 : Distributed::get(&masterStopFlag, 1, Distributed::_winStopFromR0, 0);
427 : ThreadPool::instance().main().stopFlag = masterStopFlag;
428 : }
429 : }
430 4947677 : --periodicCheck;
431 4947677 : }
432 :
433 : // pvs inspired by Xiphos
434 : template<bool pvnode>
435 4947883 : ScoreType Searcher::pvs(ScoreType alpha,
436 : ScoreType beta,
437 : const Position& p,
438 : DepthType depth,
439 : DepthType height,
440 : PVList& pv,
441 : DepthType& seldepth,
442 : DepthType extensions,
443 : bool isInCheck_,
444 : bool cutNode_,
445 : const std::vector<MiniMove>* skipMoves) {
446 :
447 : // stopFlag management and time check. Only on main thread and not at each node (see PERIODICCHECK)
448 4947883 : if (isMainThread() || isStoppableCoSearcher) timeCheck();
449 4947883 : if (stopFlag) return STOPSCORE;
450 :
451 4947880 : debug_king_cap(p);
452 :
453 : // initiate the big pvsData structure with already given parameters
454 4947880 : PVSData pvsData;
455 4947880 : pvsData.cutNode = cutNode_;
456 4947880 : pvsData.isInCheck = isInCheck_;
457 4947880 : pvsData.alpha = alpha;
458 4947880 : pvsData.beta = beta;
459 4947880 : pvsData.pvnode = pvnode;
460 4947880 : pvsData.withoutSkipMove = skipMoves == nullptr;
461 4947880 : pvsData.previousMoveIsNullMove = p.lastMove == NULLMOVE;
462 :
463 : // some evaluation are used inside search
464 4947880 : EvalData evalData;
465 :
466 : // height is updated recursively in pvs and qsearch calls
467 : // but also given to Searcher itself in order to be available inside eval (which have "context").
468 : // @todo simplify this using only one solution !
469 4947880 : height_ = height;
470 4947880 : pvsData.theirTurn = height%2;
471 4947880 : pvsData.rootnode = height == 0;
472 :
473 : // we cannot search deeper than MAX_DEPTH, if so just return static evaluation in this case
474 4947880 : if (height >= MAX_DEPTH - 1 || depth >= MAX_DEPTH - 1) return eval(p, evalData, *this);
475 :
476 : // if not at root we check for draws (3rep, fifty and material)
477 4947880 : if (!pvsData.rootnode){
478 4946510 : if (const auto INRscore = interiorNodeRecognizer<pvnode>(p, height); INRscore.has_value()){
479 6580 : return INRscore.value();
480 : }
481 : }
482 :
483 : // on pvs leaf node, call a quiet search
484 4941300 : if (depth <= 0) {
485 : // don't enter qsearch when in check
486 : //if (pvsData.isInCheck) depth = 1;
487 : //else
488 1823696 : return qsearch(alpha, beta, p, height, seldepth, 0, true, pvnode, pvsData.isInCheck);
489 : }
490 :
491 : // update selective depth as soon as we "really enter" a node
492 3117604 : seldepth = std::max(seldepth,height);
493 :
494 : // update nodes count as soon as we "really enter" a node
495 3117604 : ++stats.counters[Stats::sid_nodes];
496 :
497 3117604 : if (!pvsData.rootnode){
498 : // mate distance pruning
499 3116234 : alpha = std::max(alpha, matedScore(height));
500 3116234 : beta = std::min(beta, matingScore(height + 1));
501 3116234 : if (alpha >= beta) return alpha;
502 : }
503 : else{
504 : // all threads clear rootScore, this is usefull for helper like in genfen or rescore.
505 : rootScores.clear();
506 : }
507 :
508 : // get the CMH pointer, can be needed to update tables
509 3117543 : getCMHPtr(p.halfmoves, pvsData.cmhPtr);
510 :
511 : // the position hash will be used quite often
512 3117543 : Hash pHash = computeHash(p);
513 : // let's consider skipmove(s) in position hashing
514 3117543 : if (skipMoves){
515 89393 : for (const auto & it : *skipMoves) {
516 0 : assert( isValidMove(it) );
517 44704 : pHash ^= Zobrist::hashMove(it);
518 : }
519 : }
520 :
521 : // Check for end-game knowledge
522 : Hash matHash = nullHash;
523 : MaterialHash::Terminaison terminaison = MaterialHash::Ter_Unknown;
524 3117543 : if (p.mat[Co_White][M_t] + p.mat[Co_Black][M_t] < 5) {
525 1437439 : matHash = MaterialHash::getMaterialHash(p.mat);
526 1437439 : if ( matHash != nullHash ){
527 : const MaterialHash::MaterialHashEntry& MEntry = MaterialHash::materialHashTable[matHash];
528 1437432 : terminaison = MEntry.t;
529 : }
530 : }
531 3117543 : pvsData.isKnownEndGame = terminaison != MaterialHash::Ter_Unknown;
532 :
533 : // probe TT
534 : TT::Entry e;
535 3117543 : const bool ttDepthOk = TT::getEntry(*this, p, pHash, depth, e);
536 3117543 : pvsData.bound = static_cast<TT::Bound>(e.b & ~TT::B_allFlags);
537 : // if depth of TT entry is enough, and not at root, then we consider to early return
538 3117543 : if (ttDepthOk && !pvsData.rootnode) {
539 524326 : if ((pvsData.bound == TT::B_alpha && e.s <= alpha)
540 462640 : || (pvsData.bound == TT::B_beta && e.s >= beta)
541 110994 : || (pvsData.bound == TT::B_exact) ) {
542 : if constexpr(!pvnode) {
543 : // increase history bonus of this move
544 416051 : if (e.m != INVALIDMINIMOVE){
545 : // quiet move history
546 416051 : if (Move2Type(e.m) == T_std){
547 172262 : updateTables(*this, p, depth, height, e.m, pvsData.bound, pvsData.cmhPtr);
548 : //if (pvsData.bound == TT::B_beta) historyT.update<1>(depth, e.m, p, pvsData.cmhPtr);
549 : //else if (pvsData.bound == TT::B_alpha) historyT.update<-1>(depth, e.m, p, pvsData.cmhPtr);
550 : }
551 : // capture history
552 243789 : else if ( isCapture(e.m) ){
553 243589 : if (pvsData.bound == TT::B_beta) historyT.updateCap<1>(depth, e.m, p);
554 15767 : else if (pvsData.bound == TT::B_alpha) historyT.updateCap<-1>(depth, e.m, p);
555 : }
556 : }
557 416051 : if (p.fifty < SearchConfig::ttMaxFiftyValideDepth && !pvsData.isKnownEndGame){
558 416042 : if (pvsData.bound == TT::B_alpha) stats.incr(Stats::sid_ttAlphaCut);
559 416042 : if (pvsData.bound == TT::B_exact) stats.incr(Stats::sid_ttExactCut);
560 416042 : if (pvsData.bound == TT::B_beta) stats.incr(Stats::sid_ttBetaCut);
561 416042 : return TT::adjustHashScore(e.s, height);
562 : }
563 : }
564 : ///@todo try returning also at pv node again (but this cuts pv ...)
565 : /*
566 : else { // in "good" condition, also return a score at pvnode
567 : if ( bound == TT::B_exact && e.d > 3*depth/2 && p.fifty < SearchConfig::ttMaxFiftyValideDepth){
568 : return TT::adjustHashScore(e.s, height);
569 : }
570 : }
571 : */
572 : }
573 : else{
574 : stats.incr(Stats::sid_ttWrongBound);
575 : }
576 : }
577 :
578 : // if entry hash is not null and entry move is valid,
579 : // then this is a valid TT move (we don't care about depth of the entry here)
580 : ///@todo try to store more things in TT bound ...
581 2701501 : pvsData.ttHit = e.h != nullHash;
582 2701501 : pvsData.validTTmove = pvsData.ttHit && e.m != INVALIDMINIMOVE;
583 2701501 : pvsData.ttPV = pvnode || (pvsData.validTTmove && (e.b & TT::B_ttPVFlag));
584 2701501 : pvsData.ttIsCheck = pvsData.validTTmove && (e.b & TT::B_isCheckFlag);
585 2701501 : pvsData.formerPV = pvsData.ttPV && !pvnode;
586 :
587 : // an idea from Ethereal :
588 : // near TT hits in terms of depth can trigger early returns
589 : // if cutoff is validated by a margin
590 :
591 : if constexpr(!pvnode){
592 2685411 : if ( !pvsData.rootnode
593 : //&& !pvsData.isInCheck
594 2685411 : && pvsData.ttHit
595 1355664 : && e.d > 0 // not from QS
596 518145 : && (pvsData.bound == TT::B_alpha)
597 178047 : && e.d >= depth - SearchConfig::ttAlphaCutDepth
598 87071 : && e.s + SearchConfig::ttAlphaCutMargin * (depth - SearchConfig::ttAlphaCutDepth) <= alpha){
599 : stats.incr(Stats::sid_ttAlphaLateCut);
600 8282 : return alpha;
601 : }
602 :
603 : // and it seems we can do the same with beta bound
604 2677129 : if ( !pvsData.rootnode
605 : //&& !pvsData.isInCheck
606 2677129 : && pvsData.ttHit
607 1347382 : && e.d > 0 // not from QS
608 509863 : && (pvsData.bound == TT::B_beta)
609 338529 : && e.d >= depth - SearchConfig::ttBetaCutDepth
610 147474 : && e.s - SearchConfig::ttBetaCutMargin * (depth - SearchConfig::ttBetaCutDepth) >= beta){
611 : stats.incr(Stats::sid_ttBetaLateCut);
612 42247 : return beta;
613 : }
614 : }
615 :
616 : #ifdef WITH_SYZYGY
617 : // probe TB
618 2650972 : ScoreType tbScore = 0;
619 16090 : if (!pvsData.rootnode
620 2649602 : && pvsData.withoutSkipMove
621 5264812 : && BB::countBit(p.allPieces[Co_White] | p.allPieces[Co_Black]) <= SyzygyTb::MAX_TB_MEN){
622 0 : if (SyzygyTb::probe_wdl(p, tbScore, true) > 0) {
623 0 : ++stats.counters[Stats::sid_tbHit1];
624 : // if this is a winning/losing EGT position, we add up static evaluation
625 : // this allow to go for mate better or to defend longer
626 0 : if (abs(tbScore) == SyzygyTb::TB_WIN_SCORE) {
627 0 : tbScore += eval(p, evalData, *this);
628 0 : tbScore = clampScore(tbScore);
629 : }
630 0 : else if (abs(tbScore) == SyzygyTb::TB_CURSED_SCORE) {
631 0 : Logging::LogIt(Logging::logInfo) << "cursed position " << GetFEN(p);
632 0 : tbScore = drawScore(p, height);
633 : }
634 : // store TB hits into TT (without associated move, but with max depth)
635 : //TT::setEntry(*this, pHash, INVALIDMOVE, TT::createHashScore(tbScore, height), TT::createHashScore(tbScore, height), TT::B_none, DepthType(MAX_DEPTH), isMainThread());
636 0 : return tbScore;
637 : }
638 : else {
639 : stats.incr(Stats::sid_tbFail);
640 : }
641 : }
642 : #endif
643 :
644 2650972 : assert(p.halfmoves - 1 < MAX_PLY && p.halfmoves - 1 >= 0);
645 :
646 : // now, let's get a static score for the position.
647 : ScoreType evalScore;
648 :
649 : // do not eval position when in check, we won't use it (as we won't forward prune)
650 2650972 : if (pvsData.isInCheck){
651 : evalScore = matedScore(height);
652 : }
653 : // skip eval: if nullmove just applied we can hack
654 : // but this won't work with asymetric HalfKA NNUE
655 2315845 : else if (!DynamicConfig::useNNUE && pvsData.previousMoveIsNullMove && height > 0){
656 0 : evalScore = 2 * EvalConfig::tempo - stack[p.halfmoves - 1].eval;
657 : #ifdef DEBUG_STATICEVAL
658 : checkEval(p,evalScore,*this,"null move trick (pvs)");
659 : #endif
660 : }
661 : else {
662 : // if we had a TT hit (with or without associated move),
663 : // we can use its eval instead of calling eval()
664 2315845 : if (pvsData.ttHit) {
665 : stats.incr(Stats::sid_ttschits);
666 1188398 : evalScore = e.e;
667 : // but we are missing game phase in this case
668 : // so let's look for a material match
669 1188398 : matHash = matHash != nullHash ? matHash : MaterialHash::getMaterialHash(p.mat);
670 629696 : if (matHash != nullHash) {
671 : stats.incr(Stats::sid_materialTableHitsSearch);
672 : const MaterialHash::MaterialHashEntry& MEntry = MaterialHash::materialHashTable[matHash];
673 1188286 : evalData.gp = MEntry.gamePhase();
674 : }
675 : else {
676 : stats.incr(Stats::sid_materialTableMissSearch);
677 : }
678 : #ifdef DEBUG_STATICEVAL
679 : checkEval(p,evalScore,*this,"from TT (pvs)");
680 : #endif
681 : }
682 : // if no TT hit call evaluation
683 : else {
684 : stats.incr(Stats::sid_ttscmiss);
685 1127447 : evalScore = eval(p, evalData, *this);
686 : #ifdef DEBUG_STATICEVAL
687 : checkEval(p,evalScore,*this,"from eval (pvs)");
688 : #endif
689 : }
690 : }
691 :
692 2650972 : if (evalData.gp == 0){
693 : // if no match yet, compute game phase now
694 335239 : ScoreType matScoreW = 0;
695 335239 : ScoreType matScoreB = 0;
696 335239 : evalData.gp = gamePhase(p.mat, matScoreW, matScoreB);
697 : }
698 :
699 : // insert only static eval in stack data, never hash score for consistancy!
700 2650972 : stack[p.halfmoves].eval = evalScore;
701 :
702 : // backup the static evaluation score as we will try to get a better evalScore approximation
703 : const ScoreType staticScore = evalScore;
704 :
705 : // if no TT hit yet, we insert an eval without a move here in case of forward pruning (depth is negative, bound is none) ...
706 : // Be carefull here, _data2 in Entry is always (INVALIDMOVE,B_none,-2) here, so that collisions are a lot more likely
707 2650972 : if (!pvsData.ttHit) TT::setEntry(*this, pHash, INVALIDMOVE, TT::createHashScore(evalScore, height), TT::createHashScore(staticScore, height), TT::B_none, -2, isMainThread());
708 :
709 : // if TT hit, we can use entry score as a best draft
710 : // but we set evalScoreIsHashScore to be aware of that !
711 2650972 : if (pvsData.ttHit && e.d > 0 && !pvsData.isInCheck && !pvsData.isKnownEndGame
712 409132 : && ((pvsData.bound == TT::B_alpha && e.s < evalScore) || (pvsData.bound == TT::B_beta && e.s > evalScore) || (pvsData.bound == TT::B_exact))){
713 191236 : evalScore = TT::adjustHashScore(e.s, height);
714 191236 : pvsData.evalScoreIsHashScore = true;
715 : stats.incr(Stats::sid_staticScoreIsFromSearch);
716 : }
717 :
718 : // take **initial** position situation (from game history) into account for pruning ?
719 : ///@todo retry this
720 2650972 : pvsData.isBoomingAttack = positionEvolution == MoveDifficultyUtil::PE_boomingAttack;
721 2650972 : pvsData.isBoomingDefend = positionEvolution == MoveDifficultyUtil::PE_boomingDefence;
722 2650972 : pvsData.isMoobingAttack = positionEvolution == MoveDifficultyUtil::PE_moobingAttack;
723 2650972 : pvsData.isMoobingDefend = positionEvolution == MoveDifficultyUtil::PE_moobingDefence;
724 :
725 : // take **initial** position situation (from IID variability) into account for pruning ?
726 : ///@todo retry this
727 2650972 : pvsData.isEmergencyDefence = false;//moveDifficulty == MoveDifficultyUtil::MD_moobDefenceIID;
728 2650972 : pvsData.isEmergencyAttack = false;//moveDifficulty == MoveDifficultyUtil::MD_moobAttackIID;
729 :
730 : // take **current** position danger level into account for purning
731 : // no HCE has been done, we need to work a little to get data from evaluation of the position
732 2650972 : if (!evalData.evalDone) {
733 : EvalScore mobilityScore = {0, 0};
734 2366863 : array2d<BitBoard,2,6> checkers = {{emptyBitBoard}};
735 2366863 : array2d<BitBoard,2,6> attFromPiece = {{emptyBitBoard}};
736 2366863 : colored<BitBoard> att = {emptyBitBoard, emptyBitBoard};
737 2366863 : colored<BitBoard> att2 = {emptyBitBoard, emptyBitBoard};
738 :
739 : evalFeatures(p, attFromPiece, att, att2, checkers, evalData.danger, mobilityScore, evalData.mobility);
740 :
741 2366863 : evalData.haveThreats[Co_White] = (att[Co_White] & p.allPieces[Co_Black]) != emptyBitBoard;
742 2366863 : evalData.haveThreats[Co_Black] = (att[Co_Black] & p.allPieces[Co_White]) != emptyBitBoard;
743 :
744 2366863 : evalData.goodThreats[Co_White] = ((attFromPiece[Co_White][P_wp - 1] & p.allPieces[Co_Black] & ~p.blackPawn()) |
745 2366863 : (attFromPiece[Co_White][P_wn - 1] & (p.blackQueen() | p.blackRook())) |
746 2366863 : (attFromPiece[Co_White][P_wb - 1] & (p.blackQueen() | p.blackRook())) |
747 2366863 : (attFromPiece[Co_White][P_wr - 1] & p.blackQueen())) != emptyBitBoard;
748 2366863 : evalData.goodThreats[Co_Black] = ((attFromPiece[Co_Black][P_wp - 1] & p.allPieces[Co_White] & ~p.whitePawn()) |
749 2366863 : (attFromPiece[Co_Black][P_wn - 1] & (p.whiteQueen() | p.whiteRook())) |
750 2366863 : (attFromPiece[Co_Black][P_wb - 1] & (p.whiteQueen() | p.whiteRook())) |
751 2366863 : (attFromPiece[Co_Black][P_wr - 1] & p.whiteQueen())) != emptyBitBoard;
752 : }
753 :
754 : // if the position is really intense, eventually for both side (thus very sharp), will try to prune/reduce a little less
755 2650972 : const int dangerFactor = (evalData.danger[Co_White] + evalData.danger[Co_Black]) / SearchConfig::dangerDivisor;
756 2650972 : const bool isDangerPrune = dangerFactor >= SearchConfig::dangerLimitPruning;
757 2650972 : const bool isDangerForwardPrune = dangerFactor >= SearchConfig::dangerLimitForwardPruning;
758 2650972 : const bool isDangerRed = dangerFactor >= SearchConfig::dangerLimitReduction;
759 : ///@todo this is not used for now
760 2650972 : if (isDangerPrune) stats.incr(Stats::sid_dangerPrune);
761 2650972 : if (isDangerForwardPrune) stats.incr(Stats::sid_dangerForwardPrune);
762 2650972 : if (isDangerRed) stats.incr(Stats::sid_dangerReduce);
763 :
764 : // if we are doing a big attack, we will look for tactics involving sacrifices
765 2650972 : const int dangerGoodAttack = evalData.danger[~p.c] / SearchConfig::dangerDivisor;
766 : // unless if we are ourself under attack
767 2650972 : const int dangerUnderAttack = evalData.danger[p.c] / SearchConfig::dangerDivisor;
768 :
769 : // when score is fluctuating a lot in the main ID search, let's prune a bit less
770 2650972 : const DepthType emergencyDepthCorrection = pvsData.isEmergencyDefence || pvsData.isEmergencyAttack;
771 : // take asymetry into account, prune less when it is not our turn
772 : const DepthType asymetryDepthCorrection = 0; //pvsData.theirTurn; ///@todo
773 : // when score is fluctuating a lot in the current game, let's prune a bit less
774 : const DepthType situationDepthCorrection = 0; /*pvsData.isBoomingAttack
775 : || pvsData.isMoobingAttack
776 : || pvsData.isBoomingDefend
777 : || pvsData.isMoobingDefend;*/
778 :
779 : ///@todo this is not used for now (==0)
780 : // take current situation and asymetry into account.
781 : const DepthType depthCorrection = emergencyDepthCorrection || asymetryDepthCorrection || situationDepthCorrection;
782 :
783 : // some heuristic will depend on not-updated initial alpha
784 2650972 : const ScoreType alphaInit = alpha;
785 :
786 : // moves loop data
787 2650972 : MoveList moves;
788 : bool moveGenerated = false;
789 : bool capMoveGenerated = false;
790 :
791 : // nmp things
792 2650972 : pvsData.mateThreat = false;
793 : MiniMove refutation = INVALIDMINIMOVE;
794 :
795 : // a depth that take TT depth into account
796 2650972 : pvsData.marginDepth = std::max(0, depth - (pvsData.evalScoreIsHashScore ? e.d : 0));
797 :
798 : // is the reported static eval better than a move before in the search tree ?
799 : // ! be carefull pvsData.improving implies not being in check !
800 2650972 : pvsData.improving = (!pvsData.isInCheck && height > 1 && stack[p.halfmoves].eval >= stack[p.halfmoves - 2].eval);
801 :
802 : // in end game situations, some prudence is required with pruning
803 2650972 : pvsData.isNotPawnEndGame = p.mat[p.c][M_t] > 0;
804 2650972 : pvsData.lessZugzwangRisk = pvsData.isNotPawnEndGame || evalData.mobility[p.c] > 4;
805 :
806 : // forward prunings (only at not pvnode)
807 : if constexpr(!pvnode){
808 : // removing the !isMateScore(beta) is not losing that much elo and allow for better check mate finding ...
809 2634882 : if (!DynamicConfig::mateFinder && !pvsData.rootnode && !pvsData.isInCheck /*&& !isMateScore(beta)*/) {
810 :
811 : // static null move
812 2301131 : if (SearchConfig::doStaticNullMove && !isMateScore(evalScore) && pvsData.lessZugzwangRisk && SearchConfig::staticNullMoveCoeff.isActive(depth, pvsData.evalScoreIsHashScore) ) {
813 2031456 : const ScoreType margin = SearchConfig::staticNullMoveCoeff.threshold(depth, evalData.gp, pvsData.evalScoreIsHashScore, pvsData.improving);
814 2031456 : if (evalScore > beta + margin) return stats.incr(Stats::sid_staticNullMove), evalScore - margin;
815 : }
816 :
817 : // (absence of) opponent threats pruning (idea origin from Koivisto)
818 1438295 : if ( SearchConfig::doThreatsPruning && !isMateScore(evalScore) && pvsData.lessZugzwangRisk && !evalData.goodThreats[~p.c] && SearchConfig::threatCoeff.isActive(depth, pvsData.evalScoreIsHashScore) ) {
819 545547 : const ScoreType margin = SearchConfig::threatCoeff.threshold(depth, evalData.gp, pvsData.evalScoreIsHashScore, pvsData.improving);
820 545547 : if (evalScore > beta + margin) return stats.incr(Stats::sid_threatsPruning), evalScore - margin;
821 : }
822 : /*
823 : // own threats pruning
824 : if ( SearchConfig::doThreatsPruning && !isMateScore(evalScore) && pvsData.lessZugzwangRisk && SearchConfig::ownThreatCoeff.isActive(depth, pvsData.evalScoreIsHashScore) &&
825 : !evalData.goodThreats[p.c] && evalScore < alpha - SearchConfig::ownThreatCoeff.threshold(depth, evalData.gp, pvsData.evalScoreIsHashScore, pvsData.improving) ){
826 : return stats.incr(Stats::sid_threatsPruning), alpha;
827 : }
828 : */
829 : // razoring
830 1353009 : if (const ScoreType rAlpha = alpha - SearchConfig::razoringCoeff.threshold(pvsData.marginDepth, evalData.gp, pvsData.evalScoreIsHashScore, pvsData.improving);
831 1353009 : SearchConfig::doRazoring && SearchConfig::razoringCoeff.isActive(depth, pvsData.evalScoreIsHashScore) && evalScore <= rAlpha) {
832 : stats.incr(Stats::sid_razoringTry);
833 174930 : if (!evalData.haveThreats[p.c]) return stats.incr(Stats::sid_razoringNoThreat), rAlpha;
834 147872 : const ScoreType qScore = qsearch(alpha, beta, p, height, seldepth, 0, true, pvnode, pvsData.isInCheck);
835 147872 : if (stopFlag) return STOPSCORE;
836 : //if (pvsData.evalScoreIsHashScore) return stats.incr(Stats::sid_razoringNoQ), qScore; // won't happen often as depth limit is small...
837 147872 : if (qScore <= alpha) return stats.incr(Stats::sid_razoring), qScore;
838 : }
839 :
840 : // null move
841 2394245 : if (SearchConfig::doNullMove && !subSearch &&
842 1192244 : depth >= SearchConfig::nullMoveMinDepth &&
843 1008618 : pvsData.lessZugzwangRisk &&
844 : //!pvsData.isKnownEndGame &&
845 997712 : pvsData.withoutSkipMove &&
846 970114 : (evalScore == beta || evalScore >= beta + SearchConfig::nullMoveMargin) &&
847 516832 : evalScore >= stack[p.halfmoves].eval &&
848 1715106 : stack[p.halfmoves].p.lastMove != NULLMOVE &&
849 501702 : (height >= nullMoveMinPly || nullMoveVerifColor != p.c)) {
850 491394 : PVList nullPV;
851 : stats.incr(Stats::sid_nullMoveTry);
852 982788 : const DepthType R = SearchConfig::nullMoveReductionInit +
853 982788 : depth / SearchConfig::nullMoveReductionDepthDivisor +
854 491394 : std::min((evalScore - beta) / SearchConfig::nullMoveDynamicDivisor, 7); // adaptative
855 491394 : const DepthType nullDepth = std::max(0, depth - R);
856 491394 : Position pN = p;
857 491394 : applyNull(*this, pN);
858 491394 : assert(pN.halfmoves < MAX_PLY && pN.halfmoves >= 0);
859 491394 : stack[pN.halfmoves].p = pN; ///@todo another expensive copy !!!!
860 491394 : stack[pN.halfmoves].h = pN.h;
861 491394 : ScoreType nullscore = -pvs<false>(-beta, -beta + 1, pN, nullDepth, height + 1, nullPV, seldepth, extensions, pvsData.isInCheck, !pvsData.cutNode);
862 491394 : if (stopFlag) return STOPSCORE;
863 : TT::Entry nullEThreat;
864 491394 : TT::getEntry(*this, pN, computeHash(pN), 0, nullEThreat);
865 491394 : if (nullEThreat.h != nullHash && nullEThreat.m != INVALIDMINIMOVE) refutation = nullEThreat.m;
866 491394 : if (isMatedScore(nullscore)) pvsData.mateThreat = true;
867 491394 : if (nullscore >= beta) { // verification search
868 221509 : if ( (!pvsData.lessZugzwangRisk || depth > SearchConfig::nullMoveVerifDepth) && nullMoveMinPly == 0){
869 : stats.incr(Stats::sid_nullMoveTry3);
870 106223 : nullMoveMinPly = height + 3*nullDepth/4;
871 106223 : nullMoveVerifColor = p.c;
872 106223 : nullscore = pvs<false>(beta - 1, beta, p, nullDepth, height+1, nullPV, seldepth, extensions, pvsData.isInCheck, false);
873 106223 : nullMoveMinPly = 0;
874 106223 : nullMoveVerifColor = Co_None;
875 106223 : if (stopFlag) return STOPSCORE;
876 106223 : if (nullscore >= beta ) return stats.incr(Stats::sid_nullMove2), nullscore;
877 : }
878 : else {
879 115286 : return stats.incr(Stats::sid_nullMove), (isMateScore(nullscore) ? beta : nullscore);
880 : }
881 : }
882 491394 : }
883 :
884 : // ProbCut
885 980587 : const ScoreType betaPC = beta + SearchConfig::probCutMargin + SearchConfig::probCutMarginSlope * pvsData.improving;
886 48519 : if (SearchConfig::doProbcut && depth >= SearchConfig::probCutMinDepth && !isMateScore(beta) &&
887 48519 : evalData.haveThreats[p.c]
888 : //&& !pvsData.isKnownEndGame
889 39126 : && (pvsData.cutNode || staticScore >= betaPC)
890 1006836 : && !( pvsData.validTTmove &&
891 22593 : e.d >= depth / SearchConfig::probCutSearchDepthFactor + 1 &&
892 19219 : e.s < betaPC)
893 : ) {
894 : stats.incr(Stats::sid_probcutTry);
895 : int probCutCount = 0;
896 : capMoveGenerated = true;
897 14457 : MoveGen::generate<MoveGen::GP_cap>(p, moves);
898 : //if (moves.empty()) stats.incr(Stats::sid_probcutNoCap); // should be 0 as there is threats ...
899 : #ifdef USE_PARTIAL_SORT
900 18113 : MoveSorter::score(*this, moves, p, evalData.gp, height, pvsData.cmhPtr, true, pvsData.isInCheck, pvsData.validTTmove ? &e : nullptr);
901 14457 : size_t offset = 0;
902 : const Move* it = nullptr;
903 : //if(!pvsData.cutNode) MoveSorter::sort(moves); // we expect one of the first best move to fail high on cutNode
904 53458 : while ((it = MoveSorter::pickNext(moves, offset/*, !pvsData.cutNode)*/)) && probCutCount < SearchConfig::probCutMaxMoves) {
905 : #else
906 : MoveSorter::scoreAndSort(*this, moves, p, evalData.gp, height, pvsData.cmhPtr, true, pvsData.isInCheck, pvsData.validTTmove ? &e : nullptr);
907 : for (auto it = moves.begin(); it != moves.end() && probCutCount < SearchConfig::probCutMaxMoves; ++it) {
908 : #endif
909 : stats.incr(Stats::sid_probcutMoves);
910 34149 : if ((pvsData.validTTmove && sameMove(e.m, *it)) || isBadCap(*it)) continue; // skip TT move if quiet or bad captures
911 11503 : Position p2 = p;
912 11503 : const MoveInfo moveInfo(p2,*it);
913 11503 : if (!applyMove(p2, moveInfo, true)) continue;
914 : #ifdef WITH_NNUE
915 11424 : NNUEEvaluator newEvaluator = p.evaluator();
916 : p2.associateEvaluator(newEvaluator);
917 11424 : applyMoveNNUEUpdate(p2, moveInfo);
918 : #endif
919 11424 : ++probCutCount;
920 11424 : ScoreType scorePC = -qsearch(-betaPC, -betaPC + 1, p2, height + 1, seldepth, 0, true, pvnode);
921 11424 : PVList pcPV;
922 11424 : if (stopFlag) return STOPSCORE;
923 11424 : const DepthType probCutSearchDepth = depth / SearchConfig::probCutSearchDepthFactor;
924 11424 : if (scorePC >= betaPC) {
925 : stats.incr(Stats::sid_probcutTry2);
926 6697 : scorePC = -pvs<false>(-betaPC, -betaPC + 1, p2, probCutSearchDepth, height + 1, pcPV, seldepth, extensions,
927 6697 : isPosInCheck(p2), !pvsData.cutNode);
928 : }
929 11424 : if (stopFlag) return STOPSCORE;
930 11424 : if (scorePC >= betaPC){
931 : /*
932 : const DepthType bonusDepth = probCutSearchDepth - 1 + (scorePC > (beta + SearchConfig::betaMarginDynamicHistory));
933 : historyT.updateCap<1>(bonusDepth, *it, p);
934 : for (auto it2 = moves.begin(); it2 != moves.end() && !sameMove(*it2, *it); ++it2) {
935 : if (isCapture(*it2))
936 : historyT.updateCap<-1>(bonusDepth, *it2, p);
937 : }
938 : */
939 : /*
940 : TT::setEntry(*this, pHash, *it, TT::createHashScore(scorePC, height), TT::createHashScore(evalScore, height),
941 : static_cast<TT::Bound>(TT::B_beta |
942 : (pvsData.ttPV ? TT::B_ttPVFlag : TT::B_none) |
943 : (pvsData.bestMoveIsCheck ? TT::B_isCheckFlag : TT::B_none) |
944 : (pvsData.isInCheck ? TT::B_isInCheckFlag : TT::B_none)),
945 : probCutSearchDepth-1,
946 : isMainThread()); // we applied one move
947 : */
948 6493 : return stats.incr(Stats::sid_probcut), scorePC;
949 : }
950 : }
951 : }
952 : }
953 : }
954 :
955 : // Ed Schroder style IIR
956 1323935 : if (SearchConfig::doIIR && depth >= SearchConfig::iirMinDepth && !pvsData.ttHit){
957 : stats.incr(Stats::sid_iid);
958 279780 : depth -= SearchConfig::iirReduction;
959 : }
960 :
961 : // Classic IID
962 : if (SearchConfig::doIID && !pvsData.validTTmove /*|| e.d < depth-4*/) {
963 : if ((pvnode && depth >= SearchConfig::iidMinDepth) || (pvsData.cutNode && depth >= SearchConfig::iidMinDepth2)) { ///@todo try with cutNode only ?
964 : stats.incr(Stats::sid_iid);
965 : PVList iidPV;
966 : DISCARD pvs<pvnode>(alpha, beta, p, depth / 2, height, iidPV, seldepth, extensions, pvsData.isInCheck, pvsData.cutNode, skipMoves);
967 : if (stopFlag) return STOPSCORE;
968 : TT::getEntry(*this, p, pHash, 0, e);
969 : pvsData.ttHit = e.h != nullHash;
970 : pvsData.validTTmove = pvsData.ttHit && e.m != INVALIDMINIMOVE;
971 : pvsData.bound = static_cast<TT::Bound>(e.b & ~TT::B_allFlags);
972 : pvsData.ttPV = pvnode || (pvsData.ttHit && (e.b & TT::B_ttPVFlag));
973 : pvsData.ttIsCheck = pvsData.validTTmove && (e.b & TT::B_isCheckFlag);
974 : pvsData.formerPV = pvsData.ttPV && !pvnode;
975 : if (pvsData.ttHit && e.d > 0 && !pvsData.isInCheck &&
976 : ((pvsData.bound == TT::B_alpha && e.s < evalScore) || (pvsData.bound == TT::B_beta && e.s > evalScore) || (pvsData.bound == TT::B_exact))) {
977 : evalScore = TT::adjustHashScore(e.s, height);
978 : pvsData.evalScoreIsHashScore = true;
979 : pvsData.marginDepth = std::max(0, depth - (pvsData.evalScoreIsHashScore ? e.d : 0)); // a depth that take TT depth into account
980 : }
981 : }
982 : }
983 :
984 : // reset killers
985 : if (height <= MAX_DEPTH - 2){
986 1323935 : killerT.killers[height + 1][0] = killerT.killers[height + 1][1] = INVALIDMOVE;
987 : }
988 :
989 : // backup refutation from null move heuristic
990 1323935 : stack[p.halfmoves].threat = refutation;
991 :
992 : // verify threat evolution for Botvinnik-Markoff extension
993 1307845 : const MiniMove formerRefutation = height > 1 ? stack[p.halfmoves - 2].threat : INVALIDMINIMOVE;
994 1323935 : pvsData.BMextension = DynamicConfig::useNNUE && height > 1 &&
995 1330698 : isValidMove(refutation) && isValidMove(formerRefutation) &&
996 19688 : (sameMove(refutation, formerRefutation) ||
997 45636 : (isCapture(refutation) && Move2To(refutation) == correctedMove2ToKingDest(formerRefutation)));
998 :
999 : // verify situation for various pruning heuristics
1000 1323935 : if (!pvsData.rootnode) {
1001 : // LMP
1002 1322565 : pvsData.lmp = SearchConfig::doLMP && depth <= SearchConfig::lmpMaxDepth;
1003 : // futility
1004 1322565 : const ScoreType futilityScore = alpha - SearchConfig::futilityPruningCoeff.threshold(pvsData.marginDepth, evalData.gp, pvsData.evalScoreIsHashScore, pvsData.improving);
1005 1322565 : pvsData.futility = SearchConfig::doFutility && SearchConfig::futilityPruningCoeff.isActive(depth, pvsData.evalScoreIsHashScore) && evalScore <= futilityScore;
1006 : // history pruning
1007 1322565 : pvsData.historyPruning = SearchConfig::doHistoryPruning && pvsData.isNotPawnEndGame && SearchConfig::historyPruningCoeff.isActive(depth, pvsData.improving);
1008 : // CMH pruning
1009 1322565 : pvsData.CMHPruning = SearchConfig::doCMHPruning && pvsData.isNotPawnEndGame && depth < SearchConfig::CMHMaxDepth[pvsData.improving];
1010 : // capture history pruning
1011 1322565 : pvsData.capHistoryPruning = SearchConfig::doCapHistoryPruning && pvsData.isNotPawnEndGame && SearchConfig::captureHistoryPruningCoeff.isActive(depth, pvsData.improving);
1012 : }
1013 :
1014 : #ifdef WITH_SYZYGY
1015 1323935 : if (pvsData.rootnode && pvsData.withoutSkipMove && (BB::countBit(p.allPieces[Co_White] | p.allPieces[Co_Black])) <= SyzygyTb::MAX_TB_MEN) {
1016 0 : tbScore = 0;
1017 0 : if (MoveList movesTB; SyzygyTb::probe_root(*this, p, tbScore, movesTB) < 0) { // only good moves if TB success
1018 : stats.incr(Stats::sid_tbFail);
1019 0 : if (capMoveGenerated) MoveGen::generate<MoveGen::GP_quiet>(p, moves, true);
1020 : else
1021 0 : if ( pvsData.isInCheck ) MoveGen::generate<MoveGen::GP_evasion>(p, moves, false);
1022 0 : else MoveGen::generate<MoveGen::GP_all>(p, moves, false);
1023 : }
1024 : else {
1025 : moves = movesTB;
1026 0 : ++stats.counters[Stats::sid_tbHit2];
1027 : }
1028 : moveGenerated = true;
1029 : }
1030 : #endif
1031 :
1032 : // bestScore / bestMove will be updated in move loop and returned at the end and inserted in TT
1033 : ScoreType bestScore = matedScore(height);
1034 16090 : Move bestMove = INVALIDMOVE;
1035 :
1036 : TT::Bound hashBound = TT::B_alpha;
1037 :
1038 : // try the tt move before move generation (if not skipped move)
1039 514839 : if (pvsData.validTTmove &&
1040 1330695 : (moves.empty() || !pvsData.rootnode) && // avoid trying TT move at root if coming from a TB probe hit that filled moves
1041 514839 : !isSkipMove(e.m, skipMoves)) {
1042 :
1043 : #ifdef DEBUG_APPLY
1044 : // to debug race condition in entry affectation !
1045 : if (!isPseudoLegal(p, e.m)) { Logging::LogIt(Logging::logFatal) << "invalide TT move !"; }
1046 : #endif
1047 :
1048 514839 : pvsData.ttMoveTried = true;
1049 514839 : pvsData.isTTMove = true;
1050 514839 : if (isCapture(e.m)) pvsData.ttMoveIsCapture = true;
1051 12877 : bestMove = e.m; // in order to preserve tt move for alpha bound entry
1052 :
1053 514839 : Position p2 = p;
1054 514839 : if (const MoveInfo moveInfo(p2,e.m); applyMove(p2, moveInfo, true)) {
1055 :
1056 : // We have a TT move.
1057 : // The TT move can trigger singular extension
1058 : // And it won't be reduced by any mean
1059 : // Remember that if no tt hit, depth has been reduced already (by IIR)
1060 : DepthType extension = 0;
1061 514839 : if (DynamicConfig::level > 80) {
1062 : // singular move extension
1063 514829 : if (pvsData.withoutSkipMove
1064 503491 : && depth >= SearchConfig::singularExtensionDepth
1065 103076 : && !pvsData.rootnode
1066 102907 : && !isMateScore(e.s)
1067 102294 : && (pvsData.bound == TT::B_exact || pvsData.bound == TT::B_beta)
1068 578173 : && e.d >= depth - SearchConfig::singularExtensionDepthMinus) {
1069 44714 : const ScoreType betaC = e.s - 2 * depth;
1070 44714 : PVList sePV;
1071 44714 : DepthType seSeldepth = 0;
1072 44714 : std::vector<MiniMove> skip{e.m};
1073 44714 : const ScoreType score = pvs<false>(betaC - 1, betaC, p, depth / 2, height, sePV, seSeldepth, extensions, pvsData.isInCheck, pvsData.cutNode, &skip);
1074 44714 : if (stopFlag) return STOPSCORE;
1075 44714 : if (score < betaC /*&& extensions <= 6*/) { // TT move is singular
1076 : stats.incr(Stats::sid_singularExtension);
1077 21397 : pvsData.ttMoveSingularExt=true;
1078 : ++extension;
1079 : // TT move is "very singular" and depth is small : kind of single reply extension
1080 21397 : if (/*!pvsData.pvnode &&*/ score < betaC - 4 * depth && extensions <= 6) {
1081 : stats.incr(Stats::sid_singularExtension2);
1082 : ++extension;
1083 : /*
1084 : if (score < betaC - 8 * depth && !pvsData.ttMoveIsCapture && extensions <= 6){
1085 : stats.incr(Stats::sid_singularExtension6);
1086 : ++extension;
1087 : }
1088 : */
1089 : }
1090 : }
1091 : // multi cut (at least the TT move and another move are above beta)
1092 23317 : else if (betaC >= beta) {
1093 10535 : return stats.incr(Stats::sid_singularExtension3), betaC; // fail-soft
1094 : }
1095 : // if TT move is above beta, we try a reduce search early to see if another move is above beta (from SF)
1096 12782 : else if (e.s >= beta) {
1097 : //const ScoreType score2 = pvs<false>(beta - 1, beta, p, depth - 4, height, sePV, seSeldepth, extensions, pvsData.isInCheck, pvsData.cutNode, &skip);
1098 : //if (score2 > beta) return stats.incr(Stats::sid_singularExtension4), beta; // fail-hard
1099 4874 : extension = -2 + pvsData.pvnode;
1100 : stats.incr(Stats::sid_singularExtension4);
1101 : }
1102 : /*
1103 : else if (pvsData.cutNode){
1104 : extension = -1;
1105 : stats.incr(Stats::sid_singularExtension7);
1106 : }
1107 : */
1108 7908 : else if (e.s <= alpha){
1109 : extension = -1;
1110 : stats.incr(Stats::sid_singularExtension5);
1111 : }
1112 44714 : }
1113 : }
1114 :
1115 : // prefetch as soon as possible
1116 504304 : TT::prefetch(computeHash(p2));
1117 :
1118 : #ifdef WITH_NNUE
1119 504304 : NNUEEvaluator newEvaluator = p.evaluator();
1120 : p2.associateEvaluator(newEvaluator);
1121 504304 : applyMoveNNUEUpdate(p2, moveInfo);
1122 : #endif
1123 :
1124 504304 : ++pvsData.validMoveCount;
1125 504304 : ++pvsData.validNonPrunedCount;
1126 :
1127 504304 : pvsData.earlyMove = true;
1128 1008608 : pvsData.isQuiet = Move2Type(e.m) == T_std && !isNoisy(p, e.m);
1129 504304 : if (pvsData.isQuiet) ++pvsData.validQuietMoveCount;
1130 :
1131 504304 : pvsData.isCheck = pvsData.ttIsCheck || isPosInCheck(p2);
1132 :
1133 504304 : assert(p2.halfmoves < MAX_PLY && p2.halfmoves >= 0);
1134 504304 : stack[p2.halfmoves].p = p2; ///@todo another expensive copy !!!!
1135 504304 : stack[p2.halfmoves].h = p2.h;
1136 :
1137 : #ifdef DEBUG_TT_CHECK
1138 : if (pvsData.ttIsCheck && !isPosInCheck(p2)) {
1139 : std::cout << "Error ttIsCheck" << std::endl;
1140 : std::cout << ToString(p2) << std::endl;
1141 : }
1142 : #endif
1143 :
1144 504304 : PVList childPV;
1145 : ScoreType ttScore;
1146 504304 : ttScore = -pvs<pvnode>(-beta, -alpha, p2, depth - 1 + extension, height + 1, childPV, seldepth, static_cast<DepthType>(extensions + extension), pvsData.isCheck, !pvsData.cutNode);
1147 :
1148 504304 : if (stopFlag) return STOPSCORE;
1149 :
1150 504304 : if (pvsData.rootnode) {
1151 1345 : rootScores.emplace_back(e.m, ttScore);
1152 : }
1153 :
1154 504304 : if (ttScore > bestScore) {
1155 504299 : if (pvsData.rootnode) previousBest = e.m;
1156 : bestScore = ttScore;
1157 504299 : bestMove = e.m;
1158 504299 : pvsData.bestMoveIsCheck = pvsData.isCheck;
1159 504299 : if (ttScore > alpha) {
1160 : hashBound = TT::B_exact;
1161 280578 : pvsData.alphaUpdated = true;
1162 : if constexpr(pvnode) updatePV(pv, bestMove, childPV);
1163 280578 : if (ttScore >= beta) {
1164 : stats.incr(Stats::sid_ttbeta);
1165 :
1166 : // increase history bonus of this move
1167 274965 : if (!pvsData.isInCheck){
1168 186305 : if (pvsData.isQuiet /*&& depth > 1*/) // quiet move history
1169 71863 : updateTables(*this, p, depth + (ttScore > (beta + SearchConfig::betaMarginDynamicHistory)), height, bestMove, TT::B_beta, pvsData.cmhPtr);
1170 114442 : else if (isCapture(bestMove)) // capture history
1171 114348 : historyT.updateCap<1>(depth + (ttScore > (beta + SearchConfig::betaMarginDynamicHistory)), bestMove, p);
1172 : }
1173 :
1174 274965 : TT::setEntry(*this, pHash, bestMove, TT::createHashScore(ttScore, height), TT::createHashScore(evalScore, height),
1175 274965 : static_cast<TT::Bound>(TT::B_beta |
1176 274965 : (pvsData.ttPV ? TT::B_ttPVFlag : TT::B_none) |
1177 549930 : (pvsData.bestMoveIsCheck ? TT::B_isCheckFlag : TT::B_none) |
1178 274965 : (pvsData.isInCheck ? TT::B_isInCheckFlag : TT::B_none)),
1179 : depth,
1180 274965 : isMainThread());
1181 : return ttScore;
1182 : }
1183 : stats.incr(Stats::sid_ttalpha);
1184 5613 : alpha = ttScore;
1185 : }
1186 : }
1187 5 : else if (pvsData.rootnode && !pvsData.isInCheck && ttScore < alpha - SearchConfig::failLowRootMargin /*&& !isMateScore(ttScore)*/) {
1188 0 : return alpha - SearchConfig::failLowRootMargin;
1189 : }
1190 504304 : }
1191 514839 : }
1192 :
1193 1038435 : ScoreType score = matedScore(height);
1194 : bool skipQuiet = false;
1195 : bool skipCap = false;
1196 :
1197 : // depending if probecut already generates capture or not, generate all moves or only missing quiets
1198 1038435 : if (!moveGenerated) {
1199 1025557 : if (capMoveGenerated) MoveGen::generate<MoveGen::GP_quiet>(p, moves, true);
1200 : else
1201 1036599 : if ( pvsData.isInCheck ) MoveGen::generate<MoveGen::GP_evasion>(p, moves, false);
1202 792594 : else MoveGen::generate<MoveGen::GP_all>(p, moves, false);
1203 : }
1204 1038435 : if (moves.empty()) return pvsData.isInCheck ? matedScore(height) : drawScore(p, height);
1205 :
1206 : #ifdef USE_PARTIAL_SORT
1207 1893709 : MoveSorter ms(*this, p, evalData.gp, height, pvsData.cmhPtr, true, pvsData.isInCheck, pvsData.validTTmove ? &e : nullptr,
1208 46204 : refutation != INVALIDMINIMOVE && isCapture(Move2Type(refutation)) ? refutation : INVALIDMINIMOVE);
1209 1038422 : ms.score(moves);
1210 1038422 : size_t offset = 0;
1211 : const Move* it = nullptr;
1212 : //if(!pvsData.cutNode) ms.sort(moves); // we expect one of the first best move to fail high on cutNode
1213 25417272 : while ((it = ms.pickNextLazy(moves, offset/*, !pvsData.cutNode*/)) && !stopFlag) {
1214 : #else
1215 : MoveSorter::scoreAndSort(moves);
1216 : for (auto it = moves.begin(); it != moves.end() && !stopFlag; ++it) {
1217 : #endif
1218 :
1219 12584253 : pvsData.isTTMove = false;
1220 26579120 : pvsData.isQuiet = Move2Type(*it) == T_std && !isNoisy(p,*it);
1221 :
1222 8831172 : if (isSkipMove(*it, skipMoves)) continue; // skipmoves
1223 12557774 : if (pvsData.validTTmove && pvsData.ttMoveTried && sameMove(e.m, *it)) continue; // already tried
1224 :
1225 12328435 : Position p2 = p;
1226 12328435 : const MoveInfo moveInfo(p2,*it);
1227 :
1228 : // do not apply NNUE update here, but later after prunning, right before next call to pvs
1229 12328435 : if (!applyMove(p2, moveInfo, true)) continue;
1230 :
1231 : // prefetch as soon as possible
1232 11192400 : TT::prefetch(computeHash(p2));
1233 11192400 : const Square to = Move2To(*it);
1234 : #ifdef DEBUG_KING_CAP
1235 : if (p.c == Co_White && to == p.king[Co_Black]) return matingScore(height - 1);
1236 : if (p.c == Co_Black && to == p.king[Co_White]) return matingScore(height - 1);
1237 : #endif
1238 :
1239 11192400 : ++pvsData.validMoveCount;
1240 11192400 : if (pvsData.isQuiet) ++pvsData.validQuietMoveCount;
1241 :
1242 11192400 : pvsData.isCheck = isPosInCheck(p2);
1243 :
1244 11192400 : const bool noCheck = !pvsData.isInCheck && !pvsData.isCheck;
1245 :
1246 22384800 : pvsData.isAdvancedPawnPush = PieceTools::getPieceType(p, Move2From(*it)) == P_wp && (SQRANK(to) > 5 || SQRANK(to) < 2);
1247 11192400 : pvsData.earlyMove = pvsData.validMoveCount < (2 /*+2*pvsData.rootnode*/);
1248 :
1249 11192400 : PVList childPV;
1250 : // PVS
1251 11192400 : if (pvsData.earlyMove || !SearchConfig::doPVS){
1252 805068 : stack[p2.halfmoves].p = p2;
1253 805068 : stack[p2.halfmoves].h = p2.h;
1254 : #ifdef WITH_NNUE
1255 805068 : NNUEEvaluator newEvaluator = p.evaluator();
1256 : p2.associateEvaluator(newEvaluator);
1257 805068 : applyMoveNNUEUpdate(p2, moveInfo);
1258 : #endif
1259 : // get depth of next search
1260 : // Remember that if no tt hit, depth has been reduced already (by IIR)
1261 : const auto [nextDepth, extension, reduction] = depthPolicy(p, depth, height, *it, pvsData, evalData, evalScore, extensions, false);
1262 805068 : score = -pvs<pvnode>(-beta, -alpha, p2, nextDepth, height + 1, childPV, seldepth, static_cast<DepthType>(extensions + extension), pvsData.isCheck, false);
1263 805068 : ++pvsData.validNonPrunedCount;
1264 : }
1265 : else {
1266 : // reductions & prunings
1267 10387332 : const bool isPrunable = /*pvsData.isNotPawnEndGame &&*/ !pvsData.isAdvancedPawnPush && !isMateScore(alpha) && !killerT.isKiller(*it, height) && !DynamicConfig::mateFinder;
1268 10387332 : const bool isReductible = SearchConfig::doLMR && depth >= SearchConfig::lmrMinDepth && /*pvsData.isNotPawnEndGame &&*/ !pvsData.isAdvancedPawnPush && !DynamicConfig::mateFinder;
1269 10387332 : const bool isPrunableStd = isPrunable && pvsData.isQuiet;
1270 10387332 : const bool isPrunableStdNoCheck = isPrunableStd && noCheck;
1271 20715573 : const bool isPrunableCap = isPrunable && Move2Type(*it) == T_capture && noCheck;
1272 400989 : const bool isPrunableBadCap = isPrunableCap && isBadCap(*it);
1273 :
1274 : // skip quiet if LMP was triggered
1275 10387332 : if (skipQuiet && pvsData.isQuiet && noCheck && isPrunableStdNoCheck){
1276 : stats.incr(Stats::sid_lmp);
1277 13841942 : continue;
1278 : }
1279 : // skip other bad capture
1280 4149634 : if (skipCap && Move2Type(*it) == T_capture && isPrunableBadCap){
1281 : stats.incr(Stats::sid_see2);
1282 51900 : continue;
1283 : }
1284 :
1285 : // forward pruning heuristic for quiet moves
1286 3932809 : if (isPrunableStdNoCheck){
1287 : // futility
1288 2726557 : if (pvsData.futility) {
1289 : stats.incr(Stats::sid_futility);
1290 : skipQuiet = true;
1291 112670 : continue;
1292 : }
1293 :
1294 : // LMP
1295 2613887 : if (pvsData.lmp && pvsData.validMoveCount > SearchConfig::lmpLimit[pvsData.improving][depth + depthCorrection]) {
1296 : stats.incr(Stats::sid_lmp);
1297 : skipQuiet = true;
1298 220505 : continue;
1299 : }
1300 :
1301 : // History pruning (including CMH)
1302 2577458 : if (pvsData.historyPruning &&
1303 368152 : Move2Score(*it) < SearchConfig::historyPruningCoeff.threshold(depth, evalData.gp, pvsData.improving, pvsData.cutNode)) {
1304 : stats.incr(Stats::sid_historyPruning);
1305 : skipQuiet = true;
1306 33122 : continue;
1307 : }
1308 :
1309 : // CMH pruning alone
1310 2360260 : if (pvsData.CMHPruning ) {
1311 526842 : if (isCMHBad(p, Move2From(*it), Move2To(*it), pvsData.cmhPtr, SearchConfig::CMHMargin)) {
1312 : stats.incr(Stats::sid_CMHPruning);
1313 88589 : continue;
1314 : }
1315 : }
1316 : }
1317 : else{
1318 : // capture history pruning (only std cap)
1319 1440650 : if (pvsData.capHistoryPruning && isPrunableCap &&
1320 234398 : historyT.historyCap[PieceIdx(p.board_const(Move2From(*it)))][to][Abs(p.board_const(to))-1] < SearchConfig::captureHistoryPruningCoeff.threshold(depth, evalData.gp, pvsData.improving, pvsData.cutNode)){
1321 : stats.incr(Stats::sid_capHistPruning);
1322 9358 : continue;
1323 : }
1324 :
1325 : // SEE (capture)
1326 1196894 : if (!pvsData.rootnode && isPrunableBadCap) {
1327 219806 : if (pvsData.futility) {
1328 : stats.incr(Stats::sid_see);
1329 : skipCap = true;
1330 40178 : continue;
1331 : }
1332 267419 : else if ( badCapScore(*it) < - (SearchConfig::seeCaptureInit + SearchConfig::seeCaptureFactor * (depth - 1 + std::max(0, dangerGoodAttack - dangerUnderAttack)/SearchConfig::seeCapDangerDivisor))) {
1333 : stats.incr(Stats::sid_see2);
1334 : skipCap = true;
1335 109700 : continue;
1336 : }
1337 : }
1338 : }
1339 :
1340 : // get depth of next search
1341 : // Remember that if no tt hit, depth has been reduced already (by IIR)
1342 3318687 : auto [nextDepth, extension, reduction] = depthPolicy(p, depth, height, *it, pvsData, evalData, evalScore, extensions, isReductible);
1343 :
1344 : // SEE (quiet)
1345 : ScoreType seeValue = 0;
1346 3318687 : if (isPrunableStdNoCheck) {
1347 2271671 : seeValue = SEE(p, *it);
1348 3234634 : if (!pvsData.rootnode && seeValue < - (SearchConfig::seeQuietInit + SearchConfig::seeQuietFactor * (nextDepth - 1) * (nextDepth + std::max(0, dangerGoodAttack - dangerUnderAttack)/SearchConfig::seeQuietDangerDivisor))){
1349 : stats.incr(Stats::sid_seeQuiet);
1350 370674 : continue;
1351 : }
1352 : // reduce bad quiet more
1353 : //else if (seeValue < 0 && nextDepth > 1) --nextDepth;
1354 : }
1355 :
1356 2948013 : ++pvsData.validNonPrunedCount;
1357 :
1358 : // PVS
1359 2948013 : stack[p2.halfmoves].p = p2;
1360 2948013 : stack[p2.halfmoves].h = p2.h;
1361 : #ifdef WITH_NNUE
1362 2948013 : NNUEEvaluator newEvaluator = p.evaluator();
1363 : p2.associateEvaluator(newEvaluator);
1364 2948013 : applyMoveNNUEUpdate(p2, moveInfo);
1365 : #endif
1366 2948013 : score = -pvs<false>(-alpha - 1, -alpha, p2, nextDepth, height + 1, childPV, seldepth, static_cast<DepthType>(extensions + extension), pvsData.isCheck, true);
1367 2948013 : if (reduction > 0 && score > alpha) {
1368 : stats.incr(Stats::sid_lmrFail);
1369 : childPV.clear();
1370 37143 : score = -pvs<false>(-alpha - 1, -alpha, p2, depth - 1 + extension, height + 1, childPV, seldepth, static_cast<DepthType>(extensions + extension), pvsData.isCheck, !pvsData.cutNode);
1371 : /*
1372 : if (pvsData.isQuiet){
1373 : if (score > alpha) historyT.update<1>(nextDepth, *it, p, pvsData.cmhPtr);
1374 : else historyT.update<-1>(nextDepth, *it, p, pvsData.cmhPtr);
1375 : }
1376 : */
1377 : /*
1378 : else{
1379 : if (score > alpha) historyT.updateCap<1>(nextDepth, *it, p);
1380 : else historyT.updateCap<-1>(nextDepth, *it, p);
1381 : }
1382 : */
1383 : }
1384 2948013 : if ( score > alpha && (pvsData.rootnode || score < beta)) {
1385 : stats.incr(Stats::sid_pvsFail);
1386 : childPV.clear();
1387 : // potential new pv node
1388 2957 : score = -pvs<true>(-beta, -alpha, p2, depth - 1 + extension, height + 1, childPV, seldepth, static_cast<DepthType>(extensions + extension), pvsData.isCheck, false);
1389 : }
1390 : }
1391 :
1392 3753081 : if (stopFlag) return STOPSCORE;
1393 :
1394 3753079 : if (pvsData.rootnode) {
1395 28070 : rootScores.emplace_back(*it, score);
1396 : }
1397 3753079 : if (score > bestScore) {
1398 1202232 : if (pvsData.rootnode) previousBest = *it;
1399 : bestScore = score;
1400 1202232 : bestMove = *it;
1401 1202232 : pvsData.bestMoveIsCheck = pvsData.isCheck;
1402 : //bestScoreUpdated = true;
1403 1202232 : if (score > alpha) {
1404 : if constexpr(pvnode) updatePV(pv, bestMove, childPV);
1405 536525 : pvsData.alphaUpdated = true;
1406 536525 : alpha = score;
1407 : hashBound = TT::B_exact;
1408 536525 : if (score >= beta) {
1409 : stats.incr(Stats::sid_beta);
1410 : #ifdef WITH_BETACUTSTATS
1411 : updateStatBetaCut(p, *it, height);
1412 : #endif
1413 533836 : if (!pvsData.isInCheck){
1414 378760 : const DepthType bonusDepth = depth + (score > beta + SearchConfig::betaMarginDynamicHistory);
1415 378760 : if (pvsData.isQuiet /*&& depth > 1*/ /*&& !( depth == 1 && validQuietMoveCount == 1 )*/) { // quiet move history
1416 : // increase history of this move
1417 107847 : updateTables(*this, p, bonusDepth, height, bestMove, TT::B_beta, pvsData.cmhPtr);
1418 : // reduce history of all previous
1419 285119 : for (auto it2 = moves.begin(); it2 != moves.end() && !sameMove(*it2, bestMove); ++it2) {
1420 177272 : if (Move2Type(*it2) == T_std)
1421 : historyT.update<-1>(bonusDepth, *it2, p, pvsData.cmhPtr);
1422 : }
1423 : }
1424 270913 : else if ( isCapture(bestMove)){ // capture history
1425 : historyT.updateCap<1>(bonusDepth, bestMove, p);
1426 395563 : for (auto it2 = moves.begin(); it2 != moves.end() && !sameMove(*it2, bestMove); ++it2) {
1427 125372 : if (isCapture(*it2))
1428 : historyT.updateCap<-1>(bonusDepth, *it2, p);
1429 : }
1430 : }
1431 : }
1432 : hashBound = TT::B_beta;
1433 : break;
1434 : }
1435 : stats.incr(Stats::sid_alpha);
1436 : }
1437 : }
1438 2550847 : else if (pvsData.rootnode && !pvsData.isInCheck && pvsData.earlyMove && score < alpha - SearchConfig::failLowRootMargin) {
1439 0 : return alpha - SearchConfig::failLowRootMargin;
1440 : }
1441 : }
1442 :
1443 1038420 : if (alphaInit == alpha ) stats.incr(Stats::sid_alphanoupdate);
1444 :
1445 : // check for draw and check mate
1446 1038420 : if (pvsData.validMoveCount == 0){
1447 4015 : return !pvsData.withoutSkipMove ? alpha : pvsData.isInCheck ? matedScore(height) : drawScore(p, height);
1448 : //return (pvsData.isInCheck || !pvsData.withoutSkipMove) ? matedScore(height) : drawScore(p, height);
1449 : }
1450 : // post move loop version
1451 1034405 : else if (is50moves(p,false)){
1452 0 : return drawScore(p, height);
1453 : }
1454 :
1455 : // insert data in TT
1456 1034405 : TT::setEntry(*this, pHash, bestMove, TT::createHashScore(bestScore, height), TT::createHashScore(evalScore, height),
1457 1034405 : static_cast<TT::Bound>(hashBound |
1458 1034405 : (pvsData.ttPV ? TT::B_ttPVFlag : TT::B_none) |
1459 2068810 : (pvsData.bestMoveIsCheck ? TT::B_isCheckFlag : TT::B_none) |
1460 1034405 : (pvsData.isInCheck ? TT::B_isInCheckFlag : TT::B_none)),
1461 : depth,
1462 1034405 : isMainThread());
1463 :
1464 : return bestScore;
1465 : }
|
