Kilominx God's number bounds

Discussion in 'Puzzle Theory' started by xyzzy, Dec 20, 2017.

Welcome to the Speedsolving.com. You are currently viewing our boards as a guest which gives you limited access to join discussions and access our other features. By joining our free community of over 30,000 people, you will have access to post topics, communicate privately with other members (PM), respond to polls, upload content and access many other special features. Registration is fast, simple and absolutely free so please, join our community today!

If you have any problems with the registration process or your account login, please contact us and we'll help you get started. We look forward to seeing you on the forums!

Already a member? Login to stop seeing this message.
  1. xyzzy

    xyzzy Member

    919
    440
    Dec 24, 2015
    tl;dr: between 16 and 46 moves (inclusive).

    The kilominx has (19!/2) ⋅ 3^18 ~ 24 septillion states (with a fixed corner), which is well beyond what we can exhaustively enumerate. Even with full symmetry+antisymmetry reduction, that's still around 98 sextillion states, which is a lot larger than the number of 3×3×3 states without any symmetry reduction. (You know a number is large when the spelling checker thinks that it's not a real word.)

    This first post will be about an upper bound. (Lower bound analysis to come later, but for now you can have the "trivial" lower bound of 16 moves by counting move sequences without immediate cancellations.) We divide solving the kilominx into two phases, given by the following chain of subgroups: $$G_0:=\langle\text{all 12 moves}, \text{rotations}\rangle$$, $$G_1:=\langle U,R,F,D,DB,DBL\rangle$$, $$G_2:=\langle\rangle$$. For this, we do not use a fixed corner, so $$G_0$$ includes all 20!/2 even permutations of the corners. Further, while rotations can be done solely with face turns, keeping the "core" fixed, we explicitly include them in the generating set and treat them as free moves (i.e. rotations don't contribute to the move count).

    Phase 1: separation

    Note that $$G_1=\langle U,R,F,D,DB,DBL\rangle=\langle U,R,F\rangle\times\langle D,DB,DBL\rangle$$. This effectively divides the puzzle into two disjoint "hemispheres" that don't interact, centred at the U-R-F and D-DB-DBL corner pieces. For convenience, call these the north and south hemispheres, respectively. The right coset space $$G_1\backslash G_0$$ can be treated as a vector of 20 bits corresponding to whether each corner piece belongs to the south hemisphere in the solved state, along with an additional value in $$\mathbb Z/3$$ corresponding to the sum of the orientations of the 10 pieces belonging to the south hemisphere. In other words, this phase is equivalent to separating the pieces into the hemispheres they belong to, and ensuring that the corner orientation within each hemisphere adds up to 0.

    EDIT: This is slightly wrong because I forgot about parity, but I don't have time to fix it right now. See qqwref's post later in this thread. The overall upper bound is unaffected, but the average move count increases slightly.

    The coset space has $$\binom{20}{10}\cdot3=554268$$ cosets, but there is no need to consider the whole coset space. Firstly, we don't even need to care about corner orientation here; once the corners are separated into the hemispheres, we can change the total corner orientation within each hemisphere (without affecting the separation) by just rotating around the U-R-F corner. Secondly, it doesn't matter whether the pieces are all moved to the correct hemispheres; we could also have them all moved to the wrong hemispheres and then rotate the puzzle to put them in the correct hemispheres. This reduces the number of cases to consider to $$\binom{20}{10}/2=92378$$.

    depth# reduced cosets
    010
    1240
    24050
    326890
    452552
    58616
    620
    Average: 3.707
    Upper bound: 6

    Phase 2: two 3-gen solves

    The $$\langle U,R,F\rangle$$ subgroup, while much smaller than $$G_0$$, is still pretty large, having 36 billion states. It's small enough that a full breadth-first search can be done if symmetry+antisymmetry reduction is used, but I will leave this for another time.

    Anyway, we can split this into solving orientation then permutation; for this, I used the same definition of orientation as in my solver. Unlike on a 2×2×2, it's not possible to define orientation in terms of a subgroup generated by single moves (e.g. you can't just say something like "the orientation defined by ⟨U, R2, F2⟩"). Here, we choose reference stickers on each of the corner pieces by taking the one that is closest to perpendicular to the U-D axis; equivalently, corner orientation is preserved by U, (R' F R F')3, flip and y. (There's a different choice of reference stickers that is more symmetrical when restricted to $$\langle U,R,F\rangle$$, which would make implementing symmetry/antisymmetry reduction easier.)

    Orientation:
    depth# cosets
    01
    18
    261
    3452
    42674
    59182
    67070
    7235
    Average: 5.19
    Upper bound: 7

    Permutation:
    depth# states
    01
    14
    46
    556
    6190
    7746
    84727
    925251
    10140966
    11602085
    12944543
    1395825
    Average: 11.510
    Upper bound: 13

    (The distribution for the orientation substep is done with a standard breadth first search, but the distribution for the permutation step was computed by doing an IDA* search on each of the 10!/2 states with pieces already oriented. It's not possible to use a BFS to directly compute the latter distribution, as most moves disturb corner orientation.)

    This gives an upper bound of 20 moves for $$\langle U,R,F\rangle$$, and since $$G_1$$ is just two copies of $$\langle U,R,F\rangle$$, the upper bound for phase 2 as a whole is 40 moves.

    To conclude, this gives an upper bound of 46 moves for solving a kilominx.

    depth# states
    00
    10
    20
    31
    40
    53
    610
    787
    8671
    95453
    1040232
    11245288
    12600187
    13108065
    143
    Average: 11.763

    These are the three 14-move states (or, well, the inverses of these, but same thing):
    U R U2' R2' F' U2 F' U2' R F2 R2 U' R2 U'
    U R2 U2 R2 F' U R F' R2' F2' U2' R2' U' F2
    U R U2' F2' U2' R F' R F U2 R2 F2' R2 U2'

    These can probably be solved in fewer moves if we allow moves other than just U, R and F. (I don't have a full optimal solver yet.)
    Ignoring orientation, there are 284 permutations at depth 9 (and none at depth 10). Solving all 284×3^9 states with those permutations, we get this distribution:
    depth# states
    918648
    10175957
    111239372
    123447704
    13707850
    14441
    Average: 11.832

    The proportion of 14-movers in this specially chosen sample is much higher than in a uniform random sample. All of these 14-movers are local maxima, and most are "strict" local maxima (in the sense that every legal move brings it to depth 13). Up to symmetry, there's one 14-mover among these that isn't a strict local maximum, and it's one move away from a 14-mover not among those; this new 14-mover is also a local maximum and isn't adjacent to any other 14-movers.

    This very strongly suggests that the actual diameter should be 14 moves, which would bring the overall upper bound down to 6+14+14=34 moves.

    On another note, my current kilominx random state scrambler uses different solving phases and has a move count of 27.8±1.3 moves. The scrambling/solving is done with "hemisphere notation", which includes the U, R, F, L, BL and BR moves, in addition to flipping the whole puzzle over (i.e. rotating 180 degrees around the left-right axis), denoted as either "x2" or "flip". Since scramble sequences are meant to be applied by human scramblers, minimising rotations was a design goal, and the solving method used outputs a maximum of two flips per scramble. (Furthermore, we want to avoid "weird" rotations, because that would require additional scrambling notation, and the simpler the notation, the less likely scrambling mistakes are; to that end, flipping is the only type of rotation used.)

    While the phases used in this post would lead to a slightly lower average move count (3.707+11.763+11.763 = 27.233 moves), the first phase makes use of arbitrary rotations while separating the pieces, which is extremely undesirable.
     
    Last edited: Feb 12, 2018 at 1:08 AM
  2. jaap

    jaap Member

    30
    0
    Sep 22, 2009
    Netherlands
    WCA:
    2003SCHE01
    YouTube:
    jaapsch2
    Did you count (R' F R F')3 as 4 moves?
     
  3. xyzzy

    xyzzy Member

    919
    440
    Dec 24, 2015
    That move sequence would be counted as 12 moves. (Not actually used in the solver, but to demonstrate the moves that preserve corner orientation.)
     
  4. jaap

    jaap Member

    30
    0
    Sep 22, 2009
    Netherlands
    WCA:
    2003SCHE01
    YouTube:
    jaapsch2
    Ok. I was a bit confused by your permutations calculation, as it has to preserve orientations, but presumably then you didn't just use a breadth first search using the orientation preserving generators you listed. Did you do a breadth first search using single moves and just filter from the output the ones that had the wrong orientation? Or did that take too long and you had to tackle the deeper positions separately with separate searches?
     
  5. xyzzy

    xyzzy Member

    919
    440
    Dec 24, 2015
    Right, I should've elaborated on this. I solved all of the 10!/2 positions with oriented pieces with IDA*. For example, this is one of the solutions produced: F' R' F2' R2' U2 F2' U2 R U2 R2' U. Each solve takes ~4 milliseconds, so this "brute force" approach took only around two hours to complete.
     
  6. jaap

    jaap Member

    30
    0
    Sep 22, 2009
    Netherlands
    WCA:
    2003SCHE01
    YouTube:
    jaapsch2
    Cool. Anyway, this is really good work. I like the clever reductions due to the rotations of the whole puzzle.

    Have you tested the neighbours (and neighbours of the inverses) of the three depth 14 positions you found in <U,R,F>? It's unlikely to result in a depth 15 position, but it is worth checking.
     
  7. xyzzy

    xyzzy Member

    919
    440
    Dec 24, 2015
    Oh, I didn't think of that. Just ran the solver on the neighbours, and those three positions and their inverses are local maxima (every move brings them to depth 13).

    Funny thing is, I originally had this idea for megaminx, where you cannot use these "automatic symmetry reductions" because of the fixed centres. (And on a megaminx, G_1\G_0 is a much larger coset space because of the edges.) Still trying to figure out what's a good way of upper-bounding megaminx god's number that isn't just "build blocks, then more blocks, etc. etc.". I have some vague ideas, but they would be tricky to implement.
     
  8. qqwref

    qqwref Member

    7,830
    30
    Dec 18, 2007
    a <script> tag near you
    WCA:
    2006GOTT01
    YouTube:
    qqwref2
    Ben Whitmore recently computed God's Algorithm on the <U,R,F> subgroup and God's Number is 14. So the whole puzzle can be solved in at most 34 moves.
    http://cubezzz.dyndns.org/drupal/?q=node/view/560

    EDIT: Hey xyzzy, if you see this, it doesn't sound like you considered permutation parity in the separation step. That is, each half must have even permutation. Can you try doing the computation taking that into account? One way might be, for each coset, continue searching for separation algorithms until you find two where the permutation parities of the "top hemisphere" pieces differ. Then one of those two will solve one permutation-parity version of that coset and the other will solve the other, even though you don't know which is which. You can check for differing hemisphere permutations on a puzzle with all pieces distinct, but the search can still be done in the coset space.
     
    Last edited: Feb 11, 2018
    DGCubes likes this.
  9. xyzzy

    xyzzy Member

    919
    440
    Dec 24, 2015
    Oh dang, you're right. There's a way to incorporate the permutation parity into the separation directly and I've done this before (for the Redi Cube solver/scrambler). I don't know why I suddenly just forgot about it…

    Will rerun the code and post results shortly.

    Edit: Take 2! This is the fixed move distribution for the separation step, now taking parity into account:

    depth# reduced cosets
    020
    1480
    29480
    386960
    4223808
    548684
    680
    Average: 3.841
    Upper bound: 6

    Upper bound remains unchanged, which is nice to know. I didn't feel like wrapping my head around whether some of the symmetry I exploited in the original post was valid with parity taken into consideration, so this only does the "corner twist" symmetry reduction and has $$\binom{20}{10}\cdot2$$ reduced cosets.

    Also interesting to note is that the depth-6 positions are the same regardless of whether parity is taken into account. (The original (incorrect) table lists 20 reduced cosets and this one lists 80 reduced cosets; this factor-of-four difference comes from using less symmetry reduction (2) and including parity (2).)
     
    Last edited: Feb 13, 2018 at 2:28 AM
    muchacho, qqwref and DGCubes like this.
  10. qqwref

    qqwref Member

    7,830
    30
    Dec 18, 2007
    a <script> tag near you
    WCA:
    2006GOTT01
    YouTube:
    qqwref2
    Thanks, cool stuff! Ben Whitmore has also computed <R,U,F> in qtm:
    DepthNewTotal
    011
    167
    23037
    3144181
    4696877
    533604237
    61617620413
    77752097933
    8369444467377
    917522042219581
    10825439010473971
    113849008748964058
    12176067961225032019
    13772274582997306601
    1430621700564059476657
    15943999232913499468986
    161562815683629127625822
    17643341658435561042406
    1815179055135712832957
    19224335712835200
    Would you mind computing separation in qtm as well?
     
  11. xyzzy

    xyzzy Member

    919
    440
    Dec 24, 2015
    Clearly we should unban Ben and let him post here directly…

    My BFS code doesn't directly support "qtm" but it shouldn't be too hard to add that. (In class now; will do later.)

    Edit: Separation + parity, qtm.

    depth# reduced cosets
    020
    1240
    22460
    316640
    469644
    5144740
    6119688
    7160000
    880
    Combined with Ben's upper bound of 19q for ⟨R,U,F⟩, this gives a bound of 46q in total. (Incidentally, the same as my original bound for FTM…) It'd be nice to get independent verification for this, since I haven't tested this BFS function in an actual solver.
     
    Last edited: Feb 13, 2018 at 4:52 AM
    DGCubes likes this.

Share This Page