# Approximating Dodecahedron Upper Bound



## One Wheel (May 19, 2017)

I'm not much of a mathematician, but I'm wondering if anybody has any idea how to calculate an upper bound for God's number for megaminx/gigaminx, etc? I want to make a mechanical scrambler, and it's an interesting side query to see if it is at all feasible to set it up so that it could theoretically reach any possible position.

While I'm at it I've calculated lower bounds as follows:

3x3: 3 possible first moves (cw, ccw, 1/2 turn, which face doesn't matter)
15 second moves (the other 5 faces)
4/5 3rd moves = 15 possible, 1/5 3rd moves, 12 possible (if the 2nd move was opposite the 1st)
Therefore scrambles of length n = 3*14.4^(n-1)
Length n >/=:
1 3
2 48
.
.
.
17 1.1e19
18 1.6e20

This is obviously a lower bound because some scrambles will result in identical positions.

Roughly similar methodology for bigger cubes, except only counting move counts for WCA scrambles:
40-move 4x4 scrambles: 9.78e59 scrambles, 7.40e45 possible positions
60-move 5x5 scrambles: 1.41e91 scrambles, 2.80e74 possible positions
80-move 6x6 scrambles: 8.93e135 scrambles, 1.57e116 possible positions
100-move 7x7 scrambles: 6.05e170 scrambles, 1.95e160 possible positions
It looks like somebody ran the same figures I did and rounded up to figure out how many moves to require for WCA scrambles.

Calculating possible scrambles using Pochmann notation for megaminx is much simpler, because there are no prohibited moves, and each move is essentially 1 bit of information (direction of turn: which face is determined by preceding moves). Therefore:
70-move megaminx scrambles: 1.18e21 scrambles, 1.01e68 possible positions.
226-move megaminx scrambles: 1.08e68 scrambles. Not feasible for hand scrambling, but otherwise I'm convinced marginally better, because the current method leaves out all but 1/8.56e46 of the possible positions if you assume (probably falsely) that there are no two allowed scrambles that result in the same position.

Gigaminx scrambles using an extended Pochmann notation would have two bits of information per move: depth and direction, therefore:
438-move gigaminx scrambles: 5.04e263 scrambles, 3.648e263 possible positions
500-move gigaminx scramble: 1.07e301 possible scrambles, and a nice round number. Without building a mechanical scrambler yet, my guess is that it could easily complete a 500-move scramble in about 4 minutes (~2 TPS), quite possibly half that (~4 TPS) or better. A 360-move gigaminx scramble would result in a similar percentage as current megaminx scrambles do, and at 6 TPS could be done in one minute.

So I guess the point is: I have a pretty good idea of the minimum number of moves for a "good" scramble. What is the maximum? And am I making a big mistake in the math that I have done?


----------



## xyzzy (May 19, 2017)

One Wheel said:


> I'm wondering if anybody has any idea how to calculate an upper bound for God's number for megaminx/gigaminx, etc?


This is a thing I'll work on in the next few weeks once I get some free time! For the megaminx, there's a lower bound of 48 moves from a counting argument, and an upper bound of 194 moves. This is with all twelve face moves, not just the two moves used in Pochmann notation.

I don't think anyone's proven that you can get to all possible states with Pochmann-style scrambles (although I'd put my money on this being true), and if you're thinking of making a mechanical scrambler, 12-face scrambles might be better. Pochmann-style scrambles are mainly beneficial for _humans_ because 12-face scramble sequences are hard for us to apply correctly.

The calculations seem to be essentially correct, although I should point out that you can apply a lot of moves and still have a noticeable bias. You're guaranteed (*) to converge to the stationary distribution as the number of moves increases, and while the convergence is also guaranteed to be exponential (in that the difference from the stationary distribution after N moves decays like exp(−λN)), "exponential" doesn't mean "fast".

(* Caveat: this applies only if the Markov chain of the puzzle state (**) is aperiodic. Usually random-move scramblers result in aperiodic Markov chains, and exceptions to this typically have some implicit parity constraint. Consider for example scrambling a cube with only quarter turns. You can only return to the solved state after an even number of moves due to parity, so this is not an aperiodic Markov chain. In particular, the parity of the scrambled state will never differ from the parity of the number of moves, so no matter how many moves you apply, you'll never converge to the uniform distribution.)

(** Actually, you have to consider both the puzzle state _and_ and the scrambler state, depending on how the scrambler is designed. For example, if you forbid the scrambler from making a move on the same face twice in a row, then you need some extra state to keep track of which was the last face used. This extra state should also be considered as part of the Markov chain.)


----------



## One Wheel (May 19, 2017)

Thanks! My reasoning for using Pochman-style was just simplicity of the mechanism. Using 12-face scrambles would require either a system for accurately reorienting the puzzle or 12 different mechanisms for turning faces. Pochman-style would only require rotation on two axes, with 1/6 the number of stepper motors, which will probably be the expensive part of the project.

Edit: I think the question of whether Pochman-style sequences can reach any position can be demonstrated with a very small number of finite sequences: 24 sequences that end with each of the 12 faces rotated by 1/5 of a turn and 2/5 of a turn and the rest of the puzzle solved. -1/5 and -2/5 can be demonstrated with the inverse of the first 24. I don't have the know-how or the hardware, but that feels like the kind of problem that could be brute-forced on a decent super-computer with a lookup table of the 1024 results of every 10-move Pochman-style scramble sequence.

Edit 2: this might not even require a supercomputer: number all 60 possible orientations of the cube, 60 locations+orientations of edges, and 60 locations+orientations of corners, and fill 3 columns for each of the 1024 10-move sequences, and sum mod 60. Not sure if that makes any sense. I blame the cows if it doesn't.

E3: Nvm E2. I think instead of 3 columns it should be 1 for centers, 30 for edges, and 20 for corners.


----------



## xyzzy (May 20, 2017)

One Wheel said:


> Using 12-face scrambles would require either a system for accurately reorienting the puzzle or 12 different mechanisms for turning faces. Pochman-style would only require rotation on two axes, with 1/6 the number of stepper motors, which will probably be the expensive part of the project.


Yeah, that's definitely true and not something I'd considered! In that sense, Pochmann-style would minimise (?) the number of motors needed.



One Wheel said:


> Edit: I think the question of whether Pochman-style sequences can reach any position can be demonstrated with a very small number of finite sequences: 24 sequences that end with each of the 12 faces rotated by 1/5 of a turn and 2/5 of a turn and the rest of the puzzle solved.


This can be done with GAP, but it doesn't look like anyone's bothered to do it in the years since Pochmann-style scrambles were introduced. What the heck, maybe I'll learn how to use GAP and do it later. One thing to note is that once you have the 1/5 turn, you don't need anything else. You can get 2/5 from applying it twice, 2/5 in the other direction from applying it thrice, and 1/5 in the other direction from applying it four times.


----------



## shadowslice e (May 20, 2017)

You could try singmaester approach (I apologise because I probably misspelled the name) And just add up the maximum move count for each step in a method to get a rough upper bound though this could well get to 500+ moves.

You could also to to find a position which you think is really hard to get to for mega (like super flip/supertwist etc) and then use k solve or something to try to optimally solve it to get another lower bound.


----------



## xyzzy (May 20, 2017)

Wow, GAP is actually pretty annoying to use.



Spoiler





```
gap> R :=
> (1, 12, 32, 53, 29)
> (2, 13, 33, 54, 30)
> (3, 14, 34, 55, 26)
> (16, 40, 60, 47, 22)
> (17, 36, 56, 48, 23)
> (18, 37, 57, 49, 24)
> (19, 38, 58, 50, 25)
> (20, 39, 59, 46, 21)
> (41, 45, 44, 43, 42)
> (61, 71, 92, 113, 88)
> (62, 72, 93, 114, 89)
> (63, 73, 94, 115, 90)
> (64, 74, 95, 111, 86)
> (78, 98, 118, 110, 84)
> (79, 99, 119, 106, 85)
> (80, 100, 120, 107, 81)
> (76, 96, 116, 108, 82)
> (77, 97, 117, 109, 83)
> (101, 105, 104, 103, 102)
> (121, 123, 127, 131, 126)
> (124, 128, 132, 130, 125)
> ;
(1,12,32,53,29)(2,13,33,54,30)(3,14,34,55,26)(16,40,60,47,22)(17,36,56,48,23)(18,37,57,49,24)(19,38,58,50,25)(20,39,
59,46,21)(41,45,44,43,42)(61,71,92,113,88)(62,72,93,114,89)(63,73,94,115,90)(64,74,95,111,86)(76,96,116,108,82)(77,97,
117,109,83)(78,98,118,110,84)(79,99,119,106,85)(80,100,120,107,81)(101,105,104,103,102)(121,123,127,131,126)(124,128,
132,130,125)
gap> D :=
> (28, 23, 18, 13, 8)
> (29, 24, 19, 14, 9)
> (30, 25, 20, 15, 10)
> (51, 46, 41, 36, 31)
> (52, 47, 42, 37, 32)
> (53, 48, 43, 38, 33)
> (54, 49, 44, 39, 34)
> (55, 50, 45, 40, 35)
> (60, 59, 58, 57, 56)
> (87, 82, 77, 72, 67)
> (88, 83, 78, 73, 68)
> (89, 84, 79, 74, 69)
> (90, 85, 80, 75, 70)
> (111, 106, 101, 96, 91)
> (112, 107, 102, 97, 92)
> (113, 108, 103, 98, 93)
> (114, 109, 104, 99, 94)
> (115, 110, 105, 100, 95)
> (120, 119, 118, 117, 116)
> (126, 125, 124, 123, 122)
> (131, 130, 129, 128, 127)
> ;
(8,28,23,18,13)(9,29,24,19,14)(10,30,25,20,15)(31,51,46,41,36)(32,52,47,42,37)(33,53,48,43,38)(34,54,49,44,39)(35,55,
50,45,40)(56,60,59,58,57)(67,87,82,77,72)(68,88,83,78,73)(69,89,84,79,74)(70,90,85,80,75)(91,111,106,101,96)(92,112,
107,102,97)(93,113,108,103,98)(94,114,109,104,99)(95,115,110,105,100)(116,120,119,118,117)(122,126,125,124,123)(127,
131,130,129,128)
gap> U :=
> (5, 4, 3, 2, 1)
> (6, 11, 16, 21, 26)
> (7, 12, 17, 22, 27)
> (65, 64, 63, 62, 61)
> (66, 71, 76, 81, 86)
> ;
(1,5,4,3,2)(6,11,16,21,26)(7,12,17,22,27)(61,65,64,63,62)(66,71,76,81,86)
gap> pochmann_rdu := Group(R, D, U);
<permutation group with 3 generators>
gap> Size(pochmann_rdu);
6040176993211400827350961938818730310121286984661186117632000000000000
gap> Factorial(20)/2 * 3^19 * Factorial(30)/2 * 2^29 * 60;
6040176993211400827350961938818730310121286984661186117632000000000000
```




If we don't restrict to 10-move sequences with 2/5 turns, then we can get all possible states (in all possible orientations). But what if we do? I'm not going to generate all 1024 possible 10-move sequences, so let's just pick three random ones and hope for the best.



Spoiler





```
gap> a := R^-2 * D^2 * R^2 * D^-2 * R^-2 * D^2 * R^-2 * D^-2 * R^2 * D^2 * U;
(1,5,4,3,45,32,49,29,24,17,22,27,7,12,19,40,43,47,42,21,26,6,11,16,37,14,58,55,50,2)(8,51,44,48,30,25,15,28,57,54,46,
41,31,10,38,59,23,18)(9,52,35)(13,20,36)(61,91,69,113,89,84,74,119,82,72,79,96,114,106,63,105,78,100,103,81,86,68,112,
95,107,102,92,109,90,80,97,73,120,83,76,98,101,93,110,62)(64,104,108,65)(66,71,118,115)(67,111,87,117,85,75,88,70,99,
77)(121,127,130)(122,131,126)(123,132,125)(124,128,129)
gap> b := R^-2 * D^-2 * R^-2 * D^2 * R^2 * D^2 * R^-2 * D^2 * R^-2 * D^2 * U;
(1,51,46,2,18,42,26,28,23,21,25,24,22,10,30,17,41,50)(3,47,35,27,7,12,55,9,6,11,16,29,52,5,4)(8,20,56,58,14,59,15,36,
33,43,40,48,31,13,39,49,32,54)(19,60,57,37,34,44,45,53,38)(62,112,65,64,106)(63,107,95,105,101)(66,71,83,81,69)(67,79,
116,118,117,85,84)(68,80,88,73,115)(70,90,87,82)(72,111,96,108,91)(74,120,119)(75,97,94,104,99,77,102)(76,89,113,98,
78)(92,114,109)(93,103,100,110)(122,124,126,123,125)(127,129,131,128,130)
gap> c := R^-2 * D^2 * R^-2 * D^-2 * R^-2 * D^2 * R^-2 * D^2 * R^-2 * D^-2 * U^-1;
(1,50,17,12,7,27,22,24,21,16,11,6,26,42,2,3,4,5)(8,59,15,48,31,54)(9,60,55,40,58,57,56,51,35,53,47,32,43,38,33,28,52,
34,29,14,49,44,39,10)(13,23,36,46,20,30)(61,110,76,71,113,68,120,75,109,92,105,65)(62,106,79,89,72,82,84,81,83,97,107,
80,90,102)(63,64,95,91,114,67,119,74,98,66,86,103)(69,116,111,96,108,93,104,99,77,87,112,94,88,73,115,100,118,117,85,
70)(121,130,124,126,129)(122,132,123,131,128)
gap> some_subgroup := Group(a,b,c);
<permutation group with 3 generators>
gap> Size(some_subgroup);
6040176993211400827350961938818730310121286984661186117632000000000000
```




Well, what do you know, we do get the full group too!


----------



## One Wheel (May 20, 2017)

xyzzy said:


> Well, what do you know, we do get the full group too!



95% of what you said went over my head (sorry) but am I understanding correctly that you have demonstrated that Pochman-style scrambles can reach any possible position on a megaminx? Sweet! Even if it's prohibitively long (4.69e73 moves as an upper bound? The last number in that post x 194 x 10 x 4.)

Your point about 1/5 being extendable to 2/5, 3/5, and 4/5 is good. I felt sure there was a way to further reduce it, but I was trying to think about applying the same algorithm to other faces instead of repeatedly to the same face. 

I was hoping, if I ever build my scrambler, to use truly random (or at least excellent pseudo-random) scrambles by generating them with colored marbles: if you need, say, 1,000 moves to reach any position, put 1,000 black marbles and 1,000 white marbles in a hopper above a photodiode, and generate the sequence from the first 1,000 marbles down the tube. I don't think I'll be going out and buying 9.38e73 marbles, but it is good to know that Pochman-style moves are likely to result in a representative scramble.


----------



## xyzzy (May 20, 2017)

One Wheel said:


> am I understanding correctly that you have demonstrated that Pochman-style scrambles can reach any possible position on a megaminx?


Yup. There's no guarantee on the length though; I tried to get GAP to generate move sequences for basic moves and it just decided to run out of memory instead, so either I'm doing something wrong or the sequences really are just too long.

I'd expect God's number with Pochmann scrambles to be on the order of 1e3 rows (so ~1e4 moves), but that's just a wild guess. Definitely nowhere as large as 5e73, though!


----------

