View unanswered posts  View active topics

Page 1 of 1

[ 7 posts ] 

Author 
Message 
Brandon Enright

Post subject: Efficiently using 3cycles to solve orientationless pieces Posted: Sat Mar 03, 2012 9:13 pm 

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 3cycles. 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 3cycling 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 3cycles 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 > AThe 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 > RFor 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 > 4By breaking the permutation down into cycles like this we can immediately know how many 3cycles would be needed to solve the puzzle. With 1cycles the pieces are already solved so no 3cycle is required. For a 3cycle only one 3cycle is required. For 5cycles you need two 3cycles (first solve two pieces with 3cycle which will setup a perfect 3cycle to finish the remaining 3 pieces). For evencycles you must find a duplicate piece somewhere else in the puzzle and use it in the cycle. In general the number of 3cycles you need to solve an Ncycle is: (N  (N mod 2)) / 2The benefit of writing a program to do these deconstructions is that we can gather statistics about the expected number of Ncycles for a given piece type. 1000 trials for a cubelike group (24 pieces in 6 groups of 4):1cycle E[X]: 3.914 per scramble 2cycle E[X]: 2.015 per scramble 3cycle E[X]: 4.051 per scramble 4cycle E[X]: 0.526 per scramble 5cycle E[X]: 0.271 per scramble 6cycle E[X]: 0.074 per scramble Averaged 7.882 3cycles needed persolve over 1000 scrambles1000 trials for a dodecahedronlike group (60 pieces in 12 groups of 5):1cycle E[X]: 5.032 per scramble 2cycle E[X]: 2.308 per scramble 3cycle E[X]: 10.782 per scramble 4cycle E[X]: 0.785 per scramble 5cycle E[X]: 1.831 per scramble 6cycle E[X]: 0.342 per scramble 7cycle E[X]: 0.261 per scramble 8cycle E[X]: 0.152 per scramble 9cycle E[X]: 0.039 per scramble 10cycle E[X]: 0.021 per scramble 11cycle E[X]: 0.005 per scramble Averaged 21.025 3cycles needed persolve over 1000 scramblesNow, my program isn't selecting the cycles totally optimally to reduce the number of 3cycles needed to solve the permutation. The heuristic it uses is favoring odd cycles over even ones. It first searches for all 1cycles (solved pieces), then 3cycles, then 5cycles, 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 3cycles in the points. You should first search for all of the 3cycles. Then look for the 5cycles. Other cycles are rare enough that it won't cost you too much if you just switch to solving twoatatime after that. The numbers also give us a heuristic lowerbound on the number of 3cycles 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 bestoffive produced slightly better stats: 1cycle E[X]: 4.960 per scramble 2cycle E[X]: 1.971 per scramble 3cycle E[X]: 11.018 per scramble 4cycle E[X]: 0.549 per scramble 5cycle E[X]: 2.049 per scramble 6cycle E[X]: 0.244 per scramble 7cycle E[X]: 0.380 per scramble 8cycle E[X]: 0.086 per scramble 9cycle E[X]: 0.062 per scramble 10cycle E[X]: 0.014 per scramble 11cycle E[X]: 0.003 per scramble 12cycle E[X]: 0.005 per scramble Averaged 20.764 3cycles needed persolve over 1000 scrambles Unfortunately it isn't realistic for a human to know beforehand if there is a BETTER pure 3cycle than the pure 3cycle 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 


gelatinbrain

Post subject: Re: Efficiently using 3cycles to solve orientationless piec Posted: Sun Mar 04, 2012 5:48 pm 

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 nonbruteforce 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 


Brandon Enright

Post subject: Re: Efficiently using 3cycles to solve orientationless piec Posted: Mon Mar 05, 2012 2:25 am 

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 nonbruteforce 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 


DKwan

Post subject: Re: Efficiently using 3cycles to solve orientationless piec Posted: Mon Mar 05, 2012 6:00 pm 

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 downside is that since the cycles were "unnaturally" discovered, the ratio of setupmoves 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 cycleset I continued to finish the solve on my own to the best of my ability (doing perfect 3cycles whenever possible & convenient, and solving 2atatime otherwise). Afterwards, Brandon sent me the list of prescribed cycles his program yielded, and I went back to the savepoint and resolved the tips a second time, this time following the script. The savepoint was 142 moves into the solve, and there were 38 tips remaining. My personal solve used an additional 162 moves to make 16 3cycles (averaging 1.06 setup moves per cycle), and for the scripted solve, I ended up using 192 moves to make 15 3cycles (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 setupmove 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 savepoint, this time without using that extra trick. This time, I ended up making 17 3cycles 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 computeraid, I think this experiment demonstrates that using a computergenerated 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 3cycles whenever they appear will yield a closeenough 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 


rline

Post subject: Re: Efficiently using 3cycles to solve orientationless piec Posted: Mon Mar 05, 2012 10:56 pm 

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 OctoStar Cube  GERANIUM  Wheel of Wisdom


Top 


Brandon Enright

Post subject: Re: Efficiently using 3cycles to solve orientationless piec Posted: Mon Mar 05, 2012 11:10 pm 

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 3cycles 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 3cycle 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 semioptimal 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 3cycles. 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 3cycles 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 3cycles would probably take the computer 04 setup moves total so it would likely solve all of the Starminx points in 120124 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 nearoptimal cycle decomposition is quite amazing though.
_________________ Prior to using my real name I posted under the account named bmenrigh.


Top 


DKwan

Post subject: Re: Efficiently using 3cycles to solve orientationless piec Posted: Tue Mar 06, 2012 12:11 am 

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 tipsolving 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 movecounts 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 2atatime. I don't actively look for perfect 3cycles. I only really do a perfect 3cycle 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 searchingtime 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 movecount, so the solves on GB run much differently.


Top 



Page 1 of 1

[ 7 posts ] 

Who is online 
Users browsing this forum: Google Adsense [Bot] and 7 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


