Selective Futlity Condition at Quiescence Nodes

[Pradu]

In Heinz's book Scalable Search in Computer Chess, he describes the Selective Futlity Condition at Quiescence Nodes as

mat_balance(node)+mat_gain(move)+qs_futil_margin<=alpha

This fuitility pruning at quiesce nodes reduced my branching factor by about .6 with no other kind of pruning in a simple fail-soft alphabeta search. But the reduction in playing strength by using this futility condition is huge (the engine using futility pruning loses almost 100% of the time). I use a ray-casting SEE to calculate mat_gain(move) and my qs_futil_margin is 50 and I have not gotten this futility condition to work well for me. Did any of you ever get Futility pruning to work at quiesce nodes?

[Edsel Apostol]

Hi there Pradu,

My engine uses that kind of pruning and it helps a lot. They call it delta

pruning. Fruit's implementation for the "mat_gain(move)" in that

expression is the piece value of the captured piece and not the SEE value.

Just give it a try, that works in my engine. By the way, the latest version

of my engine that supports it is not yet released.

Here is the expression:

"mat_balance + piece_value_capt + margin <= alpha"

Edsel

[Pradu]

Odd, why will SEE not work? (I've tested my SEE throughly)

[Tony van Roon-Werten]

In Heinz's book Scalable Search in Computer Chess, he describes the Selective Futlity Condition at Quiescence Nodes as

mat_balance(node)+mat_gain(move)+qs_futil_margin<=alpha

This fuitility pruning at quiesce nodes reduced my branching factor by about .6 with no other kind of pruning in a simple fail-soft alphabeta search. But the reduction in playing strength by using this futility condition is huge (the engine using futility pruning loses almost 100% of the time). I use a ray-casting SEE to calculate mat_gain(move) and my qs_futil_margin is 50 and I have not gotten this futility condition to work well for me. Did any of you ever get Futility pruning to work at quiesce nodes?

With this kind of stuff there is a default way to test.

If the condition is met, set a flag but continue search as normal. If the resulting search doesn't meet the condition, print the board and look what the reason for the exception is.
Then decide wether you should adjust the condition or accept the error.

Cheers,

Tony

[Pradu]

I will try and post feed back if I find a solution.


Starting Position (Winboard)

No Futility
1 7 1 40 e4
2 7 1 185 e3
3 11 1 1609 d4
4 7 3 5314 d4
5 8 6 38062 d4
6 5 46 193691 d4
7 6 204 1327822 d4
8 5 3737 16995298 d4

Futility
1 7 0 40 e4
2 7 0 176 e3
3 11 0 1618 e3
4 4 1 4915 e3
5 102 6 55806 e3
6 3 28 131939 e3
7 100 142 1214988 e3
8 -90 2748 14062851 e3

[Daniel Mehrmann]

In Heinz's book Scalable Search in Computer Chess, he describes the Selective Futlity Condition at Quiescence Nodes as

mat_balance(node)+mat_gain(move)+qs_futil_margin<=alpha

This fuitility pruning at quiesce nodes reduced my branching factor by about .6 with no other kind of pruning in a simple fail-soft alphabeta search. But the reduction in playing strength by using this futility condition is huge (the engine using futility pruning loses almost 100% of the time). I use a ray-casting SEE to calculate mat_gain(move) and my qs_futil_margin is 50 and I have not gotten this futility condition to work well for me. Did any of you ever get Futility pruning to work at quiesce nodes?

Hi

Well, the upperbounds will be determined extremly throught the qs search. So please be very carefull with any pruning in the qs search. So your tree and branches lives from good eval which return the qs.

So do never use only material balance as basis for pruning in qs, expect you're in an Null-Window. Its better to use the StandPat (full eval) as basis for such jobs.

I do it on the following way:

[....]

Code: Select all

/* futility qs pruning */
 if (BestScore > alpha)
        alpha = BestScore;
    else if (beta == orgAlpha + 1) {   //Null window
        if (BestScore + 600 <= alpha)
            return BestScore;
    }


[....]

Code: Select all

/* we're looping thought the moves */
SearchResult = StandPat + ScoreMove(*mPtr) + 150;

if (SearchResult <= alpha) {
    qs_drop++;
     continue;
}


Also a nice trick is do full qs on PVnodes and limit your qs depth on AllNodes

For futility pruning i'm using here a static value. Other programmer may use here her highest eval score but at least a static value of x.

Best,
Daniel

[Volker Böhm]

In my opigion you can do one of those in q-search

cureval = eval()

loop through moves

1. if SEE(move) <0 then prune
2. if cureval + mat(move) + delta < alpha then prune
3. if cureval + SEE(move) + bigger_delta < alpha then prune


greetings volker

[Daniel Shawul]

using futility pruning loses almost 100% of the time). I use a ray-casting SEE to calculate mat_gain(move) and my qs_futil_margin is 50 and I have not gotten this futility condition to work

