hgm wrote:Why would you use different margins at d=0 and d=1 (or d=2 and d=3)? The situation is exactly the same: you are only one ply (three plies) removed from the opponent's stand-pat.
Because the risks involved. The whole idea of futility pruning is based on the fact the material score is not going to change dramatically in the last plies before the horizon. Futility pruning is present in most chess programs. For details checkout my page.
You mean that the positional score is not going to change? The material value can change by a Queen on any move, also near the horizon (as long as the opponent has a Queen), but you would know if it did trivially.
But I also don't see why the positional value of a move is limited to a lower value near the horizon. If you have moves that can improve positional value by +1, e.g. for creating a passer on the 5th rank, you would need a MARGIN of +1. Also at d=0, as the move creating this positional aspect can very well be a capture. A move that is futile at d=0 is just as futile at d=1, as the opponent is allowed to react to it in the same way. (In both cases you will get a d=0 reply.)
It seems to me that on your pages you don't keep a clear distinction between 'Lazy Eval' and 'Futility Pruning'. IMO, if you derive the Eval value from that of the previous ply, then it is not called Lazy Eval but Futility Pruning. (If you use the Eval estimate for Pruning, i.e. return it as a score. But I don't see what else you could use it for.)
Uri Blass wrote:Do you do something like the following:
if lazy evaluation>(beta+0.50) and the last move was no checking move return beta;
It depends at which level you are talking. Usually you consider the score at the level where you generate the move, but decide not to search it. There the condition would be
This is similar to what you propose one level deeper (but saving you the call and return). The difference is that LazyEval is usually something that is done from scratch, while the evaluation estimate used in futility pruning is based on a full evaluation plus an estimate of the differential update (which can be much more accurate for moves that cannot have a large positional impact).
At d=0 you only consider captures, but with futility pruning you ignore captures that cannot possibly raise the evaluation score above Alpha. Because you know the move will at most return that evaluation score, as the opponent can always stand pat in the reply.
That is exactly the same at d=1. The only difference is that at d=1 you also apply it to non-captures. But I see no reason why captures could not have positional gains at least as big as non-captures.
1)I understand what you mean.
I thought about pruning like if eval>beta+margin return beta.
I understand that we talk about pruning of the type
if (eval after move that I may prune)<alpha-margin return alpha.
practically I use both types of pruning.
I considered both of them as futility.
2)It seems to me that you are right that you practically can use the same margin when remaining depth is 0 and when remaining depth is 1 except the fact that you may generate all moves when remaining depth is 1 and you generate only part of them when remaining depth is 0(I do not say only captures because most programs generate also checks in part of the cases and reply to checks)
Checks seems not to be relevant if we assume that pruning is not used for checking moves.
The only reason that I can see for bigger risk at depth=1 is in case that you know that your pruning is not sound and may give wrong results and the risk to get wrong result is smaller at depth=0 when you consider part of the moves relative to the case when the depth=1 and you consider all the moves.
hgm wrote:You mean that the positional score is not going to change? The material value can change by a Queen on any move, also near the horizon (as long as the opponent has a Queen), but you would know if it did trivially.
But I also don't see why the positional value of a move is limited to a lower value near the horizon. If you have moves that can improve positional value by +1, e.g. for creating a passer on the 5th rank, you would need a MARGIN of +1. Also at d=0, as the move creating this positional aspect can very well be a capture. A move that is futile at d=0 is just as futile at d=1, as the opponent is allowed to react to it in the same way. (In both cases you will get a d=0 reply.)
It seems to me that on your pages you don't keep a clear distinction between 'Lazy Eval' and 'Futility Pruning'. IMO, if you derive the Eval value from that of the previous ply, then it is not called Lazy Eval but Futility Pruning. (If you use the Eval estimate for Pruning, i.e. return it as a score. But I don't see what else you could use it for.)
based on my knowledge What Ed describes as lazy evaluation is based on knowledge of full evaluation in previous plies.
It seems to me that you assume sound pruning(0% risk) when pruning that has a small probability to be unsound is practically better in games.
Uri Blass wrote:based on my knowledge What Ed describes as lazy evaluation is based on knowledge of full evaluation in previous plies.
Yes!
That is my solution to the dangers of Futility Pruning & Lazy Eval. Else use bigger margins as the originator of the idea (Ernst Heinz) suggested, but then the algorithm is less powerful. Here is the URL of Heinz initial work.
I agree that the error bounds at d=0 and d=1 are the same.
It does not mean that the margin should be the same(when I assume pruning that take some risk of being wrong)
and the only way to know what is better is by testing.
Well, I expect requiring a different reliability at d=0 and d=1 merely to invite horizon effect, which QS was designed to prevent. If a certain capture has disastrous positional drawbacks (e.g. the recapture gives the opponent an advanced passer) it will push the capture to QS and count itself rich, just as withut QS it will push the swapoff of a high piece to the horizon (playing ostrich for the recapture). Very bad idea.
hgm wrote:A move that is futile at d=0 is just as futile at d=1, as the opponent is allowed to react to it in the same way. (In both cases you will get a d=0 reply.)
In some engines the behavior at d=0 is different from d=-1, e.g. by allowing checking moves in the first case.
hgm wrote:Well, I expect requiring a different reliability at d=0 and d=1 merely to invite horizon effect, which QS was designed to prevent. If a certain capture has disastrous positional drawbacks (e.g. the recapture gives the opponent an advanced passer) it will push the capture to QS and count itself rich, just as withut QS it will push the swapoff of a high piece to the horizon (playing ostrich for the recapture). Very bad idea.
I do not understand what you mean
Assume that you have something like Rxa7 bxa7 when bxa7 creates a passed pawn so Rxa7 is not good for positional reasons.
I understand that this is the type of the example that you mean.
I also understand that without futility pruning
the program search Rxa7 bxa7 and decide that white is better because of the passed pawn and Rxa7 is not good.
What is going to happen with futility pruning.
Rxa7 is going to be searched because this capture is not futile capture assuming no bxa7.
The only danger is that the program is not going to search bxa7 so I do not see how futility at d=1 is relevant here.
