EBF definition problem in chess wiki

[Daniel Shawul]

I think the definition of EBF there is problematic http://chessprogramming.wikispaces.com/ ... ite_note-3

The effective branching factor (EBF) is related to iterative deepening. The EBF is the average ratio of nodes (or time used) revisited of the current iteration N versus the previous iteration N-1.

The EBF is tied to an iterative deepening search. Because of this adhoc defintion tieing it to iterative deepening search it suffers from problems when search becomes selective. A little down the page it says.

However, when all sorts of extensions, reductions and pruning are applied to the tree, it is not at all clear that the average branch is searched precisely one ply deeper at iteration N+1 than at iteration N, which makes this definition of effective branching factor rather meaningless [3].

There is a definition of EBF which avoids all this problems. The EBF as defined in chess wiki is actually a ratio that measure the effort required to go from iteration N to N + 1.

The definition of "effective branching factor" as describe in many places.
http://cseweb.ucsd.edu/~elkan/250A/jan17.html
http://cs-alb-pc3.massey.ac.nz/notes/59302/l04.html

The effective branching factor b* is the branching factor that a uniform tree of depth d would have to have in order to contain N nodes.

Code: Select all

N = 1 + b* + b* ^ 2 + ... + b* ^ d
    =  (b* (d + 1) - 1) / (b* - 1)

Hence if we are given number of nodes N the effective branching factor b* can be calculated iteratively from the above equation. This definition avoids the problem associated with selective search I mentioned above. It can even be used with a mix of algorithms depth-first, best-first & breadth first searches to compare performance of algorithms in general.

The existing definition relates nodes searched N with its previous value at the last iteration, instead of a standard uniform tree. This obviously causes problem when the search is selective...

The results of these two definitions could be significantly different from one another as I tried to show in the following plots. Red is the new defintions and blue the old one. Even with a constant "width of search at each node" the result can be significantly different in the beginning.

[bob]

I think the definition of EBF there is problematic http://chessprogramming.wikispaces.com/ ... ite_note-3

The effective branching factor (EBF) is related to iterative deepening. The EBF is the average ratio of nodes (or time used) revisited of the current iteration N versus the previous iteration N-1.

The EBF is tied to an iterative deepening search. Because of this adhoc defintion tieing it to iterative deepening search it suffers from problems when search becomes selective. A little down the page it says.

However, when all sorts of extensions, reductions and pruning are applied to the tree, it is not at all clear that the average branch is searched precisely one ply deeper at iteration N+1 than at iteration N, which makes this definition of effective branching factor rather meaningless [3].

There is a definition of EBF which avoids all this problems. The EBF as defined in chess wiki is actually a ratio that measure the effort required to go from iteration N to N + 1.

The definition of "effective branching factor" as describe in many places.
http://cseweb.ucsd.edu/~elkan/250A/jan17.html
http://cs-alb-pc3.massey.ac.nz/notes/59302/l04.html

The effective branching factor b* is the branching factor that a uniform tree of depth d would have to have in order to contain N nodes.

Code: Select all

N = 1 + b* + b* ^ 2 + ... + b* ^ d
    =  (b* (d + 1) - 1) / (b* - 1)

Hence if we are given number of nodes N the effective branching factor b* can be calculated iteratively from the above equation. This definition avoids the problem associated with selective search I mentioned above. It can even be used with a mix of algorithms depth-first, best-first & breadth first searches to compare performance of algorithms in general.

The existing definition relates nodes searched N with its previous value at the last iteration, instead of a standard uniform tree. This obviously causes problem when the search is selective...

The results of these two definitions could be significantly different from one another as I tried to show in the following plots. Red is the new defintions and blue the old one. Even with a constant "width of search at each node" the result can be significantly different in the beginning.

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. The BF is determined by the rules of the game (how pieces move, for chess it averages 38). EBF is simply used to estimate the time for the next iteration. Or it can be used to notice that something is happening (when it gets suddenly larger) to make the tree grow larger, generally caused by move ordering worsening. For that to happen, we have to run into something we did not see at the last iteration, something that is tactically painful, and difficult to defend against. So old move ordering things (from TT move to killers and such) suddenly don't work so well in light of the new problem/issue discovered.

I don't see any sensible reason to try to define it as something other than what it has been intended to be... If your search is more selective, your EBF goes down. If your search is less selective, EBF goes up. What more would you want???

[Daniel Shawul]

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

[Evert]

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

I looked at the definition in those links and I'm not entirely sure why you think they're not equivalent to the definition given on the wiki? I mean, sure, the way it's worded is very different, but it seems to me that you can show that those definitions are actually equivalent (within an iterative deepening framework anyway)...
I didn't spend a great deal of time looking at it though, so maybe I'm missing something.

[Daniel Shawul]

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

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.

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.

[Gerd Isenberg]

Yes, that definition of EBF does not refer tree traversals by best-first A* path finding algorithms, but depth-first alpha-beta with iterative deepening. This should be made more clear. Thanks for your critique and the links. Any suggestions to re-write parts of the article are welcome.

Gerd

[Gerd Isenberg]

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?

[Daniel Shawul]

Here is what I don't get and this applies for depth first search. For a uniform tree of width W at all nodes, shouldn't the BF be same as EBF i.e EBF = BF = W. Whatever statistics we use mean BF = median BF = effective BF = BF = W. But the ID definition says it decreases asymptotically until it reaches W. The rate of increase from one iteration to iteration may be an important measure but is not the definition of EBF. At the lower end of the spectrum when W = 1, the effort required to go from depth 5 to 6 , is 6/5 times difficult, but BF is still 1.
A wiki definition 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)

Then how can it decrease for a unifrom tree of width W with this definition ?

If we are given a tree which may have been constructed either of the methods depth-first, breadth-first or best-first, then what is the branching factor ? Is the effective branching factor a metric much different from the other BF measures , that we need to associate it with a secondary enhancement such as ID.

[hgm]

At the lower end of the spectrum when W = 1, the effort required to go from depth 5 to 6 , is 6/5 times difficult, but BF is still 1.

I think with that notion of EBF you are supposed to count leaf nodes. So when going from d=5 to d=6 you would go from 1 to 1, or EBF = 1, as it should. For W>=2 this distinction already is 'below noise level', as the difference with counting interior nodes as well is something like 1/((W-1)*totalNodeCount). So for W=2 it has already dropped to 1/totlNodes. But for W=1 it happens to be infinite.

[Daniel Shawul]

I think with that notion of EBF you are supposed to count leaf nodes. So when going from d=5 to d=6 you would go from 1 to 1, or EBF = 1, as it should.

Exactly. EBF should never have been greater than 1. To illustrate this difference, I have calculated branching factors with different definitions on a tic-tac-toe tree. The branching factor decreases from 9 to 1 layer by layer. Note here the tree is continued even when the game could be over before all squares are marked.

The leaf branching factor can be calculated from the ratio of the non-cumulative number of nodes and exactly match the BF at each layer. For example , right before the end of the game, the BF is 1 with this definition since you only have one move for each possible move at the previous depth. But if we use the cumulative definition it is something else...

With the EBF definition which compares it to a uniform tree , I calculated a BF of about 4.51 for this tree. The mean,meadian and mode are also shown.