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

• In pure Minimax, the effective branching factor is equal to the average branching factor
• In Alpha-Beta, assuming good move ordering, the branching factor is reduced to about square root of the average branching factor ^[2][3]
• Alpha-beta enhancements, transposition tables, null move pruning and late move reductions further reduce the EBF below three, strong programs even near or below two ^[4]

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

• Gérard M. Baudet (1978). On the branching factor of the alpha-beta pruning algorithm. Artificial Intelligence 10
• 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

Forum Posts

1997 ...

• branching factor question by vince, rgcc, June 04, 1997
• Please, say in few words what can reduce the "branching factor" by Leonid, CCC, September 19, 1999

2000 ...

• Branching factor, make me confuse more that ever by Leonid, CCC, April 01, 2000
• Definition of branching factor? by Severi Salminen, CCC, January 30, 2001
• Branching Factor = q/p ? by Matthias Gemuh, CCC, November 23, 2001
• Measured min-max branching factor by James Swafford, CCC, October 17, 2002
• What's best low BF or good WAC result? by Albert Bertilsson, CCC, March 18, 2003
• PVS and MTD(f) branching factor by Russell Reagan, CCC, June 17, 2003 » PVS, MTD(f)
• Improvements in BF makes my MoveGen suck =( by Albert Bertilsson, CCC, June 26, 2003 » Move Generation
• To Ed: Branching factor formula in Rebel 12 by Federico Corigliano, CCC, August 15, 2003 » Rebel
• Question about evaluation and branch factor by Marcus Prewarski, CCC, November 20, 2003 » Evaluation

2005 ...

• iterative deepening and branching factor by J. Wesley Cleveland, CCC, July 09, 2007 » Iterative Deepening
• Calculation of branching factor by PK-4, CCC, March 23, 2008

2010 ...

• effective branching factor of chess programs by Uri Blass, CCC, December 21, 2010
• EBF question by Clemens Pruell, CCC, February 01, 2011
• EBF definition problem in chess wiki by Daniel Shawul, CCC, May 13, 2011
• Node counts at a given depth/iteration in search by BB+, OpenChess Forum, May 23, 2011
• Bigger steps when branching factor < 2? by Marcel van Kervinck, CCC, November 05, 2011 » Iterative Deepening
• Branching Factor of top engines by Kai Laskos, CCC, June 15, 2013 » Houdini 3, Stockfish 3, Komodo 5 CCT, Shredder 6
• Some fun with Komodo 8 by Kai Laskos, CCC, September 23, 2014 » Komodo 8

2015 ...

• High branching factor when mate score is found by Sander Maassen vd Brink, CCC, March 16, 2017

External Links

• Branching factor from Wikipedia
• Combinatorial explosion from Wikipedia
• Branching Factor from FGRL by Andreas Strangmüller
• Led Zeppelin - How Many More Times (Danish TV 1969) , YouTube Video
  

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