Online since 2002. Over 3300 puzzles, 2600 worldwide members, and 270,000 messages.

TwistyPuzzles.com Forum

It is currently Tue Jul 22, 2014 5:57 pm

All times are UTC - 5 hours



Post new topic Reply to topic  [ 7 posts ] 
Author Message
 Post subject: Efficiently using 3-cycles to solve orientationless pieces
PostPosted: Sat Mar 03, 2012 9:13 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
This post concerns random permutation statistics however that page is so dense I decided to write a simulator instead...

There are a lot of puzzles with at least one piece type easiest solved last with 3-cycles. The Starminx point pieces are a good example. Many of the big complex dodecahedron's in Gelatinbrain's program have more than one piece like this.

I find that when I'm trying to compete for fewest moves with other good solvers I almost always get CRUSHED when it comes to efficiently 3-cycling lots of pieces around. Julian, Elwyn, Dan (DKwan), and others have demonstrated much more skill and efficiency than me.

So Dan and I were discussing cycling strategies (solving two pieces at a time, minimizing setups, etc) and Dan observed that if you deconstruct the permutation into the cycles and solve pieces only within their cycle you will automatically use as few 3-cycles as possible.

The catch is that when there are duplicate pieces (for example there are 5 Starminx points of each color) there are multiple ways to deconstruct the cycles and I don't know how to pick the most efficient choice. The great news is that there is a simple heuristic that does very good.

So what am I talking about? Here is a small example. Suppose you have the elements {A, B, C, D, E, F}. You can permute these pieces 6! ways. Here is an example of my program permuting this and then breaking down the cycles:

Original: A, B, C, D, E, F
Permutation: F, A, C, D, B, E
Cycle (1): 2 // C
Cycle (1): 3 // D
Cycle (4): 0 -> 5 -> 4 -> 1 // F -> E -> B -> A


The cycle (1) are elements that are in their correct spot. You can see C and D have not moved.
The first part before the // is the indecies of the pieces in the cycle and the part after the // is the values of the pieces in those spots.

So in the cycle 0 -> 5 -> 4 -> 1 The piece in the 0 spot needs to move to the 5 spot and you can see that F -> E -> B -> A shows that the value of that piece is F. Offering both the index and value representation eliminates ambiguity when you have duplicate pieces.

For most complicated cubes there is at least one pieces type that has 24 pieces in 6 groups of 4 identical colors. Here is an example:

Original: W, W, W, W, G, G, G, G, R, R, R, R, B, B, B, B, O, O, O, O, Y, Y, Y, Y
Permutation: O, Y, W, Y, Y, G, O, O, B, R, B, G, W, R, W, R, R, G, Y, B, G, O, B, W
Cycle (1): 2 // W
Cycle (1): 5 // G
Cycle (1): 9 // R
Cycle (3): 0 -> 18 -> 23 // O -> Y -> W
Cycle (3): 1 -> 22 -> 12 // Y -> B -> W
Cycle (3): 4 -> 21 -> 17 // Y -> O -> G
Cycle (3): 6 -> 16 -> 11 // O -> R -> G
Cycle (5): 3 -> 20 -> 7 -> 19 -> 14 // Y -> G -> O -> B -> W
Cycle (2): 8 -> 13 // B -> R
Cycle (2): 10 -> 15 // B -> R


For an example from the dodecahedra, the Starminx has 60 points in 12 groups of 5:

