Selective Futlity Condition at Quiescence Nodes

[diepeveen]

Code: Select all

 view pruning near the leaves (e.g. any scheme with a "depth <= 4" condition, plain futility being "depth = 1") as a speed improvement (although one with risk), as they affect IMO only a roughly constant proportion of nodes at most (say 20%), no matter the iteration number.


you are right branching factor will not decrease by a significant amount.
standard futility pruning at depth == 1 is the same as Lazy eval
at top of quiescence search. Both sac positional aspect of eval for speed.
regards
daniel

Hi, you mix 2 things perhaps.

If you do not see a few moves at depthleft == 1, say you only see a move or 10 and the other 30 you throw away, you still get accurate scores back for those 10 moves.

However lazy evaluation you *modify* with a few metarules the positions score.

So lazy evaluation is far more dangerous than killing a few moves at depthleft == 1.

In either case of course, Fabien is correct, it doesn't improve branching factor. Note that pruning last 3 ply in my experience gives 2 ply extra search depth if you limit the number of tactical moves you look at.

Vincent

[Daniel Shawul]

HI vincent
I do not get it. Those moves that are not pruned at depth 1 (first 10 in this case), will not be lazy evaluated at quiescence. the condition for standard futility pruning and lazy evaluation at top of qsearch is the same.
score + margin < alpha score - margin > beta
since i use the same margin for both, i don't need to do standard futility pruning as those futile moves get pruned after makin a move.
The positions score will be the same as long as you use the same margin.
I agree that both speed up the search. But any pruning decrease branching factor in general. If i count nodes that are pruned by futility as "full" nodes, doesnt that mean branching factor has decreased.
daniel

[Daniel Shawul]

Code: Select all

will not be lazy evaluated at quiescence. the condition for standard futility pruning and lazy evaluation at top of qsearch is the same

^^^^^^^^^^
stand pat condition

[diepeveen]

HI vincent
I do not get it. Those moves that are not pruned at depth 1 (first 10 in this case), will not be lazy evaluated at quiescence. the condition for standard futility pruning and lazy evaluation at top of qsearch is the same.
daniel

The difference is that if you lazy evaluate, my engine is 100 points tactical weaker. If you forward prune last 3 plies by just seeing a few nodes, you are 300 points tactical stronger.

So a difference of a factor 400 tactical *instantly*.

If you do not see why, then please go think longer about this.

Like what store in hashtables at depthleft == 1 for seeing 'a few moves always' versus lazy evaluation which will positional and tactical rape your score and engines play.

It's easy to use a little bit of chessknowledge at last few ply depths to select which moves to visit. The same type of chessknowledge won't work for lazy evaluation however. Only a full eval can give the score there.

Note that i don't say forward pruning last 3 plies is a good idea, but from tactical viewpoint it sure can modify diep into a tactician world has not seen before (and it scores 20% less in games at 3 hours a move, because games at standard time control tactics is pretty irrelevant).

score + margin < alpha score - margin > beta
since i use the same margin for both, i don't need to do standard futility pruning as those futile moves get pruned after makin a move.
The positions score will be the same as long as you use the same margin.
I agree that both speed up the search. But any pruning decrease branching factor in general. If i count nodes that are pruned by futility as "full" nodes, doesnt that mean branching factor has decreased.
daniel

[Daniel Shawul]

Code: Select all

The difference is that if you lazy evaluate, my engine is 100 points tactical weaker. If you forward prune last 3 plies by just seeing a few nodes, you are 300 points tactical stronger.


Lazy evaluation hurts *positional* knowledge, not tactics.
Futility pruning also hurts postional knowledge. Sow what you said above is wrong. They both rely on current material score to decide whether to continue the search. So i think you should think over it.

[Daniel Shawul]

Same is true for futility pruning done inside qsearch, sometimes known as delta pruning. Having lazy eval and futilty pruning both is redundant.

[Uri Blass]

Code: Select all

The difference is that if you lazy evaluate, my engine is 100 points tactical weaker. If you forward prune last 3 plies by just seeing a few nodes, you are 300 points tactical stronger.


Lazy evaluation hurts *positional* knowledge, not tactics.
Futility pruning also hurts postional knowledge. Sow what you said above is wrong. They both rely on current material score to decide whether to continue the search. So i think you should think over it.

Correction(I deleted my previous words when I edited the post):
It seems that I did not read Vincent post correctly.

I found the opposite to Vincent.

I found that pruning in the last plies based on evaluation and depth and other factors can be counter productive in test suites and productive in games.

I think that it is possible to fix the tactical problem without reduction in playing strength by having better conditions when not to prune and I did something about it later.

Uri

[Daniel Shawul]

Uri please explain this to me.

