Calculation of branching factor

[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

[hgm]

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

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

[sje]

It's easy to do.

Mean branching factor = count of all nodes / count of non terminal nodes

[Dann Corbit]

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.

[sje]

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 assume you mean "previous iteration" and "current iteration". This can be a useful metric, but it can have problems describing the branching factor because of possible search restarts due to intermediate results falling outside an aspiration window.

Oh, and a correction to my earlier post:

Mean branching factor = (count of all nodes - 1) / count of non terminal nodes

(Defined only for graphs with at least two nodes.)

[Dann Corbit]

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 assume you mean "previous iteration" and "current iteration". This can be a useful metric, but it can have problems describing the branching factor because of possible search restarts due to intermediate results falling outside an aspiration window.

Yes, and I imagine I should call it "effective branching factor" EBF because it is the branching factor we achieve in practice and has little relationship to the actual tree (e.g. Chess has a true branching factor of about 35, and effective branching factor of about 6 with null move and about 2 if all the current pruning tricks are applied intelligently).

Oh, and a correction to my earlier post:

Mean branching factor = (count of all nodes - 1) / count of non terminal nodes

(Defined only for graphs with at least two nodes.)

[ernest]

Chess has a true branching factor of about 35, and effective branching factor of about 6 with null move and about 2 if all the current pruning tricks are applied intelligently

My understanding was that 6 (= square root of 35) was simply with efficient alpha-beta (no null move needed)
With null move and some pruning tricks you get to 3 or even 2.5
And with the "best" pruning tricks you even get to 2.

[Tord Romstad]

(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

[wgarvin]

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.

Is "average distance from the root of the tree" even a meaningful metric, though?

Today's searchers are pretty selective. Searching deeply in some parts of the tree is a good thing because the engine has decided that those parts look "interesting". Meanwhile in other parts of the tree, searching deeply is a bad thing because the engine has decided that those parts are hopelessly bad and probably a waste of time. An "average depth" over all nodes, does not distinguish between the two.

Would it be possible to invent a standard metric of some kind that quantified "what percentage of the nodes I searched turned out to be interesting ones"? I.e. how efficiently is the search effort focused?

Maybe at the end of searching a node, it could choose some sort of "interestingness" value between 0.0 and 1.0 for that node, and accumulate those across the search, and divide by total number of nodes to get an "average interestingness". That still leaves the question though, of what is a useful definition of "interestingness" that would be portable across most alpha-beta-based engines?

[Dann Corbit]

Chess has a true branching factor of about 35, and effective branching factor of about 6 with null move and about 2 if all the current pruning tricks are applied intelligently

My understanding was that 6 (= square root of 35) was simply with efficient alpha-beta (no null move needed)
With null move and some pruning tricks you get to 3 or even 2.5
And with the "best" pruning tricks you even get to 2.

Yes, you are clearly correct. An optimally ordered alpha beta gives you sqrt(minimax factor) nodes.