4x4x4 FMC (computer and human) round 2

[rokicki]

Welcome to 4x4x4 FMC round 2!

Time: May 15 to June 30 2015

When you say June 30th, is this noon June 30th in Hawaii? Or some other specific time?

It's not a big deal probably but might as well get it right; I'd hate to submit my final
solution 20 hours after the contest ended.

 

[ch_ts]

OK, let's say June 30 11:59pm GMT officially, but unofficially I'll accept solutions until I check on July 1.

 

[ch_ts]

Results

These were incredible solutions in the computer division! Both rokicki and qq280833822 found very short solutions. Very impressive solutions! In the human division, cuBerBruce defends! Well, there were no challengers but I'm sure it would have been difficult to beat him anyway, as he was sub-80 in all his solutions.

Computer Division

rokicki: 36 (35) 36 (37) 36 => 108

Spoiler

1. 2R' 2L2 B' 2U D L2 D R2 2D 2B 2L' U2 2F F' R' F' 2R 2B2 R' 2U' D' R' F' R2 U F' B2 U' D' B2 U B2 R2 B2 R B
2. 2R2 2F 2L 2D' R' D' F' 2U' 2L' 2U' F' U 2B 2R' 2F U B 2R D' L2 D2 2R U L D R' F2 D' L2 F L F2 U' R B'
3. R' F' 2U' D' 2F2 2L2 2B 2L' F D 2R' B' L2 R' 2U 2L 2F2 2R' 2F' 2R2 2F2 2L' L2 U' B2 D2 F2 R' D2 B2 D' F' U2 R' D' L2
4. R' 3Fw2 3Uw' 3R F 3U2 3Uw2 R 3Fw 2U' 3Fw' 3U' 3F' U2 3R2 3Uw' 3F 3Fw2 3U' U' R L' D L' U R B2 U' F2 U F L U D' F L F
5. 2R' F 2D' 2L2 2F' 2D 2R 2F2 U2 B2 2L2 L' 2F2 2D' R2 U' 2B D 2F' L2 R' D' F' L B2 U2 L' U2 F' R B D' R L2 U2 B2

qq280833822: (37) 37 37 37 (38) => 111

Spoiler

1. R 2L' 2U' F U' 2D2 2L B2 U' R' D' B' 2D' 2R' 2B' z R2 B' 2L2 U' 2U2 2F2
R2 F' R2 U' R2 F2 U' F2 L R B D2 R D2 F' R2
2. B 2F R' 2L B L' U' L 2U2 2B 2L2 2U B 2F2 2U z R2 D2 B2 2U2 2R2 B 2R2
F R D' B' L B2 R' U' B U L2 F' L U' F2
3. U R2 2B2 D 2D2 R F' 2U2 R2 B 2R' U2 2U 2B F U 2F2 U 2U2 F' 2U2
D L' F2 D' L2 B D R U2 L2 B' U' B U' B' U
4. 2R 2B U' 2B R B U R 2B L' 2U2 2L' U L2 2F z B' D2 F' 2L2 B 2U2
R B R D2 R2 B D' F' D L B' D R U' F D2
5. 2U2 2R F' L 2U' 2D' B' 2B U' 2R' 2F L2 F U' 2U2 F2 2L2 B' U' 2R2
R2 D' U' R' F' L' B2 R2 D' F R' F D2 R U2 F2 R2 U2

ch_ts: 50 (49) (1000) 1000 1000 => 2050

Spoiler

1. F2 2L2 2U F2 D 2F
D' 2L 2D2 D' 2R R 2D2 L
D U F' 2U2 U B 2R2 F
R2 2F2 R2 2B2 U' 2R2 F2 U' R2 2F2
D' L' D2 R2 F U R' B2 R2 B' L B L B D2 L2 F2 B2
2. F' U2 2L 2U' D2 R2 2B'
2R' R' B' 2R2 2U2 D B 2R L
B 2L2 U2 B 2R2 2U2 F
R2 2F2 2L2 D' 2F2 U' R2 2F2 2R2
F D' F' U B2 D' F' R2 B' U' F2 U F' U2 F2 R2 B

Human Division

cuBerBruce: (73) (79) 77 76 75 => 228

Spoiler

1. 2R 2U 2F' 2D' R' 2D U' D R2 D' L D R2 2F B 2L2 U 2L' U2 2L' U 2F U 2F' x2
R' U' 2L B' R2 B D' R D 2L'
U2 L 2B U' F2 B U 2B2
L' D F' L D' 2B
R' B' U F' R' F' R' F U2
L' U L F' U2
L' D2 R' B' R D2 L' F L' F' L
2. L' 2D 2R2 F2 2R F2 L 2D U' 2F R2 2F' B2 R 2D'
L 2U2 L 2U' B' 2U' y2
2R D R2 D' 2R'
L' F' U' F' 2D' L D' L' R' D2 R B' D B 2D
D 2F U B' U' 2F'
B' U' R F' U'
D' B' D B D2
F L2 F' L2 F L F'
L' B L2 B' L' B L2 B'
F U L U' L' F' L
3. L' 2F' U' 2R' R' 2U' R2 2U D' 2R L' 2U2
D 2L B U' 2L2 D2 2L U2 L D 2F2 z
2R U R2 U' F' L' F 2R'
U B 2R' F' R2 F D' R' D 2R
L2 U 2L' D' B R' D B' 2L
L' U2 L R' U R U
R2 F R B' R' F2 R B U' R' U F'
R2 F' U' B2 R' L' B U2
4. B 2R R D 2B2 D 2B' F 2L' U2 2L R F L' 2U2
R' 2U' R B2 2U2 R2 2U'
L F' 2L2 F' R' F B L B' 2L2
D L 2D' B U B' R U' R' 2D
2R F' L F 2R'
L' R2 B D' R' B2 R B
U' L' U R2 U' L U B2 R
D2 U R' D R U' R' B' R2
L' B2 L'
5. F2 2U L 2U D' 2B R2 2B'
D' 2R' U B' D' 2R' U2 2R' B2 2R D2 2R z' y2
R U 2R D' L' R D B' R B 2R'
L B2 L 2U' R D2 R' F2 U' B2 U F U' B2 F 2U2
L' U L 2U'
B2 U' B' R2 U' R B' R
B U R
F' U' F R' B R B' R' F D' L D' L'

 

