From @wvnvm.wvnet.edu:BRYAN@WVNVM.WVNET.EDU Mon May 30 22:48:07 1994
Return-Path: <@wvnvm.wvnet.edu:BRYAN@WVNVM.WVNET.EDU>
Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA22299; Mon, 30 May 94 22:48:07 EDT
Message-Id: <9405310248.AA22299@life.ai.mit.edu>
Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2)
with BSMTP id 2575; Mon, 30 May 94 21:36:09 EDT
Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU
(LMail V1.1d/1.7f) with BSMTP id 6359; Mon, 30 May 1994 21:36:08 -0400
X-Acknowledge-To:
Date: Mon, 30 May 1994 21:36:07 EDT
From: "Jerry Bryan"
To: "Cube Lovers List"
Subject: Branching Factors and God's Algorithm Search Trees
At various times, there have been discussions about what the maximum
distance from Start might be in God's algorithm. One argument is made
with respect to worst/best case branching factors. For example,
a simple calculation is that the first move has at most twelve
possibilities and that each subsequent move has eleven possibilities,
when dealing with Q-turns only. For Q-turns plus H-turns, the same
argument would be eighteen possibilities for the first move and seventeen
possibilities for each subsequent move.
My experience is that search trees tend to develop relatively
constant branching factors after some sort of variable startup.
I expect Rubik's cube to be no different. I just wonder if anyone
has calculated some number of levels for the full Rubik's cube,
enough levels for the hypothesized steady state branching factor
to be achieved. I have not done so, but if anyone has, it might
shed considerable light on the question of the maximum distance
from Start.
Subsets of the cube such as corners only and edges only have been
calculated. It is suggestive to examine branching factors for the
cases which have already been calculated. The question of "average
branching factor" is subject to interpretation because it is not
necessarily clear when the distribution has achieved its steady
state. I am including a number of tables giving branching factors
for the cases which have been calculated already. I will preface
the tables with the following comments:
1. The distributions for edges-only cubes have a variable branching
factor during a startup phase, then have a relatively constant
branching factor for several levels. and finally the distribution
has sort of a tail.
2. The distributions for corners-only cubes have a variable branching
factor during a startup phase, and almost immediately the
distribution has a tail. The number of cases simply is not
large enough to support an extended constant branching factor
in the middle of the distribution. It's sort of like a very
short airplane flight where it is time to descend about the
time the ascent is completed.
3. I would expect the distributions for a full cube to have an
even longer period with a constant branching factor than
the distributions for edges-only cubes because the number
of cases is so much larger. There should be plenty of time
for a plateau between the startup phase and any tail of the
distribution.
4. There are an equal number of odd and even permutations. For
the cases where you restrict yourself to Q-turns, there are
therefore equal numbers of states an even distance from Start
and an odd distance from Start. Hence, the distribution tends
either to have two adjacent levels with approximately equal
numbers of states, or else tends to have one dominant level with
a level on each side of the dominant level with about half
the number of states in the dominant level.
5. For the cases where you allow both Q-turns and H-turns, there
tends to be one dominant level which contains most of the
of the states.
6. Those of you who followed all the traffic on this list in
December and January will recall that my work with God's
algorithm exploits symmetric conjugates in order to reduce
the size of the problem. It turns out that using conjugates
does not change the average branching factor once you get
past the startup portion of the distribution. This effect
can be a bit hard to see for corners-only cubes because the
steady state portion of the distribution is so short, but
the effect is very striking for edges-only cubes. I would
expect the effect to be very striking, as well, for the
case of the full cube.
------------------------------------------------------------------
2x2x2 Cube using Q-turns and H-turns
Distance Number of Branching Number of Branching Ratio of
from Cubes Factor M Factor Cubes to
Start Conjugates Conjugates
0 1 1 1.00
1 9 9.00 2 2.00 4.50
2 54 6.00 5 2.50 10.80
3 321 5.94 19 3.80 16.89
4 1847 5.75 68 3.58 27.16
5 9992 5.41 271 3.99 36.87
6 50136 5.02 1148 4.24 43.67
7 227536 4.54 4915 4.28 46.29
8 870072 3.82 18364 3.74 47.38
9 1887748 2.17 39707 2.16 47.54
10 623800 0.33 13225 0.33 47.17
11 2644 0.00 77 0.01 34.34
Total/Avg 3674160 ? 4.83 77802 ? 3.54 47.22
------------------------------------------------------------------
2x2x2 Cube using Q-turns
Distance Number of Branching Number of Branching Ratio of
from Cubes Factor M Factor Cubes to
Start Conjugates Conjugates
0 1 1 1.00
1 6 6.00 1 1.00 6.00
2 27 4.50 3 3.00 9.00
3 120 4.44 6 2.00 20.00
4 534 4.45 17 2.83 31.41
5 2256 4.22 59 3.47 38.24
6 8969 3.98 217 3.68 41.33
7 33058 3.69 738 3.40 44.79
8 114149 3.45 2465 3.34 46.31
9 360508 3.16 7646 3.10 47.15
10 930588 2.58 19641 2.57 47.38
11 1350852 1.45 28475 1.45 47.44
12 782536 0.58 16547 0.58 47.29
13 90280 0.12 1976 0.12 45.69
14 276 0.00 10 0.01 27.60
Total/Avg 3674160 ? 3.05 77802 ? 2.92 47.22
------------------------------------------------------------------
Corners of 3x3x3 Cube using Q-turns and H-turns
Distance Number of Branching Number of Branching Ratio of
from Cubes Factor M Factor Cubes to
Start Conjugates Conjugates
0 1 1 1.00
1 18 18.00 2 2.00 9.00
2 243 13.50 9 4.50 27.00
3 2874 11.83 71 7.89 40.48
4 28000 9.74 637 8.97 43.96
5 205416 7.34 4449 6.98 46.17
6 1168516 5.69 24629 5.54 47.44
7 5402628 4.62 113049 4.59 47.79
8 20776176 3.85 433611 3.84 47.91
9 45391616 2.18 947208 2.18 47.92
10 15139616 0.33 316823 0.33 47.79
11 64736 0.00 1481 0.00 43.71
Total/Avg 88179840 ? 4.74 1841970 ? 4.63 47.87
------------------------------------------------------------------
Corners of 3x3x3 Cube using Q-turns
Distance Number of Branching Number of Branching Ratio of
from Cubes Factor M Factor Cubes to
Start Conjugates Conjugates
0 1 1 1.00
1 12 12.00 1 1.00 12.00
2 114 9.50 5 5.00 22.80
3 924 8.11 24 4.80 38.50
4 6539 7.08 149 6.21 43.89
5 39528 6.04 850 5.70 46.50
6 199926 5.06 4257 5.01 46.96
7 806136 4.03 16937 3.98 47.60
8 2761740 3.43 57800 3.41 47.78
9 8656152 3.13 180639 3.13 47.92
10 22334112 2.58 466052 2.58 47.92
11 32420448 1.45 676790 1.45 47.90
12 18780864 0.58 392558 0.58 47.84
13 2166720 0.12 45744 0.12 47.37
14 6624 0.00 163 0.00 40.64
Total/Avg 88179840 ? 4.48 1841970 ? 4.29 47.87
------------------------------------------------------------------
Edges of 3x3x3 Cube Without Centers using Q-turns and H-Turns
Distance Number of Branching Number of Branching Ratio of
from Cubes Factor M Factor Cubes to
Start Conjugates Conjugates
0 1 1 1.00
1 18 18.00 2 2.00 9.00
2 243 13.50 9 4.50 27.00
3 3240 13.33 75 8.33 43.20
4 42359 13.07 919 12.25 46.09
5 538034 12.70 11344 12.34 47.43
6 6666501 12.39 139325 12.28 47.85
7 79820832 11.97 1664347 11.95 47.96
8 888915100 11.14 18524022 11.13 47.99
9 8056929021 9.06 167864679 9.06 48.00
10 27958086888 3.47 582489607 3.47 48.00
11 3883792136 0.14 80930364 0.14 47.99
12 8827 0.00 314 0.00 28.11
Total/Avg 40874803200 ? 12.26 851625008 ? 11.99 48.00
------------------------------------------------------------------
Edges of 3x3x3 Cube Without Centers Using Q-turns
Distance Number of Branching Number of Branching Ratio of
from Cubes Factor M Factor Cubes to
Start Conjugates Conjugates
0 1 1 1.00
1 12 12.00 1 1.00 12.00
2 114 9.50 5 5.00 22.80
3 1068 9.37 25 5.00 42.72
4 9759 9.14 215 8.60 45.39
5 88144 9.03 1860 8.65 47.39
6 786500 8.92 16481 8.86 47.72
7 6916192 8.79 144334 8.76 47.92
8 59623239 8.62 1242992 8.61 47.97
9 495496593 8.31 10324847 8.31 47.99
10 3695351994 7.46 76993295 7.46 48.00
11 17853871137 4.83 371975385 4.83 48.00
12 18367613703 1.03 382690120 1.03 48.00
13 395043663 0.02 8235392 0.02 47.97
14 1080 0.00 54 0.00 20.00
15 1 0.00 1 0.02 1.00
Total/Avg 40874803200 ? 8.80 851625008 ? 8.63 48.00
------------------------------------------------------------------
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
Robert G. Bryan (Jerry Bryan) (304) 293-5192
Associate Director, WVNET (304) 293-5540 fax
837 Chestnut Ridge Road BRYAN@WVNVM
Morgantown, WV 26505 BRYAN@WVNVM.WVNET.EDU
If you don't have time to do it right today, what makes you think you are
going to have time to do it over again tomorrow?