Calculation of branching factor

[Uri Blass]

(Effective) branching factor is the factor the search time increases per ply depth increase. As plies of depth are meaningless quantities, due to the different extension and reduction policies of different engines, so are the branchig factors.

Exactly. The "search depth" displayed by chess programs is nothing more than the iteration counter, and 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 (even if the initial depth in the call to search() is increased by exactly one ply per iteration, which is not the case in all programs).

In my program, it seems that going from iteration N to N+1 increases the effective search depth by about half a ply. For other programs, the increase might be bigger or smaller, rendering comparisons of effective branching factors useless (just like comparisons of search depths).

Not much that can be done about this. Unless you can devise a universal way to define search depth, of course.

Here's a proposal: Count the number of nodes at each ply in the search tree. The search depth is the average distance from the root of all nodes in the tree. With this definition of depth, it would at least be possible to make somewhat more meaningful comparisons of the search depths of different programs.

Tord

I think that this is misleading.
by selective search that include only single move at every node except the root
I can easily have at iteration 199 the following nodes:
20 node at ply 1,20 nodes at ply 2,20 nodes at ply 3,.....
20 nodes at ply 199

It means that the average depth is 100 when the program searchs iteration 199

I think that the only way to compare depths of different programs is to play games and compare the practical playing strength of the program at fixed depth to
the practical playing strength at fixed depth with no extensions and no reductions(it is also possible to agree about qsearch that includes only captures).

You can modify glaurung to have no reductions and no extensions and play normal glaurung at depth 12 against the modified version at depth 11.

If the result is 50% then you can say that iteration 12 of normal glaurung is equivalent to depth 11.

There may be a problem with big depth because games may take too much time so we can guess some formula based on exrtopolation after having some table of equivalence for small depths.

Uri

[PK-4]

Hi All,
What is the usual method for calculation of branching factor? Any comparison of quoted branching factors would be meaningless unless the same method is used for all engines. Also, is it not better to find branching factor separately for middle game since the usual big improvement in the endgame may mask weakness in the middle game?

Regards

The two most common methods are:
BF = (nodes of this ply) / (nodes of previous ply)
and
BF = (time of this ply) / (time of previous ply)

Just calculate whichever one is simpler for you, because the dimentionless constant is about the same either way.

The best engines today have a branch factor of about 2.

I appreciate this reply. So far I was considering only nodes to calculate effective branching factor(EBF), but 'time' captures the total search effort nicely. Of course one should be careful in using GetTickCount() for this purpose at low time controls at which testing is usually done. The time obtained for searching the penultimate depth can be somewhat inaccurate because of the 1 milisecond resolution of this function as I saw for myself after getting this reply. Is there a standard function with a better resolution, say, 1 microsecond?

I am using nowEBF=sqrt(nodes[N]/nodes[N-2]) which seems to give a stable result. If I use nowEBF=nodes[N]/nodes[N-1] the result is somewhat unstable from move to move, particularly in endgame. This may be due to odd/even ply effect, please comment. I average nowEBF for phases of the game.

I am interested in EBF because it helps in tracking small improvements. It is a better indicator than NPS. If my engine has a poorer NPS but better EBF compared to another engine I know that I shall outsearch the other engine at some higher time control provided EBF is a slowly varying function of time control. For this reason and also because of often seen statements about better engines having EBF of about 2, I am curious and interested in finding a widely acceptable metric of search effectiveness. Matches of course are the ultimate way to decide search effectiveness but not always feasible for me, especially at high time control.

Regards

P.K.Mukhopadhyay

[Ron Murawski]

So far I was considering only nodes to calculate effective branching factor(EBF), but 'time' captures the total search effort nicely. Of course one should be careful in using GetTickCount() for this purpose at low time controls at which testing is usually done. The time obtained for searching the penultimate depth can be somewhat inaccurate because of the 1 milisecond resolution of this function as I saw for myself after getting this reply. Is there a standard function with a better resolution, say, 1 microsecond?


Regards

P.K.Mukhopadhyay

In Windows:

Code: Select all

BOOL QueryPerformanceFrequency(      
    LARGE_INTEGER *lpFrequency
);

"QueryPerformanceFrequency function retrieves the frequency of the high-resolution performance counter, if one exists. The frequency cannot change while the system is running." See:
http://msdn2.microsoft.com/en-us/librar ... S.85).aspx

Code: Select all

BOOL QueryPerformanceCounter(      
    LARGE_INTEGER *lpPerformanceCount
);

"QueryPerformanceCounter function retrieves the current value of the high-resolution performance counter." See:
http://msdn2.microsoft.com/en-us/librar ... S.85).aspx

A LARGE_INTEGER is a 64 bit structure.

Ron