[rokicki]

Writeup

Thanks for running the contest! I spent way too much time on it
but had a lot of fun. Here are my notes.

Two-phase solver for 4x4x4

My approach for this contest was to implement a two-phase solver
for the 4x4x4. The first phase finds optimal and suboptimal
reductions (move sequences that take the input position to the
subgroup (U, F, R, D, B, L)), and the second phase uses standard
3x3x3 optimal solvers to finish the solution. Only the first
phase is new work, so I will focus on that here.

I must open by saying this is not a practical 4x4x4 solver;
using a high-powered machine (16 cores) with a lot of memory
(256GB) running nearly non-stop for nearly two months, I was
able to directly find only 42 actual reduction solutions.
However, through the use of near-miss solves and derived
solves, I was able to generate more near-optimal reduction
solutions that helped me find shorter solutions.

Pruning Tables

My reduction solver used two large pruning tables, one for the
edges and one for the middles. Since each table was too
large to fit into memory, rather than using a subgroup indexing
approach, I instead used a hashing approach with collisions
to generate an inexact pruning table. I allocated four bits
per hash entry; the value in those four bits is always the
least value of all positions that hash to that value. Given a
maximum distance for hash table generation, I simply filled
each table with that distance plus one, then did an iterated
depth-first exploration from solved, hashing each position
solved and updating hash table entries along the way. For my
edge pruning table, I used 5GB of RAM, and for my middle
pruning table, I used 215GB of RAM. I explored edges out to
a distance of 10, and middles out to a distance of 10.
For both edges and middles, most entries of the hashtable
were unset by the search from solved to a depth of 10, so
for most random positions, the pruning table returned an
immediate lower bound on distance of 11.

For edges, if I had spent the time to complete a search
from solved of depth 11, I would have probably sped up the
program a fair bit; it would probably have taken about
four days to generate this table. In hindsight this
would probably have been wise; the search through depth
10 for edges only touched a total of 2.3B out of the 430B
hash table entries. I guess I was in just too much of a
hurry to get results. I may do this and see how performance
differs in the coming weeks; this may make the solver
significantly faster! Writing this at the end of the contest,
I'm disappointed I did not consider this earlier.

The hash function I used implicitly reduced the positions by
48 ways of symmetry. Also, the moves I considered were
restricted to keep a particular corner fixed, giving me an
additional reduction by a factor of 24. Details of the hash
function themselves are somewhat intricate and I would be
willing to write them up if anyone has interest.

My code is written to support the slice turn metric, block
turn metric, and outer block turn metric; I have focused on the
slice turn metric for this contest but am considering exploring
the other metrics as well.

The target subgroup for edges for my pruning table is that where
edges are matched and the total edge parity is even. (Note that
rotations and conjugation by rotations/mirroring does not change
the parity of the edge permutation.) The target "subgroup" for
middles was with each face a solid color (but not necessarily to
have the colors in a solved position). I put subgroup in
quotes because of course the middle positions do not form a
group because not all pieces are distinguishable.

Designing pruning tables is still somewhat more of an art than
a science. I considered generating one big pruning table that
combined edges and middles, but experiments showed that this
pruning table got too "wide" too quickly, and I could get better
average distances by using separate edge and middle pruning
tables. I did not fully implement and optimize a combined
pruning table so I do not have conclusive evidence that it would
be worse.

Initial Results

These are the initial results based on just using the simple
reduction solver and an optimal 3x3x3 solver with no additional
improvements. The input positions were as follows:

!: R2 F2 Rw' R D' Uw' L B' L' Rw2 R2 F Uw2 Fw F2 Rw2 B D B2 Rw' F2 Uw2
B' Rw R U Fw' Rw' U' Rw' B' D F2 U Fw' R2 B L2 Uw L2 U D R U2 Uw2
2: B' Fw' L' D F B2 Uw2 D2 R2 L Fw2 F R' Uw' Fw2 B2 Uw Rw2 F L R D U Rw
B Fw' R2 Rw2 L' D' B D' F' L2 Uw2 Rw F2 Rw2 F Fw2 U F' Rw' R U
3: Rw F' Rw2 L' Fw2 F2 B2 U' R' L Uw B' R' Rw2 B Fw L2 Rw' Uw2 B' L B2
Fw2 Rw' U Fw Rw2 B R' Uw2 R' B Uw2 B2 Fw2 F2 D' R' B2 U Rw F' R2 Rw2 L
4: B R F' D U' R' B2 D2 B' R B' D2 F' B L2 F' D2 F' U2 R2 Uw2 Rw2 L' B
U2 L' B2 Uw2 B' R' D2 B2 Uw Rw2 R2 D2 B2 U' Fw' Rw' B' F2 Uw U' R B2
U' R F2 U
5: F2 L2 B' U2 D2 R2 U2 F U F2 R B R2 D2 B D L' U Fw2 D Rw2 R Fw2 R
Uw2 F2 R2 D Rw2 D2 U' Fw F L' Fw2 Rw' Uw F' D2 Rw' B Uw2 B L B U' F2

