# Fingertrick Analyzer



## watermelon (May 3, 2008)

I recently made a program that, given an algorithm, will analyze it to find the best execution (this is determined by the number of regrips, and which fingers have been specified to turn which sides).

In this program, hand positions are defined as follows: "neutral" position (number 0) has the right thumb on FUR, right index on BUR, and right ring on DBR, the left thumb on FUL, left index on BUL, and left ring on DBL. To get to right hand position n, do R n times from position 0 and see where your right thumb/index/ring end up. The same instructions follow for left hand, but you do L' n times instead.

For example, here is the output for the common T-permutation with the following options: only wrists can turn R/L, thumbs and ring fingers cannot turn U.

Algorithm: C R U R' U' R' F R2 U' R' U' R U R' F'
Execution:
LH = 0, RH = 3
R (right wrist) U (right index) R' (right wrist) U' (left index) R' (right wrist) (RH = 3) F (right index) R2 (right wrist) U' (left index) R' (right wrist) U' (left index) R (right wrist) (RH = 0) U (right index) R' (right wrist) F' (right thumb) 
Hand Regrips: 2

Algorithm: C R U R' U' R' F R2 U' R' U' R U R' F'
Execution:
LH = 0, RH = 3
R (right wrist) U (right index) R' (right wrist) U' (left index) R' (right wrist) (LH = 3) F (left thumb) R2 (right wrist) (LH = 0) U' (left index) R' (right wrist) U' (left index) R (right wrist) U (right index) R' (right wrist) F' (right thumb) 
Hand Regrips: 2

Algorithm: C R U R' U' R' F R2 U' R' U' R U R' F'
Execution:
LH = 0, RH = 3
R (right wrist) U (right index) R' (right wrist) U' (left index) R' (right wrist) (LH = 1) F (left ring) R2 (right wrist) (LH = 0) U' (left index) R' (right wrist) U' (left index) R (right wrist) U (right index) R' (right wrist) F' (right thumb) 
Hand Regrips: 2

You will notice that I put a C (change hand position) at the beginning of the algorithm. Whenever the program encounters a C in the algorithm, it will try out all possible hand positions at that point to determine which is the best one. You can put Cs anywhere in the algorithm, but their main uses should be at the beginning and at rotations.

As you can see, although the first option is probably the fastest, the other two options require the same number of regrips. In this case using your left thumb or ring finger for F isn't practical, but in some OLLs or other algorithms it is the best option.

As another example, here is the output for the clockwise A-permutation:

Algorithm: C R' U R' D2 R U' R' D2 R2
Execution:
LH = 0, RH = 1
R' (right wrist) U (right index) R' (right wrist) D2 (left ring) R (right wrist) U' (left index) R' (right wrist) D2 (left ring) R2 (right wrist) 
Hand Regrips: 0

It should also be noted that the program assumes double triggers for double moves, so D2 (left ring) can be performed as (left ring)*2 or (left ring) (left middle).

I can add in wrist turning for sides other than R/L if needed, but from the regrip-perspective, it is probably not the best option.

Once the program has been cleaned up a bit and given a few more options, I'll post it on here. If anyone thinks this will be useful or has suggestions, please let me know.


----------



## badmephisto (May 3, 2008)

hmmmm i wonder how many complications you have and have not considered. Its not exactly clear from your description, but of course, you made sure that you cant, for example, do 4 R turns easily, because thats of course impossible and would need regrip.

Also, once you have an analyzer for this, you can try going here
http://opticubes.com/pll.php
and plugging all the output into your analyzer to see what is the best PLL for each diagram. You should probably have your program try and do y/x/z rotations as well, because even though they give you a regrip, the next 10 moves may be simplified greatly. (and for that matter possibly even the slice move M)

You could also give penalty for example for switching from right hand to left hand turns, because you have to grip the cube with one of the hands and start turning with the other. For example, executing R L R L would suck. Of course thats just like M2 but im trying to make an example.

Anyway gl, sounds interesting


----------



## watermelon (May 3, 2008)

Thanks for your advice!



badmephisto said:


> you made sure that you cant, for example, do 4 R turns easily, because thats of course impossible and would need regrip


I'm still in the process of adding this in, but it hasn't been a problem yet (of course if you had something like R U R B R D R F, my program would not need any regrips, but you would need some in real life).