IMO the margin is too low. It means you are only taking in to account a positional variation +/- 50. This will lose all positional knowledge.
you have to have some way to determine approximate the positional knowledge, or make the margin much larger (for eg. 300).
Using SEE score is questionalble because the positional value may change significantly after swapping of pieces(which can take several moves) is finished.
One very nice idea availble on ED's page is to approximate the postional
eval of the current ply from the previous ply's evaluation. This works with a margin as low as 50. Exceptions arise when huge positional scores are added just by a *single* move. In my engine i have tracked down all the exceptions and include them in my lazy eval along with the material score,if possible. For eg. I do this when a bishop is trapped (positional score is +- 150). Using this method a margin of 200 returns 99% correct score for me. But unfortunately it is not enough to be always correct.
lower margins seem to work better (currently 100). Note because of the method i use , i can account for > 100 positional scores.
regards
daniel

[Pradu]

using futility pruning loses almost 100% of the time). I use a ray-casting SEE to calculate mat_gain(move) and my qs_futil_margin is 50 and I have not gotten this futility condition to work

IMO the margin is too low. It means you are only taking in to account a positional variation +/- 50. This will lose all positional knowledge.
you have to have some way to determine approximate the positional knowledge, or make the margin much larger (for eg. 300).
Using SEE score is questionalble because the positional value may change significantly after swapping of pieces(which can take several moves) is finished.
One very nice idea availble on ED's page is to approximate the postional
eval of the current ply from the previous ply's evaluation. This works with a margin as low as 50. Exceptions arise when huge positional scores are added just by a *single* move. In my engine i have tracked down all the exceptions and include them in my lazy eval along with the material score,if possible. For eg. I do this when a bishop is trapped (positional score is +- 150). Using this method a margin of 200 returns 99% correct score for me. But unfortunately it is not enough to be always correct.
lower margins seem to work better (currently 100). Note because of the method i use , i can account for > 100 positional scores.
regards
daniel

Hi Daniel,
Your way of doing it seems interesting. Do you know how much less branching factor you get when you do futility this way? You see, if the difference in branching factor from a safe futility is not much, it might not be worth doing it. Using a higher margin is of course safer but it may cause a much lesser number of cuttoffs.

[Alvaro Begue]

What do you guys mean by "branching factor" in this context? If I understand correctly, this technique will only reduce the size of the quiescence searches, so the overall branching factor of the search tree (ratio of number of nodes searched in depth n+1 and number of nodes searched in depth n) will not be affected much. Am I missing something?

[Pradu]

What do you guys mean by "branching factor" in this context? If I understand correctly, this technique will only reduce the size of the quiescence searches, so the overall branching factor of the search tree (ratio of number of nodes searched in depth n+1 and number of nodes searched in depth n) will not be affected much. Am I missing something?

I am assuming that the node count includes the quiescence nodes without the concidering the respective average depth of the quiescence search, therefore the branching factor is aproximately:

Code: Select all

(leafnodes+quiesnodes)^(1/search_depth)

That '^' isn't xor it is a power.

[Sven Schüle]

