Hi from a LEGO Speedcuber robot creator

[Ashmnafa]

You are a genius my friend.

 

[masterofthebass]

Can I ask all you guys if you know how many moves it typically takes you to speedsolve all cube sizes from 2x2x2 up to 7x7x7?

From what I can tell, your solutions for larger cubes become MUCH more efficient than speedsolving solutions, but in my opinion, movecount doesn't help too much in speedsolving if its accompanied by a lack of recognition/continuity. Without watching your video, I seem to remember a number in the 200s for a 6x6 solution, which is quite under the amount of moves it takes me to solve it in 2:30 (i think). I'll do some movecount solves when I get some time though.

 

[IAssemble]

Can I ask all you guys if you know how many moves it typically takes you to speedsolve all cube sizes from 2x2x2 up to 7x7x7?

From what I can tell, your solutions for larger cubes become MUCH more efficient than speedsolving solutions, but in my opinion, movecount doesn't help too much in speedsolving if its accompanied by a lack of recognition/continuity. Without watching your video, I seem to remember a number in the 200s for a 6x6 solution, which is quite under the amount of moves it takes me to solve it in 2:30 (i think). I'll do some movecount solves when I get some time though.

I understand that for speedcubing recognition and continuity (as you put it) are essential. In fact I think I spend most of the time when solving the larger cubes myself looking for pieces.

My software typically finds a solution of about 300 moves for the 6x6x6 (it was 306 in the video).

Thanks for offering to do some movecount solves. I would be interested in the result although as you say, movecount is by no means everything for a human solve.

Congratulations on your 2:30 6x6x6 time - mine is more like 15:00

 

[masterofthebass]

