# More on Branching Factors

Submitted by Jerry Bryan on Mon, 05/21/2007 - 23:32.

I think it's useful to define branching factors for some other situations than are normally considered. For the most part, I'll speak to the quarter turn metric, but generalizations to the face turn metric are not hard to come by.

I was pretty sure that I posted an article to this site about Starts-With and Ends-With, but if so I can't find it. In any case, for a position x we define Starts-With(x) to be the set of moves with which a minimal process for x can start, and Ends-With(x) to be the set of moves with which a minimal process for x can end. If Ends-With(x)=Q (the set of quarter turns), then x is a local maximum. A similar formulation of the same idea is that if |Ends-With(x)|=12, then x is a local maximum.

For a position x, we define the branching factor for x as B(x)=12-|Ends-With(x)|. More generally, we define the left branching factor for x as B

If T[n] is the number of positions that are n moves away from Start, then the actual branching factor T[n+1]/T[n] is bounded by the average of the individual branching factors of all the positions that are exactly n moves from Start. If there are no duplicate positions when you go from T[n] to T[n+1], then the average of the individual branching factors of all the positions that are exactly n moves from Start will be exactly equal to T[n+1]/T[n]. The extent by which T[n+1]/T[n] deviates from the average of the individual branching factors of all the positions that are exactly n moves from Start is indicative of how many duplicate positions there are in moving from T[n] to T[n+1].

In general, it is not the case that B

I was pretty sure that I posted an article to this site about Starts-With and Ends-With, but if so I can't find it. In any case, for a position x we define Starts-With(x) to be the set of moves with which a minimal process for x can start, and Ends-With(x) to be the set of moves with which a minimal process for x can end. If Ends-With(x)=Q (the set of quarter turns), then x is a local maximum. A similar formulation of the same idea is that if |Ends-With(x)|=12, then x is a local maximum.

For a position x, we define the branching factor for x as B(x)=12-|Ends-With(x)|. More generally, we define the left branching factor for x as B

_{L}(x)=12-|Starts-With(x)| and the right branching factor for x as B_{R}(x)=12-|Ends-With(x)|.If T[n] is the number of positions that are n moves away from Start, then the actual branching factor T[n+1]/T[n] is bounded by the average of the individual branching factors of all the positions that are exactly n moves from Start. If there are no duplicate positions when you go from T[n] to T[n+1], then the average of the individual branching factors of all the positions that are exactly n moves from Start will be exactly equal to T[n+1]/T[n]. The extent by which T[n+1]/T[n] deviates from the average of the individual branching factors of all the positions that are exactly n moves from Start is indicative of how many duplicate positions there are in moving from T[n] to T[n+1].

In general, it is not the case that B

_{L}(x) is equal to B_{R}(x) (informally, the left branching factor for x often is not equal to the right branching factor for x). However, the right branching factor of a position is equal to the left branching factor of its inverse and vice versa. As an example, the inverse of a local maximum need not be a local maximum. But because of antisymmetry, the average of all the left branching factors for all the positions exactly n moves from Start is exactly equal to the average of all the right branching factors for all the positions exactly n moves from Start.