Original: 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12
Permutation: 3, 5, 1, 10, 4, 5, 7, 6, 9, 2, 8, 6, 12, 11, 3, 12, 10, 9, 11, 5, 4, 3, 8, 8, 7, 11, 9, 10, 4, 1, 7, 3, 2, 12, 2, 7, 7, 4, 12, 1, 10, 4, 3, 6, 1, 2, 5, 8, 12, 9, 2, 5, 11, 6, 11, 10, 8, 1, 6, 9
Cycle (1): 2 // 1
Cycle (1): 9 // 2
Cycle (1): 14 // 3
Cycle (1): 30 // 7
Cycle (1): 52 // 11
Cycle (1): 54 // 11
Cycle (3): 0 -> 10 -> 39 // 3 -> 8 -> 1
Cycle (3): 3 -> 48 -> 57 // 10 -> 12 -> 1
Cycle (3): 4 -> 17 -> 44 // 4 -> 9 -> 1
Cycle (3): 5 -> 24 -> 32 // 5 -> 7 -> 2
Cycle (3): 7 -> 25 -> 50 // 6 -> 11 -> 2
Cycle (3): 8 -> 40 -> 45 // 9 -> 10 -> 2
Cycle (3): 11 -> 26 -> 42 // 6 -> 9 -> 3
Cycle (3): 13 -> 51 -> 21 // 11 -> 5 -> 3
Cycle (3): 15 -> 56 -> 37 // 12 -> 8 -> 4
Cycle (3): 16 -> 46 -> 20 // 10 -> 5 -> 4
Cycle (3): 18 -> 53 -> 28 // 11 -> 6 -> 4
Cycle (3): 27 -> 49 -> 43 // 10 -> 9 -> 6
Cycle (3): 38 -> 55 -> 47 // 12 -> 10 -> 8
Cycle (7): 1 -> 22 -> 35 -> 31 -> 12 -> 58 -> 29 // 5 -> 8 -> 7 -> 3 -> 12 -> 6 -> 1
Cycle (2): 6 -> 34 // 7 -> 2
Cycle (6): 19 -> 23 -> 36 -> 33 -> 59 -> 41 // 5 -> 8 -> 7 -> 12 -> 9 -> 4



By breaking the permutation down into cycles like this we can immediately know how many 3-cycles would be needed to solve the puzzle. With 1-cycles the pieces are already solved so no 3-cycle is required. For a 3-cycle only one 3-cycle is required. For 5-cycles you need two 3-cycles (first solve two pieces with 3-cycle which will setup a perfect 3-cycle to finish the remaining 3 pieces). For even-cycles you must find a duplicate piece somewhere else in the puzzle and use it in the cycle.

In general the number of 3-cycles you need to solve an N-cycle is:
(N - (N mod 2)) / 2

The benefit of writing a program to do these deconstructions is that we can gather statistics about the expected number of N-cycles for a given piece type.

1000 trials for a cube-like group (24 pieces in 6 groups of 4):
1-cycle E[X]: 3.914 per scramble
2-cycle E[X]: 2.015 per scramble
3-cycle E[X]: 4.051 per scramble
4-cycle E[X]: 0.526 per scramble
5-cycle E[X]: 0.271 per scramble
6-cycle E[X]: 0.074 per scramble
Averaged 7.882 3-cycles needed per-solve over 1000 scrambles


1000 trials for a dodecahedron-like group (60 pieces in 12 groups of 5):
1-cycle E[X]: 5.032 per scramble
2-cycle E[X]: 2.308 per scramble
3-cycle E[X]: 10.782 per scramble
4-cycle E[X]: 0.785 per scramble
5-cycle E[X]: 1.831 per scramble
6-cycle E[X]: 0.342 per scramble
7-cycle E[X]: 0.261 per scramble
8-cycle E[X]: 0.152 per scramble
9-cycle E[X]: 0.039 per scramble
10-cycle E[X]: 0.021 per scramble
11-cycle E[X]: 0.005 per scramble
Averaged 21.025 3-cycles needed per-solve over 1000 scrambles



Now, my program isn't selecting the cycles totally optimally to reduce the number of 3-cycles needed to solve the permutation. The heuristic it uses is favoring odd cycles over even ones. It first searches for all 1-cycles (solved pieces), then 3-cycles, then 5-cycles, etc. Once all of those have been found in then tries the {2, 3, 4, ....}-cycles. There are still lots of ways to select the cycles with this heuristic but my program just sticks with the first one it finds rather than backtracking to find others.

What these numbers are telling us is that if you're solving a random Starminx scramble there often at least 10 perfect 3-cycles in the points. You should first search for all of the 3-cycles. Then look for the 5-cycles. Other cycles are rare enough that it won't cost you too much if you just switch to solving two-at-a-time after that.

The numbers also give us a heuristic lower-bound on the number of 3-cycles you'd need to solve pieces in groups like these.


EDIT:
Dan and I were brainstorming about how much better the OPTIMAL cycle decomposition would be. I can't think of an algorithm to find the optimal decomposition that would be fast enough to be usable. I can choose the best of a bunch of random decompositions though. After lots of testing I found that 5 random decompositions was enough to find the best decomposition in all of the cases I could find. That is, I tested 1000 random decompositions for a bunch of scrambles an in each case, the best decomposition I found was always found in the first 5 random choices.

