EBF definition problem in chess wiki

[hgm]

Tic Tac Toe and Chess from the opening position are kind of pathological cases, as the tree is quite inhomogeneous, layer by layer. I doubt that any defenition would have much practical use in such cases. For me the quantity that gives the ratio of leave nodes at N+1 and N ply is the most useful one. On a fixed-depth tree you could call that the marginal branching factor. On a selective search you could call it the effective marginal branching factor.

[Daniel Shawul]

I agree that the marginal BF definition makes much more sense compared to the "ID BF cumulative". Becuase any definition of effective BF should converge to
the actual branching factor for a uniform tree. The existing ID EBF definition can give an unrealistic
branching factor outside possible bounds. Any EBF definition should be bounded between the minimum and maximum BF observed
in the tree. The marginal EBF definition satisfies this rule as it just caclulates the average BF in a layer. But the cummulative
ID EBF can give a value of 1.2 for a uniform tree of BF = 1...

From a practical point of view, this discussion was originally about stockfish which prunes more with depth. For instance it uses a "smooth scaling nullmove"
d -= fraction * D (more pruning at larger depth), more LMR reduction at larger depths using logarithmic formula. So if we assume that its
BF decreases, then the effect is more or less similar to tic-tac-toe tree. The cummulative ID EBF formula (even though I won't call it EBF)
suggests a much lower curve than the EBF definition with out taking the cummulative, as shown in the third plot in my original post.

p.s: glad that I don't have to make another excel plot

[bob]

What are you missing ? I just gave you a couple of links that state the correct definition of EBF as applied to artificial intelligence. I repeat I did not come up with defintion myself.
http://cseweb.ucsd.edu/~elkan/250A/jan17.html
http://cs-alb-pc3.massey.ac.nz/notes/59302/l04.html

If you look at the original definition, it matches what we are doing today for chess. the ratio of the times taken for two consecutive iterations, or the nodes searched for the same.

The backward definition really doesn't make any sense other than as a theoretical comment. We still discuss N = 2 * W ^ (D/2) for perfect alpha/beta, even though W^D is not the shape of our trees, and hasn't been since search extensions and null-move were added in the 80's.

The only definition that makes any sense, IMHO, is the definition we have been using, EBF = T(n) / T(n-1), or replace T with N if you prefer, since NPS is pretty constant for a given position...

The question is, how are you going to use the number? I only see two valid purposes. (1) predict the time for the next iteration; (2) determine that something pathological is happening inside the tree.

What, exactly, do you want to change the definition for? As used, it makes perfect sense within chess... And it has made sense since the concept was originally defined to get around re-defining "BF" which would be confusing...

[bob]

Look at the plots I provided , Red and blue lines . That is by how much they differ.

When there is selectivity in the search , the definition that is tied to iterative deepening fails.

Please provide some basis for that claim. I ran several tests, and have even added an EBF calculation into Crafty. It is as consistent as I would expect, except for the occasional pathological case where it jumps significantly when something odd happens at a particular depth. My EBF does not slowly climb, nor slowly fall, as the iterations go by...

Also if I just give you a single tree, and asked you to calculate its effective branching factor, what would you do? In other words, what is the EBF at iteration depth 1 ? My point here is EBF is a property of a single tree. Wiki definition.

"who would care?"

The effective branching factor of the tree is the average number of children of each node (i.e., the average number of legal moves in a position)

Suppose I don't use iterative deepening enhancement at all. Lets say search to fixed depth=7 directly , then what is my EBF now ? You can not compare it to anything but to a uniform tree.

Again, "who would care"? This has always been applied in an iterative-deepening scenario...

The definition which calculates EBF as a ratio of nodes of two trees at different iteration depth is a close approximation but is not the actual definition. It is just a side effect that happens to approximate it well.

I also recommend this definition from an AI book pages 91-93. There is no mention of iterative deepening anywhere, and there shouldn't be IMHO.

Question: If EBF is the average number children of each node as in the wiki definition above, why then is our definition using the ID method shows an asymptotical decrease for constant BF of say 3 as shown by the blue curve in the first plot ?? Doesn't make any sense.
Ofcourse it has to remain constant at 3, which is what we get using the the correct definition as shown in the red curve on the same plot.

[Daniel Shawul]

Why are ignoring the elephant in the room? Your way of calculation is _not_ an estimate of EBF. If you say it is, please address the following questions. The BF for the three trees I provided range between 1.5 < BF < 4

a) For the first plot, why does your EBF not remain constant ?