For all positions but number 2, the optimal reduction was of length
19; for position 2, the optimal reduction was of length 20. (Surprisingly
position 2 is also the position we found the shortest solution for.)
An example optimal reduction for the moves is shown here:

1: 2R2 R B2 2U2 2F 2U 2B' 2R2 2U2 D' 2R2 2F' B' L 2F2 2D 2L2 L' 2F' (19*)
2: 2R2 2F 2L 2D' R' D' F' 2U' 2L' 2U' F' U 2B 2R' 2F U B 2R D 2L (20*)
3: 2F L2 R' 2D' F 2D' D L' 2F2 D 2L 2U' 2L' 2B B2 2R' U' D' 2F' (19*)
4: R' B2 U' 2B' R 2U2 U2 B R 2F' R' 2U 2R D2 2F2 U' 2B' B2 2U (19*)
5: 2R' F 2D' 2L2 2F' 2D 2R 2F2 U2 B2 2L2 L' 2F2 2D' R2 U' 2B D 2F' (19*)

The count of direct reductions we found (limited to those sequences
that do not end in a face turn):

    19   20    From 19   From 20  Best
1:   2   10   19+18=37  20+16=36   36
2:   0    2             20+16=36   36
3:   2   10   19+18=37  20+17=37   37
4:   2    6   19+18=37  20+17=37   37
5:   2    6   19+17=36  20+18=38   36

We completed reduction search through a depth of 19, and finished
a fair fraction (maybe 30%?) of the search through depth 20.

