Hi from a LEGO Speedcuber robot creator

[qqwref]

It's easier to just keep it in one thread. Anyone who wants to follow the discussion will know to look here for new posts.

 

[IAssemble]

Yes for sequences up to 12 moves. Any position that requires more than 12 moves in the second phase is ignored and alternative first-phase solutions are tried until a good overall solution is found. The 12 move threshold is partly because of the time taken for my current algorithm to find optimal entries of more moves but more importantly because of the sheer size of the two tables and the amount of RAM available in my laptop

That's neat. So the second step is pretty much always an optimal 12 moves. Maybe you should get someone with more RAM to generate tables for you and send them to you.

Thanks. Yes 12 or fewer moves optimally. Errrrr... it's not the generation that needs the RAM, it's actually the size of the tables themselves.... Over all between the two tables for the two phases, there about 250M entries in total occupying about 1.2GB RAM I am working an an algorithm that requires less RAM for the same quality of results (or maybe slightly better results using about the same amount of RAM?)

One think I was thinking of last night is that webcam input is a bit cumbersome for cubers looking to generate their own algorithms - but there is a plethora of alternatives I'm sure you know about.

Any particular favourites?

Facelet definition is usually the fastest method, but permutation and orientation definition can be faster in certain circumstances. Both I think are the most efficient input methods for humans when done visually, however; command line based input isn't too much of a problem - this is what Acube does.

Other methods I can think of are definition of the cubestate by an actual algorithm.

Thanks - I'll think about this.

Just thinking.... this thread has already gone way beyond a "Member's Introduction". Do you think we should create a new thread somewhere more appropriate to continue the discussion or is it ok and easier to keep track of the thread if we just continue here?

If you ask one of the mods they can move the thread for you if you like.

 

[nitrocan]

I have assembled a lego robot to solve the 3x3 too, but the ones you did look awesome. They seem very reliable and accurate.

 

[IAssemble]

I have assembled a lego robot to solve the 3x3 too, but the ones you did look awesome. They seem very reliable and accurate.

Cool - do you have any videos of it? Have you considered trying to build a robot to solve sizes other than 3x3x3?

Thanks - yes, the MultiCuber solvers in particular are fairly reliable - they have to be to solve the larger cubes!

 

[IAssemble]

I am curious, how does it handle the pure edge flip case for the 4x4 and 5x5. (Can you post the algorithm)?

Edit:
An optimal (in quarter turns please), not necessarily fast one.

Here is the first sequence that my solver finds to flip the last edge for 4x4x4 (it works in face turn metrics). I don't know if this is optimal and it does swap the corners adjacent to the edge so effectively flips an entire edge of 2 corners and two edge pieces... is this what you meant by "pure edge flip"?

F2 D2 Lw' F2 Lw D2 Lw' D2 Lw B2 Lw' U2 Rw' U2 Lw B2

(I hand translated the output from my current program to what I believe is the appropriate notation... I am using Lw to mean two layers of the left face - is this correct?)

 

[nitrocan]

I have assembled a lego robot to solve the 3x3 too, but the ones you did look awesome. They seem very reliable and accurate.

Cool - do you have any videos of it? Have you considered trying to build a robot to solve sizes other than 3x3x3?

Thanks - yes, the MultiCuber solvers in particular are fairly reliable - they have to be to solve the larger cubes!

Yes I have one in my youtube channel. http://www.youtube.com/watch?v=QWyE5Ly9Oq8

As you can see though, it has a very inaccurate rotating system. I had very limited pieces, that was probably why though. Your idea of boxing the cube is very good.

By the way, how did you get the camera to read all the colors so well every time, even with the 5x5? That was always a problem with me. I tried every different thing possible, like RGB, CMYK, HSV etc. A slight change of lighting could make the software mix red and orange up.

 

[IAssemble]

I have assembled a lego robot to solve the 3x3 too, but the ones you did look awesome. They seem very reliable and accurate.

Cool - do you have any videos of it? Have you considered trying to build a robot to solve sizes other than 3x3x3?