What do you guys mean by "branching factor" in this context? If I understand correctly, this technique will only reduce the size of the quiescence searches, so the overall branching factor of the search tree (ratio of number of nodes searched in depth n+1 and number of nodes searched in depth n) will not be affected much. Am I missing something?

I am assuming that the node count includes the quiescence nodes without the concidering the respective average depth of the quiescence search, therefore the branching factor is aproximately:

Code: Select all

(leafnodes+quiesnodes)^(1/search_depth)

That '^' isn't xor it is a power.

Hi,

is this formula widely accepted?

IMHO it should be slightly modified at least to take into account that the node count of the first iteration is totally independent from the branching factor. Also I think that some people calculate the BF differently, by just dividing the total node counts of the last two completed iterations. Including the early iterations may potentially lead to bad results because of their relatively small node counts.

Is there any "official" way of calculating the branching factor from a given "vector" of node counts for K completed iterations?

Furthermore, I think the branching factor is not affected by the qsearch. The average size of a qsearch tree may be defined as NQ nodes (including its root) and does not depend much on the depth of its root, the full search leaf. So if a full search to depth D requires NF(D) nodes then this iteration requires approximately NF(D) * NQ nodes. Obviously the BF depends on NF(D) but not on NQ.

Thus improving the qsearch tree size by, say, futility pruning will most probably lead to a constant speedup of X percent, independent from the search depth.

Sven

[Pradu]

What do you guys mean by "branching factor" in this context? If I understand correctly, this technique will only reduce the size of the quiescence searches, so the overall branching factor of the search tree (ratio of number of nodes searched in depth n+1 and number of nodes searched in depth n) will not be affected much. Am I missing something?

I am assuming that the node count includes the quiescence nodes without the concidering the respective average depth of the quiescence search, therefore the branching factor is aproximately:

Code: Select all

(leafnodes+quiesnodes)^(1/search_depth)

That '^' isn't xor it is a power.

Hi,

is this formula widely accepted?

IMHO it should be slightly modified at least to take into account that the node count of the first iteration is totally independent from the branching factor.

Treat leafnodes as being reset every ply if you want it to be that accurate.

Furthermore, I think the branching factor is not affected by the qsearch. The average size of a qsearch tree may be defined as NQ nodes (including its root) and does not depend much on the depth of its root, the full search leaf. So if a full search to depth D requires NF(D) nodes then this iteration requires approximately NF(D) * NQ nodes. Obviously the BF depends on NF(D) but not on NQ.

Thus improving the qsearch tree size by, say, futility pruning will most probably lead to a constant speedup of X percent, independent from the search depth.
Sven

Well, most of the search is in the quies, and an important thing in computer chess is how much ply you can get in a certain amount of time. If you don't concider qsearch in leafnodes as well, the respective branching factor will not be that great a representation of the search power of your engine.

[Sven Schüle]

Hi Pradu,

I'm afraid you did not get my point in both cases yet. I was not talking about accuracy but about a formula which I consider to be wrong. The node count of iteration no. 1 depends on the number of legal moves at the root position only, not on the branching factor. Say it is 36, your number of iterations is 10 and your "real" branching factor is 2, then your result when taking your formula would be wrong by a factor of 18 ^ (1/10) = about 1,34.

Also your second answer does not match Look at all your qsearch subtrees and compare their sizes at different search depths, are they different? If not, how should a reduction of the average qsearch tree size affect the overall branching factor? If you make the qsearch smaller by P percent this speeds up each single iteration by the same constant factor f(P), so the branching factor remains unchanged. However, if you add a good pruning method at full search or heavily improve move ordering there, you speed up each iteration i by a factor g(i), which directly influences the branching factor.

I'm sorry to insist

Sven

[Daniel Shawul]

Hi Daniel,
Your way of doing it seems interesting. Do you know how much less branching factor you get when you do futility this way? You see, if the difference in branching factor from a safe futility is not much, it might not be worth doing it. Using a higher margin is of course safer but it may cause a much lesser number of cuttoffs.

