Home »

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 BL(x)=12-|Starts-With(x)| and the right branching factor for x as BR(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 BL(x) is equal to BR(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.
» login or register to post comments | previous forum topic | next forum topic

Comment viewing options

Select your preferred way to display the comments and click 'Save settings' to activate your changes.

Another (dubious) approach to branching factors (FTM)

Submitted by Herbert Kociemba on Wed, 05/23/2007 - 12:48.
If we sum up the number of nontrivial maneuvers up to n moves we get in good approximation

s[n] = (3/116)*(30 + 11*Sqrt[6])*(6 + 3*Sqrt[6])^n

moves.
Now we generate all maneuvers with increasing length.
If we assume (what definitely is wrong) that each maneuver gives any of the n0 = 43252003274489856000 possible cube positions by random with the same probability, the probability that the next maneuver does not give a duplicate but a new position is proportional to the number of still not produces cubes. This is similar to the equation which describes radioactive decay and leads to some exponential function. It is not difficult to show, that this implies

h[n] = 1 - Exp[-s[n]/n0]

where h[n] gives the part of cubes we get within n moves, and h[n]-h[n-1] is fraction of the cube space we get with exactly n moves.

For small n h[n] is about s[n]/n0, which is obviously correct.
To see how the approximation is for bigger n we use Rockiki's result who optimally solved 22756 random cubes and got the following distribution for 14,..20 moves

{0.0000439, 0.00163, 0.0254, 0.266, 0.670, 0.036, 0}

h[n]-h[n-1] gives

{0.000180, 0.00239, 0.0314, 0.336, 0.628, 0.0021, 1.84*10^-36}

which is not too bad for a wrong assumption, especially for 16, 17 and 18 moves.
» login or register to post comments

A Different Recursion Formula

Submitted by Jerry Bryan on Tue, 05/22/2007 - 21:36.
Well, I did find that I had already posted about branching factors for individual positions. Sorry for the duplication. But it's probably just as well, because I had wanted to post an alternate recursion formula for the number of positions that are n moves from Start. The alternate formula depends on the branching factors of individual positions.

If T[n] is the number of positions that are n moves from Start, then an alternate recursion formula for the quarter turn metric is as follows.

1. If n=0, then A[n]=1, and B[n]=C[n]=D[n]=E[n]=0
2. If n>0, then
    A[n] = 0
    B[n] = 12*A[n-1] + 8*B[n-1] + 8*C[n-1] + 8*D[n-1] + 8*E[n-1]
    C[n] = 3*B[n-1]/2
    D[n] = 2*C[n-1]/3
    E[n] = 1*D[n-1]/4
3. T[n] = A[n] + B[n] + C[n] + D[n] + E[n]

The recursion formula above is equivalent to the one that Dan Hoey posted to Cube Lovers (and that Herbert must have used in developing his own very nice formula, and that Jaap made reference to in his message about Herbert's formula). I would describe Dan's recursion as being based on what he called syllable analysis, where a syllable is a sequence of moves on the same or opposite faces (up to four such successive moves in the quarter turn metric and up to two such successive moves in the face turn metric). I would describe the formula above as being based on branching factor analysis, but of course the branching factor analysis can be derived from the syllable analysis and vice versa.

Here's the way the formula above works. The Start position has a branching factor of 12 in the quarter turn metric. Suppose the first move is F. F has a branching factor of 11, which we write as 3+8. The next move can come either from the F-B faces or not. If it does come from the F-B faces, there are 3 choices and and if not there are 8 choices. If the second move is also from the F-B faces, the resultant position (e.g., FB) has a branching factor of 10 which we write as 2+8. The next move can come either from the F-B faces or not. If it does come from the F-B faces, there are 2 choices and if not there are 8 choices. If the third move is also from the F-B faces, the resultant position (e.g., FBF) has a branching factor of 9 which we write as 1+8. The next move can come either from the F-B faces or not. If it does come from the F-B faces, there is 1 choice and if not there are 8 choices. If the fourth move is also from the F-B faces, the resultant position (e.g., FBFB) has a branching factor of 8 which we write as 0+8. There are now 0 moves that can come from the F-B faces and we are forced to choose one of the 8 moves from the other faces. If at any time, we choose a move from one of the "other" faces, the branching factor goes back up to 11 which we write as 3+8 and the process repeats. The divisors in the formulas for C, D, and E are there to be sure that duplicate positions are counted only once.

The A[n] term takes care of the special case of the Start position. The B[n] term takes care of the "+8" part of the 3+8, 2+8, 1+8, and 0+8 cases. The C[n] term takes care of the 3 part of the 3+8 case. The D[n] term takes care of the 2 part of the 2+8 case. And the E[n] term takes care of the 1 part of the 1+8 case.

The formula of Dan Hoey et.al. is much simpler than the one above. The only reason I like the one above at all is that the value of T[n] depends explicitly only on the value of T[n-1], and therefore it relates directly to the branching factor of each position. In Dan's formula, the value of T[n] in the face turn metric depends explicitly on the values of T[n-1] and T[n-2], and in the quarter turn metric the value of T[n] depends explicitly on the values of T[n-1], T[n-2], T[n-3] and T[n-4].
» login or register to post comments