Here is my initial comparison of Crafty 22.1
search.c to that in Crafty 23.4.
There are a few irrelevant differences in declared variables. Both then peek at the clock, depending on the node count. A repetition check is made. A hash probe is made, with 22.1 having more flags (EXACT/LOWER/UPPER and AVOID_NULL_MOVE) than 23.4 (HIT/MISS/AVOID). An EGTBProbe is done.
Then null move is considered. Both use
null_depth as 3 throughout. The 22.1 version has a PLY define to allow fractional increments. The arithmetic differs slightly (
1-beta in 22.1 versus
-beta+1 in 23.4). The 22.1 version uses mate threats as a "feedback" item from null move, while 23.4 seems not to do so.
Both then do IID, where it seems 23.4 has an SMP difference. So far, so irrelevant, IMO.
The main loop over moves then commences. The 22.1 version has
SearchControl() for extensions/reductions, while 23.4 does it inline. One difference is that 22.1 extend mate threats and one-replies. Both extend moves that give check, but the 23.4 version has an
SwapO function to determine whether it is "safe". Both then do some LMR, the conditions being quite similar, involving REMAINING_MOVES phase, not extended (or: not in check and doesn't give check), moving piece is not a passed pawn, move is not a capture/promotion, depth is not too close to horizon. The number of
moves_searched can affect the size of the LMR reduction in the 23.4 version.
Except for that last sentence, I haven't seen anything of interest yet. Next is the futility, which
is more of interest (my guess is this is what Ed is talking about), and after that there is some routine stuff about re-searching,
SearchParallel in one version, etc. So I'll focus on the futility.
In the 22.1 version, the futility/razoring is from Heinz essentially: if depth is less than 3 and Material is worse than
(1+bishop_value)/2 from the scout value, drop to
qsearch; and if depth is 3 or 4 and Material is worse than
(1+queen_value)/2 from scout value, reduce by a ply.
In the 23.4 version, this has been replaced by sharper "forward pruning":
Code: Select all
if (ply > 1 && depth < pruning_depth && moves_searched && // pruning_depth is 5
MaterialSTM(wtm) + pruning_margin[depth] <= alpha) {
tree->moves_pruned++;
continue;
}
So the use of
moves_searched in LMR reductions and replacing Heinz futility/razoring via sharper pruning are the main differences I see. The next step (maybe I will address it in a later post) would be to try to determine if the specifics of either could be said to derive from other engines. My impression is that the "idea" of the latter is quite old (back to the days when moves had to be pruned to reach even 2 or 3 ply). The notes say the values were derived from cluster tested, with the
pruning_margin array as
{0, 120, 120, 310, 310, 400, 400, 500} (note that only the first few values matter, due to
pruning_depth). Note that Crafty compares
alpha to Material, while others seem to compare to some sort of evaluation.
The Crafty
main.c notes that 22.2 implemented "extended futility", while 23.1 talks about the new method (calling razoring redundant with LMR).
But thanks for taking a look at this. I can not judge the technical proof, but you seem to be one of the unbiased persons in this discussion.