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);
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 ??
futility pruning in stockfish
Moderators: hgm, Rebel, chrisw
-
- Posts: 918
- Joined: Mon Jan 05, 2009 7:40 pm
- Location: Germany
- Full name: Engin Üstün
-
- Posts: 4567
- Joined: Sun Mar 12, 2006 2:40 am
- Full name:
Re: futility pruning in stockfish
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: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);
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.
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.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 ??
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; }
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));
Regards, Eelco
Debugging is twice as hard as writing the code in the first
place. Therefore, if you write the code as cleverly as possible, you
are, by definition, not smart enough to debug it.
-- Brian W. Kernighan
place. Therefore, if you write the code as cleverly as possible, you
are, by definition, not smart enough to debug it.
-- Brian W. Kernighan