From: Jerry Bryan Subject: Re: God's Number To: Keith H Randall Cc: reid@math.brown.edu, cube-lovers@ai.mit.edu Message-Id: On Wed, 1 Oct 1997, Keith H Randall wrote: > Don Dailey, Aske Plaat, and myself have a program that will do a > complete 22-ply search in about 24 hours on an 8 processor Sun > machine. The program measures distance in the QT (quarter-turn) > metric. > > I've run some experiments on random cubes, summarized as follows: > > 112 random odd cubes: > 20 depth 19 > 92 depth 21 > > 57 random even cubes: > 41 depth 20 > 16 depth 22 Wow. I am impressed with how much data you have. For the case of random cubes and guaranteed optimal solutions, I believe this is the most data which has been posted to Cube-Lovers. It would be nice to examine enough cases to raise the probability that a few positions of length 17q would show up for odd cubes and of length 18q for even cubes. At this distance from Start, the branching factor for one level is about 9.3, so the branching factor for two levels (e.g., between level 17 and level 19) would be about 85 or so. So you are just at the edge of the sample size where you would expect the shorter lengths to show up. Notwithstanding that, I decided to play with the numbers to see if I could make any reasonable projection about the overall distribution of lengths in the quarter-turn metric. Here is what I have come up with. Consider the 19q case. Your results suggest that about 17.8% of odd positions, and hence about 8.6% or 8.7% of all positions are exactly 19q from Start. (The sample size does not support an estimate of that precision, of course, but let's continue anyway). It's easy to calculate that no more than about 8.4% of positions can be 19q from Start. From this, I would conclude two things. First, your results seem right on, well within the bounds of sampling error. Second, your results suggest that it is very unlikely that the branching factor drops below about 9.3 until you pass 19q from Start. Using the best available known results, plus using your results as an estimate, plus some other guessing, I would propose that the actual search tree for the q-turn case looks something like the following. Distance Number Branching Cumulative from of Factor Number of Start Positions Positions 0 1 1 1 12 12.000 13 2 114 9.500 127 3 1068 9.368 1195 4 10011 9.374 11206 5 93840 9.374 105046 6 878880 9.366 983926 7 8221632 9.355 9205558 8 76843595 9.347 86049153 9 717789576 9.341 803838729 10 6701836858 9.337 7505675587 11 62549615248 9.333 70055290835 12 5.838E+11 9.333 6.538E+11 13 5.449E+12 9.333 6.102E+12 14 5.085E+13 9.333 5.696E+13 15 4.746E+14 9.333 5.316E+14 16 4.430E+15 9.333 4.961E+15 17 4.134E+16 9.333 4.631E+16 18 3.859E+17 9.333 4.322E+17 19 3.601E+18 9.333 4.034E+18 20 1.546E+19 4.294 1.950E+19 21 1.657E+19 1.071 3.606E+19 22 6.035E+18 0.364 4.210E+19 23 12 0.000 4.210E+19 24 1 0.083 4.210E+19 Notice that my table does not quite reach |G|, so there are probably a few more positions than this at 20q, 21q, and 22q from Start (there can't be more any closer to Start than that). Also, the branching factor probably does not remain constant at 9.333 all the way out to 19q from Start; it probably declines slightly, maybe to 9.300 or so. Finally, the distribution is probably bimodal, with modes at 20q and 21q (it almost has to be bimodal because of odd/even parity considerations). (By the way, I am making no claim whatsover that the diameter of the cube group is 24q. This is only an educated guess based on the evidence at hand. In fact I tend to doubt it. I think the branching factor in the chart just drops off too sharply at levels 21q, 22q, and 23q for the chart to be real.) = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) jbryan@pstcc.cc.tn.us Pellissippi State (423) 539-7198 10915 Hardin Valley Road (423) 694-6435 (fax) P.O. Box 22990 Knoxville, TN 37933-0990 ------------------------------ Date: Sun, 5 Oct 1997 18:54:32 -0400