b) For the second plot , why does your EBF = 0.24 at depth 31 ?

c) For the third plot, why does your EBF = 8.7 at depth 31 ?

Your EBF estimates are all unrealistic since it falls out of the range. An effective BF is an equivalent BF for a selective tree if transformed to a uniform tree.
I was even generous with the BF decrease and increase of 0.1, games like tic-tac-toe, Go, Amazons , Havannah atleast decrease BF by 1 on each move.

My only qualm with your metric is that it is not a measure of BF and just that. Yes it is more important to measure how difficult it is to go from depth N to N + 1 but that ratio is not EBF. It is a function of it. If it is, then why are we seeing an EBF of 0.24 for a tree with a minimum branching factor of 1.5 at any node? It is a ratio of two functions calculated based on two BFs i.e T(n) and T(n-1). That is why you see those unrealistic values.

I hope you keep calm address all of them instead of repeatedely telling us you don't care.

[bob]

Why are ignoring the elephant in the room? Your way of calculation is _not_ an estimate of EBF. If you say it is, please address the following questions. The BF for the three trees I provided range between 1.5 < BF < 4

a) For the first plot, why does your EBF not remain constant ?

b) For the second plot , why does your EBF = 0.24 at depth 31 ?

c) For the third plot, why does your EBF = 8.7 at depth 31 ?

Your EBF estimates are all unrealistic since it falls out of the range. An effective BF is an equivalent BF for a selective tree if transformed to a uniform tree.
I was even generous with the BF decrease and increase of 0.1, games like tic-tac-toe, Go, Amazons , Havannah atleast decrease BF by 1 on each move.

My only qualm with your metric is that it is not a measure of BF and just that. Yes it is more important to measure how difficult it is to go from depth N to N + 1 but that ratio is not EBF. It is a function of it. If it is, then why are we seeing an EBF of 0.24 for a tree with a minimum branching factor of 1.5 at any node? It is a ratio of two functions calculated based on two BFs i.e T(n) and T(n-1). That is why you see those unrealistic values.

I hope you keep calm address all of them instead of repeatedely telling us you don't care.

To answer your first question, you are making up numbers and fitting them to a formula. The definition of EBF (as opposed to BF) has always been "effort required to complete next iteration." This is not directly comparable to the BF of a tree. Alpha/beta adds complications, such as comparing N=W^D for minimax vs N=2*W^(D/2) for alpha/beta. The two were _never_ intended to represent the same thing. EBF is a much looser term that is used, as I mentioned. And for the way I (and most others here use it) it is _perfect_. I'm not going to try to replace W by EBF and then adjust as necessary to make it fit a formula. None of the existing formulas are any good anyway, if you want accurate numbers, because none factor in any of the non-uniform things we do, including extensions and reductions, much less outright pruning.

For your last statement, again, who cares? We are not talking about "BF". We are talking about "effective branching factor". Which is not the same thing at all. The "EBF" you are talking about is a different animal, where someone is trying to calculate BF, but it turns into an estimate at best.

Use some other acronym. ABF or something (Approximate Branching Factor) because EBF has been used in too many chess publications, and posts, for 20 years now. It would be both difficult, and confusing, to try to change the definition to something new.

[bob]

The definition of EBF we have been using for _many_ years is simply one of the following: (both are equivalent)

EBF = time(i) / time(i-1) or

