25,161
edits
Changes
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..."
'''[[Main Page|Home]] * [[Search]] * [[Search Tree|Tree]] * Branching Factor'''
[[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 [[Nodes|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=
In [[Chess|chess]], in average there are about 35-38 [[Moves|moves]] per [[Chess Position|position]]. One additional cycle of growth expands each [[Leaf Node|leaf]] so far accordantly. This is called the average branching factor of the [https://en.wikipedia.org/wiki/Game_tree game tree].
<span id="EffectiveBranchingFactor"></span><span id="EBF"></span>
=Effective Branching Factor=
The effective branching factor (EBF), related to [[Iterative Deepening|iterative deepening]] of [[Depth-First|depth-first search]], is conventionally defined as average ratio of [[Node|nodes]] (or time used) revisited of the current [[Iteration|iteration]] N versus the previous iteration N-1 <ref>[http://www.talkchess.com/forum/viewtopic.php?t=39073 EBF definition problem in chess wiki] by [[Daniel Shawul]], [[CCC]], May 13, 2011</ref>.
* In pure [[Minimax]], the effective branching factor is equal to the average branching factor
* In [[Alpha-Beta]], assuming good [[Move Ordering|move ordering]], the branching factor is reduced to about square root of the average branching factor <ref>[[Gérard M. Baudet]] ('''1978'''). ''On the branching factor of the alpha-beta pruning algorithm''. [[Artificial Intelligence#Journals|Artificial Intelligence]] 10</ref><ref>[[Judea Pearl]] ('''1982'''). ''[http://portal.acm.org/citation.cfm?id=358616&dl=ACM&coll=DL&CFID=27355608&CFTOKEN=40935826 The Solution for the Branching Factor of the Alpha-Beta Pruning Algorithm and its Optimality]''. [[ACM#Communications|Communications of the ACM]], Vol. 25, No. 8
</ref>
* Alpha-beta enhancements, [[Transposition Table|transposition tables]], [[Null Move Pruning|null move pruning]] and [[Late Move Reductions|late move reductions]] further reduce the EBF below three, strong programs even near or below two <ref>[http://www.talkchess.com/forum/viewtopic.php?t=48281 Branching Factor of top engines] by [[Kai Laskos]], [[CCC]], June 15, 2013 » [[Houdini|Houdini 3]], [[Stockfish|Stockfish 3]], [[Komodo|Komodo 5 CCT]], [[Shredder|Shredder 6]]</ref>
EBF(N-1) ::= nodes(N-1) / nodes(N-2)
EBF(N) ::= nodes(N) / nodes(N-1)
Due to the [[Odd-Even Effect|odd-even effect]] of [[Alpha-Beta]] as described by [[Michael Levin#Theorem|Michael Levin's Theorem]], this is lower if 'N' is even, and higher if 'N' is odd. Due to [[Extensions|extensions]], [[Reductions|reductions]] and various [[Pruning|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 <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=181822&t=20301 Re: Calculation of branching factor] by [[Tord Romstad]], March 28, 2008</ref>, despite some programs even perform ID depth increments of [[Depth#FractionalPlies|fractions]] of one ply.
=Mean Branching Factor=
[[Steven Edwards]] made following reasonable proposal of a Mean Branching Factor <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=181617&t=20301 Re: Calculation of branching factor] by [[Steven Edwards]], March 27, 2008</ref>:
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#Journals|Artificial Intelligence]] 10
* [[Judea Pearl]] ('''1982'''). ''[http://portal.acm.org/citation.cfm?id=358616&dl=ACM&coll=DL&CFID=27355608&CFTOKEN=40935826 The Solution for the Branching Factor of the Alpha-Beta Pruning Algorithm and its Optimality]''. [[ACM#Communications|Communications of the ACM]], Vol. 25, No. 8
=Forum Posts=
==1997 ...==
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/21c702f358784af branching factor question] by vince, [[Computer Chess Forums|rgcc]], June 04, 1997
* [https://www.stmintz.com/ccc/index.php?id=69483 Please, say in few words what can reduce the "branching factor"] by [[Leonid Liberman|Leonid]], [[CCC]], September 19, 1999
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=104182 Branching factor, make me confuse more that ever] by [[Leonid Liberman|Leonid]], [[CCC]], April 01, 2000
* [https://www.stmintz.com/ccc/index.php?id=152665 Definition of branching factor?] by [[Severi Salminen]], [[CCC]], January 30, 2001
* [https://www.stmintz.com/ccc/index.php?id=198563 Branching Factor = q/p ?] by [[Matthias Gemuh]], [[CCC]], November 23, 2001
* [https://www.stmintz.com/ccc/index.php?id=259843 Measured min-max branching factor] by [[James Swafford]], [[CCC]], October 17, 2002
* [https://www.stmintz.com/ccc/index.php?id=289795 What's best low BF or good WAC result?] by [[Albert Bertilsson]], [[CCC]], March 18, 2003
* [https://www.stmintz.com/ccc/index.php?id=301402 PVS and MTD(f) branching factor] by [[Russell Reagan]], [[CCC]], June 17, 2003 » [[Principal Variation Search|PVS]], [[MTD(f)]]
* [https://www.stmintz.com/ccc/index.php?id=303316 Improvements in BF makes my MoveGen suck =(] by [[Albert Bertilsson]], [[CCC]], June 26, 2003 » [[Move Generation]]
* [https://www.stmintz.com/ccc/index.php?id=311344 To Ed: Branching factor formula in Rebel 12] by [[Federico Andrés Corigliano|Federico Corigliano]], [[CCC]], August 15, 2003 » [[Rebel]]
* [https://www.stmintz.com/ccc/index.php?id=328924 Question about evaluation and branch factor] by [[Marcus Prewarski]], [[CCC]], November 20, 2003 » [[Evaluation]]
==2005 ...==
* [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
==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=37910 EBF question] by [[Clemens Pruell]], [[CCC]], February 01, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=39073 EBF definition problem in chess wiki] by [[Daniel Shawul]], [[CCC]], May 13, 2011
* [http://www.open-chess.org/viewtopic.php?f=5&t=1403 Node counts at a given depth/iteration in search] by [[Mark Watkins|BB+]], [[Computer Chess Forums|OpenChess Forum]], May 23, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=41001 Bigger steps when branching factor < 2?] by [[Marcel van Kervinck]], [[CCC]], November 05, 2011 » [[Iterative Deepening]]
* [http://www.talkchess.com/forum/viewtopic.php?t=48281 Branching Factor of top engines] by [[Kai Laskos]], [[CCC]], June 15, 2013 » [[Houdini|Houdini 3]], [[Stockfish|Stockfish 3]], [[Komodo|Komodo 5 CCT]], [[Shredder|Shredder 6]]
* [http://www.talkchess.com/forum/viewtopic.php?t=53807 Some fun with Komodo 8] by [[Kai Laskos]], [[CCC]], September 23, 2014 » [[Komodo#8|Komodo 8]]
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=63467 High branching factor when mate score is found] by [[Sander Maassen vd Brink]], [[CCC]], March 16, 2017
=External Links=
* [https://en.wikipedia.org/wiki/Branching_factor Branching factor from Wikipedia]
* [https://en.wikipedia.org/wiki/Combinatorial_explosion Combinatorial explosion from Wikipedia]
* [http://www.fastgm.de/branching-factor.html Branching Factor] from [[FGRL]] by [[Andreas Strangmüller]]
* [[Videos#LedZeppelin|Led Zeppelin]] - [https://en.wikipedia.org/wiki/How_Many_More_Times How Many More Times] (Danish TV 1969) , [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=zE-JQzj2aEA|alignment=left|valignment=top}}
=References=
<references />
'''[[Search Tree|Up one Level]]'''
[[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 [[Nodes|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=
In [[Chess|chess]], in average there are about 35-38 [[Moves|moves]] per [[Chess Position|position]]. One additional cycle of growth expands each [[Leaf Node|leaf]] so far accordantly. This is called the average branching factor of the [https://en.wikipedia.org/wiki/Game_tree game tree].
<span id="EffectiveBranchingFactor"></span><span id="EBF"></span>
=Effective Branching Factor=
The effective branching factor (EBF), related to [[Iterative Deepening|iterative deepening]] of [[Depth-First|depth-first search]], is conventionally defined as average ratio of [[Node|nodes]] (or time used) revisited of the current [[Iteration|iteration]] N versus the previous iteration N-1 <ref>[http://www.talkchess.com/forum/viewtopic.php?t=39073 EBF definition problem in chess wiki] by [[Daniel Shawul]], [[CCC]], May 13, 2011</ref>.
* In pure [[Minimax]], the effective branching factor is equal to the average branching factor
* In [[Alpha-Beta]], assuming good [[Move Ordering|move ordering]], the branching factor is reduced to about square root of the average branching factor <ref>[[Gérard M. Baudet]] ('''1978'''). ''On the branching factor of the alpha-beta pruning algorithm''. [[Artificial Intelligence#Journals|Artificial Intelligence]] 10</ref><ref>[[Judea Pearl]] ('''1982'''). ''[http://portal.acm.org/citation.cfm?id=358616&dl=ACM&coll=DL&CFID=27355608&CFTOKEN=40935826 The Solution for the Branching Factor of the Alpha-Beta Pruning Algorithm and its Optimality]''. [[ACM#Communications|Communications of the ACM]], Vol. 25, No. 8
</ref>
* Alpha-beta enhancements, [[Transposition Table|transposition tables]], [[Null Move Pruning|null move pruning]] and [[Late Move Reductions|late move reductions]] further reduce the EBF below three, strong programs even near or below two <ref>[http://www.talkchess.com/forum/viewtopic.php?t=48281 Branching Factor of top engines] by [[Kai Laskos]], [[CCC]], June 15, 2013 » [[Houdini|Houdini 3]], [[Stockfish|Stockfish 3]], [[Komodo|Komodo 5 CCT]], [[Shredder|Shredder 6]]</ref>
EBF(N-1) ::= nodes(N-1) / nodes(N-2)
EBF(N) ::= nodes(N) / nodes(N-1)
Due to the [[Odd-Even Effect|odd-even effect]] of [[Alpha-Beta]] as described by [[Michael Levin#Theorem|Michael Levin's Theorem]], this is lower if 'N' is even, and higher if 'N' is odd. Due to [[Extensions|extensions]], [[Reductions|reductions]] and various [[Pruning|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 <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=181822&t=20301 Re: Calculation of branching factor] by [[Tord Romstad]], March 28, 2008</ref>, despite some programs even perform ID depth increments of [[Depth#FractionalPlies|fractions]] of one ply.
=Mean Branching Factor=
[[Steven Edwards]] made following reasonable proposal of a Mean Branching Factor <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=181617&t=20301 Re: Calculation of branching factor] by [[Steven Edwards]], March 27, 2008</ref>:
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#Journals|Artificial Intelligence]] 10
* [[Judea Pearl]] ('''1982'''). ''[http://portal.acm.org/citation.cfm?id=358616&dl=ACM&coll=DL&CFID=27355608&CFTOKEN=40935826 The Solution for the Branching Factor of the Alpha-Beta Pruning Algorithm and its Optimality]''. [[ACM#Communications|Communications of the ACM]], Vol. 25, No. 8
=Forum Posts=
==1997 ...==
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/21c702f358784af branching factor question] by vince, [[Computer Chess Forums|rgcc]], June 04, 1997
* [https://www.stmintz.com/ccc/index.php?id=69483 Please, say in few words what can reduce the "branching factor"] by [[Leonid Liberman|Leonid]], [[CCC]], September 19, 1999
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=104182 Branching factor, make me confuse more that ever] by [[Leonid Liberman|Leonid]], [[CCC]], April 01, 2000
* [https://www.stmintz.com/ccc/index.php?id=152665 Definition of branching factor?] by [[Severi Salminen]], [[CCC]], January 30, 2001
* [https://www.stmintz.com/ccc/index.php?id=198563 Branching Factor = q/p ?] by [[Matthias Gemuh]], [[CCC]], November 23, 2001
* [https://www.stmintz.com/ccc/index.php?id=259843 Measured min-max branching factor] by [[James Swafford]], [[CCC]], October 17, 2002
* [https://www.stmintz.com/ccc/index.php?id=289795 What's best low BF or good WAC result?] by [[Albert Bertilsson]], [[CCC]], March 18, 2003
* [https://www.stmintz.com/ccc/index.php?id=301402 PVS and MTD(f) branching factor] by [[Russell Reagan]], [[CCC]], June 17, 2003 » [[Principal Variation Search|PVS]], [[MTD(f)]]
* [https://www.stmintz.com/ccc/index.php?id=303316 Improvements in BF makes my MoveGen suck =(] by [[Albert Bertilsson]], [[CCC]], June 26, 2003 » [[Move Generation]]
* [https://www.stmintz.com/ccc/index.php?id=311344 To Ed: Branching factor formula in Rebel 12] by [[Federico Andrés Corigliano|Federico Corigliano]], [[CCC]], August 15, 2003 » [[Rebel]]
* [https://www.stmintz.com/ccc/index.php?id=328924 Question about evaluation and branch factor] by [[Marcus Prewarski]], [[CCC]], November 20, 2003 » [[Evaluation]]
==2005 ...==
* [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
==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=37910 EBF question] by [[Clemens Pruell]], [[CCC]], February 01, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=39073 EBF definition problem in chess wiki] by [[Daniel Shawul]], [[CCC]], May 13, 2011
* [http://www.open-chess.org/viewtopic.php?f=5&t=1403 Node counts at a given depth/iteration in search] by [[Mark Watkins|BB+]], [[Computer Chess Forums|OpenChess Forum]], May 23, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=41001 Bigger steps when branching factor < 2?] by [[Marcel van Kervinck]], [[CCC]], November 05, 2011 » [[Iterative Deepening]]
* [http://www.talkchess.com/forum/viewtopic.php?t=48281 Branching Factor of top engines] by [[Kai Laskos]], [[CCC]], June 15, 2013 » [[Houdini|Houdini 3]], [[Stockfish|Stockfish 3]], [[Komodo|Komodo 5 CCT]], [[Shredder|Shredder 6]]
* [http://www.talkchess.com/forum/viewtopic.php?t=53807 Some fun with Komodo 8] by [[Kai Laskos]], [[CCC]], September 23, 2014 » [[Komodo#8|Komodo 8]]
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=63467 High branching factor when mate score is found] by [[Sander Maassen vd Brink]], [[CCC]], March 16, 2017
=External Links=
* [https://en.wikipedia.org/wiki/Branching_factor Branching factor from Wikipedia]
* [https://en.wikipedia.org/wiki/Combinatorial_explosion Combinatorial explosion from Wikipedia]
* [http://www.fastgm.de/branching-factor.html Branching Factor] from [[FGRL]] by [[Andreas Strangmüller]]
* [[Videos#LedZeppelin|Led Zeppelin]] - [https://en.wikipedia.org/wiki/How_Many_More_Times How Many More Times] (Danish TV 1969) , [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=zE-JQzj2aEA|alignment=left|valignment=top}}
=References=
<references />
'''[[Search Tree|Up one Level]]'''
