floor = round down to next lower integer, ceil = round up. And for the convenient case of D being even, we get
Alpha/beta = 2 * W ^(D/2)
Now you can plug in some numbers and get an effective branching factor. Say for D=8, and assuming W=38, the number most commonly quoted for average moves in a position, over an entire game,
depth 8 nodes = 2 * (38^4) = 4, 170,272.
Depth 9 nodes = 38^4 + 38^5 = 81,320,304.
The effective branching factor is, for that case, about 20.
...
depth 10 nodes = 2 * (38^5) = 158,470,336
The effective branching factor is, for that case, about 2.
You have that individual odd and even EBF.
Isn't it more appropriate if "measuring" average EBF to take the square root from number of nodes n to n+2?
I think the number is pretty meaningless since it bounces all over. I seem to recall that Cray Blitz was in the 8-10 range, but it did have null-move, but also SE which hurts EBF...
For approximations, one might sum the odd/even numbers and divide by N, which will take it down to the 10 range Which is in the range of the expected 2 * sqrt(real branching factor).
I think the number is pretty meaningless since it bounces all over. I seem to recall that Cray Blitz was in the 8-10 range, but it did have null-move, but also SE which hurts EBF...
For approximations, one might sum the odd/even numbers and divide by N, which will take it down to the 10 range Which is in the range of the expected 2 * sqrt(real branching factor).
What do you mean with expected? Minimal Tree? Didn't alpha-beta minimal tree reduce EBF to sqrt(W) rather than 2 * sqrt(W), i.e. 6 with W = 36?
I think the number is pretty meaningless since it bounces all over. I seem to recall that Cray Blitz was in the 8-10 range, but it did have null-move, but also SE which hurts EBF...
For approximations, one might sum the odd/even numbers and divide by N, which will take it down to the 10 range Which is in the range of the expected 2 * sqrt(real branching factor).
What do you mean with expected? Minimal Tree? Didn't alpha-beta minimal tree reduce EBF to sqrt(W) rather than 2 * sqrt(W), i.e. 6 with W = 36?
I seem to recall really old data (not mine) that reported the time for iteration N+1 averaged about 10x the time for iteration N, overall. With the noted odd/even issues (the reason some did only odd ply searches never made any sense since the even ply searches are way more efficient because of the shape of the tree (the last ply is primarily made up of cut nodes where you just look at one move per node, which is why it is only about 2x larger).
Someone (monty, knuth/moore, I am not sure) mentioned the 2 * sqrt(38) as an approximation. I'll try to give it a little thought and come up with some real math to support what the EBF should be. Pure alpha/beta certainly reduces the tree size from W^D to 2 * W^(D/2) (for D even). I'll have to think about the "sqrt(w)" number you are quoting.
I think the number is pretty meaningless since it bounces all over. I seem to recall that Cray Blitz was in the 8-10 range, but it did have null-move, but also SE which hurts EBF...
For approximations, one might sum the odd/even numbers and divide by N, which will take it down to the 10 range Which is in the range of the expected 2 * sqrt(real branching factor).
What do you mean with expected? Minimal Tree? Didn't alpha-beta minimal tree reduce EBF to sqrt(W) rather than 2 * sqrt(W), i.e. 6 with W = 36?
I seem to recall really old data (not mine) that reported the time for iteration N+1 averaged about 10x the time for iteration N, overall. With the noted odd/even issues (the reason some did only odd ply searches never made any sense since the even ply searches are way more efficient because of the shape of the tree (the last ply is primarily made up of cut nodes where you just look at one move per node, which is why it is only about 2x larger).
Someone (monty, knuth/moore, I am not sure) mentioned the 2 * sqrt(38) as an approximation. I'll try to give it a little thought and come up with some real math to support what the EBF should be. Pure alpha/beta certainly reduces the tree size from W^D to 2 * W^(D/2) (for D even). I'll have to think about the "sqrt(w)" number you are quoting.
If we have perfect move ordering (which we can only hope to approximate), then alpha beta branching factor is:
b ^ ceil(n/2) + b ^ floor(n/2) - 1
The chess program wiki uses b=40 rather than 38. I have heard 36 and 38 given as approximates for the branching factor. I would guess that it would be hard to get an exact value for pure minimax branching factor because there are so many things that come into play like open or closed openings.
Which corresponds to a branching factor of sqrt(W). (2*sqrt(W)^D)
The sqrt(W) only applies to the EBF definition proposed by Gerd above (which I support). 2 * W^(D/2) is the optimal node count if D is even, and for that case you have
I think the number is pretty meaningless since it bounces all over. I seem to recall that Cray Blitz was in the 8-10 range, but it did have null-move, but also SE which hurts EBF...
For approximations, one might sum the odd/even numbers and divide by N, which will take it down to the 10 range Which is in the range of the expected 2 * sqrt(real branching factor).
What do you mean with expected? Minimal Tree? Didn't alpha-beta minimal tree reduce EBF to sqrt(W) rather than 2 * sqrt(W), i.e. 6 with W = 36?
I seem to recall really old data (not mine) that reported the time for iteration N+1 averaged about 10x the time for iteration N, overall. With the noted odd/even issues (the reason some did only odd ply searches never made any sense since the even ply searches are way more efficient because of the shape of the tree (the last ply is primarily made up of cut nodes where you just look at one move per node, which is why it is only about 2x larger).
Someone (monty, knuth/moore, I am not sure) mentioned the 2 * sqrt(38) as an approximation. I'll try to give it a little thought and come up with some real math to support what the EBF should be. Pure alpha/beta certainly reduces the tree size from W^D to 2 * W^(D/2) (for D even). I'll have to think about the "sqrt(w)" number you are quoting.
Makes sense this morning. 2* is in numerator and denominator. Thinking late at night after a lengthy call of duty session didn't work very well.
That would make the EBF in the 6 range, which seems a bit low. I have a few hardcopy logs from Cray Blitz that I will try to check, as I may well be off in what I remember. That was only 20+ years ago to go back to pre-null-move CB. Our first use of null-move was, I believe, 1989 after don wrote his "selective search without tears" paper which was published in the middle 80's. First challenge is to figure out which version saw first NM implementation, and then to find a printed log in my paper files for some searches for that version...
I think the number is pretty meaningless since it bounces all over. I seem to recall that Cray Blitz was in the 8-10 range, but it did have null-move, but also SE which hurts EBF...
For approximations, one might sum the odd/even numbers and divide by N, which will take it down to the 10 range Which is in the range of the expected 2 * sqrt(real branching factor).
What do you mean with expected? Minimal Tree? Didn't alpha-beta minimal tree reduce EBF to sqrt(W) rather than 2 * sqrt(W), i.e. 6 with W = 36?
I seem to recall really old data (not mine) that reported the time for iteration N+1 averaged about 10x the time for iteration N, overall. With the noted odd/even issues (the reason some did only odd ply searches never made any sense since the even ply searches are way more efficient because of the shape of the tree (the last ply is primarily made up of cut nodes where you just look at one move per node, which is why it is only about 2x larger).
Someone (monty, knuth/moore, I am not sure) mentioned the 2 * sqrt(38) as an approximation. I'll try to give it a little thought and come up with some real math to support what the EBF should be. Pure alpha/beta certainly reduces the tree size from W^D to 2 * W^(D/2) (for D even). I'll have to think about the "sqrt(w)" number you are quoting.
Makes sense this morning. 2* is in numerator and denominator. Thinking late at night after a lengthy call of duty session didn't work very well.
That would make the EBF in the 6 range, which seems a bit low. I have a few hardcopy logs from Cray Blitz that I will try to check, as I may well be off in what I remember. That was only 20+ years ago to go back to pre-null-move CB. Our first use of null-move was, I believe, 1989 after don wrote his "selective search without tears" paper which was published in the middle 80's. First challenge is to figure out which version saw first NM implementation, and then to find a printed log in my paper files for some searches for that version...
easier than I thought. Found some output from 1981 Cray Blitz, searching about 3K nodes per second...
some ebf numbers:
15.75
2.0
7.5
2.7
4.7
5.4
3.5
7.0
4.2
Moving along to 1983 WCCC version on a two CPU Cray XMP:
9.4
2.4
2.5
7.5
4.5
4.7
5.4
And a few numbers from 1983 Belle (no NM there either) as Ken had sent me a log for a game we played that year (this was the 160K nodes per second last edition of Belle)
8.8
5.4
5.1
7.7
6.2
5.8
8.8
5.0
4.6
So ken is right around the sqrt(38) number as well. So not quite as bad as I had remembered.
Was an interesting process to look back at old data, of course...
bob wrote:
Makes sense this morning. 2* is in numerator and denominator. Thinking late at night after a lengthy call of duty session didn't work very well.
That would make the EBF in the 6 range, which seems a bit low. I have a few hardcopy logs from Cray Blitz that I will try to check, as I may well be off in what I remember. That was only 20+ years ago to go back to pre-null-move CB. Our first use of null-move was, I believe, 1989 after don wrote his "selective search without tears" paper which was published in the middle 80's. First challenge is to figure out which version saw first NM implementation, and then to find a printed log in my paper files for some searches for that version...
Yes, Levin's formula are leaf-nodes(depth) of a minimal alpha-beta tree. Even the aggregated number of nodes of the whole tree and their n versus n-2 ratios quickly converts to the constant branching factor W, 36 here:
