One Wheel
Member
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?
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?