Шахматные программы. Общие вопросы

996 	MovePicker mp(pos, ttData.move, depth, &mainHistory, &lowPlyHistory, &captureHistory, contHist,

997 	              &sharedHistory, ss->ply);

999 	value = bestValue;

1001 	int moveCount = 0;

1003 	// Step 13. Loop through all pseudo-legal moves until no moves remain

1004 	// or a beta cutoff occurs.

1005 	while ((move = mp.next_move()) != Move::none())

1006 	{

...	    ...

1009 	    if (move == excludedMove)

1010 	        continue;



1012 	    // Check for legality

1013 	    if (!pos.legal(move))

1014 	        continue;

...	    ...

1022 	    ss->moveCount = ++moveCount;

...	    ...

1029 	    if (PvNode)

1030 	        (ss + 1)->pv = nullptr;



1032 	    extension  = 0;

1033 	    capture    = pos.capture_stage(move);

1034 	    movedPiece = pos.moved_piece(move);

1035 	    givesCheck = pos.gives_check(move);



1037 	    // Calculate new depth for this move

1038 	    newDepth = depth - 1;

1049 	    // Step 14. Pruning at shallow depths.

1051 	    if (!rootNode && pos.non_pawn_material(us) && !is_loss(bestValue))

1052 	    {

1053 	        // Skip quiet moves if movecount exceeds our FutilityMoveCount threshold

1054 	        if (moveCount >= (3 + depth * depth) / (2 - improving))

1055 	            mp.skip_quiet_moves();



1057 	        // Reduced depth of the next LMR search

1058 	        int lmrDepth = newDepth - r / 1024;



1060 	        if (capture || givesCheck)

1061 	        {

...	        ...

1081 	        }

1082 	        else

1083 	        {

1084 	            int history = (*contHist[0])[movedPiece][move.to_sq()]

1085 	                               + (*contHist[1])[movedPiece][move.to_sq()]

1086 	                               + sharedHistory.pawn_entry(pos)[movedPiece][move.to_sq()];



1088 	            // Continuation history based pruning

1089 	            if (history < -4083 * depth)

1090 	                continue;



1092 	            history += 69 * mainHistory[us][move.raw()] / 32;

1095 	            lmrDepth += history / 3208;

1097 	            Value futilityValue = ss->staticEval + 42 + 161 * !bestMove + 127 * lmrDepth

1098 	                                + 85 * (ss->staticEval > alpha);



1100 	            // Futility pruning: parent node

1103 	            if (!ss->inCheck && lmrDepth < 13 && futilityValue < = alpha)

1104 	            {

1105 	                if (bestValue < = futilityValue && !is_decisive(bestValue)

1106 	                    && !is_win(futilityValue))

1107 	                    bestValue = futilityValue;

1108 	                continue;

1109 	            }



1111 	            lmrDepth = std::max(lmrDepth, 0);



1113 	            // Prune moves with negative SEE

1114 	            if (!pos.see_ge(move, -25 * lmrDepth * lmrDepth))

1115 	                continue;

1116 	        }

1117 	    }

1119 	    // Step 15. Extensions

1120 	    // Singular extension search

1129 	    if (!rootNode && move == ttData.move && !excludedMove && depth >= 6 + ss->ttPv

1130 	        && is_valid(ttData.value) && !is_decisive(ttData.value) && (ttData.bound & BOUND_LOWER)

1131 	        && ttData.depth >= depth - 3 && !is_shuffling(move, ss, pos))

1132 	    {

1133 	        Value singularBeta  = ttData.value - (53 + 75 * (ss->ttPv && !PvNode)) * depth / 60;

1134 	        Depth singularDepth = newDepth / 2;



1136 	        ss->excludedMove = move;

1137 	        value = search< NonPV>(pos, ss, singularBeta - 1, singularBeta, singularDepth, cutNode);

1138 	        ss->excludedMove = Move::none();



1140 	        if (value < singularBeta)

1141 	        {

1142 	            int corrValAdj   = std::abs(correctionValue) / 230673;

1143 	            int doubleMargin = -4 + 199 * PvNode - 201 * !ttCapture - corrValAdj

1144 	                             - 897 * ttMoveHistory / 127649 - (ss->ply > rootDepth) * 42;

1145 	            int tripleMargin = 73 + 302 * PvNode - 248 * !ttCapture + 90 * ss->ttPv - corrValAdj

1146 	                             - (ss->ply * 2 > rootDepth * 3) * 50;



1148 	            extension =

1149 	              1 + (value < singularBeta - doubleMargin) + (value < singularBeta - tripleMargin);



1151 	            depth++;

1152 	        }



1154 	        // Multi-cut pruning

1160 	        else if (value >= beta && !is_decisive(value))

1161 	        {

1162 	            ttMoveHistory < < std::max(-400 - 100 * depth, -4000);

1163 	            return value;

1164 	        }



1166 	        // Negative extensions



1173 	        // If the ttMove is assumed to fail high over current beta

1174 	        else if (ttData.value >= beta)

1175 	            extension = -3;



1177 	        // If we are on a cutNode but the ttMove is not assumed to fail high over current beta

1179 	        else if (cutNode)

1180 	            extension = -2;

1181 	    }

1183 	    // Step 16. Make the move

1184 	    do_move(pos, move, st, givesCheck, ss);

1037 	    // Calculate new depth for this move

1038 	    newDepth = depth - 1;

1040 	    int delta = beta - alpha;

1042 	    Depth r = reduction(improving, depth, moveCount, delta);

...	    ...

1186 	    // Add extension to new depth

1187 	    newDepth += extension;

...	    ...

1199 	    // Increase reduction for cut nodes

1200 	    if (cutNode)

1201 	        r += 3372 + 997 * !ttData.move;



1203 	    // Increase reduction if ttMove is a capture

1204 	    if (ttCapture)

1205 	        r += 1119;

...	    ...

1226 	    // Scale up reductions for expected ALL nodes

1227 	    if (allNode)

1228 	        r += r / (depth + 1);

1230 	    // Step 17. Late moves reduction / extension (LMR)

1231 	    if (depth >= 2 && moveCount > 1)

1232 	    {

1238 	        Depth d = std::max(1, std::min(newDepth - r / 1024, newDepth + 2)) + PvNode;



1240 	        ss->reduction = newDepth - d;

1241 	        value         = -search< NonPV>(pos, ss + 1, -(alpha + 1), -alpha, d, true);

1242 	        ss->reduction = 0;



1244 	        // Do a full-depth search when reduced LMR search fails high

1246 	        if (value > alpha)

1247 	        {

1248 	            // Adjust full-depth search based on LMR results - if the result was

1249 	            // good enough search deeper, if it was bad enough search shallower.

1250 	            const bool doDeeperSearch    = d < newDepth && value > bestValue + 50;

1251 	            const bool doShallowerSearch = value < bestValue + 9;



1253 	            newDepth += doDeeperSearch - doShallowerSearch;



1255 	            if (newDepth > d)

1256 	                value = -search< NonPV>(pos, ss + 1, -(alpha + 1), -alpha, newDepth, !cutNode);



1258 	            // Post LMR continuation history updates

1259 	            update_continuation_histories(ss, movedPiece, move.to_sq(), 1365);

1260 	        }

1261 	    }

1263 	    // Step 18. Full-depth search when LMR is skipped

1264 	    else if (!PvNode || moveCount > 1)

1265 	    {

...	    ...

1270 	        // Note that if expected reduction is high, we reduce search depth here

1271 	        value = -search< NonPV>(pos, ss + 1, -(alpha + 1), -alpha,

1272 	                               newDepth - (r > 3957) - (r > 5654 && newDepth > 2), !cutNode);

1273 	    }



1275 	    // For PV nodes only, do a full PV search on the first move or after a fail high,

1276 	    // otherwise let the parent node fail low with value < = alpha and try another move.

1277 	    if (PvNode && (moveCount == 1 || value > alpha))

1278 	    {

1279 	        (ss + 1)->pv    = pv;

1280 	        (ss + 1)->pv[0] = Move::none();



1282 	        // Extend move from transposition table if we are about to dive into qsearch.

1283 	        // decisive score handling improves mate finding and retrograde analysis.

1284 	        if (move == ttData.move

1285 	            && ((is_valid(ttData.value) && is_decisive(ttData.value) && ttData.depth > 0)

1286 	                || ttData.depth > 1))

1287 	            newDepth = std::max(newDepth, 1);



1289 	        value = -search< PV>(pos, ss + 1, -beta, -alpha, newDepth, false);

1290 	    }

1292 	    // Step 19. Undo move

1293 	    undo_move(pos, move);

1297 	    // Step 20. Check for a new best move

1298 	    // Finished searching the move. If a stop occurred, the return value of

1299 	    // the search cannot be trusted, and we return immediately without updating

1300 	    // best move, principal variation nor transposition table.

1301 	    if (threads.stop.load(std::memory_order_relaxed))

1302 	        return VALUE_ZERO;



1304 	    if (rootNode)

1305 	    {

...	    ...

1353 	    }



1355 	    // In case we have an alternative move equal in eval to the current bestmove,

1356 	    // promote it to bestmove by pretending it just exceeds alpha (but not beta).

1357 	    int inc = (value == bestValue && ss->ply + 2 >= rootDepth && (int(nodes) & 14) == 0

1358 	               && !is_win(std::abs(value) + 1));



1360 	    if (value + inc > bestValue)

1361 	    {

1362 	        bestValue = value;



1364 	        if (value + inc > alpha)

1365 	        {

1366 	            bestMove = move;



1368 	            if (PvNode && !rootNode)  // Update pv even in fail-high case

1369 	                update_pv(ss->pv, move, (ss + 1)->pv);



1371 	            if (value >= beta)

1372 	            {



1374 	                ss->cutoffCnt += (extension < 2) || PvNode;

1375 	                assert(value >= beta);  // Fail high

1376 	                break;

1377 	            }



1379 	            // Reduce other moves if we have found at least one score improvement

1380 	            if (depth > 2 && depth < 14 && !is_decisive(value))

1381 	                depth -= 2;

...	            ...		

1384 	            alpha = value;  // Update alpha! Always alpha < beta

1385 	        }

1386 	    }