We optimally solved all the positions remaining after reduction,
and listed the best results in the table above (the format is
the reduction length, a plus sign, the best 3x3x3 result,
an equals sign, and then the resulting best sum. We list the
best overall result in the last column. As you can see we
were able to solve all positions in 37 or fewer moves, and
three of them in only 36 moves.

The optimal reduction solutions show that four of the five
positions have an optimal reduction length of 19. This means
it is more likely than not that the median reduction length
over all 4x4x4 positions is 19.

This result gave us an average of median 3 of 36.3, and an
overall average of 36.4. But we can do better.

Near Misses

Not all positions that were obtained by solving the edges and
middles separately but simultaneously were actually reduction
solutions. For instance, in some solutions the colors for the
middles were properly paired (for instance, the white middle was
not opposite the yellow middle). In some solutions, the middles
were properly paired, but the middles were in a mirror image
position. Finally, in some solutions, the total parity of the
corners and the combined edges was odd. When one of these
conditions was true, I considered the solution a "near miss";
this happened most of the time (about 87% of the time). Early
on, I ignored these near misses as they could not be solved
by a 3x3x3 solver. But later I found a way to exploit them.

First-phase solves always came in pairs (or larger sets).
The final move of any first-phase solve was always a slice move
(if it was not a slice move, the position before the final move
would also have been a first-phase solve). When I say slice
move I mean inner slice; an outer slice move is just a face move.
If moving an inner slice brings the position to a phase one
solution, then moving the opposite inner slice the other way
*also* brought the position to a phase one solution.
There are additional ways that first-phase solves can come in
bursts but they are less frequent so we will not discuss them
further here.

Given how much CPU time I was spending to compute the phase one
solutions, I decided to see if there was a way I could obtain
additional related solutions directly from those solutions, so
I took each phase one solution, trimmed off all but the first
eight moves, and ran it through the phase one solver again.
This generated a surprising wealth of additional solutions at
distances only a bit more than the original. The additional
solutions were not the trivial ones generated by appending
face moves, but were usefully different ones that, in some
cases, generated better overall solution lengths. Further, not
just the actual reduction solves themselves but in addition
the near misses also generated actual phase one solutions that
were only slightly longer. Finally, the additional solutions
were generated in seconds, so this was an easy way to leverage
a solution or near miss into many additional phase one solutions
that let me do more probes into phase two.

This table has a count of the phase-1 solutions found
organized by input sequence and length:

       19     20     21     22     23     24     25     26
1:      2     10    112   1498  17002  19558   7023     18
   +18=37 +16=36 +16=37 +16=38 +14=37 +14=38 +14=39 +17=43
2:      0      4     30    174   1174   2785     12      0
          +16=36 +17=38 +13=35 +15=38 +14=38 +17=42
3:      2     14    119    850   6979  25281  62431      0
   +18=37 +17=37 +16=37 +14=36 +14=37 +13=37 +13=38
4:      2     22     72    304   3037   7835   2181    490
   +18=37 +17=37 +16=37 +16=38 +14=37 +14=38 +15=40 +16=42
5:      2     16     55    535   4317   9865   2362      2
   +17=36 +17=37 +17=38 +15=37 +15=38 +14=38 +15=40 +18=44

With these additional probes we were able to find a
length 35 solution to input sequence 2 and a length 36
solution to input sequence 3.

Of course, with tens of thousands of candidate phase one
solutions, solving them all optimally with a 3x3x3 solver
would have taken a fair amount of CPU. But generally, once
an overall solution was known for the original 4x4x4
position, we no longer cared about longer solutions, so the
3x3x3 optimal solver could be instructed to only search to a
useful overall length, and give up if no such short solution
was found.

Let us deconstruct the two better solutions that were found
with this strategy. The length 35 solution to the second input
position was found as follows.

First, a length-20 reduction solution was found:

2R2 2F 2L 2D' R' D' F' 2U' 2L' 2U' F' U 2B 2R' 2F U B 2R D 2R

By trimming off two moves and running this through our reduction
solver again, we find the following reduction solution of length
22:

2R2 2F 2L 2D' R' D' F' 2U' 2L' 2U' F' U 2B 2R' 2F U B 2R D' L2 D2 2R

The phase one reduction is longer, but the 3x3x3 solution now is only
13 moves:

U L D R' F2 D' L2 F L F2 U' R B'

for a total of 35 moves.

For input 3, the process was as follows. We found the following
length-19 near-miss:

R' F' 2U' D' 2F2 2L2 2B 2L' F D 2R' B' L 2U2 2L2 2F 2D2 2L' 2U'

This near miss was rejected because of parity. But by trimming the
last seven moves and resolving with the reduction solver, we find the
following valid reduction of length 22:

R' F' 2U' D' 2F2 2L2 2B 2L' F D 2R' B' L2 R' 2U 2L 2F2 2R' 2F' 2R2 2F2 2L'

This has a 3x3x3 solution of only 14 moves, for a total of 36 moves:

L2 U' B2 D2 F2 R' D2 B2 D' F' U2 R' D' L2

Some questions remain that are worth exploring:

1. What is a good target subgroup for phase 1? I happened
to use one that ignored overall corner/edge parity
and middle color permutation, and it worked well, but
is there a larger subgroup that would provide more
opportunity to exploit near-misses for phase 2 probes?

2. Is there a better way to construct either separate or
combined hash functions for phase one search that
generates a higher overall depth, or that is faster
to compute?

3. What exactly is the relationship of all the solutions
generated by trimming and re-solving phase one
solutions and near-misses? Is there an alternative
or faster way to generate these that does not require
search?

4. Given the approximate nature of the pattern database,
what is the best way to compress this in order to
obtain higher average probe depth, without compromising
performance or random access?

 

[cuBerBruce]

Congratulations to Tom on his winning computer solutions!

Here are my explanations for my human solutions.

First, here is a summary of my solutions by phases:

Insertions for the 3x3x3 phases are counted against the 3x3x3 phase, regardless of where in the skeleton the insertion occurs.

Scramble  Total   Centers   Edge Pairing    3x3x3

    1      73       20          24           29
    2      79       21          26           32
    3      77       23          27           27
    4      76       22          25           29
    5      75       20          26           29

In the spoiler, are my detailed explanations.

Spoiler

1.
Scramble: R2 F2 r' R D' u' L B' L' r2 R2 F u2 f F2
r2 B D B2 r' F2 u2 B' r R U f' r' U' r'
B' D F2 U f' R2 B L2 u L2 U D R U2 u2

Solution: (73 = 20+24+29)
2R 2U 2F' 2D' R' 2D U' D R2 D' L D R2 2F
B 2L2 U 2L' U2 2L' U 2F U 2F' x2
R' U' 2L B' R2 B D' R D 2L'
U2 L 2B U' F2 B U 2B2
L' D F' L D' 2B
R' B' U F' R' F' R' F U2
L' U L F' U2
L' D2 R' B' R D2 L' F L' F' L

Explanation:

Reduction phase:
First center: 2R 2U
2nd center: 2F' 2D' R' 2D U' . L D 2F
(2 other centers 3/4 completed)
3rd & 4th centers: B 2L2 U 2L' U2 2L'
Last 2 centers: U 2F U 2F' x2
(2 dedges already formed)
3rd - 6th dedges: R' U' 2L (B' R2 B) (D' R D) 2L'
7th - 10th dedges: U2 L 2B (U' F2 U) (U' B U) 2B'
Last 2 dedges: 2B' L' D F' L D' 2B
L' D F' L D' 2B

3x3x3 phase:
"Scramble":
L2 U2 F' U B' U2 F U' B R L U2 R' L'
U' L U2 L2 U' L2 U' L2 U L F' U'
F U F' R' F R2 U2 R' L U2 L B2
R F' L2 B' R' F' R2

3x3x3 phase solution:
For 3x3x3 phase, use L2 premove (cancelling first move of above scramble).
2x2x2: R' B'
2x2x3: U F' R' F' R'
Pseudo F2L-1: F U2 L' U L
All but 4C, 2E: F' U2
2C2E "insertion": L' (D2 R' B' R D2 L' F L' F' L2) L
Premove correction: L2
Insertion for last 3 corners at ".": D R2 D' L D R2 D' L'
(4 moves cancel)

