Gripper: Rubik's Cube Algorithm Analyzer

[badmephisto]

For the past few days I have been working on a program that would analyze algorithms and output an expected time of execution. This idea is of course by no means unique, but as far as I am aware, even though there have been some attempts at this, noone has actually made or published anyhting useful.

The program I made is called gripper. It takes as input an algorithm and outputs expected time of execution (which of course is relative per cuber, but all that matters are the relative ratios of the times, not the actual numbers). It does this by trying out different grips on the cube, and following through the notation recursively to find best ways to essentially grip the cube such that an algorithm is executed quickly and efficiently.

I am currently working fulltime, parttime, and taking courses at the university, so my time is extremely limited and I will not have time to make any significant changes to the program. So I decided to just release the program as is, in its partly-functional form, and I will also make the code available on SVN. So if you know Python, you are very welcome to get the code, change it up, and extend its features. I know many of you here are programmers and I hope you agree that this kind of program would be extremely useful for speedcubing, so I hope we can get together and make something work. The idea of dumping Opticubes output into this program and having the computer do analysis for us is the optimal goal here.

The code is very well commented because I love commenting my code. It helps me stay organized. Its also very short I would say, and very easy to understand. It is not fastest as you will notice, but my main concern was functionality, not time bounds. At least for now.

Here is what I have so far: (So in particular note that I can already analyze opticubes output!)
- I can analyze any algorithm containing standard notation RLFBUD. I also support rlfbud middle layer turns but I assume that the cost of executing r is the same as that of executing R and so on. This seems like a pretty good approximation to me so far.

Things not supported:
- Cube rotation xyz
- Middle slices MSE (current implementation is sort of a hack)

Here are 3 things to still be implemented that I have thought of:
- add support for xyz rotations. This requires some manual labor as you have to define the transformation of notation for each rotation x,x2,x', y, y2, y', z, z2, z'

