Selective Futlity Condition at Quiescence Nodes

Programming Topics (Computer Chess) and technical aspects as test techniques, book building, program tuning etc

Moderator: Andres Valverde

Re: Selective Futlity Condition at Quiescence Nodes

Postby diepeveen » 05 Dec 2005, 20:04

Daniel Shawul wrote:
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
diepeveen
 
Posts: 116
Joined: 28 Jun 2005, 01:09
Location: Netherlands

Re: Selective Futlity Condition at Quiescence Nodes

Postby Daniel Shawul » 06 Dec 2005, 07:58

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
User avatar
Daniel Shawul
 
Posts: 366
Joined: 28 Sep 2004, 09:33
Location: Ethiopia

Re: Selective Futlity Condition at Quiescence Nodes

Postby Daniel Shawul » 06 Dec 2005, 08:09

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
User avatar
Daniel Shawul
 
Posts: 366
Joined: 28 Sep 2004, 09:33
Location: Ethiopia

Re: Selective Futlity Condition at Quiescence Nodes

Postby diepeveen » 06 Dec 2005, 14:22

Daniel Shawul wrote: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).

Daniel Shawul wrote: 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
diepeveen
 
Posts: 116
Joined: 28 Jun 2005, 01:09
Location: Netherlands

Re: Selective Futlity Condition at Quiescence Nodes

Postby Daniel Shawul » 06 Dec 2005, 14:34

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.
User avatar
Daniel Shawul
 
Posts: 366
Joined: 28 Sep 2004, 09:33
Location: Ethiopia

Re: Selective Futlity Condition at Quiescence Nodes

Postby Daniel Shawul » 06 Dec 2005, 14:48

Same is true for futility pruning done inside qsearch, sometimes known as delta pruning. Having lazy eval and futilty pruning both is redundant.
User avatar
Daniel Shawul
 
Posts: 366
Joined: 28 Sep 2004, 09:33
Location: Ethiopia

Re: Selective Futlity Condition at Quiescence Nodes

Postby Uri Blass » 06 Dec 2005, 15:23

Daniel Shawul wrote:
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
User avatar
Uri Blass
 
Posts: 727
Joined: 09 Oct 2004, 05:59
Location: Tel-Aviv

Re: Selective Futlity Condition at Quiescence Nodes

Postby Daniel Shawul » 06 Dec 2005, 15:53

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
User avatar
Daniel Shawul
 
Posts: 366
Joined: 28 Sep 2004, 09:33
Location: Ethiopia

Re: Selective Futlity Condition at Quiescence Nodes

Postby Uri Blass » 06 Dec 2005, 16:13

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
User avatar
Uri Blass
 
Posts: 727
Joined: 09 Oct 2004, 05:59
Location: Tel-Aviv

Re: Selective Futlity Condition at Quiescence Nodes

Postby Uri Blass » 06 Dec 2005, 16:20

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
User avatar
Uri Blass
 
Posts: 727
Joined: 09 Oct 2004, 05:59
Location: Tel-Aviv

Re: Selective Futlity Condition at Quiescence Nodes

Postby Daniel Shawul » 06 Dec 2005, 16:32

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
User avatar
Daniel Shawul
 
Posts: 366
Joined: 28 Sep 2004, 09:33
Location: Ethiopia

Re: Selective Futlity Condition at Quiescence Nodes

Postby diepeveen » 06 Dec 2005, 18:45

Daniel Shawul wrote:
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
diepeveen
 
Posts: 116
Joined: 28 Jun 2005, 01:09
Location: Netherlands

Re: Selective Futlity Condition at Quiescence Nodes

Postby Daniel Shawul » 07 Dec 2005, 06:53

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
User avatar
Daniel Shawul
 
Posts: 366
Joined: 28 Sep 2004, 09:33
Location: Ethiopia

Re: Selective Futlity Condition at Quiescence Nodes

Postby diepeveen » 07 Dec 2005, 13:58

Daniel Shawul wrote:
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
diepeveen
 
Posts: 116
Joined: 28 Jun 2005, 01:09
Location: Netherlands

Re: Selective Futlity Condition at Quiescence Nodes

Postby Daniel Shawul » 08 Dec 2005, 06:19

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
User avatar
Daniel Shawul
 
Posts: 366
Joined: 28 Sep 2004, 09:33
Location: Ethiopia

Re: Selective Futlity Condition at Quiescence Nodes

Postby diepeveen » 08 Dec 2005, 15:20

Daniel Shawul wrote: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
 
Posts: 116
Joined: 28 Jun 2005, 01:09
Location: Netherlands

Re: Selective Futlity Condition at Quiescence Nodes

Postby diepeveen » 08 Dec 2005, 15:21

Daniel Shawul wrote: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
diepeveen
 
Posts: 116
Joined: 28 Jun 2005, 01:09
Location: Netherlands

Re: Selective Futlity Condition at Quiescence Nodes

Postby Uri Blass » 08 Dec 2005, 17:07

diepeveen wrote:
Daniel Shawul wrote: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
User avatar
Uri Blass
 
Posts: 727
Joined: 09 Oct 2004, 05:59
Location: Tel-Aviv

Re: Selective Futlity Condition at Quiescence Nodes

Postby diepeveen » 08 Dec 2005, 17:13

Uri Blass wrote:
diepeveen wrote:
Daniel Shawul wrote: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?
diepeveen
 
Posts: 116
Joined: 28 Jun 2005, 01:09
Location: Netherlands

Re: Selective Futlity Condition at Quiescence Nodes

Postby Uri Blass » 08 Dec 2005, 17:14

diepeveen wrote:
Daniel Shawul wrote: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
User avatar
Uri Blass
 
Posts: 727
Joined: 09 Oct 2004, 05:59
Location: Tel-Aviv

PreviousNext

Return to Programming and Technical Discussions

Who is online

Users browsing this forum: No registered users and 10 guests

cron