So 1000 scrambles using the best-of-five produced slightly better stats:
1-cycle E[X]: 4.960 per scramble
2-cycle E[X]: 1.971 per scramble
3-cycle E[X]: 11.018 per scramble
4-cycle E[X]: 0.549 per scramble
5-cycle E[X]: 2.049 per scramble
6-cycle E[X]: 0.244 per scramble
7-cycle E[X]: 0.380 per scramble
8-cycle E[X]: 0.086 per scramble
9-cycle E[X]: 0.062 per scramble
10-cycle E[X]: 0.014 per scramble
11-cycle E[X]: 0.003 per scramble
12-cycle E[X]: 0.005 per scramble
Averaged 20.764 3-cycles needed per-solve over 1000 scrambles

Unfortunately it isn't realistic for a human to know beforehand if there is a BETTER pure 3-cycle than the pure 3-cycle they just found. That is, I don't think these improved stats are achievable by a human.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Efficiently using 3-cycles to solve orientationless piec
PostPosted: Sun Mar 04, 2012 5:48 pm 
Offline
User avatar

Joined: Thu May 31, 2007 7:13 pm
Location: Bruxelles, Belgium
Once, I had a vague idea to add a function to show these cycle infos to my puzzles. I abandonned the idea because of a technical problem.

If an orbit is consisting of only unique pieces, it's simple.
There is only one way to partition pieces into cycles for each given orientation.
But if it cotains duplicate pieces(like your example of Starminx),
Is there a non-brute-force way to enumerate all possible partitions?
I don't mean to find the optimal partition. As you wrote, it will be extremly complicated.

_________________
Virtual Magic Polyhedra
Applet(Online)
Executable Jar Installer
Win32 Executable(Download)
troubleshooting


Top
 Profile  
 
 Post subject: Re: Efficiently using 3-cycles to solve orientationless piec
PostPosted: Mon Mar 05, 2012 2:25 am 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
gelatinbrain wrote:
If an orbit is consisting of only unique pieces, it's simple.
There is only one way to partition pieces into cycles for each given orientation.
But if it cotains duplicate pieces(like your example of Starminx),
Is there a non-brute-force way to enumerate all possible partitions?
I don't mean to find the optimal partition. As you wrote, it will be extremly complicated.
Unfortunately I don't know how to enumerate them all. That is how I was planning on finding the best: find them all and select the best. Everything I have come up with for finding them all is brute force and therefore too slow.

I'm pretty sure there is an exponential number of possibilities as the number of permuted pieces grows. Any algorithm that finds an exponentially growing set is going to have an exponential runtime itself.

Of course, to just find a reasonably good partition is very fast.

For your program though, Dan and I were thinking that it would be really nice if a sticker could be marked and unmarked. I think this could take a number of different forms. You could allow the sticker color to be changed to some other color. This would be nice for keeping track of the difference between identical pieces or tracking a piece as it is moved around. I'd probably use the feature in training / demo videos. Another option would be to add a colored border around the piece which would be nice because you could highlight the piece but still see the original color.

One way this could be use is to highlight all of the pieces that are a part of a cycle and then while you're solving a different cycle, if the pieces in the marked cycle happen to line up you could solve opportunistically them without having to spend costly setup moves. I know Dan would use this a ton.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Efficiently using 3-cycles to solve orientationless piec
PostPosted: Mon Mar 05, 2012 6:00 pm 
Offline
User avatar

Joined: Fri Feb 18, 2011 5:49 pm
Location: New Jersey
Brandon and I did a test to get a grip on how efficient it might be to use his program to prescribe an optimal cycle decomposition for an actual solve in GB. The benefits of using the optimal set of cycles is you spend fewer moves on the commutators themselves. The down-side is that since the cycles were "unnaturally" discovered, the ratio of set-up-moves per commutator will most certainly be much higher than normal. The question is whether or not the moves saved by doing fewer cycles makes up for the moves spent on doing more setups than normal.

