EBF definition problem in chess wiki

[bob]

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.

Note that nothing in the usage of EBF suggests it is in any way an approximation of BF. It was a term coined many years ago, from the following reasoning:

As W increases, so does the work. In an iterated search, the work for the next iteration is proportional to W. Which is also known as "BF". Since that number is very difficult to quantify for chess, and since it varies position by position, many started to use the I / (I-1) idea since that is easy to compute. And clearly BF and EBF are related. But are not approximations of each other at all.

That's really all it has ever meant, as it gives some idea of the selectivity of the tree (EBF is smaller, selectivity is greater, and vice-versa). The same is true of the real BF. But with EBF being trivial to compute, and the real BF being all but impossible to compute (and it would be a probability-based answer if it were computed), it has been convenient to use EBF for discussions about pruning, reductions, and extensions.

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.

First, I would cite 15 years of CCC posts using it in that way. I would also cite the JICGA which has papers that use the term in that way. I might have used it as far back as the "Using Time Wisely" ICCA paper, I am not sure. I've not seen an AI book define EBF in any way, although I won't claim to have read every AI book in print. I could certainly see where a theorist might use such a term, since BF is essentially impossible to compute in today's searches...

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.

[Daniel Shawul]

Here are a gazillion AI books saying effective branching factor is another way of measuring branching factor for a selective algorithm such as alpha-beta when the metric is not constant. One of the books says it explictly that effective is to be used when BF is not constant. Many books have also an effective depth term too. It is just used to qualify a metric. One of the books even diffine three BFs and gives your kind of BF measurement a name "Heuristic branching factor" , and mine is still effective BF. And it also warns against its use because it can be greater or less than the actual BF. Really you should give up this argument now, the evidence is overwhelming. Six book definitions follow and more from the link above.

[bob]

And I don't have an quibbles with that. Again, as I said, EBF has had a "local usage" in computer chess for many years. Enough years that to change that definition is problematic...

I don't know what else one might add...

[Daniel Shawul]

First of all the AI community rules the chess community. Second you have not given a shred of evidence supporting EBF is defined differently in the chess community. Is it just based on talk b/n programmers in forums? nothing further than that? And I have even given you a name as used in AI books "heuristic BF" for your kind of EBF.

At this point there is no other way but for you to show the definition as used in chess community. If it is just used in discussion boards then I think we can stop this discussion and move on.

[Sven]

I think that all these EBF definitions are not different from the "nodes(i) / nodes(i-1)" definition if we remove qsearch from both "definition worlds". This is since qsearch trees follow completely different rules. The average number of qsearch nodes per full search leaf node is fairly constant for each given program, and usually independent from the full search depth. It depends mostly on the number of possible captures in the position, and therefore will often be smaller in endgames than in "typical" middlegames; but in total there is not much variance for that number.

What I mean is it does not matter whether we include or do not include qsearch when using the usual ID-based EBF calculation, but it makes no sense to include qsearch with the "text book" EBF definitions.

If we remove qsearch from our calculation (not from the search ) then our terminal nodes are those with remaining depth = 0, where we start doing qsearch. Now the "text book EBF" definition should become almost exactly equal to the ID-based EBF definition, at least this is my theory and looks plausible to me. It would be interesting to see some concrete numbers confirming - or rejecting - my theory.

The "text book" EBF definitions quoted above are on a very abstract level, as they should be. Essentially none of them is restricted to a specific game, like chess. And none of them seems to care about something specific like qsearch. But strong chess search needs qsearch (we talk about >98% of real existing programs, of course), and a tree including qsearch is *almost never* a uniform tree even if the full search part were somehow uniform, so the "W^D" pattern simply does not apply if we keep the qsearch nodes.

Code: Select all

TOTALNODES(D)      := FS_NONLEAVES(D) + FS_LEAVES(D) + PURE_QSNODES_WITHOUT_FS_LEAVES(D)
NORM_TOTALNODES(D) := FS_NONLEAVES(D) + FS_LEAVES(D)

Sven

[Daniel Shawul]

Sven, all what is left is to see the definition as used in chess. That is all what I ask for at this point. There is already too much discussion in this threads and the links I gave which tells which is which.

In what most engines use now, it is a ratio of two functions (node counts) based on two EBFs. But actually EBF is an equivalent BF of a uniform tree with the same BF at all nodes. One text book calls this "Heuristic BF" , and all of them agree upon what Effective BF is. The Heuristic BF can explode and give very unreleatic values so there is no converging towards the BF when the BF are different b/n iterations. Adding qsearch nodes or not barely makes a difference.

[bob]

