Editing Branching factor (section)

{{Short description|Number of children at each node of a tree}}
[[Image:Red-black tree example.svg|thumb|A [[red–black tree]] with branching factor 2]]

In [[computing]], [[tree data structure]]s, and [[game theory]], the '''branching factor''' is the number of [[child node|children]] at each [[node (computer science)|node]], the [[outdegree]]. If this value is not uniform, an ''average branching factor'' can be calculated.

For example, in [[chess]], if a "node" is considered to be a legal position, the average branching factor has been said to be about 35,<ref name="wired"/><ref>{{cite web | url=http://www.gamedev.net/page/resources/_/technical/artificial-intelligence/chess-programming-part-iv-basic-search-r1171 | title=Chess Programming Part IV: Basic Search | date= 6 August 2000 |first=François Dominic |last=Laramée | publisher=GameDev.net | accessdate=2007-05-01}}</ref> and a statistical analysis of over 2.5 million games revealed an average of 31.<ref>{{cite web |last1=Barnes |first1=David |title=What is the average number of legal moves per turn? |url=https://chess.stackexchange.com/a/24325 |website=Chess Stack Exchange |accessdate=2019-06-01}}</ref> This means that, on average, a player has about 31 to 35 legal moves at their disposal at each turn. By comparison, the average branching factor for the game [[Go (game)|Go]] is 250.<ref name="wired"/>

Higher branching factors make algorithms that follow every branch at every node, such as exhaustive [[brute-force search|brute force searches]], computationally more expensive due to the [[exponential growth|exponentially increasing]] number of nodes, leading to [[combinatorial explosion]].

For example, if the branching factor is 10, then there will be 10 nodes one level down from the current position, 10<sup>2</sup> (or 100) nodes two levels down, 10<sup>3</sup> (or 1,000) nodes three levels down, and so on. The higher the branching factor, the faster this "explosion" occurs. The branching factor can be cut down by a [[pruning (algorithm)|pruning algorithm]].

The average branching factor can be quickly calculated as the number of non-root nodes (the size of the tree, minus one; or the number of edges) divided by the number of non-leaf nodes (the number of nodes with children).