Engin wrote:hello,
what i am until now not understand is that the stockfish team stay on the futility pruning with predicted depth instead of normal depth.
what have the LMR depth to do with futility ?
code from stockfish:
Depth predictedDepth = newDepth - reduction<NonPV>(depth, moveCount);
futilityValueScaled = futilityBase + futility_margin(predictedDepth, moveCount)
+ H.gain(pos.piece_on(move_from(move)), move_to(move));
but on Glaurung 2.2 code used with normal depth:
if(depth < 6 * OnePly && approximateEval < beta) {
if(futilityValue == VALUE_NONE)
futilityValue = evaluate(pos, ei, threadID)
+ ((depth < 2 * OnePly)?
FutilityMargin1 :
FutilityMargin2 + (depth - 2*OnePly) * 32);
I don't now the code of Stockfish 2.1 very well but I think this is not such a big change, also it is not changed from version 2.0 to 2.1, using the predicted depth is reasonably "logical" because if a move passes futility pruning it is then searched first with a reduced depth:
Code: Select all
{
// Step 14. Reduced depth search
// If the move fails high will be re-searched at full depth.
bool doFullDepthSearch = true;
alpha = SpNode ? sp->alpha : alpha;
if ( depth >= 3 * ONE_PLY
&& !captureOrPromotion
&& !dangerous
&& !move_is_castle(move)
&& ss->killers[0] != move
&& ss->killers[1] != move)
{
ss->reduction = reduction<PvNode>(depth, moveCount);
if (ss->reduction)
{
alpha = SpNode ? sp->alpha : alpha;
Depth d = newDepth - ss->reduction;
value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, d);
doFullDepthSearch = (value > alpha);
}
ss->reduction = DEPTH_ZERO; // Restore original reduction
}
It only means that the futilty margin will a little bit smaller using predicted depth as an index, but it just depends what numbers are used for the futility margin really. reduction<NonPV>(depth, moveCount); is anyway a fairly small number as far as I could see, I have not made a table but it seemed to me in most cases smaller than ONE_PLY.
In the PV (especially) I would prefer less reductions in the sidebranches but that is also a case of the overall 'architecture' of search, if you just do a lot of iterations you have more reordering of the searchtree and if you do more extensions instead, you do less reordering.
the second one is that in Glaurung using move count pruning until depth 7 , but in stockfish they are pruning until depth 16 ??
is that not to much of risk ??
I think this must depend also to some degree on the number of iterations you achieve typically but this indeed some risk, IMO. Tord used to say some time ago that he tested larger numbers but even on small devices like the iPhone seven seemed to be the right number for Glaurung, for the extended quiescence search or how you would call it. But in Rainbow Serpent I actually use depth sixteen
also for value based Futility Pruning, not just move based Futility Pruning. But I do try to make it a bit safer by a lot of other measures, some of them undo a lot of the reduction effects and some measures are very little tested.
So there is in Rainbow Serpent:
Code: Select all
inline Value futility_margin(Depth d, int mn) { return d < 16 * ONE_PLY ? FutilityMarginsMatrix[Max(d, 1)][Min(mn, 63)] : 2 * VALUE_INFINITE; }
inline int futility_move_count(Depth d) { return d < 16 * ONE_PLY ? FutilityMoveCountArray[d] : 512; }
but for instance I used different values in the FutilityMarginsMatrix
Code: Select all
// Init futility margins array
for (d = 1; d < 16; d++) for (mc = 0; mc < 64; mc++)
FutilityMarginsMatrix[d][mc] = Value (Max((100 + (d * d)) * int(log(double(d * d) / 2) / log(2.0) + 1.001) - ((d+5) * (mc+1) - 45), 45));
some of the new values are actually smaller than the original values but after a certain depth they rise a bit faster, that is if I have not made an wrong calculation in the formula used? Also for instance Rainbow Serpent has a different futilityBase so that changes futility pruning there also, I think futilityBase is usually smaller so that means less chance of getting above beta so a bit more chance of pruning the move. (And then there is actually a "double pass" futility pruning in place in Rainbow Serpent with different, usually higher, added Futilty margins so even less chance of getting through the futility pruning
)
Regards, Eelco