First of all the AI community rules the chess community. Second you have not given a shred of evidence supporting EBF is defined differently in the chess community. Is it just based on talk b/n programmers in forums? nothing further than that? And I have even given you a name as used in AI books "heuristic BF" for your kind of EBF.

At this point there is no other way but for you to show the definition as used in chess community. If it is just used in discussion boards then I think we can stop this discussion and move on.

Daniel, every discussion ends like this with you, so I'm done here as well. We have been using the current definition of EBF for _many_ years. It isn't my term. I didn't like it when I first saw the usage, but it has become an accepted term in computer chess, with an accepted way of computing it, even though it is only loosely related to the real "branching factor."

So stop demanding that I provide you with something. You can search for EBF in CCC if you want, and you will find thousands of hits. If you don't like the usage of the word, use whatever you want. Most here will continue to use the accepted meaning and move right along to something more important...

[Sven]

Sven, all what is left is to see the definition as used in chess. That is all what I ask for at this point. There is already too much discussion in this threads and the links I gave which tells which is which.

In what most engines use now, it is a ratio of two functions (node counts) based on two EBFs. But actually EBF is an equivalent BF of a uniform tree with the same BF at all nodes. One text book calls this "Heuristic BF" , and all of them agree upon what Effective BF is. The Heuristic BF can explode and give very unreleatic values so there is no converging towards the BF when the BF are different b/n iterations. Adding qsearch nodes or not barely makes a difference.

I have some problems following you.

1) "BF" is defined based on the game rules only, not on any search or search algorithm. For chess it is about 38 on average. EBF == BF if the search uses minimax without alpha-beta. Not sure what you mean when using the term "BF", though. (The tic-tac-toe example is very different for a simple reason: with a sufficient search depth you can search from the initial starting position to all end-of-game leaves, and the number of legal moves constantly decreases towards the leaves. Both is not the case for chess.)

2) I propose to forget about even thinking of a "uniform tree" in chess. You simply don't have it due to alpha-beta, not yet considering extensions/reductions/pruning. The point is, how to get a realistic EBF calculation from a realistic search tree, not from an academic one. Forget the papers if they are not based on real chess search.

3) I don't see why you think that including or not including qsearch nodes does not matter when applying one of the definitions "Heuristic BF (B)" and "Effective Branching Factor (β)" from the sources you quoted. For "B" you obviously cannot include qsearch nodes. For "β" I highly doubt that it would make any sense to include qsearch nodes since the underlying model is designed for typical "full search". The qsearch nodes below the full search leaves are creating a lot of noise in that case (however: not when using the ID-based approach!) and make the "d-th root of average number of nodes" definition uncomfortable.

4) Even after that, the existence of varying search depth due to extensions/reductions/pruning makes the application of the theoretical "Effective Branching Factor (β)" concept problematic in practice. Within one (completed) iteration to depth D, count the (full search) nodes for each ply from root to some X, what do you see? Numbers jumping. Now take that D-th root of all (full search) nodes and compare it over several iterations, positions, games, what do you see? Numbers jumping probably (although I did not test it, it seems clear to me). ID-based EBF definition is better here, which might explain why we use that one.

5) Today, to my perception, a lot of chess programming knowledge, including things like how we define EBF in computer chess, are in fact present in fora like CCC but not necessarily documented in scientific papers. Time has changed, I think. Knowledge is widely spread. It would not surprise me if there were more than just that "practical EBF definition" (nodes(i) / nodes(i-1)) which you don't find in any AI book. But that does not make it irrelevant or wrong, in fact the opposite may be true: the practical definition is the one that is tested and proven to work.

Sven

[Daniel Shawul]

You missed the whole point of it and it is like you are restarting the whole discussion while being quite through out.
That is why I am reluctant but since now you insist, I will ask you the same questions I asked Bob and I hope you have answers for them

1) "BF" is defined based on the game rules only, not on any search or search algorithm. For chess it is about 38 on average. EBF == BF if the search uses minimax without alpha-beta. Not sure what you mean when using the term "BF", though. (The tic-tac-toe example is very different for a simple reason: with a sufficient search depth you can search from the initial starting position to all end-of-game leaves, and the number of legal moves constantly decreases towards the leaves. Both is not the case for chess.)

No, not if you use your EBF defintion i.e T(n)/T(n-1). See the first plot on the original post, and while the 'text book' defintion says EBF=3. Simple example is if the BF = 1, then what should EBF be in whatever defintion. It should be 1 period. But the existing EBF says 6/5 = 1.2 at depth 6 , 8/7 at depth 8 etc...
Also look at the tic-tac-toe tree in my discussion with HG. It is perfectly minimax with a decreasing BF.

More questions:

The BF for the three trees I provided range between 1.5 < BF < 4, so any EBF result you have should fall in that range , but not in your case..

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 ?