For this test, we used 1.1.5 (starminx). I started by working on a manual solve on my own up to the point where I would start solving the tips pure with [3,1] commutators. I then sent a save file for this to Brandon to run his program on, and while waiting for him to generate an optimal cycle-set I continued to finish the solve on my own to the best of my ability (doing perfect 3-cycles whenever possible & convenient, and solving 2-at-a-time otherwise). Afterwards, Brandon sent me the list of prescribed cycles his program yielded, and I went back to the save-point and re-solved the tips a second time, this time following the script.

The save-point was 142 moves into the solve, and there were 38 tips remaining. My personal solve used an additional 162 moves to make 16 3-cycles (averaging 1.06 setup moves per cycle), and for the scripted solve, I ended up using 192 moves to make 15 3-cycles (averaging 2.4 setup moves per cycle). The end counts for the solves were 304 for myself, and 334 for the scripted solve. In the end, the scripted solve only lowered the count of cycles by 1 from my personal solve (saving 8 moves), and because I was able to use so many fewer setup moves in my personal solve (19 fewer setups, or 38 fewer moves), I was able to "beat" the script.


This was perhaps not a fair comparison, because I was able to employ a setup-move saving trick in my personal solve of not undoing the last move or two of a sequence if it might be useful in helping setup for another cycle. This trick is not really feasible to do on a scripted solve because keeping track of which pieces need to be cycled is very difficult when you can only make cycles listed on the script (you can really only do 1 at a time).

In the spirit of obtaining a more realistic comparison, I did another personal solve from the same save-point, this time without using that extra trick. This time, I ended up making 17 3-cycles in 188 moves (averaging 1.53 setups per cycle). This time it was much closer to what the scripted solve resulted in (a 4 move difference).

Although I was able to get lower move counts on my own than with the computer-aid, I think this experiment demonstrates that using a computer-generated optimal cycle decomposition will certainly yield a competitive move count... especially if you consider the case of a piece type that requires something longer than a [3,1] to cycle. However, I think this also shows that optimal cycling is not such a big factor that it can overshadow the value of being able to use fewer setup moves. Being close to optimal cycling is good enough.

For me, I think Brandon's data has shown me that, for the most part, simply doing perfect 3-cycles whenever they appear will yield a close-enough to optimal cycle decomposition that the biggest factor in the move counts for a solve will probably come down to the setups (strategy aside of course). You do not have to worry too much about breaking up cycles in a terribly inefficient manner this way.


bmenrigh wrote:
For your program though, Dan and I were thinking that it would be really nice if a sticker could be marked and unmarked. I think this could take a number of different forms. You could allow the sticker color to be changed to some other color. This would be nice for keeping track of the difference between identical pieces or tracking a piece as it is moved around. I'd probably use the feature in training / demo videos. Another option would be to add a colored border around the piece which would be nice because you could highlight the piece but still see the original color.

Just to chime in, I definitely think a function along these lines which lets the user temporarily put a "mask" color over the true color of pieces (or even just allows special markings of some kind) would make a lot of cool things easier to do.


Top
 Profile  
 
 Post subject: Re: Efficiently using 3-cycles to solve orientationless piec
PostPosted: Mon Mar 05, 2012 10:56 pm 
Offline
User avatar

Joined: Mon Feb 28, 2011 4:54 am
I find this thread fascinating to ponder, and I have a couple of questions, related to the starminx (since that's the puzzle under consideration mainly).

1) Will having more than one commutator available for tips make things easier? I like only having one commutator to remember, but I'm fairly sure it means I'll end up being able to cycle home 3 at a time, less than I'd like, simply because many of the setups would be too difficult to remember (and particularly on the starminx, where it seems one or two wrong moves can throw the whole thing visually). If I had maybe 4 or 5 different commutators to choose from, I'm guessing I'd be able to utilise them better.

2) Is there any way to apply these things when doing a physical solve? I solve the same way as Dan (and Burgo) does, by doing as much as possible intuitively and then doing the tips at the end. So, would knowing exactly how many and which cycles exist, somehow make it easier or "smarter" on an actual solve?

_________________
Youtube Twisty Puzzling
Blogger Twisty Puzzling - Simple Solutions for Puzzling Twisties
Tutorials: Pitcher Octo-Star Cube | GERANIUM | Wheel of Wisdom


Top
 Profile  
 
 Post subject: Re: Efficiently using 3-cycles to solve orientationless piec
