• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 40,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

Cubing@Home - CrowdCPU Fewest Moves

MattyAB

Member
Joined
May 5, 2015
Messages
26
Hey Everyone,

I am an intermediate programmer, and had the idea of making a fewest moves calculator, where you give it the type of cube and a scramble and it calculates the fewest moves. This led me on to have the though of a Folding@Home or BOINC - style program, where you connect to the main server and it gives you a scramble, then your computer takes some time solving it in the fewest moves, then reports back the solve, and how many moves it took.

Does anyone like this idea?
Can anyone help out, either programming-wise or solving algorithms for big cubes-wise?
Is this idea even useful? Has anyone already calculated an infinite number of fewest moves?



Let me know what you think!
 

00

Member
Joined
May 1, 2015
Messages
37
For 4x4 and above, it's currently impossible to optimally solve a single state.

For 2x2, we can optimally solve every state in a few seconds (probably less).

For 3x3, it would, in theory, be possible to optimally solve every position given enough time, but how would you store all the data?
 

Lucas Garron

Administrator
Joined
Jul 6, 2007
Messages
3,718
Location
California
WCA
2006GARR01
YouTube
Visit Channel
What is your goal?

As 00 points out, it's trivial to construct a full state graph for 2x2x2, and impossible to solve 4x4x4 optimally.

If we didn't know God's number, you could use this to search for hard positions on 3x3x3. But we already know God's number for HTM, and you're unlikely to discover any new ones for QTM.

Most other puzzles are also in the "trivial" or "infeasible" category.

There might be a good problem you could solve with distributed effort, but you should have a problem you're trying to solve before you put effort into a project like this.

An idea: allow people to submit scramble, and distribute the search to get them solutions more quickly than their computer/browser could.
 

unsolved

Member
Joined
Mar 2, 2014
Messages
566
Location
Doylestown, PA
For 4x4 and above, it's currently impossible to optimally solve a single state.

Not too long ago we had a Fewest Moves Challenge for programs. One of them solved the 4x4x4 scrambles in around 40 moves each in a matter of minutes. The winning program ran with a more sophisticated algorithm over the course of many days and averaged around 36 moves for each of the 5 scrambles. So, we're not as far off as you may imagine.

For 2x2, we can optimally solve every state in a few seconds (probably less).

The 2x2x2 cube has every state mapped to a distance. It is an instantaneous lookup into a table of 88,179,840 positions, which is 3 raised to the power of 7, times 8 factorial.

For 3x3, it would, in theory, be possible to optimally solve every position given enough time, but how would you store all the data?

The 3x3x3 can be solved, optimally, many times per second. The world record machine solve, with a robot physically turning the cube, is 1.06 seconds I believe.


Can anyone help out, either programming-wise or solving algorithms for big cubes-wise?

I've already written a 5x5x5 solving program. It can solve quadrillions of positions in about 17 seconds. The problem is, the branching factor is so large, it still needs lots of time to reach depth 14. Because the mods here are a bunch of jerks, they keep deleting pictures I post of it. So if you want to see it, you can log into my machine live and view it.

Message me on here, and I'll provide instructions to view it.
 
Last edited by a moderator:

Meep

Member
Joined
Apr 2, 2008
Messages
696
Location
Vancouver, Canada
WCA
2008ASIS01
YouTube
Visit Channel
The 2x2x2 cube has every state mapped to a distance. It is an instantaneous lookup into a table of 88,179,840 positions, which is 3 raised to the power of 7, times 8 factorial.

It's only 7!*3^6 = 3,674,160 positions.

The 3x3x3 can be solved, optimally, many times per second. The world record machine solve, with a robot physically turning the cube, is 1.06 seconds I believe.

As far as I know, it can't solve states optimally that quickly. The robots I've seen just take an early sub-optimal solution instead of running it until the two phases converge on an optimal one (which can take minutes depending on specs).

I've already written a 5x5x5 solving program. It can solve quadrillions of positions in about 17 seconds. The problem is, the branching factor is so large, it still needs lots of time to reach depth 14. Because the mods here are a bunch of jerks, they keep deleting pictures I post of it. So if you want to see it, you can log into my machine live and view it.

Why don't you just upload it to some free image hosting site (like imgur) and link to it here? I'd imagine they'd be deleting it because it's either too big, or you keep uploading the same (or similar) screenshots to this site, taking up unnecessary space (with lots of free hosts available). It seems really silly to have someone log into a machine just to view what a screenshot or screen-recording could show.
 

unsolved

Member
Joined
Mar 2, 2014
Messages
566
Location
Doylestown, PA
It's only 7!*3^6 = 3,674,160 positions.

(3^7 * 8!)/24 = (3^6 * 7!), you are correct. I forgot you have only 1/24th of the positions since there are no "centers" to orient with in the 2x2x2 world.

As far as I know, it can't solve states optimally that quickly.

I've run Herbert Kociemba's code on my machine and it produces 20- and sub-20 move solutions (for cubes not scrambled to distance 20 positions) in a blink of an eye. I could be mistaken however.


Why don't you just upload it to some free image hosting site (like imgur) and link to it here?

I have.

My offer was to let any coders who wanted to partake in this project to run their code on my machine, and/or view/run their own 5x5x5 scrambles on my 5x5x5 solver. For example, go to TeamViewer.com and download their app, enter 392895346 as the "Partner ID" for my machine, and pd425k as the password, and there it is.
 
Thread starter Similar threads Forum Replies Date
abunickabhi General Speedcubing Discussion 35
Similar threads
Cubing@Home Chess event
Top