Development of a megaminx solver

[ichcubegerne]

This is the current distribution of all phases. The change of order for phases 4 and 5 yields:

The Depth gets 1 move worse and the average also suffers a bit. I am keen to see how the joined table of the phases 3 and 4 will look like, cause there is a slight possibility that its not even worth to make that change (although i doubt that heavily). I also want to test out merging the original phases 2 and 3 just to see what that would give me (but its most likely not gonna be that helpful, as that would not allow for any other optimizations of merging phases)

 

[ichcubegerne]

Update: I have been able to use my universities resources to merge phases 2 and 3 in the original order and phases 3 and 4 in the alternative order.
Phases 2 and 3 in the original order gave

and since thoses phases were 9 moves each, the bound has been lowered to 116 moves.

For phases 3 and 4 of alternative order we got
.
This is not that nice of a result, as it is 2 behind the original order. However the benefit of this order is that it makes a 7phase solver viable, as phases 1 and 2 can be merged now and that will most likely be better than 8 phases for the original order. However I doubt that I will be able to work on that table, as the next step is to verify Bens results and use that table directly to generate solutions.

I gave it superflip again and have sadly not gotten a better result, as the continuations were comparably more "average" and the original solution it found was quite lucky.

 

[UMichSpeedCubist]

76 moves, a lot better than I would have expected: Twizzle view
(Also I now know that the mechanism I have for counting moves in my solver doesnt work, because it told me the solution is 77 moves)
Interestingly it seems to be pretty lucky with the block order in the beginning. The second and third block are really short, which would have not been the case if I went for a different block order.

I only recently learned about the existence of twizzle, I will adjust the notation I am using to twizzles notation for the sake of consistency (and frankly because twizzles notation is just better) when I get around to it. Lucas wanted to set up a meeting with me to discuss the implementation a bit aswell.

Twizzle Editor supports doing (<alg>)'. This link has superflip set up at the start.

 

[MaximalMegaminx]

View attachment 37969
This is the current distribution of all phases. The change of order for phases 4 and 5 yields:
View attachment 37970
The Depth gets 1 move worse and the average also suffers a bit. I am keen to see how the joined table of the phases 3 and 4 will look like, cause there is a slight possibility that its not even worth to make that change (although i doubt that heavily). I also want to test out merging the original phases 2 and 3 just to see what that would give me (but its most likely not gonna be that helpful, as that would not allow for any other optimizations of merging phases)

have you considered trying to calculate the QTM upper bound with your code? well, more of a 5thTM I suppose, the QTM equivalent on the Megaminx, that'd be pretty nice

also I'm confused, how did you get 116? 10 + 15 + 14 + 8 + 14 + 13 + 17 + 26 = 117, however you originally said the 2nd stage of S2L takes 13 moves, and yet there's the table for Phase2Block2 going up to 14, should I assume that was a typo that got carried over to the calculations and the upper bound is 117?

 

[ichcubegerne]

have you considered trying to calculate the QTM upper bound with your code? well, more of a 5thTM I suppose, the QTM equivalent on the Megaminx, that'd be pretty nice

also I'm confused, how did you get 116? 10 + 15 + 14 + 8 + 14 + 13 + 17 + 26 = 117, however you originally said the 2nd stage of S2L takes 13 moves, and yet there's the table for Phase2Block2 going up to 14, should I assume that was a typo that got carried over to the calculations and the upper bound is 117?

Funny that you write here, I was about to post an update just today after several months

Determining QTM bounds would be a rather quick coding adventure, but the deadline for my thesis is only 1,5 months away, so I'd rather not get distracted before that. I could very well do it afterwards.

Regarding the upper bound, you are right. I originally did more of these calculations by hand, so I probably have typoed that, thanks for notifying me! Also am I mixing something up or isnt S2L just 2gen? Because thats not what that phase does.

 

[ichcubegerne]

While I had to give up on verifying Bens results due to a lack of computational expertise and time, I have worked in an alternative approach for the 2-gen phase, where <R,U> is reduced into <R,R U R'>. I currently do not have these tables formated, but the max depths are 14 and 29 for these phases respectively. Since these phases do not require a meet in the middle approach, I was able to work in some more optimizations.