EBF = nodes(i) / nodes(i-1)

This is as applied to computer chess, which is based on alpha/beta iterative deepening. Trying to make it apply to something else is problematic, because as defined above, one can easily compute it from information available as the search progresses.

EBF is independent of selectivity or anything else, it is simply intended as an _estimate_ of what iteration N+1 will take, knowing the times for N-1 and N. I am not sure what you want it to be.

Yes, but what if you increment by a fraction of one ply in the outer loop of ID?

I suppose you could still compute your own EBF for that. Except that it would be using a slightly different exponential approximation... Or you could increment by 1.5 or 2.0 or whatever, both of which have been done in the past...

[Daniel Shawul]

To answer your first question, you are making up numbers and fitting them to a formula. The definition of EBF (as opposed to BF) has always been "effort required to complete next iteration." This is not directly comparable to the BF of a tree. Alpha/beta adds complications, such as comparing N=W^D for minimax vs N=2*W^(D/2) for alpha/beta. The two were _never_ intended to represent the same thing. EBF is a much looser term that is used, as I mentioned. And for the way I (and most others here use it) it is _perfect_. I'm not going to try to replace W by EBF and then adjust as necessary to make it fit a formula. None of the existing formulas are any good anyway, if you want accurate numbers, because none factor in any of the non-uniform things we do, including extensions and reductions, much less outright pruning.

Glad that is out of the way. So in summary
The effecitve branching factor as defined by T(n)/T(n-1) is not directly comparable to BF

Now lets go on with the apparent conflit between what you say EBF is and what I am seeing elsewhere. I could not find your kind of definition from googling "effective branching factor" except at chess
wiki?!.All of them say effective BF is the number of nodes. For instance, the minimax page from wikipedia says

The effective branching factor of the tree is the average number of children of each node (i.e., the average number of legal moves in a position). The number of nodes to be explored usually increases exponentially with the number of plies (it is less than exponential if evaluating forced moves or repeated positions). The number of nodes to be explored for the analysis of a game is therefore approximately the branching factor raised to the power of the number of plies.

And you strictly say EBF is that ratio (and that it is not comparable to BF). So which is it?
Can you please provide links to AI books (preferable) or publications with that definition? No AI books I found so far has that kind of definition even when proving the effective BF of optimal alpha-beta is squaroot(b).

Use some other acronym. ABF or something (Approximate Branching Factor) because EBF has been used in too many chess publications, and posts, for 20 years now. It would be both difficult, and confusing, to try to change the definition to something new.

I can call my definition approximate BF and it would be fine since that is comparable to BF. But in your own words, your definition of EBF is not comparable to BF. It is atleast very strange to call it effective BF when it is not directly comparable to BF, don't you think ?

[bob]

To answer your first question, you are making up numbers and fitting them to a formula. The definition of EBF (as opposed to BF) has always been "effort required to complete next iteration." This is not directly comparable to the BF of a tree. Alpha/beta adds complications, such as comparing N=W^D for minimax vs N=2*W^(D/2) for alpha/beta. The two were _never_ intended to represent the same thing. EBF is a much looser term that is used, as I mentioned. And for the way I (and most others here use it) it is _perfect_. I'm not going to try to replace W by EBF and then adjust as necessary to make it fit a formula. None of the existing formulas are any good anyway, if you want accurate numbers, because none factor in any of the non-uniform things we do, including extensions and reductions, much less outright pruning.

Glad that is out of the way. So in summary
The effecitve branching factor as defined by T(n)/T(n-1) is not directly comparable to BF

No. Never was. The point was, if each iteration takes 2x longer, then the trees are getting 2x bigger per iteration. If this were minimax, one could say the branching factor is 2, since that is about the only way to get 2x the nodes for one additional ply. For alpha/beta, it would mean that the branching factor is acting like it is around 4.0, since alpha/beta searches sqrt(bf) for each additional ply...

