effective branching factor of chess programs

[AlvaroBegue]

When I was working on hash tables, I found it very enlightening to make a plot with the log of the time (or node count) in the vertical axis and depth in the horizontal axis. The slope of that plot is the log of the effective branching factor.

The interesting thing is that the plot was clearly piecewise linear: Initially the EBF was low and then it suddenly changed to a higher value. The point where the slope changed corresponded to the hash tables filling up. I suspect this was not a peculiarity of my engine.

If this is indeed the case for most engines, you should specify which of the two EBFs you are interested in.

[Uri Blass]

Even if the way of node counting of an engine is "non-standard", and even if the number of nodes depends heavily on the position type, the effective branching factor can be calculated independent from these two aspects since it is based on the ratio of nodes (or time, which is nearly equivalent as Uri stated) needed for two consecutive iterations.

If your node counting deviates from the usual way then this will not change from one iteration to the next, so you will get about the same EBF as if your node counting were "standard". A similar argument applies to the influence of the position type.

I think Uri's idea is good, and the results can be very interesting and also helpful for many programmers. Some points would have to be clarified, though:

1) Prior to each new search the hash table should be cleared, or even better, the engine should be restarted from scratch. Even though this may return results which are not perfectly realistic when compared to real game behaviour, I think this is the only way to get *comparable* results.

2) A script would be needed to drive the whole search process and to retrieve the node counts from the search output. Doing it manually will take a lot of time, is error-prone and tedious. The script would also do the final calculation and deliver results in a way suitable for further processing (e.g. CSV format).

3) By using PolyGlot it would be possible to include both WB and UCI engines.

Uri, what do you think about these points?

Sven

I agree

[Sven]

The standard is already there: making a move during search increments the node count by one. That's all. Very simple to implement.

Sven

That s new to me. Most engines i know dont increment the nodecounter
with its moveDo() procedure. Usually the nodecounter is incremented
at the beginning of a search-function (but of course that is also no standard, but the most common case i think,or not ?!)
I even dont know any engine which is doing so...

Hmm, i dont know now if your statement is just a proposal or do
you refer to some kind of already existing specification ?

(if it is a proposal, my first impression is that this does not solve the
problem of "pre-" or "post-" counting nodes like the thing with futility pruning)

Michael

I did not write "increment with its moveDo() procedure", I wrote "making a move increments ...". The concrete implementation is a different animal.

Crafty increments after each MakeMove in the search.

Stockfish increments at the beginning of search() and qsearch() but takes care, to my understanding, that making a move will always cause either search() or qsearch() to be called.

Fruit 2.1 does basically the same but simpler.

IvanHoe (a recent version 49) increments in MakeWhite() and MakeBlack().

Of course there will be a lot of very different implementations around. And yes, it is possible that there are also engines that do not increment the node counter after *every* move being made, e.g. in case of futility pruning. But even if this makes a difference and does not allow to perfectly compare these node counts with those of other engines, it will not affect the EBF much.

Sven