Game tree branching factor

The branching factor at level 3 is thus 4. Stack Overflow for Teams — Collaborate and share knowledge with a private group. Create a free Team What is Teams? Collectives on Stack Overflow. Learn more. Asked 4 years, 1 month ago.

Active 2 months ago. Viewed 20k times. The answer is 4, but can someone tell me why, I thought that it was 2. Improve this question. Cynical 8, 1 1 gold badge 14 14 silver badges 30 30 bronze badges. Wikipedia: en. Add a comment. Active Oldest Votes. From Wikipedia: In computing, tree data structures, and game theory, the branching factor is the number of children at each node, the outdegree.

This is called the average branching factor of the game tree. The effective branching factor EBF , related to iterative deepening of depth-first search , is conventionally defined as average ratio of nodes or time used revisited of the current iteration N versus the previous iteration N-1 [3]. Due to the odd-even effect of Alpha-Beta as described by Michael Levin's Theorem , this is lower if 'N' is even, and higher if 'N' is odd. Due to extensions , reductions and various pruning techniques , this odd-even effect is diminishing accordantly.

One may also use the square root of the ratio of two odd or even iterations. Steven Edwards made following reasonable proposal of a Mean Branching Factor [8] :. From Chessprogramming wiki. All game trees require the same script concepts. The names given to these scripts in this article are not official, but rather represent the functions of the scripts. The above method shows only the basic application of a game tree. In reality, the above method is not applicable to many games without some modifications.

The above script should lay the ground-work for any game tree, but is not, by any means, optimal. Here are some ways to improve a game-tree's speed or performance. Though searching every move is possible, it is often faster to just think forwards through the game about moves.

Humans play a game similarly. They do not calculate through the entire game for each move; they always think through the consequences of a given move moves in the future, and decide based on them.

Even modern computers with incredibly powerful processors are incapable of searching anywhere near this.

But computers are easily capable of searching 4 or 5 moves deep, and looking at the position to see who is winning, and this is what they do. Of course, the computer's decision will not be perfect if it does not search to the completion of the game. Thus, depth is often the control behind difficulty levels. A more difficult computer player will search to a higher depth, but will have the disadvantage of being slower.

In chess, a more suitable way to see who is "winning" is to count out the points each piece is worth. For instance, the "value" of a board could be calculate by adding up all the "good pieces' points" and subtracting all the "bad pieces' points" each chess piece is generally assigned a value, with a pawn being valued a 1-point, and a queen at 9 points. The more accurate the evaluation script, the better the moves will be, but the longer in general they'll take to run. It is important to find a balance between accuracy and speed.

More speed allows searching deeper, while greater accuracy makes the depth searched more effective.