2.
Scramble: B2 R u r2 u' r' R' f U2 f2 B U2 u B' F
L' D' F2 u' B u2 F' u2 U F' D u f2 B U'
F' u L' u2 U' f' F' B' U2 F' f L U' B2 f2

Solution: (79 = 21+26+32)
L' 2D 2R2 F2 2R F2 L 2D U' 2F R2 2F' B2 R 2D'
L 2U2 L 2U' B' 2U' y2
2R D R2 D' 2R'
L' F' U' F' 2D' L D' L' R' D2 R B' D B 2D
D 2F U B' U' 2F'
B' U' R F' U'
D' B' D B D2
F L2 F' L2 F L F'
L' B L2 B' L' B L2 B'
F U L U' L' F' L

Explanation:

Reduction phase:
First center: L' 2D 2R2 F2 2R
(with half of opposite center solved)
2nd center: F2 L 2D U' 2F R2 2F'
3rd center: B2 R 2D'
Finish centers: L 2U2 L 2U' B' 2U' y2
(1 dedge formed)
2nd  - 3rd dedges: 2R D R2 D' 2R'
4th - 9th dedges: L' F' U' F' 2D' (L D' L') (R' D2 R) (B' D B) 2D
Last 3 dedges: D 2F U B' U' 2F'

3x3x3 phase:
"Scramble":
R' F R F D' F' B2 D' F D R' D' F' U F
D2 B U2 B2 U' B R' U R U2 B U2 B' U L'
D L U' L' D' L U2 B2 U' F' U B2 U' F

3x3x3 phase solution:
2x2x2: B' U' R F' U'
Siamese 2x2x2s: D' B' D B D2
F2L-1: F L2 F' L2 F L F'
F2L: L' B L2 B' L' B L2 B'
LL: F U L U' L' F' L

3.
Scramble: U2 D2 F' D F' u2 F L' r' U2 F' L u2 L' R'
r' D u2 L u U' R' u2 D B D' L' r' f' u'
r F' f2 r2 B2 r' U' B' R' f r F' B U' u

Solution: (77 = 23+27+27)
L' 2F' U' 2R' R' 2U' R2 2U D' 2R L' 2U2
D 2L B U' 2L2 D2 2L U2 L D 2F2 z
2R U R2 U' F' L' F 2R'
U B 2R' F' R2 F D' R' D 2R
L2 U 2L' D' B R' D B' 2L
L' U2 L R' U R U
R2 F R B' R' F2 R B U' R' U F'
R2 F' U' B2 R' L' B U2

Reduction phase:
Tricolor 2 opposite centers: L' 2F' U' 2R' R' 2U' R2 2U
3rd center: D' 2R L' 2U2
Tricolor centers: D 2L B U' 2L2 D2 2L
Finish centers: U2 L D 2F2 z
(2 dedges formed)
3rd - 6th dedges: 2R (U R2 U') (F' L' F) 2R'
7th - 10th dedges: U B 2R' (F' R2 F) (D' R' D) 2R
11th - 12th dedges: L2 U 2L' D' B R' D B' 2L

3x3x3 phase:
"Inverse scramble":
R' U' L U' B' U
R' F D2 R2 B R2 B'
D' F' D F2 D2 F D2
F R F2 R' F2 R F R' F' R F2 R'
D' F2 L D F D' F' L2 F2 L D2
U F2 D' U' L' F R' F2 L F' R F2

Inverse scramble solution:
2x2x2: U2 B' R L B2
Another 2x2x1: U F R2 F U'
Siamese 2x2x2's: R U R' . F R2
F2L-1: U' R' U' R
Edges (all but 3 corners): L' U2 L
Insert at ".": R B' R' F2 R B R' F2

4.
Scramble: L' F' U' L2 U' B L D' R' B' R2 L2 D2 F L2
F' L2 U2 R2 F2 r2 B' u2 F R f2 L' u2 r2 U2
f2 F u' R2 D B' R' L D2 f L2 f' r' u' r' R' F R' B2 R2

Solution: (76 = 22+25+29)
B 2R R D 2B2 D 2B' F 2L' U2 2L R F L' 2U2
R' 2U' R B2 2U2 R2 2U'
L F' 2L2 F' R' F B L B' 2L2
D L 2D' B U B' R U' R' 2D
2R F' L F 2R'
L' R2 B D' R' B2 R B
U' L' U R2 U' L U B2 R
D2 U R' D R U' R' B' R2
L' B2 L'

Explanation:

Reduction phase:
2 oppsosite centers: B 2R R D 2B2 D 2B' F 2L' U2 2L
3rd center: R F L' 2U2
Finish centers: R' 2U' R B2 2U2 R2 2U'
(1 dedge formed)
2nd - 4th dedges: L F' 2L2 (F' R' F) (B L B') 2L2
5th - 9th dedges: D L 2D' (B U B') (R U' R') 2D
10th - 12th dedges: 2R (F' L F) 2R'

3x3x3 phase:
"Inverse scramble":
B L2 D' F2 R' B2
F U2 F2 L F U' F2
R2 B L B2 U B U' R2
D L2 D2 B D B' D L2 D'
U' L D' R2 D L' U
D' L U' R2 U L' D

Inverse scramble solution:
Premoves (for inverse scramble): R2 L
2x2x2: L B2 L
pseudo 2x2x3: R2 B . D' R D2
F2L-1: R' B2 * R2 D
Edges: D' B' R' B2 R D B'
Premove correction: R2 L
Insert at ".": R U R' D' R U' R' D
Insert at "*": U' L' U R2 U' L U R2

5.
Scramble:
U2 B2 R' U2 R2 B2 U2 F2 R D L' D2 F U2 L'
B2 D R' B R2 f2 D F2 r2 L2 u2 D' L' D' L
B2 u2 R' f R2 B' r2 U' B' r' B u' f2 B2 L D2 B' U B U D2

Solution: (75 = 20+26+29)
F2 2U L 2U D' 2B R2 2B'
D' 2R' U B' D' 2R' U2 2R' B2 2R D2 2R z' y2
R U 2R D' L' R D B' R B 2R'
L B2 L 2U' R D2 R' F2 U' B2 U F U' B2 F 2U2
L' U L 2U'
B2 U' B' R2 U' R B' R
B U R
F' U' F R' B R B' R' F D' L D' L'

Explanation:

Reduction phase:
First center: F2 2U L 2U
Opposite centers: D' 2B R2 2B'
Centers paired: D' 2R'
Finish centers: U B' D' 2R' U2 2R' B2 2R D2 2R z' y2
First 6 dedges: R U 2R (D' L' D) (D' R D) (B' R B) 2R'
7th - 9th dedges: L B2 L 2U' (R D2 R') (F' . U' F) 2U
10th - 12th dedges: 2U L' U L 2U'

