EBF definition problem in chess wiki

[Daniel Shawul]

I thought you wanted to stop the discussion Or do you just sense an opportunity to say the final word? Well I am not going to let you
Show me your definiton in books or publications,AI books or whatever.
Or else there is nothing to discuss on a scientific basis.

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.

Loud and clear. It is just not the way it is defined in standard AI books. If that doesn't bug you, good for you. Live with it.

[jacobbl]

I'm calculating my EBF based on all plies:
(Total number of nodes in all plies)^(1/number of ply)

Should be adjusted for the 1. ply where the BF is all legal moves.

In this way I get the average BF for all plies. I would think this would give a better estimate than just looking at the last ply. I often observe very different BF from ply to ply, and I don't know if they are serial correlated.

Any thoughts on this?

Regards
Jacob

[Sven]

I thought you wanted to stop the discussion Or do you just sense an opportunity to say the final word? Well I am not going to let you
Show me your definiton in books or publications,AI books or whatever.
Or else there is nothing to discuss on a scientific basis.

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.

Loud and clear. It is just not the way it is defined in standard AI books. If that doesn't bug you, good for you. Live with it.

Daniel,

let's stop the discussion. I see no other way to proceed. Use whichever AI book you want. Nobody says that there is anything wrong in it.

Please accept, however, that some people think that these AI book definitions are not closely related to the reality in most of today's chess programs. Some reasons have been given for it.

To avoid future name clashes I will use the term "ID-based EBF" from now on for the concept which we currently call EBF.

Please take the final word for you, if you like

Sven

[Daniel Shawul]

Sven, I really didn't want to be aggressive on you. Please believe me
I was just too tired and you seem to be asking questions when this discussion began which frustrated me. I think we all can agree at least EBF is defined differently for chess. If you google you only find that defintion in chess wiki. And also that the definition as is not directly comparable to BF since it can be magnified or diminished extensively, due to different prunings and widenigns at consecuative iterations. For games like tic-tac-toe, Go, amazons, hex etc the narrowing effect is natural, defining EBF like chess's definition will be problematic even without prunings and widenings.
This is not the final word btw

[Daniel Shawul]

Hi Jacob
That is exactly the way it should be done. Please don't do that EBF stuff which compares total nodes between two iterations. For more accuracy you can use
the exact formula

Total nodes = (EBF ^ (d + 1) - 1) / (EBF - 1)

But this requires iterative solution of EBF so it might not be worth it. I sense that other chess engine authors who never met Bob may be using the textbook formula

[Sven]

Sven, I really didn't want to be aggressive on you. Please believe me
I was just too tired and you seem to be asking questions when this discussion began which frustrated me. I think we all can agree at least EBF is defined differently for chess. If you google you only find that defintion in chess wiki. And also that the definition as is not directly comparable to BF since it can be magnified or diminished extensively, due to different prunings and widenigns at consecuative iterations. For games like tic-tac-toe, Go, amazons, hex etc the narrowing effect is natural, defining EBF like chess's definition will be problematic even without prunings and widenings.
This is not the final word btw

I did not perceive you as aggressive. I can only notice that my statements numbered 1,2,3,4,5 did not contain any question, so I wonder what it is you read from my post. I certainly did not go back to the beginning of the discussion (which I followed but did not post so far). I wrote about what I thought was wrong with your view, and I don't think I touched some point where the discussion had already reached a common, different agreement.

Sven

[bob]

I'm calculating my EBF based on all plies:
(Total number of nodes in all plies)^(1/number of ply)

Should be adjusted for the 1. ply where the BF is all legal moves.

In this way I get the average BF for all plies. I would think this would give a better estimate than just looking at the last ply. I often observe very different BF from ply to ply, and I don't know if they are serial correlated.

Any thoughts on this?

Regards
Jacob

The interesting thing is that the EBF often climbs in problematic positions. Hsu one wrote somewhere "deep blue will use extra time if the number of nodes searched can't be expressed as a canonical value for the normal size of the expected tree." He slightly expanded that with "when the tree size climbs above what we expect for this iteration, we suspect trouble is brewing..."

That makes the iteration-by-iteration useful, where the "overall EBF" is just a piece of data that can be used to describe the specific tree that has been searched, after-the-fact...

[jacobbl]

I use EBF to decide if I should start a new iteration with an increased ply or not. I'm afraid if I use the classic EBF formula I will start an iteration which I won't be able to finish if the EBF is too small, and that I won't start on an iteration when the EBF is high even if I probably will have enough time to finish it. But you are saying in the latter case that I should allocate more time when the EBF is high because it is an important position?

Regards
Jacob

[Daniel Shawul]

I implemented the EBF calculation in my engine Nebiyu so that it prints the EBF at each iteration. EBF is calculated in two ways :

a) EBFleaf = (Nodes) ^ (1 / depth) . Much simpler but is an upperbound on the real value since the formula uses only leaf nodes.

b) Second solves the correct equation using the bisection method. I tried Newton raphson and simple substitution method but those diverge sometimes.