Now lets go on with the apparent conflit between what you say EBF is and what I am seeing elsewhere. I could not find your kind of definition from googling "effective branching factor" except at chess
wiki?!.All of them say effective BF is the number of nodes. For instance, the minimax page from wikipedia says

The effective branching factor of the tree is the average number of children of each node (i.e., the average number of legal moves in a position).

That would seem to be an error. That is the _true_ branching factor, not the EBF. Otherwise what is "real Branching Factor"???

The number of nodes to be explored usually increases exponentially with the number of plies (it is less than exponential if evaluating forced moves or repeated positions). The number of nodes to be explored for the analysis of a game is therefore approximately the branching factor raised to the power of the number of plies.

And you strictly say EBF is that ratio (and that it is not comparable to BF). So which is it?
Can you please provide links to AI books (preferable) or publications with that definition? No AI books I found so far has that kind of definition even when proving the effective BF of optimal alpha-beta is squaroot(b).

That latter should match perfectly. Because with optimal alpha/beta, each iteration takes roughly sqrt(w) more nodes, and since w averages 38 (36 is more convenient) for normal alpha/beta, each successive iteration should take 6x more nodes (or 6x more time) than the previous iteration. That is the kind of number I saw in the 80's, prior to null-move.

Use some other acronym. ABF or something (Approximate Branching Factor) because EBF has been used in too many chess publications, and posts, for 20 years now. It would be both difficult, and confusing, to try to change the definition to something new.

I can call my definition approximate BF and it would be fine since that is comparable to BF. But in your own words, your definition of EBF is not comparable to BF. It is atleast very strange to call it effective BF when it is not directly comparable to BF, don't you think ?

I didn't create the term. I've just been using it for years. As have others that have written papers about chess search trees... Whether it is the "best terminology" is certainly open for debate. But it is so often mentioned in chess tree discussions, changing it would be confusing, to say the least...

[Daniel Shawul]

No. Never was. The point was, if each iteration takes 2x longer, then the trees are getting 2x bigger per iteration. If this were minimax, one could say the branching factor is 2, since that is about the only way to get 2x the nodes for one additional ply. For alpha/beta, it would mean that the branching factor is acting like it is around 4.0, since alpha/beta searches sqrt(bf) for each additional ply...

But that is just a rule of thumb since T(n)/T(n-1) = 2 does not mean BF = 2 even in minmax as we agreed above. Even for a uniform depth tree of constant BF, it never becomes equal to the real BF. Yes it approaches the real BF at large depths for the same BF at each depth of tree. For instance for a tic-tac-toe minimax tree, BF decreases with depth, and this definition gives incorrect results. With prunings/widening the situation is worse. The ratio T(n) than T(n-1) can become far from BF.

Code: Select all

T(n) / T(n-1) = b1^(n+1) / b2^n  = (b1/b2)^n * b1

so if b1 is slightly larger say 1.1 times larger than b2, the branching factor gets maginifed by 1.1^n which could explode at larger depths. When b1=b2 that factor is always 1. So for that to work no difference in prunings/widenings at the two iterations. So lets just drop this business of trying to determine BF from this ratio.

That would seem to be an error. That is the _true_ branching factor, not the EBF. Otherwise what is "real Branching Factor"???

You would be surprised how many AI books formulate EBF like that but I have found none so far with T(n)/T(n-1)... So I ask you once again to show me a defintion from an AI book or publication that defines EBF as you claim. I got things like how many nodes iterative deepening adds to a not iterated search i.e ( b / (b - 1) ) but none so far with consecutive iterations as used in your EBF.

I didn't create the term. I've just been using it for years. As have others that have written papers about chess search trees... Whether it is the "best terminology" is certainly open for debate. But it is so often mentioned in chess tree discussions, changing it would be confusing, to say the least...

I understand that but I am eager to see the definition apart from discussions in this board. For me it is confusing that we attach "branching factor" to the name when it is not a comparable measure to BF. So a formal definiton of EBF from a publication or AI book is necessary.