Fruit 2.1 pruning

[kongsian]

In Fruit 2.1, in the futility/delta pruning code, there is the following code.

Code: Select all

            // optimistic evaluation

            if (opt_value == +ValueInf) {
               opt_value = eval(board) + FutilityMargin;
               ASSERT&#40;opt_value<+ValueInf&#41;;
            &#125;

            value = opt_value;

            if &#40;value <= alpha&#41; &#123;

               if &#40;value > best_value&#41; &#123;
                  best_value = value;
                  PV_CLEAR&#40;pv&#41;;
               &#125;

               continue;
            &#125;

The thing I don't understand is that before pruning, the best_value is improved to value. What's the logic behind it?

Kong Sian

[Aleks Peshkov]

That is how plain alpha-beta pruning work: narrowing search window by best found value so far.

[hgm]

I guess best_value is the upper bound to the score of the node, which you return in a soft-fail scheme. So you have to update it to the upper bound of the score of the pruned move. If yuou didn't, when the pruned move could be better, best_value would no longer be a true upper bound, and later searches, retrieving it from the hash table, might take a fail low on the hash score while in fact there was a fail high.

[kongsian]

That is how plain alpha-beta pruning work: narrowing search window by best found value so far.

This is not referring to alpha-beta, rather to futility pruning. If opt_value <= alpha, the move is pruned. However before pruning, it is also used to improve best value. Since opt_value is just an estimation, I was wondering why it is okay to use it as a best value.

Kong Sian

[hgm]

Since opt_value is just an estimation, I was wondering why it is okay to use it as a best value.

Because a best_value below alpha is only an upper bound, (even if it would be based on real search scores), and the estimation was actually an estimation of an upper bound (through the addition of FutilityMargin).

[jdart]

I have had the same question about this code - if I remember correctly, futility pruning is only called on a non-PV node anyway, so won't the bounds already have been narrowed? I am not clear how often, if ever, the estimate will be > alpha but < beta.

--Jon

[Zach Wegner]

It's not alpha that's being updated, it's best_score, which is the lower bound (not upper bound) to the score. The problem that the code is addressing is that even though with futility pruning it is fairly safe to say when a move will not make it to alpha, it could still increase best_score. When the best_score is used for hashing, which it should, it would then corrupt the table with bad bounds that are too low. As a silly example, imagine a node where every single move is pruned with futility. It may indeed be a fail low node, but unless you do this safety check, best_score will be -MATE, and whenever the position is revisited it will come back as checkmate. While you should never prune every move through futility (Toga was reporting false stalemates until I bugfixed it), the same situation can happen when the real best move is pruned due to futility.

This was discussed a couple months or so ago in a thread about fail soft.

[El Gringo]

I guess best_value is the upper bound to the score of the node, which you return in a soft-fail scheme. So you have to update it to the upper bound of the score of the pruned move. If yuou didn't, when the pruned move could be better, best_value would no longer be a true upper bound, and later searches, retrieving it from the hash table, might take a fail low on the hash score while in fact there was a fail high.

Hi,

Nice flag !!!

Best
Johan

[kongsian]

It's not alpha that's being updated, it's best_score, which is the lower bound (not upper bound) to the score. The problem that the code is addressing is that even though with futility pruning it is fairly safe to say when a move will not make it to alpha, it could still increase best_score. When the best_score is used for hashing, which it should, it would then corrupt the table with bad bounds that are too low. As a silly example, imagine a node where every single move is pruned with futility. It may indeed be a fail low node, but unless you do this safety check, best_score will be -MATE, and whenever the position is revisited it will come back as checkmate. While you should never prune every move through futility (Toga was reporting false stalemates until I bugfixed it), the same situation can happen when the real best move is pruned due to futility.

This was discussed a couple months or so ago in a thread about fail soft.

Thanks. Have taken a look at the fail soft threat mention. It's clearer to me now.

Kong Sian