I am talking about *standard* futility pruning done at horizon nodes and
quiescence search. Isn't it true that this kind of futility pruning is the same as lazy eval. IE having both is redundant as long as your make move is fast.
Other kinds of futility pruning , like extended futlity pruning or something, will sure increase tactical strength much more than lazy eval does. But my point is with the standard futility pruning.
thanks
daniel

[Uri Blass]

I probably do not do standard futility pruning and I do not know what is the standard.


I understand that standard means pruning that save only one make move.

I do forward pruning when the remaining depth is small based on evaluation depth and other factors but it is not done only when there is one make move to do.

I often prune when the remaining depth is more than 1.
If it is called extended futility pruning then it is not clear to me that it is going to improve tatical strength and the question is what are the conditions for pruning.

To be more correct I did not find that my pruning was counter productive in test suites(I did not test recently the relevant pruning against no pruning in test suite) but I found that more aggresive pruning based on evaluation was productive in games and counter productive in test suites.

Uri

[Uri Blass]

Note also that I talk here only about pruning and not about reductions.

Note that I do also reductions in history based pruning and I compared recently results without them and with them and it seems that I get only 0.5-1 ply thanks for history based pruning even after some minutes of search but it clearly help me in test suites and probably also in games.

I remember that in the past history based reduction was more productive in test suites and I guess that aggresive pruning based on evaluation in the last plies made it less productive.

Uri

[Daniel Shawul]

Standard fp means sound futility pruning where no error is involved.
Extended and other prunings done with more depth left are not justified, and we
do them only to gain speed. I think extended futility pruning cause both tactical and
positinal problems as this is very unsound. The speed gain may/may not cover up for this loss depending on the engine. For me it works.

I do not know how you do history pruning. But as you pointed out this
may make fp less productive as the reduction alone reduces the branching factor a lot. Ofcourse this needs lot of testing with long time controls ,but i did not test it.

daniel

[diepeveen]

Code: Select all

The difference is that if you lazy evaluate, my engine is 100 points tactical weaker. If you forward prune last 3 plies by just seeing a few nodes, you are 300 points tactical stronger.


Lazy evaluation hurts *positional* knowledge, not tactics.
Futility pruning also hurts postional knowledge. Sow what you said above is wrong. They both rely on current material score to decide whether to continue the search. So i think you should think over it.

Lazy evaluation especially hurts tactical play, because 99% of all 'deep' combinations by todays agressive engines get found by positional scores, not because of material only.

pruning at 1 ply depthleft, again that's not futility as by definition of Heinz, but visiting a few moves there always and for the remainder skip the rest, that's quite different and less harmful than lazy evaluation in this matter.

Usually to decide whether you visit a move, you look at the evaluation before, in order to take a decision. So you look at a few moves always.

Lazy evaluation on the other hand has to figure out from the sky whether capturing that pawn has managed to raise the score to above alpha.

Who knows, perhaps capturing that pawn means you have 3 connected passers now?

Lazy eval won't see that of course. However if you do a lot of work at 1 ply depthleft to select moves, it's NO problem to always select captures to be searched. The REAL evaluation you get returned then by the quiescencesearch *without lazy eval* of course.

Note that diep is not using any futility in qsearch:
a) it would save out REAL REAL little nodes
b) i wrote thousands of lines to select which moves to try
and now some stupid single line rule is going to decide
that i selected a move to try for nothing?

So move selection in qsearch is alfa/beta independant in Diep.

I do realize however that a lot is possible last few plies. As you do a nullmove with -qsearch anyway. That's pretty rude way to cut off the search, if you think about it.

Vincent

[Daniel Shawul]

Code: Select all

Lazy evaluation especially hurts tactical play, because 99% of all 'deep' combinations by todays agressive engines get found by positional scores, not because of material only.


Ok i get your point.

Code: Select all

Usually to decide whether you visit a move, you look at the evaluation before, in order to take a decision. So you look at a few moves always.

Lazy evaluation on the other hand has to figure out from the sky whether capturing that pawn has managed to raise the score to above alpha.

Who knows, perhaps capturing that pawn means you have 3 connected passers now?

Lazy evaluation on the other hand has to figure out from the sky whether capturing that pawn has managed to raise the score to above alpha.


yes. for my engine the only two places where positional score can raise
the total evaluation significantly are king safety eval and passed pawns.
Doing this before trying lazy eval will not solve my problem as this eval take a long time. So what i do right now is take care of special moves.
. When the move is captures a queen
. when the move is a pawn capture to the 7 th rank
. and moves which threaten king
So since i use the information i get from the move, and the full evaluation before the move is made, i can say my lazy eval is safe.

Code: Select all


So move selection in qsearch is alfa/beta independant in Diep.

I do realize however that a lot is possible last few plies. As you do a nullmove with -qsearch anyway. That's pretty rude way to cut off the search, if you think about it.


