In chess, in average there are about 35-38 moves per position. One additional cycle of growth expands each leaf so far accordantly. This is called the average branching factor of the game tree.

Effective Branching Factor

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 ^{[1]}.

In pure Minimax, the effective branching factor is equal to the average branching factor

In Alpha-Beta, assuming good move ordering, the branching factor is reduced to about square root of the average branching factor ^{[2]}^{[3]}

However, with all kind of extensions, reductions, and forward pruning applied to the tree, it is not at all clear that the average branch is searched precisely one ply deeper at iteration N+1 than at iteration N, which makes such an effective branching factor quite useless to compare between programs ^{[5]}, despite some programs even perform ID depth increments of fractions of one ply.

Mean Branching Factor

Steven Edwards made following reasonable proposal of a Mean Branching Factor ^{[6]}:

MBF ::= count of all nodes / count of non terminal nodes

## Table of Contents

Home * Search * Tree * Branching Factor## Average Branching Factor

In chess, in average there are about 35-38 moves per position. One additional cycle of growth expands each leaf so far accordantly. This is called the average branching factor of the game tree.## Effective Branching Factor

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^{[1]}.^{[2]}^{[3]}^{[4]}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.

However, with all kind of extensions, reductions, and forward pruning applied to the tree, it is not at all clear that the average branch is searched precisely one ply deeper at iteration N+1 than at iteration N, which makes such an effective branching factor quite useless to compare between programs

^{[5]}, despite some programs even perform ID depth increments of fractions of one ply.## Mean Branching Factor

Steven Edwards made following reasonable proposal of a Mean Branching Factor^{[6]}:## Publications

1978).On the branching factor of the alpha-beta pruning algorithm. Artificial Intelligence 101982).The Solution for the Branching Factor of the Alpha-Beta Pruning Algorithm and its Optimality. Communications of the ACM, Vol. 25, No. 8## Forum Posts

## 1997 ...

## 2000 ...

## 2005 ...

## 2010 ...

## External Links

## References

1978).On the branching factor of the alpha-beta pruning algorithm. Artificial Intelligence 101982).The Solution for the Branching Factor of the Alpha-Beta Pruning Algorithm and its Optimality. Communications of the ACM, Vol. 25, No. 8## What links here?

Up one Level