badmephisto said:


> You should probably have your program try and do y/x/z rotations as well, because even though they give you a regrip, the next 10 moves may be simplified greatly. (and for that matter possibly even the slice move M)


The user can put rotations into the alg, and they will be ignored. However, if they put a C next to the rotation, the program will find the best way to regrip during this rotation as to make the rest of the algorithm easiest. I will consider adding slice moves as a feature, but if the user inputs something like E, I will assume they mean E (one movement) instead of d D'.



badmephisto said:


> You could also give penalty for example for switching from right hand to left hand turns, because you have to grip the cube with one of the hands and start turning with the other.


I think that might depend more on the cuber, as some people might have to completely regrip to do something like R L while others might just need a quick shift of their fingers. Maybe I'll create an option to specify if switching between R and L counts as a regrip or not.


----------



## MistArts (May 3, 2008)

Is using a right ring for D faster than wrist?


----------



## watermelon (May 3, 2008)

If the right ring finger is already in position, it doesn't require any regripping to do D'. Doing any D move with wrists always requires 2 regrips (one to do the move, one to return to the rest of the algorithm).


----------



## Lucas Garron (May 3, 2008)

I'm very interested.

In particular, I absolutely want to run this on 2-gen/3-gen MGLS algs (and find least-regrip algs).

Also, can you assign different weights to longer regrips, or take into account this + # of moves? I also really want to use this on lists of algs.


----------



## watermelon (May 3, 2008)

badmephisto said:


> Its not exactly clear from your description, but of course, you made sure that you cant, for example, do 4 R turns easily, because thats of course impossible and would need regrip.


After thinking about this some more, I do not believe it's necessary to implement this feature.
-This case will come up only in very rare situations, and I'm not sure why you would want to use such an algorithm anyway.
-How do you decide where to regrip the cube when you regrip?
-If I tilt the cube a bit, I can easily do R4 from the neutral position.


----------



## Stefan (May 3, 2008)

Ah, good, I already suspected someone would make something like this soon. Does it also rewrite the algorithms, or only finds out how to execute them best the way they're written? The latter would be cool, so we could enter pure UDLRFB algorithms and the computer would translate that possibly with double layer turns or cube rotations to make execution fast. Like what we've done manually for years. One suggestion already: When you print "regrip", also say which hand and how.


----------



## watermelon (May 3, 2008)

Lucas Garron said:


> I'm very interested.
> 
> In particular, I absolutely want to run this on 2-gen/3-gen MGLS algs (and find least-regrip algs).
> 
> Also, can you assign different weights to longer regrips, or take into account this + # of moves? I also really want to use this on lists of algs.


Let me know if I understand you correctly. As I see it, there are only two "lengths" of regrips: one move away or two (i.e. neutral to position 2). I guess you would count the latter as 2 regrips, but keep the former weighted at 1?

Also, since only one algorithm is being tested at a time, algorithm length is not a factor. However, if you think of a nice formula that incorporates number of regrips and length, I'll add in support for lists of algs .


----------



## watermelon (May 3, 2008)

StefanPochmann said:


> Ah, good, I already suspected someone would make something like this soon. Does it also rewrite the algorithms, or only finds out how to execute them best the way they're written? The latter would be cool, so we could enter pure UDLRFB algorithms and the computer would translate that possibly with double layer turns or cube rotations to make execution fast. Like what we've done manually for years. One suggestion already: When you print "regrip", also say which hand and how.


Stefan, your diploma thesis is the very reason I started this program . As of now, the program only tests the algorithm as it is given. How do you suggest going about trying to find the fastest execution? My only idea is brute-force; try every move as its corresponding double layer turn, and try out all cube rotations after every move in the algorithm. This option would considerably increase runtime though.

Edit: Regrip info added, check the first post


----------



## Paiev (May 3, 2008)

watermelon said:


> StefanPochmann said:
> 
> 
> > Ah, good, I already suspected someone would make something like this soon. Does it also rewrite the algorithms, or only finds out how to execute them best the way they're written? The latter would be cool, so we could enter pure UDLRFB algorithms and the computer would translate that possibly with double layer turns or cube rotations to make execution fast. Like what we've done manually for years. One suggestion already: When you print "regrip", also say which hand and how.
> ...



