Hey folks, I''m interested in the notion of what we mean when we say "Branching Factor" in relation to game trees. When we look at data-structures in general we usually talk about the degree of the node or tree - the amount of child nodes a parent node has or the maximum alowed in a tree respectively. Sometimes we also say the "arity" of the tree. But with game-trees, the tree wont exist in memory, rather it is created and destroyed on the fly by the iterative nature of the minimax algorithm (or some variation of it). So, is the term "branching factor" exclusive to an algorithmic construction of a tree as in the game tree, or can we say that an "in memory" construction of a tree has a branching factor too? Also, is there a general way of destinguishing between these to notions of trees - ie: do they each have names? Sorry for the academia, im writing a research thing for college and I havnt found anything on this... Thanks. Tim.

Branching factor is just the ratio of how long it takes to search ply n+1 than it takes to search ply n. So if it takes 10 seconds to search to ply 5, and it takes 40 seconds to search to ply 6, then you have a branching factor of 4. You could also measure nodes it takes to search play n+1 divided by nodes to ply n, and it should be about the same.

I don''t think it is specific to any particular type of tree or search. I would guess that different people call it different things depending on which background they come from.

In terms of data structures (as opposed to the branching factor of algorithms)...

Branching factor is used when describing tree structures (although it is occasionally used to talk about other things). The branching factor of a node in a tree is the number of children it has. The average branching factor for a level in a tree is the ratio of the number of children of that level to the number of nodes in that level and finally the average branching factor for a tree is the ratio of the number of nodes to the number of levels.

Of course, then there''s the effective branching factor of a tree, which is the branching factor that a uniform tree of appropriate depth would require for it to contain the same number of nodes as the tree in question.

Cheers,

Timkin