The branching factor of the local tree corresponding to a given site is meant to act like an average local branching factor at that site. If you are carrying out a depth-first search, then once you have worked out what this branching factor is for each site, the site which comes out with the smallest one is meant to be a good choice of site to branch over. If you use 1-ply trees everywhere then this is just the well-known method of choosing the site which has the fewest number of ways to tile it.

Let N be the depth of the tree (ply). If N=1 it is pretty
uncontroversial that the branching factor at a node is the number of
legal moves available, or the number of child nodes of the top node.
But for larger N it starts to get more interesting. Take the example
of N=2. If there is only one piece that can initially be placed at a
site, then it doesn't really matter what can be placed next - we may
as well place that unique piece immediately and then rethink
globally. So it would be wrong to think of the three two-ply trees

as equivalent even though they have the same number of endnodes after 2 levels, because (a) is morally the same as a branching factor 1 site. Here (a) is meant to represent a site where there is one legal move, and after that move is made there will be three legal moves next. (b) represents a site where there are two legal moves B1 and B2. After B1 there is only one move, and after B2 there are two moves. And of course (c) represents the case where there are three legal moves intially, but after any one of them, the next move will then be unique.(a) | (b) /\ (c) /|\ | / \ / | \ | / \ / | \ | / \ / | \ /|\ | /\ | | | / | \ | / \ | | | / | \ | / \ | | | / | \ | / \ | | |

Because these are two ply trees, to compare them with one ply trees we should talk of average branching factor (in the geometric, i.e. multiplicative, sense). For example the average branching factor in case (c) is sqrt(3)=1.732... because the overall branching factor is 3. But for (a) it comes out as 1 and for (b) it comes out as (1+sqrt(5))/2=1.618.... This strange number arises as a kind of "thermal limit" when thinking of the process as a two player game, where one player chooses the site (and is trying to minimise the number of endnodes) and the other player chooses the piece placement (and is trying to maximise the number of endnodes). So according to our method, we say that the average branching factors are in order (a)<(b)<(c), i.e., (a) is the best site to choose for tiling, or if (a) is not available then (b) is better than (c).

