If at each move there are four pieces that can move, and they can each move right or left, the branching factor of the tree is eight, giving a tree with 1 (depth 0) + 8 (depth 1) + 8 ** 2 + 8 ** 3 + 8 ** 4 = 4681 nodes in it. But, in practice, not all pieces can move in both directions (none of the x pieces in xxxx___oooo can move left, for example), and there may be fewer than four pieces, if some were lost. For example, there are 801 nodes in a tree of depth four starting from xxxx___oooo, suggesting an average branching factor of about five (801 ** (1/4) is about 5.3), not eight.