I understand that you do moves other than captures and checks in qsearch, so it is important for you to have a special move selection method.
How bad is using null move in qsearch? May be it is sometimes improtant to continue the search when there is some kind of threat.
I have no experience with this.
daniel

[diepeveen]

Code: Select all

Lazy evaluation especially hurts tactical play, because 99% of all 'deep' combinations by todays agressive engines get found by positional scores, not because of material only.


Ok i get your point.

Code: Select all

Usually to decide whether you visit a move, you look at the evaluation before, in order to take a decision. So you look at a few moves always.

Lazy evaluation on the other hand has to figure out from the sky whether capturing that pawn has managed to raise the score to above alpha.

Who knows, perhaps capturing that pawn means you have 3 connected passers now?

Lazy evaluation on the other hand has to figure out from the sky whether capturing that pawn has managed to raise the score to above alpha.


yes. for my engine the only two places where positional score can raise
the total evaluation significantly are king safety eval and passed pawns.
Doing this before trying lazy eval will not solve my problem as this eval take a long time. So what i do right now is take care of special moves.
. When the move is captures a queen
. when the move is a pawn capture to the 7 th rank
. and moves which threaten king
So since i use the information i get from the move, and the full evaluation before the move is made, i can say my lazy eval is safe.

Code: Select all


So move selection in qsearch is alfa/beta independant in Diep.

I do realize however that a lot is possible last few plies. As you do a nullmove with -qsearch anyway. That's pretty rude way to cut off the search, if you think about it.


I understand that you do moves other than captures and checks in qsearch, so it is important for you to have a special move selection method.
How bad is using null move in qsearch? May be it is sometimes improtant to continue the search when there is some kind of threat.
I have no experience with this.
daniel

If you have a program with a small eval which gives small scores also, you can safely lazy eval of course. As it is an inaccurate score anyway.
For years i could use lazy eval in my 10x10 international checkers program too. But later on i also had to kick it out there. By then
the evaluation function was only '4000 lines of code' to quote it in uri terms.

In diep i never had the luxury that lazy eval could work. If you make a move, thousands of patterns and tens of thousands of different scores, som of them, they will change the score.

How much?

I don't know in advance.

If i knew in advance what the impact of a move would be, then obviously i would need to evaluate at all as i could already estimate what would happen. No need for your evaluation function then in 90% of the cases.

I once did do an experiment making a fast estimation function. After 6 months of work i managed to get it estimate the evaluation within 3 pawns correct in 99% of the cases.

Then of course i searched with it, but it was tactical 200 points weaker at many different testsuites.

The reason for that appeared to be very simple, those 'huge scores' did a great job at finding tricks.

If you make a mistake with your lazy eval, the impact from tactical viewpoint is directly a ply or 4. As last 4 ply (R=3) i'm doing basically
-qsearch for a nullmove.

That means in short, that an eval in qsearch will determine last 4 ply how tactical strong you are.

Do you also see that?

And 3 ply if you use R=2 last plies.

So a good evaluation function will find tricks hands down 4 ply sooner if your eval is good.

Vincent

[Daniel Shawul]

How much "tactics" can the evaluation do? If we say a good eval is worth one ply, we can do a 1 ply search for depthleft 4,3,2 and qsearch for depthleft = 1. This will be slower in general than just using plain R=3 with a fat eval, but it will surely cover up for most of the bad effects of nullmoving at the tips. I think it might be safer to cover search problems with search.
I understand that your approach is to use R=3 everywhere with good eval and no dubious stuff. Which approach wins, i have no idea
daniel

[diepeveen]

How much "tactics" can the evaluation do? If we say a good eval is worth one ply, we can do a 1 ply search for depthleft 4,3,2 and qsearch for depthleft = 1. This will be slower in general than just using plain R=3 with a fat eval, but it will surely cover up for most of the bad effects of nullmoving at the tips. I think it might be safer to cover search problems with search.
I understand that your approach is to use R=3 everywhere with good eval and no dubious stuff. Which approach wins, i have no idea
daniel

Your assumption is wrong.

You ask: "how much tactics can eval do?"

That is a good question. Then you answer that with: "1 ply".

This is wrong.

Without eval you see 0 tactics.

Just kick out your evaluation function and search material only.

Now go try find the simplest trick, for example:

1.e4,e5 2.nf3,nc6 3.Bc4,Nd4

a) when does it see that Nxe5 is *losing*?
b) after Nxe5 when do you see Qg5 is *winning* the game?

You know. Simpler as this there is not.

Now let's discuss more advanced tricks. Just material only.
r1b2rk1/1p1nbppp/pq1p4/3B4/P2NP3/2N1p3/1PP3PP/R2Q1R1K w - - bm Rxf7;
f1f7

A simple trick from Nolot testset.

Do you honestely believe that a material only searcher will easily find Rxf7?

If so, at what search depth?