- it is clear that a cube rotation can dramatically decreasse time of execution by converting B's to R' and stuff like that. We need a program that takes in algorithm like (A1 A2 A3 .... An) and outputs an equivalent algorithm with cube rotations in between notation. The idea is that we will generate all possible cube rotations that can be applied to speed up the algorithm, and then analyze them all and have the program filter out non-beneficial rotations. So example of output would be in our case (x B1 B2 B3 B4 B5 y' z B6 ... Bn). This is done for the obvious reason that alg may be flagged by the program as slow, but if you enter the right rotation somewhere, it may suddenly be the best alg. Note that there may be a LOT of these variations. Exponentially many in fact. There may have to be some heuristics put in that prune the search space, or maybe we only want to generate a small subset of variations that "make sense", but someone would have to come up with a mathematical formula for that. For example if next letter is B, then maybe it makes most sense to have a cube rotation y, because then that B becomes R, etc.

- there also has to be code that will take the alg with cube rotations and postprocess it in the sense that we may have created some double layer turns there which are much faster than cube rotation and a move. Take as an example a case where somewhere in the alg you have "L x". Well this is nothing else than just r... but clearly r is MUCH faster than L x.

I hope that in this thread we can lead a discussion on both implementation details and conceptual ideas about the program and its future.

SVN Info:
Here is url and user and pass for a shared account to the repository if you just want to check it out. If you decide that you would like to try and do some development, you can msg me here, or through private message, or email, and i will create you an account
url: svn://badmephisto.mine.nu/gripper
user: others
pass: gripper

Download Info:
Source code (Python 2.4): http://badmephisto.mine.nu/gripper_release/src.zip
Binaries (exe): http://badmephisto.mine.nu/gripper_release/bin.zip

Wiki page for the project: http://badmephisto.mine.nu/gripperwiki/

Example usage:
gripper.exe R U R' U' R' F R2 U' R' U' R U R' F'
("G0 R U R' U' G1 R' F R2 U' R' U' R G1 U R' F' ", 1.9200000000000004)
Means hold cube in Grip 0, execute RUR'U' then regrip to 1, execute ... See Wiki for description of grips. Basically Grip 0 means right hand thumb is on D, Grip 1 is thumb on F, and Grip 2 is thumb on U. Left hand always just holds the cube while right hand does the work.

(tperm.txt is a file containing all algorithms from opticubes for the T permutation, so about 100 algs. Following prints top 5 best algs)
gripper_batch.exe tperm.txt 5
("R U R' U' R' F R2 U' R' U' R U R' F'\n", "G0 R U R' U' G1 R' F R2 U' R' U' R G1 U R' F' ", '1.92')
("F R U' R' U R U R2 F' R U R U' R'\n", "G0 F R U' R' G1 U R G1 U G2 R2 F' R U R U' R' ", '2.20')
("R2 U' R2 D B2 L2 U L2 D' B2 U\n", "G0 R2 U' R2 D B2 G1 ! G0 L2 U L2 D' B2 U ", '2.37')
("R2 U' R2 D B2 L2 U L2 D' B2 U\n", "G0 R2 U' R2 D B2 G1 ! G0 L2 U L2 D' B2 U ", '2.37')
("D' R2 U R2 U' R2 F2 U' F2 D R2\n", "G1 D' G0 R2 G1 U G0 R2 U' R2 F2 U' F2 D R2 ", '2.41')
First entry is the original algorithm as appears in the file
Second entry is the suggested execution of the algorithm. The Exclamation marks (!) mean that you should switch hands... i.e. execute the rest with your left hand, right hand holds the cube steady.
Third entry is the cost
(Also note that the algorithm that we all use as t-perm indeed comes up all the way at the top as the best algorithm. So gripper agrees with us... phew )

 

[watermelon]

I'm glad to see someone else has worked on this idea too! Unfortunately I'm not a Python coder, so I probably won't be able to help... Would you happen to know Java?

Also, in case you didn't know, I'm the guy behind opticubes.com, so if you need any help, just let me know.

 

[badmephisto]

I'm glad to see someone else has worked on this idea too! Unfortunately I'm not a Python coder, so I probably won't be able to help... Would you happen to know Java?

Also, in case you didn't know, I'm the guy behind opticubes.com, so if you need any help, just let me know.

hey! Yes I remember the thread you posted, but I forgot your username and the topic title so I was unable to search for it again. In fact that thread was what inspired me to make this program in the first place. I thought that you stopped working on it.

anyway, a program like this must be made by someone, and so I just took the initiative. By the way python is incredibly easy to learn I don't know... have you made any progress? It seems to me like the analysis process here is pretty modular so things can also be written in different languages. What I mean by that is... given an algorithm, a C program can be written to insert cube rotations into it and dump all resulting variations into a file, which can then be read by a python program and be analyzed, etc.
And yes I do know Java.
Mainly though I just want to get a coding repository going, and I am willing to host it. Many of us here are programmers and it just seems to me like we could write some very nice open source apps together that would help push speedcubing forward.

lastly btw I appreciate the work you are doing on opticubes, i send newbies to your f2l page to check solutions to cases

 

[watermelon]

Your approach is certainly more efficient than mine. Given your code, however, I can probably just use what's written there to help you add functionality, if you're interested. I already have a Java program that can do rotations to an algorithm (i.e. x U -> F), so if you'd like me to port that to Python, it shouldn't be any trouble.

Also, thanks for recommending people to my site. I'll definitely try to get other algorithm sets like OLL, COLL, CLL, ELL, etc. on there over the summer, and then I might try to expand the F2L section with tricks like using empty slots.

 

[badmephisto]

Your approach is certainly more efficient than mine. Given your code, however, I can probably just use what's written there to help you add functionality, if you're interested. I already have a Java program that can do rotations to an algorithm (i.e. x U -> F), so if you'd like me to port that to Python, it shouldn't be any trouble.

Also, thanks for recommending people to my site. I'll definitely try to get other algorithm sets like OLL, COLL, CLL, ELL, etc. on there over the summer, and then I might try to expand the F2L section with tricks like using empty slots.

I would very much like you to port it to python if you already have it. I need transformations for all rotations... so for example:

method applyY(alg)
INPUT: alg is a string such as for example any of "R", "r'", "x", "M"
OUTPUT: returns the new string after rotation by Y, so in this case respectively it is "F", "f'", "x", "S'"
(if you dont have it for M/S/E's thats fine just give me what you have, we can fill in gaps later)
I've set up an svn account for you ill PM you details.

 

[blgentry]

^ I have a python function I've named "rotate_cube_alg", that does almost exactly what you're asking for. I takes two arguments: The cube alg (as a list) to be rotated, and the direction to rotate it. For example:

    scramble1 = "R U R' U' R' F R2 U' R' U' R U R' F'"
 
    print "The string is: " + scramble1
    
    dir ="x'"
    print "string, rotated by " + dir + ":"
    scr1list = scramble1.split()
    rots = rotate_cube_alg(scr1list, dir)
    print string.join(rots)

Produces the following output:

-------
The string is: R U R' U' R' F R2 U' R' U' R U R' F'

string, rotated by x':
R F R' F' R' D R2 F' R' F' R F R' D'
-------

It supports rotating to any of the 9 directions, but it's currently limited to single face turns, and does not understand embedded cube rotations. IE: It will process this just fine:

F U R U' R' F'

...but it will choke on:

L r' B d

...and also chokes on:

F R B y x2 R U

Oh, and of course does not understand slices either. I could fairly easily extend it to support embedded cube rotations. I could even extend it to understand double layer turns, but that will double the size of the internal dictionary it uses to process these. That won't make it slow or anything, it's just a bunch of typing. EDIT: Doing the double layer turns is easy, it's just typing as I said. Doing the embedded rotations is much more difficult than I thought, and will require analysis.

Brian.

 

[brunson]

Coincidentally, I just sent an email to Brian regarding this very algorithm...

rotations = { "x":  "LRUDBF",
              "x2": "LRBFDU",
              "x'": "LRDUFB",
              "y":  "BFLRUD",
              "y2": "RLBFUD",
              "y'": "FBRLUD",
              "z":  "UDFBRL",
              "z2": "RLFBDU",
              "z'": "DUFBLR" }


def cuberotation( r ):
    from string import maketrans
    global rotations
    standard = "LRFBUD"
    return maketrans( standard + standard.lower(), rotations[r] + rotations[r].lower() )


def rotatealgorithm( alg, *rs ):
    for r in rs:
        alg = alg.translate( cuberotation( r ) )
    return alg

Usage:

alg = "F' U' F R2 d B' U B u' B D' R2 u2 L F2 r' F' R f R' F' R F' L'"
rotatealgorithm( alg, "x" )
>>> U' B' U R2 f D' B D b' D F' R2 b2 L U2 r' U' R u R' U' R U' L'
rotatealgorithm( alg, "y'" )
>>> R' U' R B2 d L' U L u' L D' B2 u2 F R2 b' R' B r B' R' B R' F'
rotatealgorithm( alg, "z2" )
>>> F' D' F L2 u B' D B d' B U' L2 d2 R F2 l' F' L f L' F' L F' R'

### The rotate algorithm can take multiple rotations...
print rotatealgorithm( alg, "x", "y" )
>>> U' R' U F2 l D' R D r' D L' F2 r2 B U2 f' U' F u F' U' F U' B'
print rotatealgorithm( alg, "x", "y", "z" )
>>> R' D' R F2 u L' D L d' L U' F2 d2 B R2 f' R' F r F' R' F R' B'

MSE's can be added pretty easily, but you'd have to hand code them along with the lowercases rather than translating the uppers.

So, you'd change standard to "LRFBUDlrfbudMSE", then change rotations['x'] to "LRUDBFlrudbfMSE" (I think i got them right, but you get the point).

 

[badmephisto]

thanks blgentry and brunson! I really appreciate your input.
brunson, that method is absolutely genius and it really shows the strength of python. I actually did not know that these methods existed so I probably would have ended up basically re-implementing them And yes i do get the point I don't like that you are performing string concatenation every time inside that method... it surely slows it down a lot, but these small implementation things i will figure out. i will definitely use this, thanks.

i am now wondering about the cube rotations though... im not exactly sure how to go about rotating those, hmm...
i get an algorithm like R U x B L' and I try to insert random beneficial rotations. I guess one way to do it is to first "flatten" an algorithm and remove all cube rotations altogether, so in a sense, do inverse transform, and then proceed to try and put in rotations from scratch? That may be the easiest way to go about doing this.

My current plan of attack for inserting beneficial rotations:
- there are basically 3 ways to make a move like B more convenient:
1. You do x U
2. You do y R
3. You do f and then the rest of the algorithm must have transformation applied to it, like z in this case.

so the 3 things at each step are: convert to U, convert to R, or convert to double layer turn.

pimp(A):
if len(A)=0 return ""
If A[0] is not R/R'/R2 or U/U'/U2:
       make it R/R'/R2 by inserting rotation at this place and yield that appended to pimp(transformed(A[1:]))
       make it U/U'/U2 by inserting rotation at this place and yield that appended to pimp(transformed(A[1:]))
       make it double layer turn and yield that appended to pimp(transformed(A[1:]))
yield this A[0] appended to pimp(A[1:]) //leave it alone

I think that would result in all possible modifications of the alg that really make at least some sense. I hope thats right anyway

edit: I thought more about this. I should want to try and transform to double layers also if its an R/R'/R2 U/U'/U2 move. No if statement there should be included.

 

[blgentry]

Brunson's code makes me weep in shame and envy. His Python Kung-Fu is much stronger than mine. I must run and hide! Seriously, it's quite elegant.

thanks blgentry and brunson! I really appreciate
i am now wondering about the cube rotations though... im not exactly sure how to go about rotating those, hmm...
a

I spent around an hour adding cube rotations to my alg rotator today and I have it around 90% complete. It's a subtle problem that will make you scratch your head, or beat it against a wall. I'll post more later when I have it complete and tested. You'd think cube coding would be easy. You'd be wrong.

Brian.

 

[masterofthebass]

Let me just say this:


Python kicks major arse! I love everything about it, and I hate when I need to code C++ or Java.. All the syntax gives me a headache.

 

[brunson]

Once again, I read my email before reading the forums and Brian asked about "flattening" an algorithm. Building upon the original code, I came up with this:

def removerotations( alg ):
    global rotations
    rots = []
    newalg = []
    for turn in alg.split():
        if turn in rotations.keys():
            rots.append( turn )
        else:
            newalg.append( rotatealgorithm( turn, *rots ) )

    return " ".join( newalg )

Mephisto,

Now that I'm calling cuberotation() multiple times per face turn, it would definitely be a good time to get those string concatenations out of there. I actually just did it for expediency in the first posting since you asked for the double slice turns which I hadn't accounted for in my own code since all my algorithms went through optiqtm which doesn't do them.

Here's the whole set of functions in one go, apparently Gmail didn't do a good job of preserving the formatting when I emailed it to Brian. http://pastebin.com/m7a00b97

That was easy, *inserting* the rotations is much more challenging. While thinking about this before one of my thoughts was to keep a list of triggers, like R U R' U', and then all it's different incarnations, i.e.

z: D R D' R'
z': U L U' L'
x': R F R' F'
y': B U B' U'
y: F U F' U'
x2: R D R' D'
x: R B R' B'
y2: L U L' U'
z2: L D L' D' (wow, that rotation function is useful... )

then assign weights to the algorithms performed as is, or as a sum of the cost of a cube rotation plus the rotated algorithm when you identify them in the flattened representation.

This program of yours sounds *awesome*, I'm anxious to see how it turns out.

 

[brunson]

Marshall,

What did you use to find all those algorithms on your site? It's a ridiculous number of algs.

BassMaster,

Yes, Python rulez. I've been programming professionally (definition 1, not 12 or 13) for over 20 years and I'm fluent in everything from C to Java to awk, sed and perl, but Python is the language I truly love. I'm very lucky to have landed a great job at a great company where I lead a team of developers building engineering tools for running a satellite communications network, primarily in Python.

 

[genwin]

i really like to explore programming... i know a bit of C++... how can i learn python effectively(buying a book is not an option yet)... maybe i can contribute "something" useful here someday...

 

[badmephisto]

For now I think I will just concentrate on analyzing opticubes-like output... One with no rotations/double layers, etc., just play simple moves. Therefore all rotations that I put in were created by my algorithm, and I need not worry about getting input with cube rotations in it. But the "flattening" part may come in handy later on.

1. Get alg from opticubes
2. Go through it, and branch at most 4 times at each place:
- make this move R-like
- make this move U-like
- make this double layer move
- leave it alone
3. run mincost() function on each alg to determine best 20, that are then printed for human analysis.

I did some calculations today that made me feel uneasy though... I branch 4 times each time, so my running time in terms of size of input in letters is
4^n...

for 14 move algorithm, this is something like 250 million algs outputted
for 16 move algorithm its 4.2 billion
for 10 move its 1 million.

these numbers concern me... even for 1 million algs I have no clue how fast it will run. It is clear that I will need to make sure that my methods are pinnacles of optimality at every point. I may also end up having to port the app to C for speed If it weren't for all the code that keeps track of the solution path, the whole thing is really just one relatively small recursive method. The C program could give me best algs without telling me how to grip the cube, but then I can just take the first 100 best and run that on the slow python code that will tell me easily how to get to them.

On the other hand the alg variations that I generate in pimp() will have to be passed on to that C program somehow. Writing them all into a file so that C program can read them is not practical due to the size... and re-executing the C code from within python and doing it one at a time may produce a large overhead starting the C program, and be inefficient that way.

I think Ill try to stick with python for now and optimize it, but I have no idea how it really compares to C in recursion.

brunson:
1. your job sounds awesome
2. why did you say that inserting cube rotations would be hard? It looks pretty easy to me, so now I am concerned.

edit: oh and i just realized, I am working with arrays not strings. So I may need to re-implement the transition stuff after all... Converting between strings and arrays all the time could prove inefficient. I could also maybe try just working with strings instead of arrays, but that may prove a pain because notation does not have fixed length... R is 1, R' is 2 characters... sigh!

 

[brunson]

genwin,

Python is free and I don't know of any common platform it doesn't run on, download it from python.org. There are many great tutorials out there for python, the two I usually recommend are the one written by Python's benevolent dictator for life and creator of the language, Guido van Rossum, found here: http://docs.python.org/tut/ and an online book called "Dive into Python", found here: http://diveintopython.org.

Once you have understood the basics two great resources are the python tutor mailing list, [email protected], where lots of great people will collaborate to help you program effectively and the python help list, [email protected], where a small group of python experts, including me, try to help people through problems understanding the language and funding solutions to their problems.

Mephisto,

I haven't thought about it too long and hard, but the number of different algorithms generated by inserting cube rotations makes the problem get geometrically larger. I guess "hard" was not the right term, "large" would have been a better choice.

I'm going to give my idea a little more time to simmer "on the back burner" and see if I can come up with some more concrete implementation ideas, then see about implementing them in your app. I downloaded the source from svn last night.

 

[genwin]

thanks a lot...i was not that good at C++, but i'll give python a try...

 

[badmephisto]

I've done about 2 hours of coding today, and it went very well! I now support cube rotations in mincost() method. All that has to be done now is my method that generates variations. That is about 1/3 done. I will finish implementing that and I will be fully set! I calculated that to fully analyze a 14move algorithm, at least on this pc will take approximately a day. The T permutation has 70 variations alone in opticubes. So the whole PLL will be done in about 2 months? We will see
I have a much faster PC at home and also my slave old crap computer that i can get crunching on cube stuff instead of protein folding!

 

[Johannes91]

I calculated that to fully analyze a 14move algorithm, at least on this pc will take approximately a day.

Just like calculating the Nth fibonacci number takes 2^N steps. Have you tried memoization?

 

[badmephisto]

I calculated that to fully analyze a 14move algorithm, at least on this pc will take approximately a day.

Just like calculating the Nth fibonacci number takes 2^N steps. Have you tried memoization?

I havent yet looked into optimizing the code that much, but i may be able to implement some form of memoization. I go over notation one by one in the algorithm, and each notation can be about 3moves*6sides + 3rotations*3directions + 3middleslices (MSE)*3moves = 36 things.
So I could memoize on very very short algs, but only those which are of length 2 or possibly 3 notation parts. Still, may come in handy. For now i was concerned only with correctness not with speed, but that will become important very soon.

edit: oh and its even worse, because at each stage i keep track of whether or not the cube is held with left/right hand, and also i keep track of the grip which can be 3 things. so suddenly instead of 36 we have 36*2*3 = 216 possible "base cases". So this is not looking great.

 

[badmephisto]

dang! sorry for double post, but i wanted to post an update , i am so excited! The algorithm generation now works! I did some preliminary testing with it and it returned some very clever and pretty modifications to already known algorithms that really looked very promising... it managed to use double layer turns in beautiful ways that eliminated all kinds of ugly turns in ways that a human would never be able to conceive of, at least from what i've seen.

Biggest problem right now is that the algorithm currently assumes that double layer turns are just as fast as their corresponding single turns, like u is same cost as U, etc. The program ends up abusing this fact and it recommends a lot of algs that have double layer turns in them, and they are sometimes pretty akward to execute, because to execute a u for example, you have to grip with your left hand slightly lower because you need the middle slice to be movable.

So I will have to implement rludfb turns first and make them cost a little more, and of course there will have to be some major tweaking with the costs that i assign to each turn.