There are 24 ways of holding the cube. There are also 2 ways of executing each turn. A pure brute force, then, would have O(26^n) runtime. This is not feasible. You could cut this down quite a bit, though. If you could determine a score for an algorithm, you could combine that with a DFS and throw out all paths with a score greater than the lowest score found so far. You would want to estimate scores, though, by adding on some value (lowest score for a turn * number of remaining turns would be a simple implementation) to the current score, to account for remaining turns (since a path with a terrible start might not be thrown out because it is still under the lowest score so far found).

Disclaimer: I'm still in high school. There is probably a more efficient way to do the above.

Edit: Checking for double layer turns is O(2^n), which isn't that bad.


----------



## watermelon (May 3, 2008)

I don't think it is necessary to try out all possibilities, instead we should be looking at our goal. Most algs that have double layer turns or cube rotations use those to keep the majority of the moves as RU. It may be easier to try to optimize the alg for using specific faces rather than trying to apply double layer turns and rotations whenever possible.

Maybe a preliminary step would be to make a UDRLFB to urURxyz converter, and then analyze the starting alg, some of the intermediate algs, and the final alg and compare them for number of rotations/regrips.


----------



## mrbiggs (May 3, 2008)

Paiev said:


> A pure brute force, then, would have O(26^n) runtime.



Pure brute force isn't necessary, though. A good algorithm could prune the tree very easily.

Something to consider might be using algorithms from chess software. An average chess position has ~30 options for each move, so the numbers are similar. However, the pruning algorithm is good enough that modern chess engines on a good computer can reach about 20 ply in under a minute. This means that you could get an algorithm of up to 20 moves in under a minute, which AFAIK means you'll be fine unless you're looking for the superflip.

However, there are some problems with this approach:

1. (most important) chess software is just trying to reach a better position, not trying to reach a single position. the tree for the rubik's cube can't be pruned as much because you need to make sure that the moves you're making will result in an efficient path to the solved state. If you could come up with a quantitative measure of how close a cube is to being solved, or whether a certain position has better odds than another one of being closer to a solved state, this problem would be solved. None of that would be easy.

2. Adapting the software to the rubik's cube is itself nontrivial. Chess programs generally use memory very efficiently, especially the open-source ones which are generally older and had to use the small amount of memory they had more efficiently. So modifying the old software might be harder than changing around a few variables when you include the hash table implementations. (This is conjecture; I haven't looked at chess software code closely enough to tell you that this is true for a fact).

3. I kind of lied in the above, because chess software cuts down on a lot of moves because of transpositions. It only has to consider a given position once, even if you can get to it from several different move sequences. This is also true of a Rubik's cube, but unlike in chess, R U and U R are going to lead to different positions.

But it's an idea to consider.


----------



## Stefan (May 3, 2008)

watermelon said:


> Stefan, your diploma thesis is the very reason I started this program



Ha! I can't thank my professor enough for encouraging me to make it about cubing. Had I chosen one of his own thesis ideas, I don't know whether anybody I care about would read it...



> How do you suggest going about trying to find the fastest execution?



