Development of a megaminx solver

[rokicki]

Wouldnt that cut off 2 of the upper bound?

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

Actually, Ben took the 7595 distance-25 positions in 2gen, reduced them by symmetry and inversion to 1199 distinct representatives. I then solved all of these in U,R,F and found that all of these are solvable in 24 or fewer moves. So yes, we can take two moves off the upper bound.

 

[rokicki]

I think with the computational resources that I have, it would be possible to get an upper bound using a 6 phase method (but I wouldn't be able to use it in a solver):

1. 2x2x3 block (reduce to 8 faces) (1.871 trillion states)
2. Extend with two 2x2x1s to make a "triangle" (reduce to 6 faces) (13.377 billion states)
3. Extend with a 1x2x3 and 2x2x1 (reduce to 4 faces) (7.088 trillion states)
4. Reduce to 3 faces (32.380 billion states)
5. Reduce to 2 faces + EO (2.189 billion states)
6. 2gen (7.999 trillion states)

Computing the upper bound for steps 1 3 and 6 would take quite a long time (probably over a month in total) but it should in theory be possible on my machine. Also maybe there's a different 6 phase method that has more evenly distributed state sizes but I couldn't think of one. 5 phase isn't possible for me because it would require an average state size of almost 40 trillion which is bigger than what I can do.

Here is a possible order that reduces the maximum number of states if you ignore the last phase:

U D F B L DR BL FR BR FL R DL 1.0066961655352334986e+68 1,641,669,120,000
U D F B BL R 6.1321502199860667957e+55 640,530,519,552
U F B BL R 9.5735488517783929653e+43 168,782,745,600
U F BL R 5.6721134721121592997e+32 32,380,508,160
U F R 1.751706132616839168e+22 2,189,721,600

It's probably not very ergonomic or move-efficient, however.

 

[MaximalMegaminx]

I just wanted to point out that the work done here also shows an upper bound for Gen <U, F, R> on Megaminx of 41 moves. That's 17 moves from Alexander Botz's analysis of the stage of 2nd last S2L face + EO, and Ben's Gen <U, R> God's number of 26, pushed to 24 by Rokicki's exclusion of the hardest cases. 17 + 24 = 41.

Edit: I just noticed that the cases Rokicki checked were reduced by symmetry, so it's possible some were only solved in 24 moves in <BR, R, U> instead of <F, R, U> Gen, and also I don't know what's the move restriction for Botz's "2nd last S2L face + EO" stage, so neither side of it actually work, discard my comment

 

[ichcubegerne]

I just wanted to point out that the work done here also shows an upper bound for Gen <U, F, R> on Megaminx of 41 moves. That's 17 moves from Alexander Botz's analysis of the stage of 2nd last S2L face + EO, and Ben's Gen <U, R> God's number of 26, pushed to 24 by Rokicki's exclusion of the hardest cases. 17 + 24 = 41.

Edit: I just noticed that the cases Rokicki checked were reduced by symmetry, so it's possible some were only solved in 24 moves in <BR, R, U> instead of <F, R, U> Gen, and also I don't know what's the move restriction for Botz's "2nd last S2L face + EO" stage, so neither side of it actually work, discard my comment

I am not sure what you mean by restriction, it is just a subgroup reduction and the intuitive interpretation is that i solves that block and (local) EO

 

[MaximalMegaminx]

I am not sure what you mean by restriction, it is just a subgroup reduction and the intuitive interpretation is that i solves that block and (local) EO

By restriction I mean literally a restriction of the kinds of moves you are allowed to do, like this <F, R, U> where you can only do turns on the front, right, and upper faces. I assumed that during that stage you were limited to those 3 faces, but I realized that I didn't actually know that (maybe you allowed L and BR moves too, I don't have the details to say you didn't).

 

[ichcubegerne]

By restriction I mean literally a restriction of the kinds of moves you are allowed to do, like this <F, R, U> where you can only do turns on the front, right, and upper faces. I assumed that during that stage you were limited to those 3 faces, but I realized that I didn't actually know that (maybe you allowed L and BR moves too, I don't have the details to say you didn't).

Gotcha, but all involved generators were moves in this approach, so I didnt use "outside" moves as they would have kicked me out of the subgroup.

 

[MaximalMegaminx]

Ok then so a bound of 42 for <F, R, U> is confirmed then, with your block+EO and then Ben's <R, U> 26 confirmation followed by Rokicki's improvement down to 25, so 17 + 25 = 42.

 

[ichcubegerne]

Edit: I just noticed that the cases Rokicki checked were reduced by symmetry, so it's possible some were only solved in 24 moves in <BR, R, U> instead of <F, R, U> Gen, and also I don't know what's the move restriction for Botz's "2nd last S2L face + EO" stage, so neither side of it actually work, discard my comment

Isnt BR R U Gen the same as F R U Gen?

 

[MaximalMegaminx]

Isnt BR R U Gen the same as F R U Gen?

yes but in improving the bound of the last stage to 24, you'd need to confirm that all the 25-movers in Gen <R, U> can be done in less moves in Gen <F, R, U>, but Rokicki used <F, R, U> and <BR, R, U> intermittently as far as I'm aware, if a particular case couldn't be handled in sufficient number of moves with<F, R, U>, then try with <BR, R, U>, so you might be missing some mirrored cases for the full proof

 

[ichcubegerne]

yes but in improving the bound of the last stage to 24, you'd need to confirm that all the 25-movers in Gen <R, U> can be done in less moves in Gen <F, R, U>, but Rokicki used <F, R, U> and <BR, R, U> intermittently as far as I'm aware, if a particular case couldn't be handled in sufficient number of moves with<F, R, U>, then try with <BR, R, U>, so you might be missing some mirrored cases for the full proof

But cant you just mirror the solution then?

 

[MaximalMegaminx]

But cant you just mirror the solution then?

to verify the bound of 24 for the purposes of the Gen <F, R,U> God's number, we need to solve all those 25-move <R,U> cases in <F,R,U> in 24 moves or less

what Rokicki did, essentially, is to do them in <F,R,U>, we try to get them down to 24 moves, and if that didn't work, do them in <BR,R,U>, but if a case is really impossible in <F,R,U>, so that you need <BR,R,U>, mirroring doesn't help because that's a different case entirely, actually one already implicitly covered in <F,R,U>, and we need to solve them all in <F,R,U>

(technically he didn't go through them all, he got the list of them reduced by symmetry)

 

[ichcubegerne]

to verify the bound of 24 for the purposes of the Gen <F, R,U> God's number, we need to solve all those 25-move <R,U> cases in <F,R,U> in 24 moves or less

what Rokicki did, essentially, is to do them in <F,R,U>, we try to get them down to 24 moves, and if that didn't work, do them in <BR,R,U>, but if a case is really impossible in <F,R,U>, so that you need <BR,R,U>, mirroring doesn't help because that's a different case entirely, actually one already implicitly covered in <F,R,U>, and we need to solve them all in <F,R,U>

(technically he didn't go through them all, he got the list of them reduced by symmetry)

I honestly do not understand this at all. Solving cases in FRU is obvious to me, as a bigger generating set can reduce movecounts, but I dont see how F R U and BR R U arent the same generating set up to isomorphy with respect to a case generated by R U.

 

[xyzzy]

I honestly do not understand this at all. Solving cases in FRU is obvious to me, as a bigger generating set can reduce movecounts, but I dont see how F R U and BR R U arent the same generating set up to isomorphy with respect to a case generated by R U.

An RU state being solvable in RUF in x moves doesn't imply all of its symmetric equivalents are also solvable in RUF in x moves because some of the symmetries switch F and BR.

 

[MaximalMegaminx]

I honestly do not understand this at all. Solving cases in FRU is obvious to me, as a bigger generating set can reduce movecounts, but I dont see how F R U and BR R U arent the same generating set up to isomorphy with respect to a case generated by R U.

let me phrase this like this, imagine there is a case generated by R U that can’t be done in 24 moves in F R U, but can be in BR R U, let’s call it the annoying case

now when we solve Megaminx Gen <F, R, U>, we first solve block+EO and then that fake Gen <R, U>, that’s the best we can do

on a particular case, we’ve done the 1st stage in <F, R, U> as normal, and then in the 2nd stage we get the annoying case, what do we do? we can’t move BR by definition, we’re trapped to use the unoptimal F, R, U algorithm

 

[ichcubegerne]

An RU state being solvable in RUF in x moves doesn't imply all of its symmetric equivalents are also solvable in RUF in x moves because some of the symmetries switch F and BR.

let me phrase this like this, imagine there is a case generated by R U that can’t be done in 24 moves in F R U, but can be in BR R U, let’s call it the annoying case

now when we solve Megaminx Gen <F, R, U>, we first solve block+EO and then that fake Gen <R, U>, that’s the best we can do

on a particular case, we’ve done the 1st stage in <F, R, U> as normal, and then in the 2nd stage we get the annoying case, what do we do? we can’t move BR by definition, we’re trapped to use the unoptimal F, R, U algorithm

Gotcha, thanks. I just misunderstood the situation, i think.

 

[ichcubegerne]

I worked out setups for representatives of the 17 movers of the 3Gen state:
F R' U' F2 R2 U2' F' R2 U F2 R2 U2' F R2 U2' F2' U2
F2' R U2 F2' U2 R2' F2' U' R2' F R2' U2' F2 R' U' F U
F2 U2' F2 R2' F' R' U F2' R' U2 F2' U2' R2' F2' R U2' F

 

[ichcubegerne]

I finally got around to do the QTM tables. I have not verified this data with the solver, so take it with a grain of salt (The number seem reasonable tho). In total we obtain for the original subgroup chain a total bound of 13+14+14+19+12+18+17+21=128 moves, which gives us a total bound of 128+34=162 when combined with Ben's findings for 2Gen.

The numbers below the distribution show average*1000 and total number of cases btw.

 

[ichcubegerne]

My thesis is now public at: https://tudatalib.ulb.tu-darmstadt.de/items/df505085-2ccb-43e2-9679-9bbf1dbf192f/full
The zipfile contains the thesis pdf, a gap implementation of the Megaminx and the project code, which is already on git.

 

[Jacck]

It's great! Big congrats!
And I understood most of it - until I came to page 14

 

[ichcubegerne]

It's great! Big congrats!
And I understood most of it - until I came to page 14

But thats where its starting to get really interesting!