PostPosted: Mon Mar 05, 2012 11:10 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
rline wrote:
I find this thread fascinating to ponder, and I have a couple of questions, related to the starminx (since that's the puzzle under consideration mainly).
The Starminx is the example puzzle only because it has 60 tips that don't have orientation and it is such a well understood puzzle. These results apply more broadly than just to the Starminx.

rline wrote:
1) Will having more than one commutator available for tips make things easier? I like only having one commutator to remember, but I'm fairly sure it means I'll end up being able to cycle home 3 at a time, less than I'd like, simply because many of the setups would be too difficult to remember (and particularly on the starminx, where it seems one or two wrong moves can throw the whole thing visually). If I had maybe 4 or 5 different commutators to choose from, I'm guessing I'd be able to utilise them better.
So unfortunately all a bunch more 3-cycles will help you with is reducing setup moves. The cycle analysis looks at cycles no matter what the position of the pieces are on the puzzle. If you popped the permutation into the program to get the list of cycles, having more 3-cycle variations would help you to follow the script but it in no way could "beat" the minimum the program tells you.

rline wrote:
2) Is there any way to apply these things when doing a physical solve? I solve the same way as Dan (and Burgo) does, by doing as much as possible intuitively and then doing the tips at the end. So, would knowing exactly how many and which cycles exist, somehow make it easier or "smarter" on an actual solve?
It would be very hard to use a semi-optimal decomposition of the permutation physically because generating the decomposition is "hard" to do manually. The best thing you can do if you're going for as few moves as possible is to aggressively pursue pure 3-cycles. Once you can't find anymore just switch to solving two pieces at a time. This strategy gets surprisingly close to what my program finds.

As Dan has shown, going for 3-cycles where you can solve two pieces at once with 0 or 1 setup move has the ability to beat the scripted solve in most cases. This is an extreme amount of work though and Dan is a phenomenal solver. The program would likely be VERY hard to beat for the average solver trying their best.

For what it's worth, if program were aware of the physical locations of the pieces and could search for setup moves then there is a way for the computer to essentially eliminate the need for setup moves. To do 15 3-cycles would probably take the computer 0-4 setup moves total so it would likely solve all of the Starminx points in 120-124 moves on Dan's test case.

I suppose the fact that a computer can beat a human should come as no surprise though. The fact that Dan can beat near-optimal cycle decomposition is quite amazing though.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Efficiently using 3-cycles to solve orientationless piec
PostPosted: Tue Mar 06, 2012 12:11 am 
Offline
User avatar

Joined: Fri Feb 18, 2011 5:49 pm
Location: New Jersey
rline wrote:
Will having more than one commutator available for tips make things easier?

When I did these solves, I used the base commutator [F'2,C2,F2,C'&2,F'2,C'2,F2,C&2]. I also allowed for any amount of rotation on the slice turn, and of course doing the sequence backwards or mirror imaged. I find these to be relatively easy to setup for, because you can break it down into 2 steps...

1. bring 2 of the points together so they are touching the same corner...
2. bring the 3rd piece to any of the 8 locations which you could move either of the first 2 pieces to with a slice move.

(You will find that in a lot of cases at the start of the tip-solving stage, you can skip step 1 by just finding a tip that belongs in an adjacent face at that corner.)

Of course having a greater variety of commutators for a given piece should theoretically make lower move-counts possible, but for the purpose of making things "easier" for following a script, I personally don't think it is required.

rline wrote:
Is there any way to apply these things when doing a physical solve?

I agree with Brandon, that attempting to use his program to optimize the cycles on a physical puzzle would be rather difficult. I also think it would not be particularly worthwhile, because you're going for speed, not move count, on a physical solve. I should mention that when I solve the physical starminx, most of my cycles are only 2-at-a-time. I don't actively look for perfect 3-cycles. I only really do a perfect 3-cycle when I trace the 2nd piece to it's face, and I happen to find a tip of the first color (which does still happen quite a few times every solve). This seems to give a nice balance of searching-time and move efficiency for my physical solves.

By the way, although I use the conjugate approach (that I had posted about in that other thread) for the first half of the physical starminx, that method is not efficient at all for move-count, so the solves on GB run much differently.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 7 posts ] 

All times are UTC - 5 hours


Who is online

Users browsing this forum: No registered users and 6 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  

Forum powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group