wow... I just did a 6x6 solve in 285 moves STM (counting any "turn" as 1 move. probably should've done it in block turn, but I wasn't aware I was close to your program's solution. Quite an impressive program in my opinion.

 

[IAssemble]

wow... I just did a 6x6 solve in 285 moves STM (counting any "turn" as 1 move. probably should've done it in block turn, but I wasn't aware I was close to your program's solution. Quite an impressive program in my opinion.

*wow* indeed - I'm very impressed! Does that include many slice turns? I assume you counted each of these as one?

Do you have any idea about speedcubing move counts for other cube sizes?

Hmmm, so 285 moves in 2:30... that's "only" 1.9 moves/sec I suspect this indicates how much time is spent looking while solving compared with, say, 3x3x3 solves? Although I guess the 6x6x6 cubes are harder to manipulate as quickly?

I'm currently guessing that for 3x3x3 the move rate is significantly higher than this?

 

[Me]

Having messed around the the NXT kit for a semester doing trivial things (solving a maze, inscribing a circle of a given diameter) this is extremely impressive. Using NXT Python to program it, we could never get a great deal of precision with the motors I guess that's different in a C++ interface? Nevertheless I find it very awesome on both the hardware and software levels.

 

[reThinking the Cube]

we could never get a great deal of precision with the motors I guess that's different in a C++ interface? Nevertheless I find it very awesome on both the hardware and software levels.

I once developed a stepper motor routine (head positioning) for Apple IIe/c floppy drives that could even be "interrupted" by having all the branches for each interrupt handler routine, add the #of execution cycles back into the stepper motor timer loops. Now that was an interesting challenge! Needed it to be that way to maintain an RS232 interrupt driven clock for the system. It worked great, and was considered impossible to do at the time. 6502C ruled back then, and it was fun. LDA.

IAssemble: A 4x4x4 test case for your program that has eluded direct solution by man&beast alike is the following: single corner exchange ULF<->DBR

Here is fazrulz (feliks zemdegs) 31q "indirect" solution:

r2 U2 r2 Uw2 r2 u2
R2 y' T permutation (R U R' U' R' F R2 U' R' U' R U R' F')
B2
*Note u2 is inner slice only, and Uw2 is both the inner and outer slices.

I would be very interested in ANY solutions your program could find for this.

...

 

[IAssemble]

Having messed around the the NXT kit for a semester doing trivial things (solving a maze, inscribing a circle of a given diameter) this is extremely impressive. Using NXT Python to program it, we could never get a great deal of precision with the motors I guess that's different in a C++ interface? Nevertheless I find it very awesome on both the hardware and software levels.

Thanks - although you shouldn't be so dismissive of your own achievements. Creating a maze solving robot is not "trivial"!

Actually no, the motor precision was one of the trickier things to get right. The interface provided by the C++ libraries I used effectively only had read_rotation_sensor() and set_motor_power(). There was no rotate_by_degrees() or similar routine. In order to turn precisely and smoothly I had to implement my own "servo motor" routines to monitor the motor position and predict how much power to apply to accelerate and brake by the appropriate amount. This feedback control loop is executed about 100 times per second. The rotation sensors themselves provide accuracy to 1 degree of the output shaft rotation but without the feedback logic in the motor control the motors would overshoot wildly!

 

[IAssemble]

we could never get a great deal of precision with the motors I guess that's different in a C++ interface? Nevertheless I find it very awesome on both the hardware and software levels.

I once developed a stepper motor routine (head positioning) for Apple IIe/c floppy drives that could even be "interrupted" by having all the branches for each interrupt handler routine, add the #of execution cycles back into the stepper motor timer loops. Now that was an interesting challenge! Needed it to be that way to maintain an RS232 interrupt driven clock for the system. It worked great, and was considered impossible to do at the time. 6502C ruled back then, and it was fun. LDA.

Careful - you're showing your age there Although I can recall programming in 6502 assembler on a Commodore Pet and later in Z80 assembler on a Sinclair ZX81 so I'm one to talk! Anyway - we should stay on-topic before someone tells us off

IAssemble: A 4x4x4 test case for your program that has eluded direct solution by man&beast alike is the following: single corner exchange ULF<->DBR

Here is fazrulz (feliks zemdegs) 31q "indirect" solution:

r2 U2 r2 Uw2 r2 u2
R2 y' T permutation (R U R' U' R' F R2 U' R' U' R U R' F')
B2
*Note u2 is inner slice only, and Uw2 is both the inner and outer slices.

I would be very interested in ANY solutions your program could find for this.

...

Thanks for this - I'll find some time in the next day or so to run this through my existing solver and let you know what it finds...

 

[IAssemble]

we could never get a great deal of precision with the motors I guess that's different in a C++ interface? Nevertheless I find it very awesome on both the hardware and software levels.

I once developed a stepper motor routine (head positioning) for Apple IIe/c floppy drives that could even be "interrupted" by having all the branches for each interrupt handler routine, add the #of execution cycles back into the stepper motor timer loops. Now that was an interesting challenge! Needed it to be that way to maintain an RS232 interrupt driven clock for the system. It worked great, and was considered impossible to do at the time. 6502C ruled back then, and it was fun. LDA.

Careful - you're showing your age there Although I can recall programming in 6502 assembler on a Commodore Pet and later in Z80 assembler on a Sinclair ZX81 so I'm one to talk! Anyway - we should stay on-topic before someone tells us off

IAssemble: A 4x4x4 test case for your program that has eluded direct solution by man&beast alike is the following: single corner exchange ULF<->DBR

Here is fazrulz (feliks zemdegs) 31q "indirect" solution:

r2 U2 r2 Uw2 r2 u2
R2 y' T permutation (R U R' U' R' F R2 U' R' U' R U R' F')
B2
*Note u2 is inner slice only, and Uw2 is both the inner and outer slices.

I would be very interested in ANY solutions your program could find for this.

...

Thanks for this - I'll find some time in the next day or so to run this through my existing solver and let you know what it finds...

Here are the first three results that my existing 4x4x4 solver finds for the problem I think you are describing - please can you check that they do what you expect?

The two numbers after the "SOLVED:" are block half-turn and block quarter-turn metrics I believe. This is followed by time in seconds since the solve was started so all these came out in the first 0.8s.

SOLVED: 30 41 0.0s F' L B' L' F L B L' D2 U' Uw2 Rw2 R2 Uw2 Lw2 D2 Lw2 U B2 L' D L B2 R D2 L D' R' D L'
SOLVED: 27 43 0.0s L B' L' F' L B L' D2 F' R2 U2 B' U2 B U2 B Bw2 U2 Fw2 Uw2 F2 Bw2 Dw2 U2 R2 F2 D2
SOLVED: 26 41 0.8s U' D2 F2 D F2 D F2 D F2 U F2 L' B' L F2 L' B L Dw2 R2 F2 Uw2 F2 R2 Dw2 B2

It currently only outputs solutions that it finds that are shorter than the previous ones (rather than all the solutions it finds). I'll leave it running and let you know if it generates any better ones....

 

[IAssemble]

How about these? (I won't post any more until you confirm these are correct for the problem you're describing)

SOLVED: 25 37 668.9s U' F2 Uw' R' D' R Uw F2 Dw' L' U L Dw U B2 U' B2 Dw2 R2 F2 Uw2 F2 R2 Dw2 B2
SOLVED: 21 33 1282.2s Uw' B2 R' U' R B2 L' D L Uw L2 D' L2 Uw2 F2 R2 Dw2 R2 F2 Uw2 L2

 

[reThinking the Cube]

How about these? (I won't post any more until you confirm these are correct for the problem you're describing)

SOLVED: 25 37 668.9s U' F2 Uw' R' D' R Uw F2 Dw' L' U L Dw U B2 U' B2 Dw2 R2 F2 Uw2 F2 R2 Dw2 B2
SOLVED: 21 33 1282.2s Uw' B2 R' U' R B2 L' D L Uw L2 D' L2 Uw2 F2 R2 Dw2 R2 F2 Uw2 L2

YES! These are correct, and very interesting too. You are making and awesome contribution to cubing here. Much appreciated.

 

[qqwref]

SOLVED: 21 33 1282.2s Uw' B2 R' U' R B2 L' D L Uw L2 D' L2 Uw2 F2 R2 Dw2 R2 F2 Uw2 L2

U' B2 R' U' R B2 L' D L U L2 D' Uw2 F2 R2 Dw2 R2 F2 Uw2 (19 bhtm, 29 bqtm)

 

[IAssemble]

SOLVED: 21 33 1282.2s Uw' B2 R' U' R B2 L' D L Uw L2 D' L2 Uw2 F2 R2 Dw2 R2 F2 Uw2 L2

U' B2 R' U' R B2 L' D L U L2 D' Uw2 F2 R2 Dw2 R2 F2 Uw2 (19 bhtm, 29 bqtm)

Interesting! Is that one you already knew or did you optimise the last solution my solver found?

 

[qqwref]

I optimized it. It was composed of two sequences ending in L2, and the second one didn't affect the L slice, so you could just setup the second sequence by L2 and remove both L2s. Also, the Uw and Uw' in the first sequence could be reduced to U and U' because the middle layers didn't get changed by the intervening moves.

 

[IAssemble]

I optimized it. It was composed of two sequences ending in L2, and the second one didn't affect the L slice, so you could just setup the second sequence by L2 and remove both L2s. Also, the Uw and Uw' in the first sequence could be reduced to U and U' because the middle layers didn't get changed by the intervening moves.

Brilliant - well observed/analysed!

So is the resulting solution shorter than your previous best solution? Is it "speedcuber friendly" for manipulation speed by any chance? I'm curious

BTW I left my solver running and it has not yet found a solution with fewer than 21 bhts...

I previously experimented with ways of post-optimising 3x3x3 move sequences when I was initially trying to get a complete solve reliably under 25 or so moves but very rarely did it find an optimisation... I didn't think to try the idea with 4x4x4 but as you observe, maybe there is more scope with 4x4x4 because of the extra layers?

This is very thought-provoking! Thanks

 

[qqwref]

In general, the longer a sequence is, the easier it is to squeeze moves out of. Some other optimization possibilities (the intent being always to cancel moves) are:
- If a sequence does something symmetrical, you can try rotating it to get a different and equally long sequence which does the same thing. So a completely symmetrical sequence (say one which flips every edge) can be made to end with any face you want.
- If a sequence can generate and solve the same pattern, you can try the inverse of the sequence instead.
- If a sequence leaves a layer (or even a certain set of pieces) unchanged, you can try doing setups (that is, X sequence X', with X being the setup) to find longer algs that do the same thing but might cancel with something else.
- If a sequence cycles exactly 3 pieces (typically this will be a 'commutator', of the form X Y X' Y') you can try cycling those pieces at any point in your algorithm. This is known as an "insertion" in fewest moves solving.
- If you notice that some part of your algorithm is only 3x3 moves (outer-layer turns), you can try running a 3x3 solver on that to find shorter solutions. You would want to get as many outer-layer turns in a row as possible for this, because the longer a sequence of 3x3 turns is the less likely it is optimal.

Normally all of these (and more, perhaps) would be done by hand/cleverness. It would be amazing to have a computer program able to do it! I wouldn't expect every sequence you try to be given this kind of treatment, but whenever your program finds a better (or equal) sequence for the pattern, it would be helpful to try some of these.

 

[IAssemble]

In general, the longer a sequence is, the easier it is to squeeze moves out of. Some other optimization possibilities (the intent being always to cancel moves) are:
- If a sequence does something symmetrical, you can try rotating it to get a different and equally long sequence which does the same thing. So a completely symmetrical sequence (say one which flips every edge) can be made to end with any face you want.
- If a sequence can generate and solve the same pattern, you can try the inverse of the sequence instead.
- If a sequence leaves a layer (or even a certain set of pieces) unchanged, you can try doing setups (that is, X sequence X', with X being the setup) to find longer algs that do the same thing but might cancel with something else.
- If a sequence cycles exactly 3 pieces (typically this will be a 'commutator', of the form X Y X' Y') you can try cycling those pieces at any point in your algorithm. This is known as an "insertion" in fewest moves solving.
- If you notice that some part of your algorithm is only 3x3 moves (outer-layer turns), you can try running a 3x3 solver on that to find shorter solutions. You would want to get as many outer-layer turns in a row as possible for this, because the longer a sequence of 3x3 turns is the less likely it is optimal.

Normally all of these (and more, perhaps) would be done by hand/cleverness. It would be amazing to have a computer program able to do it! I wouldn't expect every sequence you try to be given this kind of treatment, but whenever your program finds a better (or equal) sequence for the pattern, it would be helpful to try some of these.

Thanks - now this is getting *really* interesting!

You may remember I said in one of my earlier posts "There are a variety of algorithms that I use to generate the table entries..." for the multi-phase table-driven algorithms that some of my solvers use?

Well this "variety of algorithms" includes:

1) rotation of previously discovered sequences
2) reversal of ...
3) addition of a pre-amble at the start of and inverse of this pre-amble at the end of ...

EDIT: I hope it is obvious that these are just my way of thinking about what you describe much more eloquently and completely in your first three points above!

And more significantly (for my generator) all combinations of the above such as:

4) all rotations with an additional pre-/post amble
5) all rotations of the reversal
6) all rotations of the reversal with additional pre-/post-amble