3x3x3 phase:
"Inverse scramble":
U F B' U B2 R2 F2 U'
B D R B2 D2 R2 B'
D F D F' D2 R' D' R
L' D2 L D' B D
R D R' D' B'
D B D B' L' F' D' F L D'
B R' B L2 B' R B L2 B2
D' B' D F D' B D F'

Inverse scramble solution:
Use premove (on inverse scramble): B U B2 (for fixing 2 2x2x1 blocks)
2x2x2: L D L' D F'
2x2x3: R B R' B'
F2L-1: R F' U F
Edges (leaves corner 3-cycle): R' U' B' R' B R' U R2
Premove correction: B U B2
Insert at "." (in reduction phase): F' U' B2 U F U' B2 U

 

[rokicki]

Here are my explanations for my human solutions ...

I'm completely blown away by this. I can't believe you have such short human
solutions for these positions. I can't even fathom how you found such short
solutions for just the centers.

Congratulations!

 

[cuBerBruce]

I'm completely blown away by this. I can't believe you have such short human
solutions for these positions. I can't even fathom how you found such short
solutions for just the centers.

Congratulations!

Thanks.

I figured solutions in this metric should be comparable to OBTM solutions. My solutions are generally longer than my OBTM solutions on the earlier competition. I attribute this to not spending the same amount of time as the first competition.

I note that it was proved several years ago that 22 moves is an upper bound to solve centers in this metric. (Except for the fact that this proof did not consider OLL parity.)

Finding a good centers solution largely involved a lot of trial and error. Of course, you also want to avoid "OLL parity" in this step, so you want to complete the third center having made the correct parity of inner layer moves. It is also important to get a good solution here, as the other steps will need to be totally redone if you decide to change the centers solution.

Some other techniques I tried.

Try to preserve any paired up centers - 2 adjacent (not diagonally) center pieces of the same color. (But this can also end up adding too many moves.) Getting 3 pieces of the same color on a face can also be beneficial.

Using insertions.

Getting opposite-face colors on the same face.

After getting a centers solution, try changing the order of consecutive face moves. This does not get a shorter centers solution, but may allow you to get more edges paired up for free.

Using inserted moves.

For example, for scramble 4, the start:
2R R D 2B2 D 2B' F 2L' U2 2L R F L' 2U2 R' 2U' R B2 2U (19)

appears to require something like R' 2U R2 2U to finish, resulting in a 23-move solution.

2R R D 2B2 D 2B' F 2L' U2 2L R F L' 2U2 R' 2U' R B2 2U R' 2U R2 2U' (23)

But adding the move B at the beginning allows the ending to be changed to 2U R2 2U'.

This simplifies to:

B 2R R D 2B2 D 2B' F 2L' U2 2L R F L' 2U2 R' 2U' R B2 2U2 R2 2U' (22)

Thus, the inserted move allowed a net reduction of one move. Note that the back face after the scramble had two colors represented in the center pieces. These corresponded to the last two colors solved. Turning the back face had the "visible effect" of swapping two of the center pieces. Using the right "swap" allowed a more efficient ending.

 

[ch_ts]

Ha, I noticed in rokicki's writeup he stopped saying "I" and started saying "we" to mean "me and my machine"

In my opinion, cuBerBruce's solutions are especially strong in the edge-pairing step. I think I could match him on the centers and maybe in 3x3x3 (if I spend enough time), but not in edge-pairing. Dunno, it seems easy seeing his solutions...

 

[cuBerBruce]

In my opinion, cuBerBruce's solutions are especially strong in the edge-pairing step. I think I could match him on the centers and maybe in 3x3x3 (if I spend enough time), but not in edge-pairing. Dunno, it seems easy seeing his solutions...

Of the 3 basic phases (centers, edge pairing, 3x3x3), I estimate edge pairing is where I spend the least amount of time.

Some basic techniques/principles I use in edge pairing:

1. Use any axis for "slicing." Choose the axis separately for each n-at-a-time pairing sub-step.

