Branching Factor

Home * Search * Tree * Branching Factor

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 [1].


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 ::= sqrt(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 [5], 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 [6]:
MBF ::= count of all nodes / count of non terminal nodes

Publications


Forum Posts

1997 ...

2000 ...

2005 ...

2010 ...

2015 ...


External Links


References

  1. ^ EBF definition problem in chess wiki by Daniel Shawul, CCC, May 13, 2011
  2. ^ Gérard M. Baudet (1978). On the branching factor of the alpha-beta pruning algorithm. Artificial Intelligence 10
  3. ^ Judea Pearl (1982). The Solution for the Branching Factor of the Alpha-Beta Pruning Algorithm and its Optimality. Communications of the ACM, Vol. 25, No. 8
  4. ^ Branching Factor of top engines by Kai Laskos, CCC, June 15, 2013 » Houdini 3, Stockfish 3, Komodo 5 CCT, Shredder 6
  5. ^ Re: Calculation of branching factor by Tord Romstad, March 28, 2008
  6. ^ Re: Calculation of branching factor by Steven Edwards, March 27, 2008

What links here?


Up one Level