You seem to have the wrong concept why chessprograms find tactics.

Vincent

[diepeveen]

How much "tactics" can the evaluation do? If we say a good eval is worth one ply, we can do a 1 ply search for depthleft 4,3,2 and qsearch for depthleft = 1. This will be slower in general than just using plain R=3 with a fat eval, but it will surely cover up for most of the bad effects of nullmoving at the tips. I think it might be safer to cover search problems with search.
I understand that your approach is to use R=3 everywhere with good eval and no dubious stuff. Which approach wins, i have no idea
daniel

about winning approach: Zappa became world champion with this 'diep' approach. So there is your proof.

Vincent

[Uri Blass]

How much "tactics" can the evaluation do? If we say a good eval is worth one ply, we can do a 1 ply search for depthleft 4,3,2 and qsearch for depthleft = 1. This will be slower in general than just using plain R=3 with a fat eval, but it will surely cover up for most of the bad effects of nullmoving at the tips. I think it might be safer to cover search problems with search.
I understand that your approach is to use R=3 everywhere with good eval and no dubious stuff. Which approach wins, i have no idea
daniel

Your assumption is wrong.

You ask: "how much tactics can eval do?"

That is a good question. Then you answer that with: "1 ply".

This is wrong.

Without eval you see 0 tactics.

Just kick out your evaluation function and search material only.

Now go try find the simplest trick, for example:

1.e4,e5 2.nf3,nc6 3.Bc4,Nd4

a) when does it see that Nxe5 is *losing*?

b) after Nxe5 when do you see Qg5 is *winning* the game?

You know. Simpler as this there is not.

Now let's discuss more advanced tricks. Just material only.
r1b2rk1/1p1nbppp/pq1p4/3B4/P2NP3/2N1p3/1PP3PP/R2Q1R1K w - - bm Rxf7;
f1f7

A simple trick from Nolot testset.

Do you honestely believe that a material only searcher will easily find Rxf7?

If so, at what search depth?

You seem to have the wrong concept why chessprograms find tactics.

Vincent

I think that Daniel means how much complicated evaluation save relative to cheap evaluation and not relative to no material evaluation.

Fruit can find Rxf7 at depth 12 and I think that lazy evaluation is not going to prevent fruit from finding it at depth 12.

Uri

[diepeveen]

How much "tactics" can the evaluation do? If we say a good eval is worth one ply, we can do a 1 ply search for depthleft 4,3,2 and qsearch for depthleft = 1. This will be slower in general than just using plain R=3 with a fat eval, but it will surely cover up for most of the bad effects of nullmoving at the tips. I think it might be safer to cover search problems with search.
I understand that your approach is to use R=3 everywhere with good eval and no dubious stuff. Which approach wins, i have no idea
daniel

Your assumption is wrong.

You ask: "how much tactics can eval do?"

That is a good question. Then you answer that with: "1 ply".

This is wrong.

Without eval you see 0 tactics.

Just kick out your evaluation function and search material only.

Now go try find the simplest trick, for example:

1.e4,e5 2.nf3,nc6 3.Bc4,Nd4

a) when does it see that Nxe5 is *losing*?

b) after Nxe5 when do you see Qg5 is *winning* the game?

You know. Simpler as this there is not.

Now let's discuss more advanced tricks. Just material only.
r1b2rk1/1p1nbppp/pq1p4/3B4/P2NP3/2N1p3/1PP3PP/R2Q1R1K w - - bm Rxf7;
f1f7

A simple trick from Nolot testset.

Do you honestely believe that a material only searcher will easily find Rxf7?

If so, at what search depth?

You seem to have the wrong concept why chessprograms find tactics.

Vincent

I think that Daniel means how much complicated evaluation save relative to cheap evaluation and not relative to no material evaluation.

Fruit can find Rxf7 at depth 12 and I think that lazy evaluation is not going to prevent fruit from finding it at depth 12.

Uri

Where is your proof?

[Uri Blass]

How much "tactics" can the evaluation do? If we say a good eval is worth one ply, we can do a 1 ply search for depthleft 4,3,2 and qsearch for depthleft = 1. This will be slower in general than just using plain R=3 with a fat eval, but it will surely cover up for most of the bad effects of nullmoving at the tips. I think it might be safer to cover search problems with search.
I understand that your approach is to use R=3 everywhere with good eval and no dubious stuff. Which approach wins, i have no idea
daniel

about winning approach: Zappa became world champion with this 'diep' approach. So there is your proof.

Vincent

The question is if zappa does not do pruning stuff except null move pruning.

one idea that I remember from anatony posts is that when the evaluation is bad relative to alpha and the remaining depth is 1 you can generate only captures and promotions and checking moves and not try more moves.

If he is using this idea in zappa then it means that zappa does not try all moves in the last ply so he is using tricks except null move pruning.

Uri