2. Try to find pairs that are already "set up" for pairing. In my solution for the 3rd scramble, I not only was able to get 2 dedges for "free" during centers solving, but I also was set up for immediate "slicing" into a 4-at-a-time pairing sub-step. In only 8 moves, I was "half done" with edge pairing. You need to look for these "lucky" situations.

3. Extending the preceding point, always look for setting up pairs (particularly in the front end) that can be set up in the least number of moves.

4. Try to get paired edges for "free" during centers solving as I mentioned in my previous post. If it takes on average 2.5-3 moves to do each pairing, getting 2 dedges for "free" saves about 5-6 moves during edge pairing.

5. 6-at-a-time pairing may not be all that great a strategy. The third pair on the front end always takes (at least) 3 moves to set up (unless you get cancellations), and you generally have 9 or more moves total (barring cancellations) for the three pairs on the back end (not counting the "slicing back").

6. On the front end, you generally have two choices for which edge pair to set up for the 2nd pair. The same holds for the third pair if you do 6-at-a-time pairing. Choose the one that can be set up most efficiently.

7. In speedsolving, you generally set up the pairs on the back end in a specific order. (You "store" the front end pairs in a specific order). In FMC you have no need to do these in a specific order once you know what needs to go where. This may help get cancellations or avoid bad 4-move setup cases.

8. Avoid 4-move setups for a single pair. Choose a different pair to set up or choose to do fewer "at a time" to avoid the bad case.