2) I propose to forget about even thinking of a "uniform tree" in chess. You simply don't have it due to alpha-beta, not yet considering extensions/reductions/pruning. The point is, how to get a realistic EBF calculation from a realistic search tree, not from an academic one. Forget the papers if they are not based on real chess search.

Again you completely miss the point. We are talking about real trees. Take any tree you want, and if you have nodes counts at two iterations N and N + 1, T(N) and T(N+1), the correct way to calculate EBF according to text book is

T(N) = (b1^(N+1) - 1) / (b1 - 1) calculate b1 iteratively which will give you EBF at depth N

T(N + 1) = (b2^(N + 1) - 1) / (b2 - 1) calculate b2 iteratively which will give you EBF at depth N+1

This is just finding an equivalent BF of a uniform tree. So if you understand this your statement about being unrealistic is absurd.

That is the correct way. If you take ratio T(N)/T(N-1) you comparing two EBFs

3) I don't see why you think that including or not including qsearch nodes does not matter when applying one of the definitions "Heuristic BF (B)" and "Effective Branching Factor (β)" from the sources you quoted. For "B" you obviously cannot include qsearch nodes. For "β" I highly doubt that it would make any sense to include qsearch nodes since the underlying model is designed for typical "full search". The qsearch nodes below the full search leaves are creating a lot of noise in that case (however: not when using the ID-based approach!) and make the "d-th root of average number of nodes" definition uncomfortable.

Why do you think it affects my defintion and not yours is beyound me ? Qsearch nodes are both in T(N) and T(N-1), while you calculate one EBF using the ratio. I do two separate EBFs for each. Now how is one affected and not the other ?

4) Even after that, the existence of varying search depth due to extensions/reductions/pruning makes the application of the theoretical "Effective Branching Factor (β)" concept problematic in practice. Within one (completed) iteration to depth D, count the (full search) nodes for each ply from root to some X, what do you see? Numbers jumping. Now take that D-th root of all (full search) nodes and compare it over several iterations, positions, games, what do you see? Numbers jumping probably (although I did not test it, it seems clear to me). ID-based EBF definition is better here, which might explain why we use that one.

No you just count all nodes simple. Then construct a uniform depth tree of the N, and take the branching factor BF as the effective BF of the selective tree. Selectivity , qsearch or whatever doesn't affect this definition a bit. Infact selectivity affects the existing defintion a lot. Because engines could increase or decrease BF from iteration to iteration. Widening is very common in large BF games. Look at plots 2 and 3 of my original post.
T(N)/T(N-1) = (b1/b2)^d * b1 , That means for depth d= 10 and say BF is widened from 10 to 12, you have an EBF = (1.2^10) * b1 = 6 * b1 . Hence your EBF is magnified by 6 times.

5) Today, to my perception, a lot of chess programming knowledge, including things like how we define EBF in computer chess, are in fact present in fora like CCC but not necessarily documented in scientific papers. Time has changed, I think. Knowledge is widely spread. It would not surprise me if there were more than just that "practical EBF definition" (nodes(i) / nodes(i-1)) which you don't find in any AI book. But that does not make it irrelevant or wrong, in fact the opposite may be true: the practical definition is the one that is tested and proven to work.

Please stop really. Bob even himself said he didn't like the naming but that he had to use it, and he also said that it is really not comparable to EBF... Yest it has been used in chess lets use it. Ok. You keep on saying it is more practical blah blah, it simply is not when it even can not appropriately measure EBF of a simple uniform depth tree. There is something you are missing in the discussion and I am too tired to find out.
Please go back to the start of the thread and address the questions that I have been asking.

[bob]

You missed the whole point of it and it is like you are restarting the whole discussion while being quite through out.
That is why I am reluctant but since now you insist, I will ask you the same questions I asked Bob and I hope you have answers for them

1) "BF" is defined based on the game rules only, not on any search or search algorithm. For chess it is about 38 on average. EBF == BF if the search uses minimax without alpha-beta. Not sure what you mean when using the term "BF", though. (The tic-tac-toe example is very different for a simple reason: with a sufficient search depth you can search from the initial starting position to all end-of-game leaves, and the number of legal moves constantly decreases towards the leaves. Both is not the case for chess.)

No, not if you use your EBF defintion i.e T(n)/T(n-1). See the first plot on the original post, and while the 'text book' defintion says EBF=3. Simple example is if the BF = 1, then what should EBF be in whatever defintion. It should be 1 period. But the existing EBF says 6/5 = 1.2 at depth 6 , 8/7 at depth 8 etc...
Also look at the tic-tac-toe tree in my discussion with HG. It is perfectly minimax with a decreasing BF.

