Hi from a LEGO Speedcuber robot creator

[miniGOINGS]

I meant libraries. Of course I read what he already said.

I meant that the Windows GUI is coded in C/C++.

 

[IAssemble]

So what exactly would you want from an "algorithm generator" for 4x4x4?

An algorithm generator for 4x4 would ideally be somewhat similar to http://software.rubikscube.info/JACube/ This allows the restrictions of moves for solving, various goals for ranking output, and the ability to find multiple solutions.

Hi Kirjava, what kind of details do you want?
Initially everything is coded in C++ running under cygwin under Windows (but the code is generic C++ so could be compiled to run anywhere. I wrote a Java version of the (slow) 3x3x3 solver and generic NxNxN solver to allow them to run on Nokia and Android mobile phones as an alternative to the laptop (see http://www.youtube.com/user/ARMflix). I have a range of 3x3x3 solvers from one which procedurally implements roughly the algorithm I use to solve the cube myself (a variation of a simple 5 phase algorithm I guess) through a number of variations of table-driven versions of 7, 6, 5 and 4-phase algorithms which typically generate down to about 25 move solutions in a short time and one 2-phase algorithm that typically finds a 20 or 21 move solution. All the algorithms are used in a way that allows them to generate a large number of solutions in a short time and pick the best from those generated. My generic NxNxN solution is a multi-phase table driven algorithm which extends the 3x3x3 case up to 7x7x7. The way my algorithm works, all cubes above 7x7x7 can be solved with the tables for cubes up to 7x7x7. There are a variety of algorithms that I use to generate the table entries...

So what exactly would you want from an "algorithm generator" for 4x4x4?

Wow, I didn't know the ARM based solvers were you too. I guess it should be obvious now. Nice to hear that the applications are portable, I guess the GUI has to be reproduced for other platforms though. (Out of interest, what's the windows GUI written in? Something like Qt would be useful)

A generic NxNxN solver would be crazy useful (although all you really need is 4x4x4 to be able to apply the algorithms to any sized cube), would need either facelet definition or state definition (based on piece permutation/orientation) or both. Text input for this would be fine, but everyone loves a GUI

I imagine the problem would be making algorithms to solve 3 pieces (for example) efficient, since all your solvers so far have been designed to work with the entire cube.

As for the 3x3x3 solvers, is the 2-phase algorithm kociemba, or something else? I'd like to hear more about the 7/6/5 and 4 phase algs, too.

Thanks for the info!

Interesting that you believe 4x4x4 is sufficient to solve NxNxN - I think your human brain is able to extrapolate a bit more than my software! I have had to classify the pieces on NxNxN cubes by "type" and with my classification there are unique "types" of piece all the way up to 7x7x7. For example consider the "middle" pieces on a face, there are those on a diagonal (like the 4x4x4 center), those on the orthogonal (like the non-diagonals on a 5x5x5 center) and non-orthogonal, non-diagonals (like those introduced in the 6x6x6 in the outermost ring).... and I distinguish between non-orthogonal, non-diagonal pieces that are together (as in the 6x6x6) and separated by one or more pieces (as in those introduced in the outer ring on the 7x7x7)... The way my solver works, it can take advantage of shorter sequences for solving some of the "middle" pieces rather than having to use a completely generic sequence for all cases. In this scheme, all of the cubes larger than 7x7x7 only have more occurences of pieces of a "type" found on smaller cubes. Does any of that make sense?

My NxNxN solver typically solves groups of 2 or 4 pieces at a time.

My 3x3x3 algorithms solve varying size groups with mixtures of corner and edge pieces ranging from 2 to 6 I think. My 2-phase algorithm is my own design (although I guess it might be similar to kociemba by conincidence because I've never researched it). Again it is table-driven (and needs lots of RAM!?!) but uses a different strategy from the other solutions. It can very rapidly find many different solutions for about 7 pieces and for each of these partial solutions does a table lookup to see if it has a (fast) solution for the remaining 13 pieces. It simply continues until it has a "good enough" solution in the allocated time. Typically it finds a 20 or 21 move solution in less than 1s of CPU time on my laptop and can find a 20 move solution for "superflip" in an hour or so (it only finds a 23 move solution for this in a second).

Using my algorithms to find efficient solutions for say 3 pieces (with some others fixed and some "blank") is not too much of an issue since I already have several mechanisms for creating the table entries that have to do just this. At the moment these are configured for specific groups but it shouldn't be too hard to genericise this bit of the code... However, these algorithms generally take much longer to find really good, short solutions (for sequences longer than about 6 or 7 moves). How long would you be prepared to leave such a program running to generate a set of solutions for a given 3-piece problem? Seconds, minutes, hours or days?

EDIT - Oh - and the GUI in the PC version is written in OpenGL and is really just a display. There is no real interaction with a mouse at present.

 

[IAssemble]

Welcome to the forum! Just out of curiosity, does your 6x6 misalign during robo-solves (which is what I will be calling them from now until the end of time)?

Thanks. Yes, the 4x4x4, 5x5x5 and particularly 6x6x6 do "misalign" sometimes! The software running on the NXT is programmed to automatically try recovering when it detects a jam (i.e. the motor stalls) by turning the layer in the opposite direction by an appropriate amount (just as I do by hand when a cube jams!). This mechanism almost always recovers from the jam (except when it is the 6x6x6 "internal lockup" that sometimes occurs after rotating 3 layers )

In the videos I think this recovery mechanism was used several times during the 4x4x4, 5x5x5 and 6x6x6 solves although it is hard to see because the video is speeded up.

 

[Kirjava]

I meant libraries. Of course I read what he already said.

I meant that the Windows GUI is coded in C/C++.

I don't think you quite get me.

Interesting that you believe 4x4x4 is sufficient to solve NxNxN - I think your human brain is able to extrapolate a bit more than my software!

If I can find an algorithm to manipulate certain edges on a 4x4x4, I can apply the same algorithm to any orbital on a NxNxN by picking a different layer. I'm thinking egocentrically here. ^_^

I have had to classify the pieces on NxNxN cubes by "type" and with my classification there are unique "types" of piece all the way up to 7x7x7. For example consider the "middle" pieces on a face, there are those on a diagonal (like the 4x4x4 center), those on the orthogonal (like the non-diagonals on a 5x5x5 center) and non-orthogonal, non-diagonals (like those introduced in the 6x6x6 in the outermost ring).... and I distinguish between non-orthogonal, non-diagonal pieces that are together (as in the 6x6x6) and separated by one or more pieces (as in those introduced in the outer ring on the 7x7x7)... [...] In this scheme, all of the cubes larger than 7x7x7 only have more occurences of pieces of a "type" found on smaller cubes. Does any of that make sense?

All of it. Enjoyable explanation.

I said 4x4x4 would be good enough to help human solvers solve any size, and I thought 5x5x5 would be enough for computer solvers to solve any size cube. I now understand why this in not the case.

The way my solver works, it can take advantage of shorter sequences for solving some of the "middle" pieces rather than having to use a completely generic sequence for all cases.

I thought this was especially cool.

My NxNxN solver typically solves groups of 2 or 4 pieces at a time.

My 3x3x3 algorithms solve varying size groups with mixtures of corner and edge pieces ranging from 2 to 6 I think. My 2-phase algorithm is my own design (although I guess it might be similar to kociemba by conincidence because I've never researched it). Again it is table-driven (and needs lots of RAM!?!) but uses a different strategy from the other solutions. It can very rapidly find many different solutions for about 7 pieces and for each of these partial solutions does a table lookup to see if it has a (fast) solution for the remaining 13 pieces. It simply continues until it has a "good enough" solution in the allocated time. Typically it finds a 20 or 21 move solution in less than 1s of CPU time on my laptop and can find a 20 move solution for "superflip" in an hour or so (it only finds a 23 move solution for this in a second).

Sounds like it produces very similar results to the program CubeExplorer and uses a similar algorithm. Suboptimal first step and optimal second step.

Using my algorithms to find efficient solutions for say 3 pieces (with some others fixed and some "blank") is not too much of an issue since I already have several mechanisms for creating the table entries that have to do just this. At the moment these are configured for specific groups but it shouldn't be too hard to genericise this bit of the code... However, these algorithms generally take much longer to find really good, short solutions (for sequences longer than about 6 or 7 moves). How long would you be prepared to leave such a program running to generate a set of solutions for a given 3-piece problem? Seconds, minutes, hours or days?

Personally? minutes. But the ability to pick time vs movecount would be handy.

The thing is, in speedsolving, movecount is generally not the most important aspect. Finding fingerfriendly algorithms is. So I imagine restricting moves and generating lots of algorithms would be fairly quick compared to finding the shortest solution. From this list you could pick the algorithm you think you can execute the fastest. Often, the shortest solution is much slower to execute than a longer one. (Ok, maybe not for a robot )

EDIT - Oh - and the GUI in the PC version is written in OpenGL and is really just a display. There is no real interaction with a mouse at present.

Hah, should've guessed from the 3D cube >_<

 

[miniGOINGS]

I don't think you quite get me.

I probably don't. It wouldn't be the first time.



I wouldn't want to have any computer sovler run too long (a couple hours at most). I would think that being able to restrict moves, and blank out pieces would aid in the speed of the program. I definitely see myself using such a program. A lot.

 

[IAssemble]

Interesting that you believe 4x4x4 is sufficient to solve NxNxN - I think your human brain is able to extrapolate a bit more than my software!

If I can find an algorithm to manipulate certain edges on a 4x4x4, I can apply the same algorithm to any orbital on a NxNxN by picking a different layer. I'm thinking egocentrically here. ^_^

That's what makes humans so much better than computers!

I have had to classify the pieces on NxNxN cubes by "type" and with my classification there are unique "types" of piece all the way up to 7x7x7. For example consider the "middle" pieces on a face, there are those on a diagonal (like the 4x4x4 center), those on the orthogonal (like the non-diagonals on a 5x5x5 center) and non-orthogonal, non-diagonals (like those introduced in the 6x6x6 in the outermost ring).... and I distinguish between non-orthogonal, non-diagonal pieces that are together (as in the 6x6x6) and separated by one or more pieces (as in those introduced in the outer ring on the 7x7x7)... [...] In this scheme, all of the cubes larger than 7x7x7 only have more occurences of pieces of a "type" found on smaller cubes. Does any of that make sense?

All of it. Enjoyable explanation.

I said 4x4x4 would be good enough to help human solvers solve any size, and I thought 5x5x5 would be enough for computer solvers to solve any size cube. I now understand why this in not the case.

The way my solver works, it can take advantage of shorter sequences for solving some of the "middle" pieces rather than having to use a completely generic sequence for all cases.

I thought this was especially cool.

Thanks!

My NxNxN solver typically solves groups of 2 or 4 pieces at a time.

My 3x3x3 algorithms solve varying size groups with mixtures of corner and edge pieces ranging from 2 to 6 I think. My 2-phase algorithm is my own design (although I guess it might be similar to kociemba by conincidence because I've never researched it). Again it is table-driven (and needs lots of RAM!?!) but uses a different strategy from the other solutions. It can very rapidly find many different solutions for about 7 pieces and for each of these partial solutions does a table lookup to see if it has a (fast) solution for the remaining 13 pieces. It simply continues until it has a "good enough" solution in the allocated time. Typically it finds a 20 or 21 move solution in less than 1s of CPU time on my laptop and can find a 20 move solution for "superflip" in an hour or so (it only finds a 23 move solution for this in a second).

Sounds like it produces very similar results to the program CubeExplorer and uses a similar algorithm. Suboptimal first step and optimal second step.

Interesting. Actually the first phase would eventually find all possible solutions pretty much in order of optimality so actually tries the optimal solution to the first phase first!

I'm currently working on a variation of the second phase along the lines of a previous experimental 2-phase algorithm I tried that only produced approx 26 move solutions at best - watch this space

Using my algorithms to find efficient solutions for say 3 pieces (with some others fixed and some "blank") is not too much of an issue since I already have several mechanisms for creating the table entries that have to do just this. At the moment these are configured for specific groups but it shouldn't be too hard to genericise this bit of the code... However, these algorithms generally take much longer to find really good, short solutions (for sequences longer than about 6 or 7 moves). How long would you be prepared to leave such a program running to generate a set of solutions for a given 3-piece problem? Seconds, minutes, hours or days?

Personally? minutes. But the ability to pick time vs movecount would be handy.

The thing is, in speedsolving, movecount is generally not the most important aspect. Finding fingerfriendly algorithms is. So I imagine restricting moves and generating lots of algorithms would be fairly quick compared to finding the shortest solution. From this list you could pick the algorithm you think you can execute the fastest. Often, the shortest solution is much slower to execute than a longer one. (Ok, maybe not for a robot )

I understand that fewest moves isn't always fastest. And also I understand that speedcubers choose methods that also help speed up the visual pattern recognition required to determine which sequences to apply too?

Actually the fewest moves is not necessarily the fastest for a robot either...

Consider my four-handed "Yellow Cube Machine" - L R F B is faster than L F R because in the first sequence L and R can be done simultaneously as can F and B so it is about 2/3 of the time! Also, perhaps counterintuitively, L2 F2 R2 is much faster than L F R because the arms must be returned to the upright position to allow the adjacent faces to turn so the second sequence needs the arms to be moved away, re-positioned to vertical and then closed again between each move. The first of these sequences is almost twice as fast as the second. The solver for this robot takes the mechanical requirements into account when determining which solution is "best". In fact often a 23 or 24 move solution is found which results in a shorter solve time than a 20 or 21 move solution!

EDIT - Oh - and the GUI in the PC version is written in OpenGL and is really just a display. There is no real interaction with a mouse at present.

Hah, should've guessed from the 3D cube >_<

So you've played with one of the OpenGL example cubes too then?

 

[megaminxwin]

Kewl.

 

[xXzaKerXx]

Hey, welcome! just curious to know, what do you do for a living, if you're able to invent all those awesome robots?

 

[hyunchoi98]

Cool!
I subed to your channel too!

 

[r_517]

i learned how to control a robot to solve various problems this year still dont know how to use it solve the cube keep going

 

[Cride5]

Hi IAssemble, impressive engineering skills! We were doing exactly this kind of stuff in our Computer Science course (building a lego shopping robot). Just looking at the finished product its hard to appreciate all the technical challenges involved and I'm sure there were many!

The solver for this robot takes the mechanical requirements into account when determining which solution is "best". In fact often a 23 or 24 move solution is found which results in a shorter solve time than a 20 or 21 move solution!

Very interesting. The good thing about doing this with a robot, is that the metrics used to measure the time costs of any solution are easy to define precisely. With human solvers similar time costs exist, but they are difficult to measure exactly and vary from solver to solver.

Generally the following holds:
* Quarter turns on easy to access faces such as U and R are quickest, while faces such as F and B are slowest.
* Half turns are again slower, but will be faster for L2/R2 than U2/D2 because double flicks are required, which will again be faster than F2/B2 because a re-grip and double flick is usually required.
* The cost of a move also depends on preceding moves, so for example, adjacent layer twists in the opposite direction flow very well almost as one move (eg. R U' or R' F). Sequences like this would have a slightly lower time cost.
* For faces turned by wrist rotation (L/R) there is a cost associated with range of rotation, so for example an algorithm which has a maximum range of rotation of just 90° in the R-layer (eg. R U R' U') is much easier to execute than one which covers say a range of 360° (eg R2 U' R' U' R U R U R U' R). This is because a higher range of rotation means re-grips are more likely to be required, and without re-grips it is harder to turn adjacent layers.

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.

 

[Kirjava]

Interesting. Actually the first phase would eventually find all possible solutions pretty much in order of optimality so actually tries the optimal solution to the first phase first!

Are the tables for the second phase optimal, too?

I understand that fewest moves isn't always fastest. And also I understand that speedcubers choose methods that also help speed up the visual pattern recognition required to determine which sequences to apply too?

Yes, but this doesn't have any bearing on what makes one algorithm 'faster' than another, it's a recognition issue that robots don't have to deal with . This quote made me specifically think of OLL and I realised that not just ignoring pieces would be useful, but ignoring certain aspects of pieces would be useful, too (like orientation or permutation).

Actually the fewest moves is not necessarily the fastest for a robot either...

Consider my four-handed "Yellow Cube Machine" - L R F B is faster than L F R because in the first sequence L and R can be done simultaneously as can F and B so it is about 2/3 of the time! Also, perhaps counterintuitively, L2 F2 R2 is much faster than L F R because the arms must be returned to the upright position to allow the adjacent faces to turn so the second sequence needs the arms to be moved away, re-positioned to vertical and then closed again between each move. The first of these sequences is almost twice as fast as the second. The solver for this robot takes the mechanical requirements into account when determining which solution is "best". In fact often a 23 or 24 move solution is found which results in a shorter solve time than a 20 or 21 move solution!

I never considered that robots would be choosing speed-optimised solutions over movecount-optimal ones based on their restrictions. Badass.

So you've played with one of the OpenGL example cubes too then?

Nah, but I assumed DirectX would be way too much work for something like that and what else would you use? It is a neat display ^_^


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.

 

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

Do you mean a final edge flip without worrying about preserving the corners on the LL? I only ask because my generic software algorithm doesn't map directly on to the regular human methods...

I don't have an easy way (at the moment) to generate good (optimal) sequences other than the patterns that the current solver uses. I'll se what I can do this evening and send a reply later.

How many moves do you take for this?

 

[IAssemble]

Hey, welcome! just curious to know, what do you do for a living, if you're able to invent all those awesome robots?

I recently posted some blogs on the ARM web site that may help answer this The first was: http://blogs.arm.com/arm-events/arm-powered-nokia-n95lego-rubiks-speedcuber-creation-video

 

[IAssemble]

Cool!
I subed to your channel too!

Thanks - you might want to keep an eye on the http://www.youtube.com/user/ARMflix channel too - that's where my next video is likely to be posted

 

[IAssemble]

i learned how to control a robot to solve various problems this year still dont know how to use it solve the cube keep going

Great! Perhaps you could work on this and challenge Yellow Cube Machine or even the awesome CubeStormer in the future!

 

[IAssemble]

Hi IAssemble, impressive engineering skills! We were doing exactly this kind of stuff in our Computer Science course (building a lego shopping robot). Just looking at the finished product its hard to appreciate all the technical challenges involved and I'm sure there were many!

The solver for this robot takes the mechanical requirements into account when determining which solution is "best". In fact often a 23 or 24 move solution is found which results in a shorter solve time than a 20 or 21 move solution!

Very interesting. The good thing about doing this with a robot, is that the metrics used to measure the time costs of any solution are easy to define precisely. With human solvers similar time costs exist, but they are difficult to measure exactly and vary from solver to solver.

Generally the following holds:
* Quarter turns on easy to access faces such as U and R are quickest, while faces such as F and B are slowest.
* Half turns are again slower, but will be faster for L2/R2 than U2/D2 because double flicks are required, which will again be faster than F2/B2 because a re-grip and double flick is usually required.
* The cost of a move also depends on preceding moves, so for example, adjacent layer twists in the opposite direction flow very well almost as one move (eg. R U' or R' F). Sequences like this would have a slightly lower time cost.
* For faces turned by wrist rotation (L/R) there is a cost associated with range of rotation, so for example an algorithm which has a maximum range of rotation of just 90° in the R-layer (eg. R U R' U') is much easier to execute than one which covers say a range of 360° (eg R2 U' R' U' R U R U R U' R). This is because a higher range of rotation means re-grips are more likely to be required, and without re-grips it is harder to turn adjacent layers.

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.

Thanks - yes there were many challenges along the way!

I appreciate what you're saying about having sophisticated metrics to help order solutions to help individuals pick the best ones for them.

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?

 

[IAssemble]

Interesting. Actually the first phase would eventually find all possible solutions pretty much in order of optimality so actually tries the optimal solution to the first phase first!

Are the tables for the second phase optimal, too?

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

So you've played with one of the OpenGL example cubes too then?

Nah, but I assumed DirectX would be way too much work for something like that and what else would you use? It is a neat display ^_^

Thanks

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?

 

[IAssemble]

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?

 

[Kirjava]

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.

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.

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.