Branching Factor

From Chessprogramming wiki
Jump to: navigation, search

Home * Search * Tree * Branching Factor

A red-black tree with branching factor 2 [1]

In computing, tree data structures, and game theory, the Branching Factor is the number of children at each node, the outdegree. If this value is not uniform, an average branching factor can be calculated [2].

Average Branching Factor

In chess, in average there are about 35-38 moves per position. One additional cycle of growth expands each leaf so far accordantly. This is called the average branching factor of the game tree.

Effective Branching Factor

The effective branching factor (EBF), related to iterative deepening of depth-first search, is conventionally defined as average ratio of nodes (or time used) revisited of the current iteration N versus the previous iteration N-1 [3].

EBF(N-1) ::= nodes(N-1) / nodes(N-2)
EBF(N)   ::= nodes(N)   / nodes(N-1)

Due to the odd-even effect of Alpha-Beta as described by Michael Levin's Theorem, this is lower if 'N' is even, and higher if 'N' is odd. Due to extensions, reductions and various pruning techniques, this odd-even effect is diminishing accordantly. One may also use the square root of the ratio of two odd or even iterations.

EBF ::= √(nodes(N) / nodes(N-2));

However, with all kind of extensions, reductions, and forward pruning 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, which makes such an effective branching factor quite useless to compare between programs [7], despite some programs even perform ID depth increments of fractions of one ply.

Mean Branching Factor

Steven Edwards made following reasonable proposal of a Mean Branching Factor [8]:

MBF ::= count of all nodes / count of non terminal nodes

Publications

Forum Posts

1997 ...

2000 ...

2005 ...

2010 ...

2015 ...

2020 ...

External Links

References

Up one Level