More questions:

The BF for the three trees I provided range between 1.5 < BF < 4, so any EBF result you have should fall in that range , but not in your case..

That is simply bogus. In chess, where we talk about an EBF of 2.0, that does _not_ imply that the branching factor is 2.0. For chess, the average number is 38. So our EBF number will _never_ match the actual BF or W number. They will always be proportional, but the proportion will vary depending on the selectivity of the search.

So, once again, "EBF" and "BF" are not measuring the same thing when discussing EBF in chess.

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 ?

You can make the EBF = anything if you adjust the parameters of the search. I don't see why the questions above are even being asked, as they don't make any sense at all to me...

2) I propose to forget about even thinking of a "uniform tree" in chess. You simply don't have it due to alpha-beta, not yet considering extensions/reductions/pruning. The point is, how to get a realistic EBF calculation from a realistic search tree, not from an academic one. Forget the papers if they are not based on real chess search.

Again you completely miss the point. We are talking about real trees. Take any tree you want, and if you have nodes counts at two iterations N and N + 1, T(N) and T(N+1), the correct way to calculate EBF according to text book is

T(N) = (b1^(N+1) - 1) / (b1 - 1) calculate b1 iteratively which will give you EBF at depth N

T(N + 1) = (b2^(N + 1) - 1) / (b2 - 1) calculate b2 iteratively which will give you EBF at depth N+1

This is just finding an equivalent BF of a uniform tree. So if you understand this your statement about being unrealistic is absurd.

That is the correct way. If you take ratio T(N)/T(N-1) you comparing two EBFs

3) I don't see why you think that including or not including qsearch nodes does not matter when applying one of the definitions "Heuristic BF (B)" and "Effective Branching Factor (β)" from the sources you quoted. For "B" you obviously cannot include qsearch nodes. For "β" I highly doubt that it would make any sense to include qsearch nodes since the underlying model is designed for typical "full search". The qsearch nodes below the full search leaves are creating a lot of noise in that case (however: not when using the ID-based approach!) and make the "d-th root of average number of nodes" definition uncomfortable.

Why do you think it affects my defintion and not yours is beyound me ? Qsearch nodes are both in T(N) and T(N-1), while you calculate one EBF using the ratio. I do two separate EBFs for each. Now how is one affected and not the other ?

4) Even after that, the existence of varying search depth due to extensions/reductions/pruning makes the application of the theoretical "Effective Branching Factor (β)" concept problematic in practice. Within one (completed) iteration to depth D, count the (full search) nodes for each ply from root to some X, what do you see? Numbers jumping. Now take that D-th root of all (full search) nodes and compare it over several iterations, positions, games, what do you see? Numbers jumping probably (although I did not test it, it seems clear to me). ID-based EBF definition is better here, which might explain why we use that one.

No you just count all nodes simple. Then construct a uniform depth tree of the N, and take the branching factor BF as the effective BF of the selective tree. Selectivity , qsearch or whatever doesn't affect this definition a bit. Infact selectivity affects the existing defintion a lot. Because engines could increase or decrease BF from iteration to iteration. Widening is very common in large BF games. Look at plots 2 and 3 of my original post.
T(N)/T(N-1) = (b1/b2)^d * b1 , That means for depth d= 10 and say BF is widened from 10 to 12, you have an EBF = (1.2^10) * b1 = 6 * b1 . Hence your EBF is magnified by 6 times.

5) Today, to my perception, a lot of chess programming knowledge, including things like how we define EBF in computer chess, are in fact present in fora like CCC but not necessarily documented in scientific papers. Time has changed, I think. Knowledge is widely spread. It would not surprise me if there were more than just that "practical EBF definition" (nodes(i) / nodes(i-1)) which you don't find in any AI book. But that does not make it irrelevant or wrong, in fact the opposite may be true: the practical definition is the one that is tested and proven to work.

Please stop really. Bob even himself said he didn't like the naming but that he had to use it, and he also said that it is really not comparable to EBF... Yest it has been used in chess lets use it. Ok. You keep on saying it is more practical blah blah, it simply is not when it even can not appropriately measure EBF of a simple uniform depth tree. There is something you are missing in the discussion and I am too tired to find out.
Please go back to the start of the thread and address the questions that I have been asking.

There is nothing to answer. T(n) / T(N-1) is what we use. It is all that we use. I doubt we are going to change. Too many use that definition. If you don't like it, and don't like it bad enough, use whatever you want. But be prepared to explain your definition over and over since there is so much ingrained EBF in CC already. It just isn't going to change. I wish X86 had 32 registers like most other architectures do. It doesn't. And it isn't going to anytime soon. I just live with it.