First, I made the algorithm non-deterministic, by choosing the move that improves the current depth at random, instead of by ergonomy of the move. The optimizations are rather simplistic, as they will almost be at the very end of my thesis and i didnt want to go toooo deep into it. When generating solutions, I also choose 2 parameters n and m. The parameter n will make the algorithm generate n solutions to each phase and then pick a solution with the best resulting depth for the next phase. The parameter m just tells the algorithm to generate m total solutions and then pick one of shortest length. I have tested this with some values of n and m on the superflip with the following results:



I think the runtime testing is too inaccurate to properly represent runtimes for values below 100, but it gives the general idea. I will be working on more statistics and stuff to come soon (especially cause I wanna combine this with the meet in the middle approach and see how and if it competes with these parameters)

The best solution found was this one: 75 Moves
I Frankensteined it with the MeetInTheMiddle to: 73 Moves

 

[MaximalMegaminx]

Regarding the upper bound, you are right. I originally did more of these calculations by hand, so I probably have typoed that, thanks for notifying me! Also am I mixing something up or isnt S2L just 2gen? Because thats not what that phase does.

the way I understood it, the solving is done in 8 stages, firstly of category Phase1 which is F2L, so "Phase1Block1" is a 2x2x2, "Phase1Block2" is F2L minus a 3x2x1, "Phase1Block3" is full F2L, then Phase2 is almost full S2L save for last face (plus the top face of course), so "Phase1Block1" is a starting 2x2 block, then "Phase2Block2" is a 3x2x1 extension, "Phase2Block3" same, as if we're solving with Westlund method, and then "Phase2Block4" is the next 3x2x1 block plus EO, and then the 2 Gen <R,U> stage

so I was talking about "Phase2Block2", which is what I called the 2nd stage of S2L, in your message from 14 August 2024 it is called "ULayerBlock2" and given a value of 13 maximum moves required, when here we have a table "Phase2Block2" that goes up to 14 moves, I would just assume it was a typo that got carried over to calculations

 

[ichcubegerne]

the way I understood it, the solving is done in 8 stages, firstly of category Phase1 which is F2L, so "Phase1Block1" is a 2x2x2, "Phase1Block2" is F2L minus a 3x2x1, "Phase1Block3" is full F2L, then Phase2 is almost full S2L save for last face (plus the top face of course), so "Phase1Block1" is a starting 2x2 block, then "Phase2Block2" is a 3x2x1 extension, "Phase2Block3" same, as if we're solving with Westlund method, and then "Phase2Block4" is the next 3x2x1 block plus EO, and then the 2 Gen <R,U> stage

so I was talking about "Phase2Block2", which is what I called the 2nd stage of S2L, in your message from 14 August 2024 it is called "ULayerBlock2" and given a value of 13 maximum moves required, when here we have a table "Phase2Block2" that goes up to 14 moves, I would just assume it was a typo that got carried over to calculations

The solving is *currently* done in 10 stages, or 9 if 2Gen is solved with MeetInTheMiddle as I originally did it. The 2Gen Table was not included here, as I didnt have it until Ben generated it. I think I also just mixed up S2L and L2L

 

[MaximalMegaminx]

The solving is *currently* done in 10 stages, or 9 if 2Gen is solved with MeetInTheMiddle as I originally did it. The 2Gen Table was not included here, as I didnt have it until Ben generated it. I think I also just mixed up S2L and L2L

for your project, I imagine it's done in less stages, I meant for the theoretical best known solving method defined by the lowest upper bound

 

[ichcubegerne]

for your project, I imagine it's done in less stages, I meant for the theoretical best known solving method defined by the lowest upper bound

I dont quite understand what you mean by that.

 

[MaximalMegaminx]

I dont quite understand what you mean by that.

I'm getting 8 stages, 3 for F2L, 4 for almost S2L plus EO, and final 2 Gen <R,U> stage, i.e. the ones I listed above and which give the upper bound which give 117 as the upper bound, that's the "method" I am referring to and the one I frankly was the most curious about. You say your method now has 10 stages and I assume you mean you have a slightly different method for the practical purposes of your project, because you're going for the lowest average move count, not the best upper bound.

 

