# Difference between revisions of "Branching Factor"

GerdIsenberg (talk | contribs) |
GerdIsenberg (talk | contribs) |
||

Line 48: | Line 48: | ||

* [http://www.talkchess.com/forum/viewtopic.php?t=14963 iterative deepening and branching factor] by [[J. Wesley Cleveland]], [[CCC]], July 09, 2007 » [[Iterative Deepening]] | * [http://www.talkchess.com/forum/viewtopic.php?t=14963 iterative deepening and branching factor] by [[J. Wesley Cleveland]], [[CCC]], July 09, 2007 » [[Iterative Deepening]] | ||

* [http://www.talkchess.com/forum/viewtopic.php?t=20301 Calculation of branching factor] by PK-4, [[CCC]], March 23, 2008 | * [http://www.talkchess.com/forum/viewtopic.php?t=20301 Calculation of branching factor] by PK-4, [[CCC]], March 23, 2008 | ||

+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=24535 Reducing branching factor] by [[Fermin Serrano]], [[CCC]], October 26, 2008 | ||

==2010 ...== | ==2010 ...== | ||

* [http://www.talkchess.com/forum/viewtopic.php?t=37205 effective branching factor of chess programs] by [[Uri Blass]], [[CCC]], December 21, 2010 | * [http://www.talkchess.com/forum/viewtopic.php?t=37205 effective branching factor of chess programs] by [[Uri Blass]], [[CCC]], December 21, 2010 |

## Revision as of 15:25, 16 January 2020

**Home * Search * Tree * Branching Factor**

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

## Contents

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

- 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
^{[4]}^{[5]} - 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
^{[6]}

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

- 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 - Stefan Edelkamp, Richard Korf (
**1998**).*The Branching Factor of Regular Search Spaces*. AAAI-98, pdf

# 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
- Reducing branching factor by Fermin Serrano, CCC, October 26, 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

- ↑ Example of red-black tree by Cburnett, December 30, 2006, Wikimedia Commons
- ↑ Branching factor from Wikipedia
- ↑ EBF definition problem in chess wiki by Daniel Shawul, CCC, May 13, 2011
- ↑ 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 - ↑ Branching Factor of top engines by Kai Laskos, CCC, June 15, 2013 » Houdini 3, Stockfish 3, Komodo 5 CCT, Shredder 6
- ↑ Re: Calculation of branching factor by Tord Romstad, March 28, 2008
- ↑ Re: Calculation of branching factor by Steven Edwards, March 27, 2008