Difference between revisions of "Branching Factor"
GerdIsenberg (talk | contribs) (Created page with "'''Home * Search * Tree * Branching Factor''' FILE:Red-black tree example.svg|border|right|thumb|A [https://en.wikipedia.org/wiki/Red%E2%8...") |
GerdIsenberg (talk | contribs) m |
||
Line 3: | Line 3: | ||
[[FILE:Red-black tree example.svg|border|right|thumb|A [https://en.wikipedia.org/wiki/Red%E2%80%93black_tree red-black tree] with branching factor 2 <ref>Example of red-black tree by [https://en.wikipedia.org/wiki/User:Cburnett Cburnett], December 30, 2006, [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons]</ref> ]] | [[FILE:Red-black tree example.svg|border|right|thumb|A [https://en.wikipedia.org/wiki/Red%E2%80%93black_tree red-black tree] with branching factor 2 <ref>Example of red-black tree by [https://en.wikipedia.org/wiki/User:Cburnett Cburnett], December 30, 2006, [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons]</ref> ]] | ||
− | In [https://en.wikipedia.org/wiki/Computing computing], [https://en.wikipedia.org/wiki/Tree_(data_structure) tree data structures], and [https://en.wikipedia.org/wiki/Game_theory game theory], the '''Branching Factor''' is the number of children at each [[ | + | In [https://en.wikipedia.org/wiki/Computing computing], [https://en.wikipedia.org/wiki/Tree_(data_structure) tree data structures], and [https://en.wikipedia.org/wiki/Game_theory game theory], the '''Branching Factor''' is the number of children at each [[Node|node]], the [https://en.wikipedia.org/wiki/Directed_graph#Indegree_and_outdegree outdegree]. If this value is not uniform, an '''average branching factor''' can be calculated <ref>[https://en.wikipedia.org/wiki/Branching_factor Branching factor from Wikipedia]</ref>. |
=Average Branching Factor= | =Average Branching Factor= |
Revision as of 13:22, 3 May 2018
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
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
- ↑ 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