Home »

EndsWith Values, Corners Group, Quarter Turn Metric

Submitted by Jerry Bryan on Sun, 04/11/2010 - 11:19.

My calculations of God's algorithm have generally included an analysis of the distribution of EndsWith values.  My best God's algorithm results for the quarter turn metric are out to 13q. Tom Rokicki has since calculated out to 15q.  Out to 13q, it is the case that for the vast majority of positions x we have |EndsWith(x)| = 1.  Tom may be able to speak to the 14q and 15q cases, but I cannot.

Given the predominance of |EndsWith(x)| = 1 out to 13q, I have assumed that for the vast majority all of cube space it's probably the case that |EndsWith(x)| = 1.  I no longer believe that assumption is correct.  Which is to say, I now have an EndsWith distribution for the entirety of the corners group in the quarter turn metric.  Beyond a certain distance from Start in the corners group, there are no instances of |EndsWith(x)| = 1 whatsoever, and overall the |EndsWith(x)| = 1 cases are very much in the minority.  It now seems to me that the same is probably true for the complete cube group including corners and edges.  I suspect the reason we have not seen this effect for the complete cube group is simply that we have not yet been able to calculate out far enough from Start.

I use EndsWith as an attribute of a position, not of a maneuver.  We might look at the maneuver FB' and say that EndsWith(FB')={B'} and we might look at the maneuver B'F and say that EndsWith(B'F)={F}.  But the maneuvers FB' and B'F both effect the same position, so we have EndsWith(FB')={F,B').

EndsWith is important for a couple of reasons.  For one thing, it is closely related to branching factors.  For example, if |EndsWith(x)| = 3, then we know that from position x in the quarter turn metric there are 3 moves that go closer to Start and 9 moves that go further from Start.  Essentially, the branching factor for position x is 9.  Some of those 9 positions might be duplicated with positions effected by a different maneuver, but the maximum number of new positions further from Start that might be reached from position x is 9.

EndsWith is also closely related to syllables and non-trivial identities.  In particular, no position for which |EndsWith(x)| = 1 can be the midpoint of a non-trivial identity.  For example, we have |EndsWith(FB'U)| = {U} and |EndsWith(B'FU)| = 1.  If we take the walk FB'U through cube space, there are two minimal ways back to Start, namely U'BF' and U'F'B.  But either way back to Start yields a trivial identity, namely (FB'U)(U'BF') or (FB'U)(U'F'B), because the UU' in the middle immediately cancels out.

Given my assumed predominance of |EndsWith(x)| = 1 positions in cube space, I was also assuming that most positions in cube space could not serve as the midpoint of a non-trivial identity.  But I now believe that far enough from Start, the vast majority of positions can serve as the mid-point of a non-trivial identity.  And because most positions are far from Start, I now believe that the vast majority of positions overall can serve as the mid-point of a non-trivial identity.

Here follow the results for the corners group that have caused me to change my mind for the complete cube group about the predominance of positions for which |EndsWith(x)| = 1.

  

                                                              |EndsWith(x)|

                                                 Corners of 3x3x3, Quarter Turn Metric
 
        0      1         2      3        4     5        6     7        8     9       10    11       12    Total

  |x|

   0    1       0         0      0        0     0        0     0        0     0        0     0        0        1
   1    0      12         0      0        0     0        0     0        0     0        0     0        0       12
   2    0      96        18      0        0     0        0     0        0     0        0     0        0      114
   3    0     672       192     60        0     0        0     0        0     0        0     0        0      924
   4    0    4032      1920    480       51     0       56     0        0     0        0     0        0     6539
   5    0   19104     14904   3792      984   216      384   144        0     0        0     0        0    39528
   6    0   71184     90984  16656    13212  1872     3936   528     1344     0       96     0      114   199926
   7    0  123360    478008  42768   117576  7824    16656  1680     9096  1536     6552   480      600   806136
   8    0   23328   1911312   9024   643536  2736   121872   384    23232    96     7584   720    17916  2761740
   9    0       0   5573376      0  2327616     0   558336     0   167616     0    19008     0    10200  8656152
  10    0       0  11167488      0  7057440     0  2818176     0  1020384     0   235584     0    35040 22334112
  11    0       0   4661568      0  8314272     0  8893248     0  6746688     0  2986560     0   818112 32420448
  12    0       0     19008      0   123840     0   591744     0  2202912     0  6189120     0  9654240 18780864
  13    0       0         0      0        0     0        0     0      288     0    39168     0  2127264  2166720
  14    0       0         0      0        0     0        0     0        0     0        0     0     6624     6624

Total   1  241788  23918778  72780 18598527 12648 13004408  2736 10171560  1632  9483672  1200 12670110 88179840
    <0.01%  0.27%    27.12%  0.08%   21.09% 0.01%   14.75% <0.01%  11.54% <0.01%  10.75% <0.01%  14.37%
» 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.

Evens are prevalent for corners

Submitted by rokicki on Mon, 04/12/2010 - 23:00.
In case it's not clear to everyone why even EndsWith predominate for the corners, it is because for almost every corners position, if U+ gets you closer to solved, so does D-. Essentially, corners-only is almost (but not quite) identical to the 2x2x2; the difference is the presence of the corners. Once the distance gets larger than four or five, there are enough moves that there's great freedom in choosing between a quarter move on one face, or a quarter move on the other face in the opposite direction.

Essentially, the distance distribution for corners-only on 3x3x3 is almost exactly the distance distribution for the 2x2x2, but multiplied by the 24 possible orientations of the centers.
» login or register to post comments

Errata

Submitted by Jerry Bryan on Sun, 04/11/2010 - 13:38.
The statement:

For example, we have |EndsWith(FB'U)| = {U} and |EndsWith(B'FU)| = 1.

Should be replaced by the following:

For example, we have EndsWith(FB'U) = {U} and |EndsWith(B'FU)| = 1.
» login or register to post comments

In the quarter turn metric

Submitted by rokicki on Mon, 04/12/2010 - 22:55.
Two comments about EndsWith. For simplicity, I will use the definition

EndsWith(p) = |s . s in QTM generators and distance(p*s) < distance(p)|

The overall average of EndsWith for all positions in the QTM must be exactly 6. Consider the Cayley graph; each edge connects two nodes at distinct distances. Each edge contributes 1 to the EndsWith of the more distant node, and contributes 0 to the EndsWith of the closer node. Since there are exactly |G|*12/2 or 6*|G| edges, and |G| nodes, the overall average EndsWith is exactly 6 in the QTM.

Furthermore, for the quarter turn metric, we can compute the average EndsWith at each level knowing only the node count at each level, since the node count determines precisely the edge count between levels. The number of edges to the next level is always twelve times the number of nodes at the current level less the number of edges that came from the previous level. 

lev          nodes    edges-further average-endswith
0                1               12 0
1               12              132 1
2              114             1236 1.15789473684211
3             1068            11580 1.15730337078652
4            10011           108552 1.1567275996404
5            93840          1017528 1.15677749360614
6           878880          9529032 1.15775532495904
7          8221632         89130552 1.15901952313117
8         76843595        832992588 1.15989565558457
9        717789576       7780482324 1.16049691420985
10      6701836858      72641559972 1.16094773550216
11     62549615248     677953823004 1.16134303438937
12    583570100997    6324887388960 1.16173502008713
13   5442351625028   58983332111376 1.16216073946296
14  50729620202582  549772110319608 1.16270005325949
15 472495678811004 5120176035412440 1.16354949891407
As you can see, the EndsWith value stays very constant from levels 2 through 15. Interestingly it drops slightly from level 2 through level 4 before starting to inch up again.
» login or register to post comments

Off-topic

Submitted by secondmouse on Sat, 04/17/2010 - 14:28.
Does anyone know how to insert nice tables like the above?
Sorry can't find how to do this.
» login or register to post comments

Most people here use <pre&

Submitted by Bruce Norskog on Sat, 04/17/2010 - 22:05.

Most people here use <pre> text... </pre> for such preformatted text.

In general, use the View Source feature of your browser to see how people accomplish various formatting.

Related to this, always remember to use HTML escape sequences for less than and greater than signs.
less than = ampersand ell tee semicolon
greater than = ampersand gee tee semicolon

Also (all users), please use the <a> tag when posting web site addresses (URLs).

» login or register to post comments