To see how these numbers might arise, let's define the average
branching factor first in terms of a two-player game. To work it out
for a tree, T, imagine a board where there are many copies of T which
don't interact at all. Now think about the game between two players S
and P. The state of a game is a sequence of (distinguishable) trees,
and the initial state is many copies of the tree T. First S chooses a
tree, and then P chooses a child of the topnode of that tree. The tree
then changes into the tree rooted on that child - the rest of the tree
is discarded. If a tree gets down to the bottom then it is thrown away
altogether (it doesn't become the one-node tree). Run the game for n
moves and look at the final state. Then run the game again for n moves
and look at the final state. Keep doing this, remembering the final
state each time. P's objective is to vary his play to arrive at as
many different final states as possible, and S's objective is to keep
the number of final states to a minimum. If after n moves, the number
of possible final states is s_{n}, then the average branching
factor is the limit of the n^{th} root of s_{n}.

Take the example of (b). There are three sorts of trees that can arise
in the course of the game. There is the two-ply tree (b), which we'll call ** B**.
There is the one-ply tree

which comes from playing the left move from| | | |

/\ / \ / \ / \

The initial state of the game is

S's strategy will be to force P to play in a

or

After two moves, P can arrive at

or

and after three moves, the list is

You can get the formula for s

then the number of states reachable after n moves will be s

then the number of states reachable after n moves will be s

The idea is that this will also work to some extent when you mix trees
of different types, not just take copies of one type of tree. If the
branching factors of trees are
b_{1},b_{2},b_{3},b_{4},... where
b_{1}<=b_{2}<=b_{3}<=..., then the
number of states reachable after n moves should be somewhere between
b_{1}^{n} and
b_{1}b_{2}b_{3}...b_{n}.

As you might expect, there is a less cumbersome way to calculate these
average branching factors. We can go more-or-less directly to the
defining polynomial. The procedure is as follows. Take an n-ply
tree. Label all the level n (i.e. bottom level) nodes with the number
1. Label each level n-1 node with the expression min(b,sum of labels
of children). Label each level n-2 node with the expression
min(b^{2},sum of labels of children). Label each level n-3
node with the expression min(b^{3},sum of labels of children).
Keep going until you've labelled the level 1 nodes. Then solve the
equation (sum of labels of level 1 nodes)=b^{n}. For example
the equation for (a) is min(b,3)=b^{2}, for (b) it's
min(b,2)+1=b^{2}, and for (c) it's 3min(b,1)=b^{2}.
It should be possible to eliminate the mins by finding the
subexpression min(A,B) for which A=B is solved by the largest b, and
then evaluating the left hand side and right hand side of the
polynomial equation at this b. Because the right hand side is higher
order, if it is larger then b is too high (and vice versa). Because
one of A,B (say A) will be of higher order, if b is too high then the
min(A,B)=A and if b is too low then min(A,B)=B.

For example with (a)
at b=3 we have 3<9, so b=3 is too high, so min(b,3)=b, and the equation
becomes b=b^{2} which has the solution b=1. (b=0 is not allowed unless
there is no way to get to the bottom of the tree).

With (b) at b=2 we have 3<4, so b=2 is too high, so min(b,3)=b, and the equation
becomes b+1=b^{2}, with solution b=(1+sqrt(5))/2.

With (c) at b=1 we have 3>2, so b=1 is too low, so min(b,1)=1, and the equation
becomes 3=b^{2}, with solution b=sqrt(3).

In practice, the program only had to find the site with the smallest average branching factor, not actually evaluate it, and this was a bit easier: no polynomial equations actually need be solved.

(1) Here is how (b) is labelled.

The branching factor is the solution to the equation (sum of level 1 labels)=b^2, i.e., min(b,1)+min(b,2)=b^2 (and b>0). The label of the top node is irrelevant.min(b^2,min(b,1)+min(b,2)) /\ / \ / \ / \ min(b,1) min(b,2) | /\ | / \ | / \ | / \ 1 1 1

If you try b=2, then the left hand side (LHS) becomes 3 and the RHS 4. That means that b<2, because the RHS increases faster than the LHS. So min(b,2)=b.

If you try b=1, then the LHS becomes 2 and the RHS 1. That means that b>1, so min(b,1)=1.

Therefore the equation becomes 1+b=b^2, with solution b=(1+sqrt(5))/2=1.618...

(2) Here is a 3-ply example

To fit things in, m(x,y) means min(x,y), the minimum of x and y.

The equation to be solved is m(b^2,m(b,1)+m(b,2))+m(b^2,m(b,1)+m(b,3))=b^3/\ / \ / \ / \ / \ / \ / \ / \ m(b^2,m(b,1)+m(b,2)) m(b^2,m(b,1)+m(b,3)) /\ /\ / \ / \ / \ / \ / \ / \ m(b,2) m(b,1) m(b,1) m(b,3) /\ | | /|\ / \ | | / | \ 1 1 1 1 1 1 1

As before, we try b=3 and find LHS<RHS so b<3, try b=2 and find LHS<RHS so b<2, try b=1 and find LHS>RHS so b>1. So m(b,3)=b, m(b,2)=b, and m(b,1)=1 and the equation simplifies to m(b^2,b+1)+m(b^2,b+1)=b^3

Now we need to know if b+1>b^2, so try b=(1+sqrt(5))/2. We find that LHS>RHS, so this b is too low, so b>(1+sqrt(5))/2, so b+1<b^2, so m(b^2,b+1)=b+1, so the equation simplifies to 2(b+1)=b^3, which has the solution b=1.76929...

This thing is a generalisation of the idea that the three 2-ply trees

should all be treated as the same (and have branching factor 1): if there is a unique move, you may as well play it first and then rethink everything.| | | | | | | | | | | | * * * | / \ /|\ | / \ / | \ | / \ / | \ | / \ / | \

But more things like this are true, e.g.

are the same and have branching factor 2./\ /\ / \ / \ / \ / \ / \ and / \ /\ /\ /|\ /\ / \ / \ / | \ / \ / \ / \ / | \ / \

And sometimes you can't cross off a redundant branch entirely, but only partially, e.g. in
the first example,

is equivalent to/\ / \ / \ / \ | /\ | / \ | / \ | / \

/\ / \ / \ / \ | n | | |