Home »

100,000 cubes optimally solved

Submitted by kociemba on Fri, 01/23/2009 - 15:24.
Using my brandnew Core i7 920 CPU machine (Vista 64 bit with 6 GB of RAM) I solved 100,000 random cubes optimally with a rate of about 4-5 cubes / minute. So the computation took less than two weeks. I got the following results: 
14f*:     18
15f*:    197
16f*:   2710
17f*:  26673
18f*:  67099
19f*:   3303
No 20f* cube was encountered. According to Toms results this indeed would be very unlikely and for 100000 cubes the probability should be less than 10-6. The 95% confidence interval for the probability of 18f* is about 0.671 ±0.003, for 17f* 0.267 ±0.003 for 19f* 0.033 ±0.001 and for 16f* 0.027 ±0.001. With my new machine it should be possible to implement a fast coset solver and I would like to compute more accurate estimations for the probability of 20f* for random cubes.
» 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.

Adding Branching Factors to the Mix

Submitted by Jerry Bryan on Thu, 01/29/2009 - 22:03.

I think we can use branching factors to tighten a couple of the estimates.  Branching factors have the characteristic that they are fairly constant until you are fairly far from Start, and by "fairly constant" we mean that they are very slightly monotonically decreasing until fairly far from Start.

The branching factor from 10f to 11f is known to be about 13.19.  If we simply project this branching factor out to 14f, it predicts a probability of about .000162 for 14f rather the .00018 from the sample.  This is truly a small difference, but I think we can say with great confidence (a much higher confidence that a confidence interval would suggest) that .000162 is an upper bound on the probability for 14f, and probably a pretty tight bound.  Indeed, if the branching factor dropped to say 13.15 or 13.10 or something like that by the time we reached 14f, the .000162 estimate would have to be reduced just a little bit more.

Projecting from 14f to 15f to 16f using branching factors is a little more iffy, but I think that the probability for 15f is about .00210 rather than the .00197 from the sample, otherwise the branching factor from 14f to 15f would be too small and the branching factor from 15f to 16f would be too large.

And that's about all we can do with branching factors.  The samples that we have tell us that we really can't project from 16f to 17f with branching factors because the branching factor is so much reduced below 13.1, so from 17f to 20f the only estimates we have are from sampling.  And for 16f we are really depending more on the sampling than we are on projecting by branching factors.

» login or register to post comments

Matches

Submitted by rokicki on Sun, 01/25/2009 - 13:52.
That matches my set of optimal solves almost perfectly: 
       me         kociemba
14     1 0.000    18 0.000
15    37 0.002   197 0.002
16   579 0.025  2710 0.027
17  6063 0.266 26673 0.267
18 15266 0.671 67099 0.671
19   811 0.036  3303 0.033
The only "problem" is the 19's, where I see 0.036 (unknown confidence) and you see 0.033. And this may be because my cubes are not independent samples, but instead are waypoints on a random walk through the space. The combination of the fast machine, larger pruning table and improved program make for a huge leap in the speed of optimal solves; congratulations! From Korf's 10 optimal solves, to 100K today, is amazing progress.
» login or register to post comments