Nodes = (EBF ^ (depth + 1) - 1) / (EBF - 1)

Here is a sample result printed at the end of each iteration

[st = 5557ms, mt = 29250ms , moves_left 10]
2 0 0 164 g1f3 g8f6 EBF = 12.28 EBFleaf 12.81
3 25 1 327 g1f3 g8f6 b1c3 EBF = 6.52 EBFleaf 6.89
4 0 1 1698 g1f3 g8f6 b1c3 b8c6 EBF = 6.14 EBFleaf 6.42
5 10 1 1874 g1f3 g8f6 b1c3 b8c6 d2d4 EBF = 4.28 EBFleaf 4.51
5 10 1 1925 g1f3 g8f6 b1c3 b8c6 d2d4 EBF = 4.30 EBFleaf 4.54
6 0 1 2855 g1f3 g8f6 b1c3 b8c6 d2d4 a7a5 EBF = 3.57 EBFleaf 3.77
6 0 3 5447 g1f3 g8f6 b1c3 b8c6 d2d4 a7a5 EBF = 4.00 EBFleaf 4.19
7 25 3 7873 g1f3 g8f6 b1c3 b8c6 d2d4 a7a5 c1e3 EBF = 3.43 EBFleaf 3.60
7 25 3 8399 g1f3 g8f6 b1c3 b8c6 d2d4 a7a5 c1e3 EBF = 3.46 EBFleaf 3.64
8 5 4 12681 g1f3 g8f6 b1c3 b8c6 d2d4 e7e6 d4d5 c6e7 EBF = 3.10 EBFleaf 3.26
8 5 4 20505 g1f3 g8f6 b1c3 b8c6 d2d4 e7e6 d4d5 c6e7 EBF = 3.31 EBFleaf 3.46
9 10 6 22794 g1f3 g8f6 b1c3 b8c6 d2d4 e7e6 d4d5 c6e7 e2e4 e6d5 e4d5 EBF = 2.91 EBFleaf 3.05
9 10 6 26700 g1f3 g8f6 b1c3 b8c6 d2d4 e7e6 d4d5 c6e7 e2e4 e6d5 e4d5 EBF = 2.96 EBFleaf 3.10
10 5 7 37285 g1f3 g8f6 b1c3 b8c6 d2d4 e7e6 d4d5 c6e7 e2e4 a7a5 EBF = 2.74 EBFleaf 2.87
10 5 9 53224 g1f3 g8f6 b1c3 b8c6 d2d4 e7e6 d4d5 c6e7 e2e4 a7a5 EBF = 2.84 EBFleaf 2.97
11 10 9 67193 g1f3 g8f6 b1c3 b8c6 d2d4 e7e6 d4d5 e6d5 c3d5 f8d6 c1e3 EBF = 2.63 EBFleaf 2.75
11 10 10 90572 g1f3 g8f6 b1c3 b8c6 d2d4 e7e6 d4d5 e6d5 c3d5 f8d6 c1e3 EBF = 2.71 EBFleaf 2.82
12 10 14 135999 g1f3 g8f6 b1c3 b8c6 d2d4 d7d5 d1d3 a7a5 c1e3 c6b4 d3b5 c8d7 EBF = 2.57 EBFleaf 2.68
12 10 17 178273 g1f3 g8f6 b1c3 b8c6 d2d4 d7d5 d1d3 a7a5 c1e3 c6b4 d3b5 c8d7 EBF = 2.63 EBFleaf 2.74
13 10 25 318664 g1f3 g8f6 b1c3 b8c6 d2d4 d7d5 d1d3 c8d7 a2a3 e7e6 h2h4 f8d6 c1e3 EBF = 2.55 EBFleaf 2.65
13 15 34 495624 b1c3 g8f6 d2d4 d7d5 c1f4 c8e6 g1f3 b8c6 d1d3 g7g6 e2e4 f8g7 f4e3 EBF = 2.64 EBFleaf 2.74
13 15 37 525256 b1c3 g8f6 d2d4 d7d5 c1f4 c8e6 g1f3 b8c6 d1d3 g7g6 e2e4 f8g7 f4e3 EBF = 2.66 EBFleaf 2.75
14 15 46 696177 b1c3 g8f6 d2d4 d7d5 c1f4 c8e6 g1f3 b8c6 d1d3 g7g6 e2e4 f8g7 e4e5 e6f5 EBF = 2.52 EBFleaf 2.61
14 15 53 828740 b1c3 g8f6 d2d4 d7d5 c1f4 c8e6 g1f3 b8c6 d1d3 g7g6 e2e4 f8g7 e4e5 e6f5 EBF = 2.55 EBFleaf 2.65
15 5 100 1677214 b1c3 d7d5 d2d4 c8f5 c1f4 b8c6 g1f3 g8f6 a1c1 a8c8 f3e5 h7h5 h2h4 c6e5 f4e5 EBF = 2.51 EBFleaf 2.60
15 5 150 2640846 b1c3 d7d5 d2d4 c8f5 c1f4 b8c6 g1f3 g8f6 a1c1 a8c8 f3e5 h7h5 h2h4 c6e5 f4e5 EBF = 2.59 EBFleaf 2.68
16 10 250 4459679 b1c3 d7d5 d2d4 c8f5 c1f4 h7h6 g1f3 g8f6 h2h4 b8c6 a1c1 a7a5 e1d2 d8d7 f3e5 c6e5 f4e5 EBF = 2.52 EBFleaf 2.6
16 10 345 6231522 b1c3 d7d5 d2d4 c8f5 c1f4 h7h6 g1f3 g8f6 h2h4 b8c6 a1c1 a7a5 e1d2 d8d7 f3e5 c6e5 f4e5 EBF = 2.58 EBFleaf 2.6
17 5 407 7389727 b1c3 d7d5 d2d4 c8f5 c1f4 h7h6 g1f3 g8f6 h2h4 b8c6 a1c1 e7e6 d1d2 f8d6 c3b5 d6f4 d2f4 EBF = 2.46 EBFleaf 2.54
nodes = 10099623 <68 qnodes> time = 5578ms nps = 1810617
splits = 0 badsplits = 0
move b1c3

