OptClock - optimal Rubik's Clock solver

Discussion in 'Software Area' started by qqwref, May 25, 2014.

1. 10461394944000Banned

687
3
Mar 18, 2014
in d middle of angleland
WCA:
2009WHIT01
ben1996123
## OptClock Readme ##

== What is this? ==

OptClock is a program for optimally solving Rubik's Clock positions. It is Copyright 2014 by Michael Gottlieb and Ben Whitmore. Michael Gottlieb developed the solving algorithm and wrote the non-GUI version of the program, while Ben Whitmore created the GUI in Qt.

The exe files are compiled for Windows, but if you are not using a Windows system you may want to recompile.

== Notation Used ==

There are two types of notation used for the program: one for scrambles and one for moves.

Scrambles are just lists of 14 integers. Each number represents the "hour" displayed by one of the clock pieces, and any list of 14 integers is a valid scramble. Usually people use 1-12 for each number but this is not required. The order of the numbers is as follows:
1 2 3 . 10 .
4 5 6 11 12 13
7 8 9 . 14 .
(front) (back)
The dotted numbers do not need to be entered since their values are determined by the front corners. Also, when turning from front to back, make sure to turn so that the top of the puzzle remains on top (so 10 is opposite 2).

Moves look something like UUDU u3'. The uppercase part (UUDU) is the state of the 4 pins, in the order top-left, top-right, bottom-left, bottom-right. U means up (pin towards you) and D means down (pin away from you). If the lowercase letter is a u, it means to turn a corner that is next to a U pin; if the lowercase letter is a d, it means to turn a corner next to a D pin. The number tells you the amount to turn, and is just like the notation for cubes: the letter by itself means to turn clockwise by 1 increment; the letter with a number means to turn clockwise by that number of increments; and a ' sign always means to do the same turn counterclockwise instead of clockwise. So in this case (u3') it means to turn a corner next to a U pin counterclockwise by 3 increments.

== Using the Program ==

There are two non-GUI versions: a normal version and a statistics version. The normal version is for solving individual scrambles: just enter in a scramble with the above notation, and it will be optimally solved for you. Enter "q" to quit the program. The statistics version is for solving many scrambles at once and reporting on how many moves they took. Enter in the number of scrambles and an upper bound, and the program will generate that many scrambles and solve them all, and then print some statistics. Every 100 scrambles a number will be printed to the screen so you can be sure it's still running properly.

A little note about the upper bound. Basically, the program will stop searching for solves when it finds a solve using no more than the upper bound number of moves. The higher the upper bound is, the faster the solver will run. If you set it to 0, it will only look for optimal solves.

With the GUI version, the features are pretty much the same, but it is a little different to use. To solve a given scramble, set up the scramble by clicking on the clocks, and then press the "Solve" button. The "Generate random scramble" button will generate a random position, and the "Reset" button will move the clocks back to solved. "Batch solver" works like the statistics version as explained above, although it will also let you run the solver with multiple threads (to speed up execution) and a custom priority level.

Note that all forms of the program will create and use a 3-megabyte tables file (phase2.table). Apart from the program itself, this is all the hard drive space it needs. If you ever lose this file it will just get regenerated the next time the program is run.

== The Solving Algorithm ==

Here I will discuss how the program actually finds optimal Clock solves, since as far as I know this is a pretty new feature. The program itself has a lot of optimizations and memoization, so even if you understand the theory it may be tricky to see out exactly what the code is doing.

The solving algorithm uses two phases. Consider the 9 clocks on each side of the puzzle; we can divide these into 1 center, 4 edges, and 4 corners. The first phase of the solution matches each face's center and edges into a "cross" of 5 clocks pointing the same way. The second phase then solves the corners and two crosses optimally. At a very high level, we can quickly figure out how long a phase-2 optimal solution is, so we just try every possible phase 1 solution and determine the best total movecount we can get, where total movecount is the sum of the phase 1 movecount and phase 2 movecount.

It saves time to separate the puzzle into two phases like this because the 30 possible moves can be split into moves useful for phase 1, and moves useful for phase 2. The 16 phase 1 moves are moves that affect the cross - that is, they move a face's center without moving all four of its edges. The 14 phase 2 moves, on the other hand, preserve both crosses. By design, phase 1 moves are not useful in phase 2 (they break the cross), and phase 2 moves are not useful in phase 1 (they do not affect the cross). So, since we can do the moves of a solution in any order, it is safe to assert that phase 1 moves are only used during phase 1, and phase 2 moves are only used during phase 2.

Phase 2 is simpler, so I'll discuss it first. Because we only have two crosses and four corners to deal with, there are only 12^6 positions - about 3 million. This is small enough that we can use a standard God's Algorithm loop to compute the optimal distance for each of these positions, and then store that in a table. Having the phase 2 distance in a table lookup is what makes the solver fast enough to be practical. For the two-phase algorithm we only need the number of moves, until we want to print a solution, and then we can just work backwards from the phase 2 position to find an optimal move sequence for this phase.

In phase 1, we have to try all solutions to see which ones end up with fast phase 2 solutions, so we can't just set up an optimal table. But there are 16 possible moves, so we have to be clever about it. I divided those 16 moves into two types: edge moves such as UUDD u, which only affect one edge (relative to the center), and corner moves such as UDDD u, which affect two edges (relative to the center). If we know how much we want to do each corner move, then since each of the 8 edge moves affects only one of the 8 edges, and they all must be the same as their center after phase 1, the amount of each edge move that we do is forced. So the only "degrees of freedom" we have for our phase 1 solution is the amount of each corner move that we use. There are 8 of those, with 12 possible angles for each, so there are only 12^8 phase 1 solutions! We can simply loop through those, and check the total movecount of each possibility. The best total movecount means the optimal solution.

Now, 12^8 is about 430 million, so of course we don't want to do too much computation for each one. We can quickly compute the phase 1 movecount by splitting it into a front and a back, each affected by 4 of the 8 corner moves. We can compute the number of moves on each side for every possible set of angles for those 4 moves (that is, two tables of size 12^4) and just add the relevant entries together to get the phase 1 movecount. Then, for phase 2, with a little math we can predict the positions of the crosses and corners for any given set of corner moves, and then plug that into our phase 2 table to get the phase 2 movecount. So the movecount for the whole puzzle is computed by indexing into a bunch of tables, and all we have to do is figure out the indexes.

To save some more time, it turns out we don't even need to look at phase 2 for most of the 12^8 possibilities. Suppose we have already seen an 11-move solution. Then, if we are trying a solution that already takes at least 11 moves in phase 1, we know there's no way it can be better than what we already have, and we can decide not to even check the phase 2 movecount. Phase 1 solutions can take up to 16 moves, so we can usually throw out the vast majority of them, saving a surprising amount of time.

In the end, most of this was only possible because the moves commute - you can do a set of moves in any order. A lot of the tricks I used wouldn't be possible or useful on a cube. Still, it's cool to add this to the list of puzzles that can be solved optimally! After this release, I'm going to see if I can find God's Number. Right now, it's looking like it's 11.

2. qqwrefMember

7,830
37
Dec 18, 2007
a <script> tag near you
WCA:
2006GOTT01
qqwref2
3. rokickiMember

255
4
Oct 31, 2008
Thanks! I'm happy to say that your source compiles and runs on Linux; I needed to
comment out windows.h and add cstdlib and then all is well.

I've got 64 distance-12 positions at this point (the two we know of, times 32 different
reorientations/multiplications). I wonder how many there are . . .

