Branching factor

From Wikinfo

In computing, tree data structures, and game theory, the branching factor is the number of children of each node. 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.^[1] This means that at each move, on average, a player has about 35 legal moves, and so, for each legal position (or "node") there are, on average, 35 positions that can follow (when a move is made).

An exhaustive brute-force search of the tree (i.e. by following every branch at every node) usually becomes computationally more expensive the higher the branching factor, due to the exponentially increasing number of nodes (combinatorial explosion). For example, if the branching factor is 10, then there will be 10 nodes one level from the current position, 10² = 100 nodes two levels down, 10³ = 1000 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.

See also

• Hierarchy
• Hierarchical organization

References

1. ^ François Dominic Laramée. "Chess Programming Part IV: Basic Search". GameDev.net. http://www.gamedev.net/reference/articles/article1171.asp. Retrieved on 2007-05-01. 

This page uses content from Wikipedia. The original article was at Branching factor. The list of authors can be seen in the page history. The text of this Wikinfo article is available under the GNU Free Documentation License and the Creative Commons Attribution-Share Alike 3.0 license. English | Română | edit