9. Of course, avoid PLL parity at the end of edge edge pairing. If you get to a point where you have two dedges left, the algorithm 2D' L' F U' L F' U 2D or its mirror (2D R F' U R' F 2D') will work (this of course assumes the unpaired edges are at FL and FR with the pairs horizontal, not diagonal).

10. Don't just do one edge pairing attempt. Do a few attempts and take the best one (or possibly one that leaves a good starting point for the 3x3x3 phase).

As for 3x3x3 solving, I am not very good at finding sub-30 solutions very quickly. I typically took several hours to find each sub-30 solution. Good FMCers these days seem to be usually able to come up with sub-30 solutions within an hour, and perhaps not just sub-30, but often down in the 24-27 range as well.

 

[ch_ts]

This is what I do (when not using cmowla's reduction method) :

Centers
1. Remove 2 opposite centers from 2 faces. Let's say white/yellow. Remove white/yellow from L and R faces, so they're on F, U, B, D.
2. Make 1x2 blocks stashing them in one slice (say 2L) when necessary.
3. Make 2x2 centers by merging the 1x2 blocks. Let's say I put them on U and D
4. 3rd and 4th centers. Let's say I'm doing green and red. Make 1x2 blocks alternating green/red/green/red on R, F, L, B. If I need to solve orientation parity, put the 1x2 blocks in a slice (say 2D slice) and do an extra 2U (or Uw). Then turn two of the blocks into the U slice, do 2U2 (or Uw2)
5. Do 5th and 6th centers.

Goals:
centers: 20 moves.
centers + edge pairing together: 50 moves.
3x3x3: 30 moves.

 

[Herbert Kociemba]

My congratulation too to the three contestants, 36/37 moves in the computer division on average and 76 moves in the human division are absolutely amazing!
I hope the three phase solver I am developing will give some solutions which are not too far away from 40 moves. Phase 1 which I consider the hardest already works, it puts the cube into a position which is generated by <U,R,D,L,F2,B2,2U2,2R2,2D2,2L2,2F2,2B2>. I did not encounter a position which needed more than 14 moves for this step. Phase 2 is on the way, it puts the cube into <U,R,D,L,F2,B2>. In phase 3 there is a 3x3x3 cube left with already fixed edge orientations which wil take about 17 moves to solve on average. We will see how suboptimal solutions contribute to better overall solutions with this approach.

 

[Christopher Mowla]

I also would like to congratulate all contestants. The computer solution move-counts are breath-taking, and Bruce's human solution move-counts are very nice as well.

 

[rokicki]

Ha, I noticed in rokicki's writeup he stopped saying "I" and started saying "we" to mean "me and my machine"

I wish I could say we had been so clever! It's just poor writing.

I also want to correct a few things I have wrong in that writeup. The distance-10 positions in the middle
pruning table numbered 45B, not 4.5B, so extending the table to include distance-11 positions would
not have been useful (as almost all table entries would have been set to 11, so very few table entries
would have a value of 12).

There's a number of ways I can proceed from here. Perhaps the most natural is to simply use the
reduction solver to optimally find reductions for a larger set of random positions, and gather some
statistics on that distribution. Another is to try to determine what near-misses are most productive
in terms of generating actual reductions that are only slightly longer.

Certainly gaining more confidence in the "median of 19" solution length for reduction is worthwhile as
this sets a clear target for solvers that use reduction built out of more than one stage.

 

[ch_ts]

I hope the three phase solver I am developing will give some solutions which are not too far away from 40 moves. Phase 1 which I consider the hardest already works, it puts the cube into a position which is generated by <U,R,D,L,F2,B2,2U2,2R2,2D2,2L2,2F2,2B2>. I did not encounter a position which needed more than 14 moves for this step. Phase 2 is on the way, it puts the cube into <U,R,D,L,F2,B2>. In phase 3 there is a 3x3x3 cube left with already fixed edge orientations which wil take about 17 moves to solve on average. We will see how suboptimal solutions contribute to better overall solutions with this approach.

My estimate is this will result in solutions about 42 moves. It's a guess (but not total guess).

One of the variations I tried does your 1st phase in 2 steps, and your 2nd phase in 2 steps also, and then puts the cube into <U,D,F,B,R2,L2>. For example, for scramble 3 I have for reduction:
U 2F2 R2 2B' F' 2U D2 2L' F L U 2R R2 B 2L
B' D2 B' 2U2 F2 2U2 2R2 F R2 2R2 U2 2L2 2F2 2R2 R2 U' 2L2
and then the cube is in <U,D,F,B,R2,L2>.
view

 

[Herbert Kociemba]

My estimate is this will result in solutions about 42 moves. It's a guess (but not total guess).

One of the variations I tried does your 1st phase in 2 steps, and your 2nd phase in 2 steps also, and then puts the cube into <U,D,F,B,R2,L2>. For example, for scramble 3 I have for reduction:
U 2F2 R2 2B' F' 2U D2 2L' F L U 2R R2 B 2L
B' D2 B' 2U2 F2 2U2 2R2 F R2 2R2 U2 2L2 2F2 2R2 R2 U' 2L2
and then the cube is in <U,D,F,B,R2,L2>.

Did you use suboptimal solutions from phase1/2 to get shorter solutions in phase 3/4?

The search space of my phase 2 (your phase 3/4) is quite small and you could try to do this in one step. In phase 2 I use two coordinates: an "edge pairing" coordinate with a "raw" index from 0..12!/2, reduced by 16 symmetries the index runs from 0..14999139 and a center coordinate. I built the pruning table for "edge pairing" coordinate today and the maximum depth is 13 with an average of about 10-11 moves. So we have the preliminary result that edge pairing alone can always be done with 13 moves in phase 2.
The center coordinate for phase 2 should have 70*70*6 entries, but I have not implemented this coordinate yet.

 

[Herbert Kociemba]

I finished the coding of the phase 2 now too. The center coordinate for phase 2 has not 70*70*6 but 70*70*12 values btw. Without using suboptimal solutions, just taking the first solution of each phase I got the following for scramble 1:
3F 3U 2R2 3U 3u 3R2 3U 3F2 R 3U2 3f' 2U 3R .U L' F2 U 2B2 B2 2U2 D' 2F2 U L U' 2R2 .L' U' R' B2 L2 D L' U' L2 U L U D2 F2 D2 L2
The total length is 13+13+16=42. Using suboptimal solutions a < 40 move solution should be no problem.

Also 13/13/16 for scramble 4:
3f 3U2 R' 3r' 3F' 2U' F' R' U 2R F 3R2 3F.B2 U2 2L2 L 2D2 D B2 R' 2L2 2F2 B2 L 2U2.F2 L2 U2 D R2 D F2 R' L2 D2 B2 L2 F2 U' F2 R2

 

[Herbert Kociemba]

I tried if and how good a solution I get if applying the phase 1 and phase 2 solver to the single dedge flip. Using just the first solution which popped out for phase 1 and then applying phase2 solutions until the cube was compeletly solved I found the following 9+12=21 and move solution

2R U2 2R2 F2 U2 2R' U2 F2 2RU R2 2B2 R2 U 2R2 U' R2 2B2 R2 U 2R2

Another 9+11 solution is

2R U2 2R2 F2 U2 2R' U2 F2 2R' U 2F2 R2 2F2 U 2R2 U' 2F2 R2 2F2 U

Using suboptimal phase 1 solutions I found a 11+8 solution:

3u 2F' R2 3u2 2F' 3u2 R2 3u' 2R2 U2 2R'U' R2 U 2R2 U' R2 U' 2R2

... and a 11+7 solution:
2R F2 2R' F2 2R U2 2R2 F2 2R' F2 2R'2U2 F2 2R2 F2 U2 2R2 2U2

 

[ch_ts]

No I didn't try that... I think I may revisit my solver, there are some changes I'd like to make with it.

 

[Herbert Kociemba]

I let the dedge flip solver run over night and now found a 12 + 5 = 17 move solution in SSTM and STM for the single dedge flip

U2 3R' F2 3R U2 3R' U2 2R2 F2 3R U2 2RD2 F2 2L2 F2 D2

I hope this is quite remarkable because in https://www.speedsolving.com/wiki/index.php/4x4x4_Parity_Algorithms#One_Dedge_Flip I see only a single dedge flip algorithm which is 17 moves in STM but it is more in SSTM.

 

[rokicki]

I let the dedge flip solver run over night and now found a 12 + 5 = 17 move solution in SSTM and STM for the single dedge flip

U2 3R' F2 3R U2 3R' U2 2R2 F2 3R U2 2RD2 F2 2L2 F2 D2

I hope this is quite remarkable because in https://www.speedsolving.com/wiki/index.php/4x4x4_Parity_Algorithms#One_Dedge_Flip I see only a single dedge flip algorithm which is 17 moves in STM but it is more in SSTM.

Wow, only a 15-move reduction! That should be easy for my program; I should have
been able to find this with my new reduction solver fast enough.

I'm going to have to try running through a bunch of last-layer positions and see what
I can do. Is OBT or SST more interesting for this?

Congratulations, Herbert.