Each point of time/execution can be described by three parameters:
- How many moves have been applied already
- Orientation of the cube (24 possibilities)
- Positions of the hands (let's say 3*3=9 possibilities)

This then leads to nice dynamic programming. Define this:

*minLength[noparse][M][C][L][R][/noparse]* = minimum "length/time" for having executed the first M moves, ending up in cube orientation C, having the left hand in position L and the right hand in position R.

Initialize with minLength[noparse][0][any][0][0][/noparse] = 0. Fill the table one move at a time. The result is the minimum of minLength[noparse][all][any][any][any][/noparse], and the actual algorithm/execution can be reconstructed by going backwards. Or they could be stored alongside the lengths in a parallel table.

The table would have about 15*24*3*3=3240 cells and to compute one cell, you'd have to look at, I don't know, maybe a dozen other cells? I haven't really thought about the details. Anyway, this way you could really test *all* possible executions fairly quickly.


----------



## watermelon (May 3, 2008)

Sounds like a very interesting and effective approach. However, and this probably comes from a misunderstanding, won't this just find the best starting orientation? I don't see where the cube rotations mid-algorithm fit in.


----------



## Dene (May 4, 2008)

The first (and only) problem that I instantly notice is the original grip. I hold the cube like this:

Right thumb: FR
Right index: URB
Right middle: BR
Right ring: BDR
Right pinky: DBR

With my left hand effectively the mirror. Could it be made so that you could program your own initial hand grip?

EDIT: Also, what about OH?


----------



## watermelon (May 4, 2008)

I didn't feel the need to program in the middle/pinky fingers as I personally don't use them (except the middle during double triggers) during 2H speedsolving.

I have considered OH, and might work on it once this version is done.


----------



## Jai (May 4, 2008)

badmephisto said:


> Also, once you have an analyzer for this, you can try going here
> http://opticubes.com/pll.php


Er, that's his site.


----------



## Stefan (May 10, 2008)

I just noticed your executions in the initial message doesn't include the best one. This one comes closest:
R (right wrist) U (right index) R' (right wrist) U' (left index) R' (right wrist) (RH = 3) F ...

This one's better:
R (right wrist) U (right index) R' (right wrist) *U' (left index) (RH = 3)* R' (right wrist) F ...

The important part is that the right hand can regrip *while* the left hand pulls U', so that actually no time is wasted by the regrip at all.



watermelon said:


> Sounds like a very interesting and effective approach. However, and this probably comes from a misunderstanding, won't this just find the best starting orientation? I don't see where the cube rotations mid-algorithm fit in.



Here's an example with double layers, analyzing the OLL algorithm B U L U' L' B'. Let's look at the optimal path:

minLength[noparse][0][default][0][0][/noparse] = 0
minLength[noparse][1][by z][0][-1][/noparse] = 2 (regrip+f)
minLength[noparse][2][by z][0][0][/noparse] = 3 (R)
minLength[noparse][3][by z][0][0][/noparse] = 4 (U)
minLength[noparse][4][by z][0][-1][/noparse] = 5 (R')
minLength[noparse][5][by z][0][-1][/noparse] = 6 (U')
minLength[noparse][6][default][0][-1][/noparse] = 7 (f')

For cube rotations let's look at the optimal path of R U' R' B U B' (solving the back/right F2L pair):

minLength[noparse][0][default][0][0][/noparse] = 0
minLength[noparse][1][default][0][1][/noparse] = 1 (R)
minLength[noparse][2][default][0][1][/noparse] = 2 (U')
minLength[noparse][3][default][0][0][/noparse] = 3 (R')
minLength[noparse][4][by y][0][0][/noparse] = 5 (y+regrip+R)
minLength[noparse][5][by y][0][0][/noparse] = 6 (U)
minLength[noparse][6][by y][0][-1][/noparse] = 7 (R')

Here I counted y+regrip+R as taking two time units, maybe three or 2.5 would be more realistic.

I take back my earlier statement that each table cell might look at a dozen or so previous cells. Actually each minLength[noparse][M][C][L][R][/noparse] could come from any minLength[noparse][M-1][c][l][r][/noparse]. That's still a small number of cases for the computer, but not so easy for us to teach the computer. We'd need a transition function telling us how costly (timewise) it is to get from C/L/R to c/l/r and making a certain move. And that function is complex. I thought about splitting it into two steps, regrip/rotate and twist, but like I said above, you can regrip and twist at the same time.


----------



## qqwref (May 10, 2008)

I think in the final version you should organize the moves more in a table format, rather than on a line, because it's kind of hard to read. Perhaps you could have a column for notes like (RH=3), a column for the move you are doing, and then another column for the finger?

This is a really cool idea, and it will be really awesome to see when it's done. Keep going!


----------



## watermelon (May 10, 2008)

Thanks for the example Stefan, I'm starting to understand your logic more clearly now. Just to confirm, at each move, you'll try switching to any of the 24 cube orientations and you'll try both the move and its corresponding double layer turn? Then, for each of those possibilities, you'll have to determine which of the previous states requires the least number of time units to get to that position?

qqwref, the formatting shouldn't be too hard to add once the program is finished. I'll definitely be sure to add it in.


----------



## Stefan (May 11, 2008)

watermelon said:


> Just to confirm, at each move, you'll try switching to any of the 24 cube orientations and you'll try both the move and its corresponding double layer turn?



Yes, although I'm not sure the double layer turn needs to be tried explicitly. It might suffice to try the single layer turn if it's tried combined with any cube orientation anyway. I'm really not certain about that myself.



watermelon said:


> Then, for each of those possibilities, you'll have to determine which of the previous states requires the least number of time units to get to that position?



Not quite, at least not the way I presented it so far. Here's some pseudo code:


```
#--- Initialize table as "Everything takes infinite time".
for all M,C,L,R
  minLength[noparse][M][C][L][R][/noparse] = infinity

#--- The exception is that the start state takes zero time.
minLength[noparse][0][0][0][0][/noparse] = 0

#--- Compute how long it takes to reach each state.
for M = 1 .. AlgLength
  for all C,L,R
    for all c,l,r
      T = actualTurn( algorithm, M, c )
      minimize minLength[noparse][M][C][L][R][/noparse] by
        minLength[noparse][M-1][c][l][r][/noparse] + cost( c, l, r, T, C, L, R )
```

That's bottom-up dynamic programming. Alternatively it might be nicer to think top-down, using memoization, this might be closer to what you thought of:


```
function minLength ( M, C, L, R ) {

  #--- Start of the alg, answer is zero or infinity.
  if M == 0
    return 0 if C=L=R=0, otherwise infinity
    
  #--- If we haven't stored the result for this M/C/L/R yet, then compute it.
  if not stored[noparse][M][C][L][R][/noparse] {
    stored[noparse][M][C][L][R][/noparse] = infinity
    for all c,l,r
      T = actualTurn( algorithm, M, c )
      minimize stored[noparse][M][C][L][R][/noparse] by
        minLength( M-1, c, l, r ) + cost( c, l, r, T, C, L, R )
  }
  
  #--- Return the stored value.
  return stored[noparse][M][C][L][R][/noparse]
}
```
In both versions, this computes how fast you can get to each state, and you can use that data to construct actual executions by going "backwards" from M=algorithmLength. In case dynamic programming and memoization are new for you, it might be better to solve a simpler problem with them first, for example the longest common subsequence problem.


----------



## Stefan (May 11, 2008)

Btw, something else I realized today: When doing R2 U *R* U R' U' R' U' R' U R', I pull the bold R with my right ring finger so the orientation of the right hand pretty much stays the same and I can pull both U turns surrounding it with the right index finger and don't lose time for regripping.


----------



## watermelon (May 11, 2008)

StefanPochmann said:


> Btw, something else I realized today: When doing R2 U *R* U R' U' R' U' R' U R', I pull the bold R with my right ring finger


Don't you mean your left ring finger?


----------



## Stefan (May 11, 2008)

No I don't. But it's an interesting idea.


----------



## watermelon (May 11, 2008)

Ah, I see what you mean now.

Back to the program, I have one last question before I start to implement the latter of your solutions. Why would we initialize any initial position to infinity unless it's the starting cube orientation/hand position? Wouldn't we assume that you can start from any position without having to move there and use up valuable time?


----------



## Stefan (May 11, 2008)

watermelon said:


> Wouldn't we assume that you can start from any position without having to move there and use up valuable time?


But it *does* take time, doesn't it?


----------



## watermelon (May 11, 2008)

In that mindset, wouldn't you initialize the beginning cells to the time it takes to get to that orientation (most likely 1) rather than infinity? Again, this is probably a misunderstanding on my part.

Also, the reason for my previous response is when you're about to do an algorithm, you're not necessarily in the starting position.


----------



## Stefan (May 11, 2008)

You could do that, but it's also covered by the cost function when making the first turn. Um, let me document that one:

cost( c, l, r, T, C, L, R ) = The amount of time it takes to start at state (c,l,r), make turn T, and end up at state state (C,L,R).

Btw, I might make it sound easy, but I think this is quite a lot of work...


----------



## watermelon (May 11, 2008)

I see your reasoning now, though I might use my idea just because I'm not sure how to program in infinity.



StefanPochmann said:


> Btw, I might make it sound easy, but I think this is quite a lot of work...


Implementing this search will only require me to add two additional functions to my classes at the moment, and since you've explained the logic, I hope it won't be too hard to get working properly.


----------



## Stefan (May 11, 2008)

Try infinity = 999. Really just a large number that gets beaten by everything but not so large it overflows when something is added to it.

Or if you used float/double, you could actually use the value infinity (as those types usually have a representation for it and can calculate with it).


----------



## xXdaveXsuperstarXx (Jul 9, 2009)

I would apply algorithms from an optimal cube solver to this.


----------