Thanks - yes, the MultiCuber solvers in particular are fairly reliable - they have to be to solve the larger cubes!

Yes I have one in my youtube channel. http://www.youtube.com/watch?v=QWyE5Ly9Oq8

As you can see though, it has a very inaccurate rotating system. I had very limited pieces, that was probably why though. Your idea of boxing the cube is very good.

By the way, how did you get the camera to read all the colors so well every time, even with the 5x5? That was always a problem with me. I tried every different thing possible, like RGB, CMYK, HSV etc. A slight change of lighting could make the software mix red and orange up.

Thanks for the video link - I've 'liked' and 'favourited' this and added it to my playlist which is an attempt to collect all the unique LEGO Rubik Cube solvers
I can find!

I have tried several methods for colour "discrimination". My most reliable (which is needed for the 6x6x6!) uses HSL. My approach is to compare all of the colours observed with each other and make relative comparisons rather than trying to match each individual piece to absolute colours. This means that shadows and variations in lighting have less effect. White and yellow are the colours my solver typically has problems with, particularly under incandescent lighting which is itself slightly yellow

EDIT: and oh yes - I'm very impressed by your apparent unicycling talent - I tried unsuccessfully myself a number of years ago. BTW - do you juggle too?

 

[nitrocan]

I have assembled a lego robot to solve the 3x3 too, but the ones you did look awesome. They seem very reliable and accurate.

Cool - do you have any videos of it? Have you considered trying to build a robot to solve sizes other than 3x3x3?

Thanks - yes, the MultiCuber solvers in particular are fairly reliable - they have to be to solve the larger cubes!

Yes I have one in my youtube channel. http://www.youtube.com/watch?v=QWyE5Ly9Oq8

As you can see though, it has a very inaccurate rotating system. I had very limited pieces, that was probably why though. Your idea of boxing the cube is very good.

By the way, how did you get the camera to read all the colors so well every time, even with the 5x5? That was always a problem with me. I tried every different thing possible, like RGB, CMYK, HSV etc. A slight change of lighting could make the software mix red and orange up.

Thanks for the video link - I've 'liked' and 'favourited' this and added it to my playlist which is an attempt to collect all the unique LEGO Rubik Cube solvers
I can find!

I have tried several methods for colour "discrimination". My most reliable (which is needed for the 6x6x6!) uses HSL. My approach is to compare all of the colours observed with each other and make relative comparisons rather than trying to match each individual piece to absolute colours. This means that shadows and variations in lighting have less effect. White and yellow are the colours my solver typically has problems with, particularly under incandescent lighting which is itself slightly yellow

EDIT: and oh yes - I'm very impressed by your apparent unicycling talent - I tried unsuccessfully myself a number of years ago. BTW - do you juggle too?

I don't do juggling, and I'm not so advanced with unicycling either. I can ride it, jump and stuff but I can't ride backwards or do advanced tricks.

 

[jms_gears1]

now im feeling inspired. I want to to get the nxt set...

then i saw the price... lol

 

[IAssemble]

now im feeling inspired. I want to to get the nxt set...

then i saw the price... lol

Think of it as an investment in years of future enjoyment.... it is well worth it if you can aford it!

 

[IAssemble]

I am curious, how does it handle the pure edge flip case for the 4x4 and 5x5. (Can you post the algorithm)?

Edit:
An optimal (in quarter turns please), not necessarily fast one.

Here is the first sequence that my solver finds to flip the last edge for 4x4x4 (it works in face turn metrics). I don't know if this is optimal and it does swap the corners adjacent to the edge so effectively flips an entire edge of 2 corners and two edge pieces... is this what you meant by "pure edge flip"?

F2 D2 Lw' F2 Lw D2 Lw' D2 Lw B2 Lw' U2 Rw' U2 Lw B2

(I hand translated the output from my current program to what I believe is the appropriate notation... I am using Lw to mean two layers of the left face - is this correct?)

