EBF definition problem in chess wiki

[Daniel Shawul]

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.

Sven take it easy. Obviously you replied to my post before I *edited* it. Please give me some time before trying to pick on me Now it says only

I have to skip intermediate updates.

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):

On what basis are we taking the square root. Obviously it will lower the ratio but it is still not an estimate of BF. Yes I know Gerd tried to solve the odd/even effect that way, but that is not the question here.
Edit Ok square root is ok since we are comparing N and N+2 now

Still so bad? Smile

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

Yep Still very bad The reason is our branching factor is _actually_ high at the beginning, and when we add all our prunings it starts to decrease , but after some depth remains almost constant. It starts from about 12 and reaches to 2.5. So clearly the existing definition is missing the whole point unless it knows magically the branching factor at high depths. Taking the square root will not solve anything, except lowering the value a bit.

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

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 Smile

I am sorry but I am living with the textbook definition from now on .. no doubt! It clearly shows the effect of prunings at larger depth.

As to who is taking the trophy home..ahm..don't make say it out loud

[Sven]

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.

Sven take it easy. Obviously you replied to my post before I *edited* it. Please give me some time before trying to pick on me Now it says only

I have to skip intermediate updates.

Ok. I saw your post, then started to edit my reply. My browser does not display the fact that a visible post is being modified. When I clicked "submit" after a long editing session I got an error, then I saw that you added a second set of data at the bottom. I erroneously assumed you did not change anything else, sorry for that. (We would need a locking mechanism to avoid that but I think it's good we don't have it.)

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

I am sorry but I am living with the textbook definition from now on .. no doubt! It clearly shows the effect of prunings at larger depth.

As to who is taking the trophy home..ahm..don't make say it out loud

Note that we are in the beginning of the second quarter only

Sven

[kbhearn]

Have you even looked at which one works better in a predictive sense? You like your nice smooth line but until you get well into the asymptotic portion it always predicts high in your example (up to depth 12 it is the worst of the 3 described formulas in this thread for your example data in predicting the next iteration's node count). Using N(d)/N(d-1) is indeed erratic and regularly misses on both sides by large margins, but is still usually closer than N(d)^(1/d) at low depths. sqrt(N(d)/N(d-2)) though is the closest of the 3 overall, it avoids the erratic behavior of N(d)/N(d-1), but doesn't take 12 ply before getting close to predictive. You might try doing this comparison for many different positions...

[Daniel Shawul]

Have you even looked at which one works better in a predictive sense? You like your nice smooth line but until you get well into the asymptotic portion it always predicts high in your example (up to depth 12 it is the worst of the 3 described formulas in this thread for your example data in predicting the next iteration's node count). Using N(d)/N(d-1) is indeed erratic and regularly misses on both sides by large margins, but is still usually closer than N(d)^(1/d) at low depths. sqrt(N(d)/N(d-2)) though is the closest of the 3 overall, it avoids the erratic behavior of N(d)/N(d-1), but doesn't take 12 ply before getting close to predictive. You might try doing this comparison for many different positions...

You can't predict simple. Your selectivity changes from depth to depth. The BF is _actually_ larger at the beginning (around 12) and then smoothly falls to around 2.5. It is very clear BF is decreasing when all the prunings and reductions kick in. So the T(n) / T(n - 1) is not predicting anything, and if it did it is simply wrong. How can you predict your branching factor at depth=20, when searching depth=3... Do you call this zigzag curve prediction ??

[kbhearn]

Isn't the predictive value the main reason people care about calculating EBF inside an engine? To know whether or not they have time to do another iteration in their budgeted time? Do you have some other purpose you want to use it for that its definition is of some value to you or are you just seeking argument for the sake of argument?

[Daniel Shawul]

But you didn't answer the question, how can a depth=3 search can predict what happens at depth = 20 ? Lets say I start doing null move at d >= 6. Now how is that possible to predict at d = 3 ?

[kbhearn]

You wouldn't use the D=3 result at D=20... you'd use the D=19 result...

[Daniel Shawul]

Ofcourse T(n) / T(n - 1) is used , but how is that ratio at depth = 3 i.e T(3)/T(2) predict T(20)/T(19) ?

[kbhearn]

It doesn't... T(19)/T(18) might have some predictive value to T(20)/T(19) though. The sqrt(T(19)/T(17)) formula does seem a good balance though between using all 20 plies and losing local information, and using just the last ply which may not be characteristic.

[Daniel Shawul]

Sure that is why it zigzags. Gerd tried to solve the odd/even effect that way.
After avoiding that and getting a smooth curve, it still falls much lower than the actual BF at lower depths. As I have already proved many times in this thread
T(n) / T(n - 1) = (b1^(d+1)) / (b2^d) = [ (b1/b2)^d ] * b1
Now if b1 = b2 from iteration to iteration, the ratio becomes b1. But that is not the case f.i if you increase selectivity. Even a slight increase in width say b1 = 1.2 * b1 will maginfy the ratio by 1.2^10 at depth 10 = 6x maginification. This ratio is _not_ a measure of BF. It is a comparison between two BFs, and hence can't be called EBF (atleast according to textbooks).