4. qqwrefMember

7,830
37
Dec 18, 2007
a <script> tag near you
WCA:
2006GOTT01
qqwref2
Don't forget you can multiply a scramble by 5 or 7 without changing its orientation So you have group multiplication (x4), mirroring (x2), flipping (x2), and rotation (x4) for up to 64 positions from a non-symmetrical scramble.

5. rokickiMember

255
4
Oct 31, 2008
Right, but it turns out for the two positions we know, there is enough symmetry where this only gives us
32 distinct positions for each of our 2 root positions. If you can verify this for me I'd appreciate it.

6. qqwrefMember

7,830
37
Dec 18, 2007
a <script> tag near you
WCA:
2006GOTT01
qqwref2
You're right - I didn't even see the symmetry in Jakube's position at first. So yes, they should each have 32 equivalent positions.

I'm thinking we could do the same thing as Jakube did to prove there are no positions of at least length 13, to find all positions of at least length 12. I'd try it myself but I don't have you guys's source code, or enough RAM to do a 12^9 table anyway. It would work like this:
- Take all 7- or 8-move states of the back side and combine them with a solved cross on the front side
- Undo UUUU u=x5 in all 12 different ways, discard any positions with optimal length <8
- Undo UUdd u=x4 in all 12 different ways, discard any positions with optimal length <9
- Undo Uddd u=x3 in all 12 different ways, discard any positions with optimal length <10
- Undo dUdd u=x2 in all 12 different ways, discard any positions with optimal length <11
- Undo ddUd u=x1 in all 12 different ways, discard any positions with optimal length <12, we're done

I imagine there would be a LOT more positions at each stage than for proving God's Number, but at the end you would have a list of every 12-move position.