Or if you meant just flipping the last two edge pieces but preserving the rest of the 4x4x4 cube how about the following 36 move sequence?

D B2 D' R2 U R2 B L' B' L U' B' U2 B U Dw2 R2 Dw B2 L2 F2 Dw' F2 Dw F2 Dw' L2 Dw L2 Dw' B2 Dw B2 Dw2 R2 Dw2

 

[IAssemble]

I am curious, how does it handle the pure edge flip case for the 4x4 and 5x5. (Can you post the algorithm)?

Edit:
An optimal (in quarter turns please), not necessarily fast one.

Here is the first sequence that my solver finds to flip the last edge for 4x4x4 (it works in face turn metrics). I don't know if this is optimal and it does swap the corners adjacent to the edge so effectively flips an entire edge of 2 corners and two edge pieces... is this what you meant by "pure edge flip"?

F2 D2 Lw' F2 Lw D2 Lw' D2 Lw B2 Lw' U2 Rw' U2 Lw B2

(I hand translated the output from my current program to what I believe is the appropriate notation... I am using Lw to mean two layers of the left face - is this correct?)

Or if you meant just flipping the last two edge pieces but preserving the rest of the 4x4x4 cube how about the following 36 move sequence?

D B2 D' R2 U R2 B L' B' L U' B' U2 B U Dw2 R2 Dw B2 L2 F2 Dw' F2 Dw F2 Dw' L2 Dw L2 Dw' B2 Dw B2 Dw2 R2 Dw2

Just done a bit of research and found the thread http://www.speedsolving.com/forum/forumdisplay.php?f=9 to which you are contributing.... 36 face turns is a little slow isn't it!

A little improvement is needed before my software would really be useful to the speedcubing cimmunity perhaps?

 

[qqwref]

Just done a bit of research and found the thread http://www.speedsolving.com/forum/forumdisplay.php?f=9 to which you are contributing.... 36 face turns is a little slow isn't it!

A little improvement is needed before my software would really be useful to the speedcubing cimmunity perhaps?

I wouldn't say that. cmowla happens to be obsessed with that particular position, so it's been analyzed to death, but I'm sure your software will be very helpful with other positions and method sub-steps.

 

[reThinking the Cube]

Here is the first sequence that my solver finds to flip the last edge for 4x4x4 (it works in face turn metrics). I don't know if this is optimal and it does swap the corners adjacent to the edge so effectively flips an entire edge of 2 corners and two edge pieces... is this what you meant by "pure edge flip"?

F2 D2 Lw' F2 Lw D2 Lw' D2 Lw B2 Lw' U2 Rw' U2 Lw B2

(I hand translated the output from my current program to what I believe is the appropriate notation... I am using Lw to mean two layers of the left face - is this correct?)

Or if you meant just flipping the last two edge pieces but preserving the rest of the 4x4x4 cube how about the following 36 move sequence?

D B2 D' R2 U R2 B L' B' L U' B' U2 B U Dw2 R2 Dw B2 L2 F2 Dw' F2 Dw F2 Dw' L2 Dw L2 Dw' B2 Dw B2 Dw2 R2 Dw2

Just done a bit of research and .... 36 face turns is a little slow isn't it!

A little improvement is needed before my software would really be useful to the speedcubing community perhaps?

Not at all! In fact, that earlier parity alg F2 D2 l' F2 l D2 l' D2 l B2 l' U2 r' U2 l B2 , even though not ideal, and not pure, it IS probably a landmark breakthrough for >3x3x3 computer solving. Just a few months ago Lucas Garron tried to generate some algs for similar cases - using a 4x4x4 version of Acube, running on Stanford servers with lots of RAM. The results according to him were, "disappointing". Cubers have up till now, been limited to applying isomorphism with 3x3x3 solvers (CubeX, Acube), to generate NXNXN algs. I am not aware of any other software that can directly solve the difficult even-cycle big cube cases. There are many cases that we still don't have good algs for, and probably would never have them, without the help of a true >3x3x3 solver. I've been waiting for this tool, and I think it will turn out to be VERY USEFUL!