[ichcubegerne]

I'm getting 8 stages, 3 for F2L, 4 for almost S2L plus EO, and final 2 Gen <R,U> stage, i.e. the ones I listed above and which give the upper bound which give 117 as the upper bound, that's the "method" I am referring to and the one I frankly was the most curious about. You say your method now has 10 stages and I assume you mean you have a slightly different method for the practical purposes of your project, because you're going for the lowest average move count, not the best upper bound.

I see, i was confused by the phrasing "For your project, I imagine its donein less stages" cause that seemed to imply that I used less stages for the project, although its actually more now. I might have thought about it the wrong way around.

I did actually run more exhaustive tests with my universities HPC and the runtimes got consistent, so I assume those inconsistencies were just because of my PC multitasking or something. In over a milion solutions, the best one found is 75 moves and that solution seems to be unique, which I found interesting.

 

[ichcubegerne]

the way I understood it, the solving is done in 8 stages, firstly of category Phase1 which is F2L, so "Phase1Block1" is a 2x2x2, "Phase1Block2" is F2L minus a 3x2x1, "Phase1Block3" is full F2L, then Phase2 is almost full S2L save for last face (plus the top face of course), so "Phase1Block1" is a starting 2x2 block, then "Phase2Block2" is a 3x2x1 extension, "Phase2Block3" same, as if we're solving with Westlund method, and then "Phase2Block4" is the next 3x2x1 block plus EO, and then the 2 Gen <R,U> stage

so I was talking about "Phase2Block2", which is what I called the 2nd stage of S2L, in your message from 14 August 2024 it is called "ULayerBlock2" and given a value of 13 maximum moves required, when here we have a table "Phase2Block2" that goes up to 14 moves, I would just assume it was a typo that got carried over to calculations

Actually, there was an error in my writeup, you can see that the 6th table (with 64 milion states) has identical states for depth 10 and 12, which is a typo. This table actually only goes up to 13 moves and the state counts for 13 and 14 are supposed to be one line up each.

 

[MaximalMegaminx]

Actually, there was an error in my writeup, you can see that the 6th table (with 64 milion states) has identical states for depth 10 and 12, which is a typo. This table actually only goes up to 13 moves and the state counts for 13 and 14 are supposed to be one line up each.

no shot, so the known upper bound really is 116 then?

 

[ichcubegerne]

Since I got my deadline on monday, I have published the repository: https://git.rwth-aachen.de/alexander.botz/megaminx-solver-v2.0
Note that I have absolutely 0 understanding of git and I literally uploaded the files one by one because I couldnt get anything else to work.

 

[abunickabhi]

Since I got my deadline on monday, I have published the repository: https://git.rwth-aachen.de/alexander.botz/megaminx-solver-v2.0
Note that I have absolutely 0 understanding of git and I literally uploaded the files one by one because I couldnt get anything else to work.

You can use git bash, and just do git push from your local repo / folder.

 

[ichcubegerne]

You can use git bash, and just do git push from your local repo / folder.

Thanks for the tip, I will look into that in the future. But since it works for now, Imma leave it at that.

 

[rokicki]

The 16 26-move antipodes of U,R two-gen can be solved in 24 moves each if you add F. So this can cut one move off the upper bound.