By the way, we should be able to compute the number of positions of depths <=5 by enumeration (there are at most 22950733806 at depth 5), and get pretty good estimates of depths 6-11 by just optimally solving lots of scrambles.

7. rokickiMember

255
4
Oct 31, 2008
I found two more "base" distance-12 positions, so now we're at 4 base positions and 128 total positions.

The positions are:

Code:
2 4 2 6 1 6 3 10 3 5 3 10 3 9
2 0 4 1 5 1 2 0 4 0 6 7 11 0
2 5 2 11 2 11 9 0 9 4 5 7 5 9
8 11 8 1 6 1 5 4 5 2 6 4 6 1

Okay, I get your strategy now. That's surprisingly doable, I think. You need to
solve about 33 billion positions in the first stage.

I will mention it is always possible to solve the cross *and* any specific pair of
two diagonally opposite corners in only 6 moves.

Last edited: Jun 1, 2014
8. qqwrefMember

7,830
37
Dec 18, 2007
a <script> tag near you
WCA:
2006GOTT01
qqwref2
It's pretty much just Jakube's approach with an extra move worth of leeway. If Jakube's approach for finding (a lack of) 13-move solutions is valid, this should be too. A generalized version of his original approach could be described something like 1+1+1+1+(1+8) => 1+1+1+(1+9) => 1+1+(1+10) => 1+(1+11) => (1+12) => 13, where we start with positions that require 13 moves in 6 steps (cross move 1 through cross move 5, and then the back 9), and combine two steps together in each step. If we ever combine two steps, and a position can be solved in fewer moves than we expect, we can discard that position because it will have a solution of under 13 moves. Of course, he ended up with no positions at the end, and in fact skipped some steps as unnecessary, but it's worth thinking about the whole thing.

Now with my approach the intuition is like this: 1+1+1+1+(1+at_least_7) => 1+1+1+(1+at_least_8) => 1+1+(1+at_least_9) => 1+(1+at_least_10) => 1+(at_least_11) => at_least_12. Whenever we combine two steps, we want the total movecount to be at least 12 (i.e. either 12 or 13) and that means anything that does not hit the above boundaries (at least 8, at least 9, ...) is a position that we can be sure doesn't require 12 moves no matter what we do in the un-combined steps. So initially we have all back-9 positions that can be solved in at least 7 moves, and when we combine with cross move 5, we need the resulting position to have an optimal solution of at least 8 moves in order for the whole thing to possibly require 12 moves (there are 4 cross move steps left, each of up to 1 move). So we combine all those at-least-7-move positions with the first cross move step and then discard anything that doesn't require at least 8 moves. Continue combining steps until the end, when we combine cross move 1 with the rest of the puzzle and discard everything requiring under 12 moves, and we are done.

9. rokickiMember

255
4
Oct 31, 2008
Yep.

Just for confirmation (anyone want to check?) this is the count of states for solving one cross and four corners.

Code:
0: 1
1: 165
2: 12507
3: 555533
4: 15211818
5: 243997728
6: 1804523730
7: 2917922526
8: 177556344

I've got a number of irons on the stove, but I'll give it a shot.

For a full distance distribution, I really think the coset approach is a winner.
Maybe I'll give it a shot.

10. JakubeMember

790
4
Feb 3, 2011
Austria
WCA:
2011KOGL01
JakubeBLD
I can confirm this numbers. When I calculate the numbers from my reduced table, I'll end up with exactly the same.

I will try your approach, qqwref. Since my 12-proof has nearly the same approach, I'll only have to change a few lines of code. But I guess, that the execution of the program will take much more time.

11. JakubeMember

790
4
Feb 3, 2011
Austria
WCA:
2011KOGL01
JakubeBLD
Quick update:
I've written the necessary code for the distance-12-states, as suggested. But it is way too slow.
- There are way too many 7 and 8 states for the full side.
- Instead of solving the state suboptimal (as I did in my proof), here we have to solve them optimally. Therefore much slower.
- I'm not sure, how many states 'survive' during each elimination, but I guess, they are too many (at least for the first 1-2 undo steps).

summary: My program run for about 3 hours and only checked ~90.000 different 7/8-move-states. And there are more than 3.000.000.000 of them.

12. rokickiMember

255
4
Oct 31, 2008
I've got my coset solver working, and it's solving 5.2B positions in about 200 seconds on one core.
That's about 25M optimal solves a second. I'm currently running the 9900 cosets on two desktops;
they should finish in a couple of days.

And I've found oodles and oodles of distance-12's. More results in a couple of days.

13. 10461394944000Banned

687
3
Mar 18, 2014
in d middle of angleland
WCA:
2009WHIT01