The N-ply average local branching factor

The aim here is to take a tree of moves and define a single number which will behave like a branching factor corresponding to that tree. For example, in the simplest case every node at level d has b children at level d+1, in which case the branching factor for that tree will come to be b. For Eternity, you get a local tree of moves for every site you want to consider tiling. For a given site, the branches at the top level of the tree correspond to ways of tiling that site, and the branches at the next level correspond to followup moves in some restricted local sense (e.g., must place adjacent to a previously placed piece).

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

     (a)    |              (b)    /\                 (c)       /|\
            |                    /  \                         / | \
            |                   /    \                       /  |  \
            |                  /      \                     /   |   \
           /|\                 |      /\                    |   |   |
          / | \                |     /  \                   |   |   |
         /  |  \               |    /    \                  |   |   |
        /   |   \              |   /      \                 |   |   |
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.

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 sn, then the average branching factor is the limit of the nth root of sn.

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 B. We'll call this 1. And there is the one-ply tree
          /\   
         /  \  
        /    \ 
       /      \
which comes from playing the right move from B. We'll call this 2.
The initial state of the game is
BBBBBBBBB...
S's strategy will be to force P to play in a 1 if one exists, otherwise force P to play in the first new B (never letting P play in a 2). So after one move, P can arrive at
1BBBBBBBB...
or
2BBBBBBBB...
After two moves, P can arrive at
-BBBBBBBB...,
21BBBBBBB...
or
22BBBBBBB...
and after three moves, the list is
-1BBBBBBB...
-2BBBBBBB...
2-BBBBBBB...
221BBBBBB...
222BBBBBB...
You can get the formula for sn, the number of reachable states after n moves, by considering what happens after the first move. If the first move is to
2BBBBBBBB...
then the number of states reachable after n moves will be sn-1, because the 2 is never played in and so can be ignored. So this state is like the initial state, but there are only n-1 moves remaining. If the first move is to
1BBBBBBBB...
then the number of states reachable after n moves will be sn-2, because the 1 is always played in next move, which absorbs a move, and after that you get back to a state like the initial state, but with only n-2 moves left to play. So sn=sn-1+sn-2 and sn is the nth Fibonacci number, which means the limit of the nth root of sn is (1+sqrt(5))/2=1.618....

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 b1,b2,b3,b4,... where b1<=b2<=b3<=..., then the number of states reachable after n moves should be somewhere between b1n and b1b2b3...bn.

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(b2,sum of labels of children). Label each level n-3 node with the expression min(b3,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)=bn. For example the equation for (a) is min(b,3)=b2, for (b) it's min(b,2)+1=b2, and for (c) it's 3min(b,1)=b2. 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=b2 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=b2, 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=b2, 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.

Some more detailed examples.

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

      min(b^2,min(b,1)+min(b,2))
                /\           
               /  \         
              /    \        
             /      \       
         min(b,1) min(b,2)
             |      /\      
             |     /  \     
             |    /    \    
             |   /      \   
             1  1        1
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.

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.

                   /\
                  /  \
                 /    \
                /      \
               /        \
              /          \
             /            \
            /              \
  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
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

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.

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

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

                /\           
               /  \         
              /    \        
             /      \       
             |      /\      
             |     /  \     
             |    /    \    
             |   /      \   
is equivalent to
                /\           
               /  \         
              /    \        
             /      \       
             |       n
             |
             |
             |
(where n represents a node with n children) if and only if n>=(1+sqrt(5))/2. So in the original n=2 example, some funny fraction of those 2 branches were redundant.