# writing cube solvers



## emg (Aug 13, 2010)

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


----------



## Kenneth (Aug 13, 2010)

Twistlewait, I don't know, it must be much easier to just brute force attack the thing.

For tables, orientation does not exist really, all posititons are permutations. "Orientation" of the UF edge is, you permute the U sticker to the F side.


----------



## emg (Aug 18, 2010)

*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


----------



## emg (Aug 18, 2010)

View attachment solve.c.txt

Quick update, I was initiating the phase 2 corner permutation pruning table wrong, using all moves not just moves from second phase group <U, D, F2, B2, R2, L2>

with that fix, it runs much faster

see attached

-emg


----------



## qqwref (Aug 21, 2010)

emg said:


> 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 (Aug 22, 2010)

qqwref said:


> emg said:
> 
> 
> > 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[...]
> ...



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 (Aug 22, 2010)

rokicki said:


> qqwref said:
> 
> 
> > emg said:
> ...


Maybe I misunderstand, but I don't see how a full phase 1 table could help you generate suboptimal solutions...?


----------



## Herbert Kociemba (Aug 22, 2010)

qqwref said:


> 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.


----------



## qqwref (Aug 22, 2010)

Ah, I see. Just storing the minimal distances from each state is a good idea.


----------



## cuBerBruce (Aug 24, 2010)

emg said:


> 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.


----------