The difference is that my table generator uses them to find new potential solutions rather than to identify when they could be used to optimise existing ones, but the principles are obviously the same.

Actually I even effectively apply 3) by hand on-the-fly when I solve the corners of the LL in my human solve (my "slow" ~45s solve that is )

Also, my first attempt at a "high speed" solver worked almost completely by combining multiple, nested commutators as you call them for many different "group" types as I called them in my code.

So I am already familiar with and have software that uses these ideas when generating the tables for my solvers!

Thinking laterally for a moment (for my own benefit) the mechanism I previously used for post-solve optimisation was not directly based on any of these ideas... so if I could use my table generation algorithms for post-solve optimisation maybe my existing post-solve optimisation (which is more software than human friendly) could be applied to table generation too!?!

(thinking out loud here....) I guess I need to think about the best way of applying these more directly during the solve... or as a post-solve optimisation phase... or maybe how my solver should be changed to become a more useful algorithm generator emplying thes ideas as solution generators rather than solution optimisers... I'm really beginning to see more parallels between my table generators and algorithm generators than between my solvers and algorithm generators.... more "food for thought"!

Thanks for a further stimulating discussion!

BTW you didn't answer my question about whether your improved 19 bhtm, 29 bqtm solution was shorter than your previously know solution and whether it is "speedcuber friendly". I'm just curious...

 

[IAssemble]

BTW my commutator-based solver considered cycles of length 3, 5 and 7 pieces and even "group"s with multple cycles such as a combined "group" with two cycles of length 2 (i.e 4 pieces in total). I experimented with more complex ones such as three cycles of lengths 1, 1 and 2 (where the cycles of length one are single piece edge flips or corner twists and the cycle of length 2 is obviously an exchange of 2 pieces)....

I suspect humans might find it hard to consider these larger and more complex cycles and groups but it can be done relatively easily in software.

Hope that makes sense?

 

[qqwref]

BTW you didn't answer my question about whether your improved 19 bhtm, 29 bqtm solution was shorter than your previously know solution and whether it is "speedcuber friendly". I'm just curious...

Well, it was certainly shorter than the one posted earlier. I don't personally know an optimized way to do that position since it can't come up in my solves. It does seem speedcuber-friendly although adding some rotations could help out (although I don't expect an algorithm-generating software to care about that).