Hi pradu
This method does not decrease branching factor.
Futility pruning and lazy eval give the same result in a different way.
Pruning avoids investigation of futile moves obviously decreasing branching factor. But lazy eval decreases the time required to investigate
a node(increases speed) but not branching factor. I prefer doing lazy eval only because my eval takes 90% of time. If your make/unmake is fast
it doesn't matter if you prune the move now or one move later.
best
daniel

[Pradu]

Hi Pradu,

I'm afraid you did not get my point in both cases yet. I was not talking about accuracy but about a formula which I consider to be wrong. The node count of iteration no. 1 depends on the number of legal moves at the root position only, not on the branching factor. Say it is 36, your number of iterations is 10 and your "real" branching factor is 2, then your result when taking your formula would be wrong by a factor of 18 ^ (1/10) = about 1,34.

Sven I don't understand what you said right here but here's my reasoning for the formula.

Code: Select all

bf^depth=leafnodes
(bf^(depth))^(1/depth)=leafnodes^(1/depth)
bf^(depth/depth)=leafnodes^(1/depth)
bf=leafnodes^(1/depth)


This should be universal.

Also your second answer does not match Look at all your qsearch subtrees and compare their sizes at different search depths, are they different? If not, how should a reduction of the average qsearch tree size affect the overall branching factor? If you make the qsearch smaller by P percent this speeds up each single iteration by the same constant factor f(P), so the branching factor remains unchanged. However, if you add a good pruning method at full search or heavily improve move ordering there, you speed up each iteration i by a factor g(i), which directly influences the branching factor.

Sven

[Sven Schüle]

Sven I don't understand what you said right here but here's my reasoning for the formula.

Code: Select all

bf^depth=leafnodes
...

This should be universal.

Pradu,
you can't derive the branching factor from just two numbers, depth and leafnodes. The problem in your formula is the first iteration.

Say your bf is 3 (not bad but also not one of the best ones). Does a chess engine produce such numbers?

Code: Select all

leafnodes(1) = 3
leafnodes(2) = 9
leafnodes(3) = 27
...
leafnodes(10) = 59049

Or more likely these ones:

Code: Select all

leafnodes(1) = 36
leafnodes(2) = 108
leafnodes(3) = 324
...
leafnodes(10) = 708588

?

bf tells you how many more nodes (leaf nodes if you like) are searched for an iteration i compared to the previous iteration i-1, so you can't look on the numbers of only one iteration:

Code: Select all

(1) bf(depth) = leafnodes(depth) / leafnodes(depth-1)

Obviously this is valid at most for depth >=2. leafnodes(1) is independent from any branching factor. So you might perhaps write the following:

Code: Select all

(2) bf_average = (leafnodes(depth) / leafnodes(1)) ^ (1 / (depth-1))

Note the different result of (2) compared to your formula, it is quite significant if leafnodes(1) is large compared to bf_average.

I have not tested the practical quality of (2). But still I assume it's better to derive the bf of an engine (for a given position) by applying (1) to the last completed iteration of a search, instead of calculating a somehow arbitrary bf_average using (2).

Perhaps we both should go and test our formulas now

Sven

[Alvaro Begue]

You could try to plot the logarithm of the number of nodes searched (or leaves if you wish) against depth, and try to match it with a straight line. The slope of the straight line will give you a good idea of what the branching factor is.

Of course you might want to weigh the larger depths more, since I don't think we really care what the branching factor is for going from depth 1 to depth 2.

Anyway, changing the size of the typical quiescence search should have no impact on the branching factor, no matter what. It would change the y-intercept of the line, but not the slope.

[Fabien Letouzey]

Futility pruning and lazy eval give the same result in a different way.
Pruning avoids investigation of futile moves obviously decreasing branching factor. But lazy eval decreases the time required to investigate
a node(increases speed) but not branching factor.

Hi Daniel,

I don't agree with "all pruning schemes affect branching factor". I might have misunderstood your statement though.

I 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.

Fabien.

[Daniel Shawul]

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