And here is the existing EBF calculation using the existing T(n) / T(n-1) forumula

2 0 0 164
3 25 1 327 1.993902439
4 0 1 1698 5.19266055
5 10 1 1874
5 10 1 1925 1.13368669
6 0 1 2855
6 0 3 5447 2.82961039
7 25 3 7873
7 25 3 8399 1.541949697
8 5 4 12681
8 5 4 20505 2.441362067
9 10 6 22794
9 10 6 26700 1.302121434
10 5 7 37285
10 5 9 53224 1.99340824
11 10 9 67193
11 10 10 90572 1.701713513
12 10 14 135999
12 10 17 178273 1.968301462
13 10 25 318664
13 15 34 495624
13 15 37 525256 2.946357553
14 15 46 696177
14 15 53 828740 1.577783024
15 5 100 1677214
15 5 150 2640846 3.186579627
16 10 250 4459679
16 10 345 6231522 2.359668833
17 5 407 7389727

I have to skip intermediate updates.
You can see that this ratio is very much different from what is called EBF in text books. And the text books definition clearly shows smoothly decreasing EBF with depth, unlike the second case which gives values all over the place . So judge for yourself which one is more accurate.

Here is another on the start positon and the corresponding plots

[Sven]

I have to skip intermediate updates because the formula doesn't allow it unlike the textbook's EBF definition.

Any EBF calculation is useless for incomplete trees. Therefore you *must* skip these, as well as the last iteration in case it was interrupted by timeout.

A further correction might be necessary depending on the way you are printing your node counts. If they are cumulative then you'll need to get the values per iteration first, before starting any EBF calculation.

You can see that this ratio is very much different from what is called EBF in text books. And the text books defintion clearly shows decreasing EBF with depth, unlike the second case which gives values all over the place . So judge for yourself which one is more accurate.

Replace the nodes(i)/nodes(i-1) by the improved version ("EBF_ID_mod" in the table below): sqrt(nodes(i)/nodes(i-2)), then you'll get these numbers (based on the assumptions that your node counts are cumulative and the last iteration was incomplete - you are free to correct both, of course):

Code: Select all

First set of data:

 d   dnodes  EBF_AI  EBF_ID_mod
 2      164   12,81
 3      163    5,46
 4     1535    6,26        3,06
 5      390    3,30        1,55
 6     5057    4,14        1,82
 7     3342    3,19        2,93
 8    17163    3,38        1,84
 9     9537    2,77        1,69
10    43687    2,91        1,60
11    46885    2,66        2,22
12   131388    2,67        1,73
13   393868    2,69        2,90
14   434872    2,53        1,82
15  2205974    2,65        2,37
16  4025548    2,59        3,04

Second set of data:

 d   dnodes  EBF_AI  EBF_ID_mod
 2      165   12,85
 3      165    5,48
 4     1328    6,04        2,84
 5      360    3,25        1,48
 6     4341    4,04        1,81
 7     4353    3,31        3,48
 8     8591    3,10        1,41
 9    17088    2,95        1,98
10    60807    3,01        2,66
11    57644    2,71        1,84
12   168850    2,73        1,67
13   926145    2,88        4,01
14   756135    2,63        2,12
15  1746284    2,61        1,37
16  2828766    2,53        1,93

Still so bad?

Well, I think the "EBF_ID_mod" curve is not nice but while "EBF_AI" seems to be asymptotically approaching some constant value which looks like the average of "EBF_ID_mod", the latter is already about there from the beginning ...

I agree that the original nodes(i)/nodes(i-1) formula is not optimal, which is caused by the odd/even effects of alpha-beta search. But the improvement for that tiny problem has already been proposed a couple of months ago by Gerd Isenberg, which you might have read.

We can open an "EBF competition" with just two participants

Seriously, for both ways of calculation I think there are advantages and disadvantages. And both are not a perfect tool for getting an estimate of the time needed for the next iteration, if this is a question the engine has to answer. So maybe we can even live with both tools

Sven