In
computing
Computing is any goal-oriented activity requiring, benefiting from, or creating computing machinery. It includes the study and experimentation of algorithmic processes, and development of both hardware and software. Computing has scientific, e ...
,
tree data structure
In computer science, a tree is a widely used abstract data type that represents a hierarchical tree structure with a set of connected nodes. Each node in the tree can be connected to many children (depending on the type of tree), but must be conn ...
s, and
game theory
Game theory is the study of mathematical models of strategic interactions among rational agents. Myerson, Roger B. (1991). ''Game Theory: Analysis of Conflict,'' Harvard University Press, p.&nbs1 Chapter-preview links, ppvii–xi It has appli ...
, the branching factor is the number of
children
A child ( : children) is a human being between the stages of birth and puberty, or between the developmental period of infancy and puberty. The legal definition of ''child'' generally refers to a minor, otherwise known as a person younger ...
at each
node
In general, a node is a localized swelling (a "knot") or a point of intersection (a vertex).
Node may refer to:
In mathematics
*Vertex (graph theory), a vertex in a mathematical graph
*Vertex (geometry), a point where two or more curves, lines, ...
, the
outdegree
In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs.
Definition
In formal terms, a directed graph is an ordered pai ...
. If this value is not uniform, an ''average branching factor'' can be calculated.
For example, in
chess
Chess is a board game for two players, called White and Black, each controlling an army of chess pieces in their color, with the objective to checkmate the opponent's king. It is sometimes called international chess or Western chess to disti ...
, if a "node" is considered to be a legal position, the average branching factor has been said to be about 35,
and a statistical analysis of over 2.5 million games revealed an average of 31.
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 is 250.
Higher branching factors make algorithms that follow every branch at every node, such as exhaustive
brute force searches, computationally more expensive due to the
exponentially increasing number of nodes, leading to
combinatorial explosion
In mathematics, a combinatorial explosion is the rapid growth of the complexity of a problem due to how the combinatorics of the problem is affected by the input, constraints, and bounds of the problem. Combinatorial explosion is sometimes used ...
.
For example, if the branching factor is 10, then there will be 10 nodes one level down from the current position, 10
2 (or 100) nodes two levels down, 10
3 (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.
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).
See also
*
k-ary tree
In graph theory, an ''m''-ary tree (also known as ''n''-ary, ''k''-ary or ''k''-way tree) is a rooted tree in which each node has no more than ''m'' children. A binary tree is the special case where ''m'' = 2, and a ternary tree is another ...
*
Outdegree
In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs.
Definition
In formal terms, a directed graph is an ordered pai ...
*
Hierarchy
A hierarchy (from Greek: , from , 'president of sacred rites') is an arrangement of items (objects, names, values, categories, etc.) that are represented as being "above", "below", or "at the same level as" one another. Hierarchy is an important ...
*
Hierarchical organization
A hierarchical organization or hierarchical organisation (see spelling differences) is an organizational structure where every entity in the organization, except one, is subordinate to a single other entity. This arrangement is a form of a hierar ...
References
{{reflist, refs=
[{{cite web, title=The Mystery of Go, the Ancient Game That Computers Still Can’t Win
, url= https://www.wired.com/2014/05/the-world-of-computer-go/
, first=Alan, last= Levinovitz , date= 12 May 2014 , publisher= ]Wired
''Wired'' (stylized as ''WIRED'') is a monthly American magazine, published in print and online editions, that focuses on how emerging technologies affect culture, the economy, and politics. Owned by Condé Nast, it is headquartered in San Fra ...
, quote=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 like minimax
Minimax (sometimes MinMax, MM or saddle point) is a decision rule used in artificial intelligence, decision theory, game theory, statistics, and philosophy for ''mini''mizing the possible loss for a worst case (''max''imum loss) scenario. When de ...
extremely costly.
, accessdate= 2014-06-02
Trees (data structures)
Analysis of algorithms
Combinatorial game theory
Computer chess