• 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!

writing cube solvers

emg

Member
Joined
Aug 12, 2010
Messages
24
Location
United States
WCA
2004GATE02
Hello,

I've been out of the loop for a few years, but the recent announcement on cube20.org has piqued my interest, and the first thing I want to do is write a new cube solver (I lost the code for my last one :(), Thistlethwaite(-esque) at first, and hopefully a two stage/Kociemba solver later. As such I have a few questions pertaining to my quest, and a few others that I'm just plain curious about.

After a fair amount of reading I think I understand the idea behind representing the cube as coordinates (terminology from Kociemba's site, not sure if that's standard or not), using transition tables to move from one set of coordinates to the next based on the current move, and using the coordinates as indices into pruning tables. When it comes to generating these transition tables though, it's necessary to represent the cube in another way, preform a move, calculate the coordinates in the new position, and fill in the corresponding entries, right? My main questions (for now) are
1) Is it possible to perform arithmetic operations on the coordinates to represent moves, thus making some other way of representing the cube unnecessary, and making transition tables unnecessary (if you're willing to do the math instead of the lookup)? I've looked around and thought about it until my head hurts, but haven't found a definitive answer yet
2) What is the / are some generally preferred ways to represent a cube in a program? An array for permutation and one for orentation? One of each for edges and corners? Some more convoluted data structure?

And out of curiosity, has anyone found and stored full index tables for the two stages of Kociemba's algorithm (analogous to Thistlethwaite's original algorithm in which he had full tables)? Is there any point in doing that or would the penalties from dealing with such a large table make it slower than just doing IDA*?

Thanks,
-emg
 

emg

Member
Joined
Aug 12, 2010
Messages
24
Location
United States
WCA
2004GATE02
two phase solver

View attachment solve.c.txt

Well I went ahead and slapped together a two phase solver. It's not remarkably fast or pretty, but it's fairly short (387 SLOC according to sloccount, 494 physical lines) and seems to work. I've attached it to the post for anyone who's interested. Rename to solve.c and compile with 'gcc -O3 solve.c' (first program I've written where I find the -O3 actually makes a difference). It reads cube states of the standard form
"UF UR UB UL DF DR DB DL FR FL BR BL UFR URB UBL ULF DRF DFL DLB DBR"
on standard in, separated by newlines. It doesn't do any error checking on input.

It doesn't take advantage of any symmetry and currently each phase uses three separate pruning tables, one for each coordinate that is used in that phase. Phase 1 uses edge orientation, corner orientation, and UD slice phase 1 coordinates. Phase 2 uses edge permutation, corner permutation, and UD slice phase 2 coordinates. With this approach phase 2 searches over 14 moves can be fairly slow. I think the next step would be to combine coordinates into larger pruning tables that give a better heuristic.

I'd like to add that Jaap's puzzle page and Kociemba's cube explorer page were amazing resources for this and I couldn't have written it without them, thanks guys :)

Enjoy, and please give feedback,
-emg
 

qqwref

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
And out of curiosity, has anyone found and stored full index tables for the two stages of Kociemba's algorithm (analogous to Thistlethwaite's original algorithm in which he had full tables)? Is there any point in doing that[...]
Actually, there isn't. The reason Kociemba always produces good solutions is because it searches non-optimal first stage solutions as well. Using only optimal ones would probably give you a worst case of some 25-27 moves. Since optimal solutions to the second stage are stored, checking non-optimal solutions for the first stage is quite fast.
 

rokicki

Member
Joined
Oct 31, 2008
Messages
301
And out of curiosity, has anyone found and stored full index tables for the two stages of Kociemba's algorithm (analogous to Thistlethwaite's original algorithm in which he had full tables)? Is there any point in doing that[...]
Actually, there isn't. The reason Kociemba always produces good solutions is because it searches non-optimal first stage solutions as well. Using only optimal ones would probably give you a worst case of some 25-27 moves. Since optimal solutions to the second stage are stored, checking non-optimal solutions for the first stage is quite fast.

Well, using full tables (which I do use, and which were important for the recent 20 proof) lets you generate phase 1 solutions much faster and also check them much faster. This is why my two-phase solver, with six axes, can find distance-20 solutions to about 3900 positions a second.

Now, if you don't need sub-millisecond solution time, partial tables work fine, take less disk space, take less time to generate, and take less memory. But if you have twenty billion positions to check (as we did), every bit of speed is a good thing.
 

qqwref

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
And out of curiosity, has anyone found and stored full index tables for the two stages of Kociemba's algorithm (analogous to Thistlethwaite's original algorithm in which he had full tables)? Is there any point in doing that[...]
Actually, there isn't. The reason Kociemba always produces good solutions is because it searches non-optimal first stage solutions as well. Using only optimal ones would probably give you a worst case of some 25-27 moves. Since optimal solutions to the second stage are stored, checking non-optimal solutions for the first stage is quite fast.

Well, using full tables (which I do use, and which were important for the recent 20 proof) lets you generate phase 1 solutions much faster and also check them much faster. This is why my two-phase solver, with six axes, can find distance-20 solutions to about 3900 positions a second.
Maybe I misunderstand, but I don't see how a full phase 1 table could help you generate suboptimal solutions...?
 
Joined
Nov 29, 2008
Messages
214
Maybe I misunderstand, but I don't see how a full phase 1 table could help you generate suboptimal solutions...?

For a fast two-phase solver, a full phase 1 table is absolutely important. For phase 2 this is not very important, because in most cases, the phase 2 length is short, maybe 6 moves.

Maybe you misunderstood what we mean with a "full phase 1" table. It does not mean we store maneuvers for each state. It just means we store distances to the goal state (eventually additional information about the moves if there is enough memory) which is much more effective and of course allows suboptimal maneuver generation.
 
Last edited:

cuBerBruce

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
Visit Channel
And out of curiosity, has anyone found and stored full index tables for the two stages of Kociemba's algorithm (analogous to Thistlethwaite's original algorithm in which he had full tables)? Is there any point in doing that or would the penalties from dealing with such a large table make it slower than just doing IDA*?
I have also used "full" tables for phase 1 and 2.

When I proved 38 quarter-turns suffice, I needed to solve several millions of positions using no more than 38 quarter-turns. I used a 2-phase solver that could directly look up the distance for phase 1 and phases 2 positions. I used symmetry-reduction to reduce the size of the tables. My phase 1 table stored 4-bit values and took 70,454,205 bytes. My phase 2 table didn't store actual distance, but rather (distance/2) mod 4. It required 334,817,280 bytes. (Note for QTM, the LSB of the distance can be determined from parity. I still needed to store two bits in the table because phase 2 requires using some "double quarter-turn" moves.) My solver would also try all 3 axes, if needed.
 
Top