Incomputing,tree data structures, andgame theory, thebranching factor is the number ofchildren at eachnode, theoutdegree. If this value is not uniform, anaverage branching factor can be calculated.
For example, inchess, if a "node" is considered to be a legal position, the average branching factor has been said to be about 35,[1][2] and a statistical analysis of over 2.5 million games revealed an average of 31.[3] 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 gameGo is 250.[1]
Higher branching factors make algorithms that follow every branch at every node, such as exhaustivebrute force searches, computationally more expensive due to theexponentially increasing number of nodes, leading tocombinatorial explosion.
For example, if the branching factor is 10, then there will be 10 nodes one level down from the current position, 102 (or 100) nodes two levels down, 103 (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 apruning 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).
The rate at which possible positions increase is directly related to a game's "branching factor," or the average number of moves available on any given turn. Chess's branching factor is 35. Go's is 250. Games with high branching factors make classic search algorithms likeminimax extremely costly.