FROM:My 20 years of SpeedCubing - Jessica Fridrich
http://www.ws.binghamton.edu/fridrich/history.html

"I would dare to say that nothing important happened in speed cubing and cubing in general over the next decade. Then, in 1992 Herbert Kociemba developed a computer algorithm with a performance very close to the God's Algorithm (the shortest moves from any position). It was, in my opinion, the biggest event in cubing in general. Suddenly, we could obtain the shortest moves for any position and any pattern. Surprisingly, Kociemba's algorithm always seemed to find a solution within 20 face moves. The famous cube-in-cube pattern turned out to have an elegant short solution L F L D'B D L² F² D'F'R U'R'F² D as we suspected for a long time but never found it. Progress has been made in identifying the farthest positions on the cube (superflip and supertwist). To give you an idea how revolutionary Kociemba's discovery was, the previous best computer solution was always able to solve the cube within 38 moves, but could not guarantee better (Thistlewaite's algorithm). Even though Kociemba's algorithm did not provide a proof that the diameter of the cube group is indeed 20 in face counting, it has been an impressive piece of work, indeed. As the computer speed and memory increased, optimal solvers came to life, and suddenly, to my opinion, the cube lost much of its enigma."

Here is the first sequence that my solver finds to flip the last edge for 4x4x4

You stated that F2 D2 l' F2 l D2 l' D2 l B2 l' U2 r' U2 l B2 was the "first" sequence. How long did that take, and could you get some shorter/better ones by letting it run longer?
For example: Here is the parity alg that I use for that exact case -
reParity™ - r U2 l' U2 x' r' U2 l U2 r' U2 l U2 l' U2 y' 2m2 y'
If I take out the cube rotations, then it could be written like this -
r U2 l' U2 r' B2 l B2 r' B2 l B2 l' B2 2e2

Could your program also find that alg?

...

 

[reThinking the Cube]

There are many cases that we still don't have good algs for, and probably would never have them,...

What cases are you talking about?

For starters:
http://www.speedsolving.com/forum/showpost.php?p=332172&postcount=33

Cride: cube applet can custom display for >3x3x3 soon?

It seems that algorithms which are "good" to speedcubers are ones which are formed from the conventional method (done with a 3X3X3 solver), as they only use the moves involving {U2, B2, D2, F2, Rw',Rw2, Rw2,Lw', Lw2, Lw} (this is the whole set, but of course, opinions will vary one whether or not an algorithm should just have U2, or have U2 with F2 or B2...and whether or not Rw22 and Lw22 are a waste of time or not).

Take it easy, Chris, I agree with you, and it sure does "seem" that way. The reason for this seemingly irrational preference, is simply because of isomorphic restrictions on the move set. I can computer generate lots of 3x3x3 algs to solve for J-perm, or any other similar perm, and any of these could change 4x4x4 parity cases. The real problem is determining which algs fix the parity issue without messing up the rest. Restrict the move set to only <U2,B2,D2,F2> and any <R,L> and I can still use those 3x3x3 permutation algs to fix parity on a 4x4x4 without messing up the centers (by changing all the <R,L> into <r,l>). I am actually hoping that a true 4x4x4 solver can find some nice parity algs that are NOT restricted to just that move set. You fortunately, are not a computer, and can create parity algs for 4x4x4 that are free from isomorphic restrictions, but unfortunately, you are also human and cannot generate all that are possible, so that I can decide for myself which ones "stink" more than others.

...

 

[Cride5]

Cride: cube applet can custom display for >3x3x3 soon?

Are you talking about VisualCube? Its just a case of setting aside some time to do it (not easy at the moment). I'll try to get it updated soon..

It would be great to have a system which sorts algorithm lists based on these complex metrics, also with the possibility of allowing the user to choose their own metrics to reflect their cubing style.