Here are the 24-move solutions.

 U F' R F R2' U2' R U2' R2 U2' F' U R2 U2 R' U2' R U R' U2' R2 F U2' R2'
 U R2' U' R2' F' U2' F R' U' F' R2' U2 R2 F U2' F' R2' U R2 F2 R F' U2 R'
 U R U' R' U R2 F' R' F U2 F' U2 R2 U2' R' U2 R2 U R2 U2 F R2 U2 R
 U R U R2 U2 F R2 U2 R U2 R2 U' R2' U2 R2 F' R2 F U' F' U2 R U' R'
 U2' R U' R2 F' U F2 U2 R U2' F' R2' F U2 R2 U2' F' R' U' F R2' F' U2' R'
 U2 R' F' R2' U2' R F U2 F' R2 U2' F R F R2' F' R' U2 R2 F' R2 U2' F R2'
 U2 F R2 U2 R U2 R2 U' R2' U2 R2 F' R2 U R U' F R' U R U2' F' U2' R2
 U R' U2 R U2 F R2 F' U R F U2 R2' U2' F' R2 F U2 R' U2' F2' U' F R2'
 U R2 U2 F R2 U2 R U2 R2 U' R2' U2 R2 F' R2 F U' F' U2 R U' R' U R
 U2 F U2 R' U' R F' U R' U' R2' F R2' U2' R2 U R2' U2' R' U2' R2' F' U2' R2'
 U R2 U' R U2' F R' F2' R2' U' R2 F U2 F' R2' U2' R2 F U R F' U2 F R2
 U R' U2' F U F' R2' F R2' U2' R2 U R2' U2' R' U2' R2' F' U2' R2' U' R' U' R
 U F U2 R2 U' F' R2' F U2' R2 F' U' F' U2 F U R2' U2' F U2' R2 F' U2 R2'
 U R F' U2 F R2 U R2 U' R U2' F R' F2' R2' U' R2 F U2 F' R2' U2' R2 F
 U2' R2' F' U2' R2' U' R2' U2' R U2 R2' U2' F U2' F' R F R2' U' R U R' U' R'
 U2 F R2 F' U R F U2 R2' U2' F' R2 F U2 R' U2' F2' U' F R2' U R' U2 R

 

[ichcubegerne]

The 16 26-move antipodes of U,R two-gen can be solved in 24 moves each if you add F. So this can cut one move off the upper bound.

Here are the 24-move solutions.

 U F' R F R2' U2' R U2' R2 U2' F' U R2 U2 R' U2' R U R' U2' R2 F U2' R2'
 U R2' U' R2' F' U2' F R' U' F' R2' U2 R2 F U2' F' R2' U R2 F2 R F' U2 R'
 U R U' R' U R2 F' R' F U2 F' U2 R2 U2' R' U2 R2 U R2 U2 F R2 U2 R
 U R U R2 U2 F R2 U2 R U2 R2 U' R2' U2 R2 F' R2 F U' F' U2 R U' R'
 U2' R U' R2 F' U F2 U2 R U2' F' R2' F U2 R2 U2' F' R' U' F R2' F' U2' R'
 U2 R' F' R2' U2' R F U2 F' R2 U2' F R F R2' F' R' U2 R2 F' R2 U2' F R2'
 U2 F R2 U2 R U2 R2 U' R2' U2 R2 F' R2 U R U' F R' U R U2' F' U2' R2
 U R' U2 R U2 F R2 F' U R F U2 R2' U2' F' R2 F U2 R' U2' F2' U' F R2'
 U R2 U2 F R2 U2 R U2 R2 U' R2' U2 R2 F' R2 F U' F' U2 R U' R' U R
 U2 F U2 R' U' R F' U R' U' R2' F R2' U2' R2 U R2' U2' R' U2' R2' F' U2' R2'
 U R2 U' R U2' F R' F2' R2' U' R2 F U2 F' R2' U2' R2 F U R F' U2 F R2
 U R' U2' F U F' R2' F R2' U2' R2 U R2' U2' R' U2' R2' F' U2' R2' U' R' U' R
 U F U2 R2 U' F' R2' F U2' R2 F' U' F' U2 F U R2' U2' F U2' R2 F' U2 R2'
 U R F' U2 F R2 U R2 U' R U2' F R' F2' R2' U' R2 F U2 F' R2' U2' R2 F
 U2' R2' F' U2' R2' U' R2' U2' R U2 R2' U2' F U2' F' R F R2' U' R U R' U' R'
 U2 F R2 F' U R F U2 R2' U2' F' R2 F U2 R' U2' F2' U' F R2' U R' U2 R

Wouldnt that cut off 2 of the upper bound?

Edit: Ahh, it wouldnt because of the 25-movers.

 

[ichcubegerne]

Here btw a nicer summary. For a more basic version I solved 2Gen in 2 steps, the second being R,RUR'-generated.

I could check later how the 3 worst cases for the 3 Gen phase look like, that could probably also be reduced. (Interestingly the superflip is only a 16 mover here)