I'm seriously thinking about adapting my generic algorithm to being able to generate "algorithms" for the 4x4x4 cube initially but are you suggesting that even for the 3x3x3 there is scope for a more flexible, configurable generator?

Certainly, yes! Currently, as far as I'm aware no 3x3x3 solvers actually conduct the search using any of these kind of metrics. The most they allow is to exclude the use of selected faces. It may be easier to apply these metrics after alg-generation, so that large generated lists can be sorted/filtered before being presented to the user. Is this how your solver currently generates good solutions for your robot?

It would be better if these metrics were actually built into the solver. Instead of generating a huge pile of sub-optimal algs and reducing it down, the system would simply generate the best algs for the chosen metrics directly.

 

[qqwref]

Speedsolving Theorem:
Let A be a potentially good speedsolving parity algorithm.
Then A must contain some elements of X={U2, B2, D2, F2, Rw',Rw2, Rw2, Lw', Lw2, Lw}, but not all elements of X.
PROOF:
Ask any speedsolver for big cubes

Can you PLEASE stop putting idiotic "proof"s on the forum? Not only are many of them nonsensical or wrong, but you sound like a crank and I think you could do a lot better. Stop trying to take over someone's thread with meaningless mathematical-sounding language, bold text, and minefields of asterisks. This guy has some interesting stuff to contribute and we don't want to push him away by concentrating on one tiny and irrelevant topic.

As to your point: if you're looking for algs in <U2,B2,F2,D2,Lw,Rw> we can find these using a 3x3 solver (or a slight modification). This is known and has been known for a long time. If you want to try to look for algorithms that are more efficient than what 3x3 solvers will give you (in <U2,B2,F2,D2,L,R>) you WILL have to consider moves outside this set. A new approach should have no such preconceptions about what is required to approach optimality.

 

[IAssemble]

.... This guy has some interesting stuff to contribute and we don't want to push him away by concentrating on one tiny and irrelevant topic.

Thanks qqwref - don't worry, I won't get "pushed away" by stuff like this. I'm interested in everyone's opinion

I have been thinking about trying to making my 4x4x4 solver more useful and it was good to realise during this discussion that, although for complete solves from random positions it is probably reasonable, it is not currently very useful for "algorithm generation" with only a few pieces to solve (and "blanks" included).

So I've been playing with the idea of adapting some of the concepts I use in my fast 2-phase 3x3x3 algorithm into a 4x4x4 solver that is specifically designed to find (short) algorithms (including blanks). I've been using the pure edge flip as a test case.

I see from earlier posts that speedcuber algorithms for the 4x4x4 can be around 16 moves in half turn metrics. Is this typical of the complexity of algorithms for which people would like to explore different solutions or are there some other examples that would be of interest, particularly those already have known shorter solutions?

BTW I left my original 4x4x4 solver working on the pure edge flip case and it has found a 23 move solution - getting closer

 

[IAssemble]

... Currently, as far as I'm aware no 3x3x3 solvers actually conduct the search using any of these kind of metrics. The most they allow is to exclude the use of selected faces. It may be easier to apply these metrics after alg-generation, so that large generated lists can be sorted/filtered before being presented to the user. Is this how your solver currently generates good solutions for your robot?

Interesting thought... At the moment my solvers generate sequences without any restriction and effectively filter the solutions on the fly as each is generated. For complete solves from random positions this is probably a reasonable approach but for algorithm generation it may be more efficient to restrict the moves that the solver can use to reduce the search space...

It would be better if these metrics were actually built into the solver. Instead of generating a huge pile of sub-optimal algs and reducing it down, the system would simply generate the best algs for the chosen metrics directly.

Yeah right, "simply"

But seriously, I take your point and for some types of metric it would be straightforward to use them to speed up the search by incorporating them into the solve algorithm.

I asked just now about example 4x4x4 algorithms that people would be interested in improving... Can someone also suggest some 3x3x3 positions (with blanks) that would be good to explore and include some example known "good" algorithms for them?

Thanks. I can see this might keep me "entertained" for a while!?!

 

[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?