4x4x4 God's Number Position Hunt

[rokicki]

How much CPU time to search through depth 16?

Days and days (but just one thread). Since the patterns were "nearly" solved,
my pruning tables didn't help too much though, and I also don't think I used the
best pruning tables. I think if I use multiple threads and start with more random
positions, I can probably get a few more plies.

I may even be able to contrive a position that is as deep as my pruning tables
go, specifically to try to get an easy position to prove deep.

And if I can ensure the position has enough symmetry, I can probably get a bit
deeper yet.

But my 4x4 code is probably not nearly as advanced or mature as other
posters on this site.

 

[unsolved]

But my 4x4 code is probably not nearly as advanced or mature as other
posters on this site.

I use a 6 separate 64-bit variables to represent the 4x4x4 cube. That way, I can use very fast bit-operations to generate moves, rather than more expensive matrix updates. Example:

BITBOARD_4x4x4_CUBE T_PLUS(BITBOARD_4x4x4_CUBE original_4x4x4_cube)
{
BITBOARD_4x4x4_CUBE new_cube;

/**************************************************************************/
/* Rotating the top will change something on every face except the bottom */
/**************************************************************************/
new_cube._4x4x4_bottom = original_4x4x4_cube._4x4x4_bottom;

/******************************************************************************************/
/* Entire row of cubes moves from right -----> front -----> left -----> back -----> right */
/* new front = old right; new right = old back; new back = old left; new left = old front */ 
/******************************************************************************************/
new_cube._4x4x4_front = (original_4x4x4_cube._4x4x4_front & BITMASK_CUBE_FACE_NOT_ROW_01) | (original_4x4x4_cube._4x4x4_right & BITMASK_CUBE_FACE_ROW_01);
new_cube._4x4x4_right = (original_4x4x4_cube._4x4x4_right & BITMASK_CUBE_FACE_NOT_ROW_01) | (original_4x4x4_cube._4x4x4_back  & BITMASK_CUBE_FACE_ROW_01);
new_cube._4x4x4_back  = (original_4x4x4_cube._4x4x4_back  & BITMASK_CUBE_FACE_NOT_ROW_01) | (original_4x4x4_cube._4x4x4_left  & BITMASK_CUBE_FACE_ROW_01);
new_cube._4x4x4_left  = (original_4x4x4_cube._4x4x4_left  & BITMASK_CUBE_FACE_NOT_ROW_01) | (original_4x4x4_cube._4x4x4_front & BITMASK_CUBE_FACE_ROW_01);

/*********************************************************************************/
/*                                 Rotate the TOP                                */
/*********************************************************************************/
/*                                                                               */
/* THESE CUBE LOCATIONS BECOME....              THESE CUBE LOCATIONS             */
/*                                                                               */
/*                                                                               */
/*********************************/             /*********************************/
/*  01   *  02   *  03   *   04  */             /*  13   *  09   *  05   *   01  */
/*********************************/             /*********************************/
/*  05   *  06   *  07   *   08  */             /*  14   *  10   *  06   *   02  */
/*********************************/             /*********************************/
/*  09   *  10   *  11   *   12  */             /*  15   *  11   *  07   *   03  */
/*********************************/             /*********************************/
/*  13   *  14   *  15   *   16  */             /*  16   *  12   *  08   *   04  */
/*********************************/             /*********************************/
/*                                                                               */
/*                                                                               */
/*********************************************************************************/

new_cube._4x4x4_top = ((original_4x4x4_cube._4x4x4_top & BITMASK_CUBE_FACE_SQUARE_13) << 48)  | \
						((original_4x4x4_cube._4x4x4_top & BITMASK_CUBE_FACE_SQUARE_09) << 28)  | \
						((original_4x4x4_cube._4x4x4_top & BITMASK_CUBE_FACE_SQUARE_05) << 8)   | \
						((original_4x4x4_cube._4x4x4_top & BITMASK_CUBE_FACE_SQUARE_01) >> 12)  | \
						((original_4x4x4_cube._4x4x4_top & BITMASK_CUBE_FACE_SQUARE_14) << 36)  | \
						((original_4x4x4_cube._4x4x4_top & BITMASK_CUBE_FACE_SQUARE_10) << 16)  | \
						((original_4x4x4_cube._4x4x4_top & BITMASK_CUBE_FACE_SQUARE_06) >> 4)   | \
						((original_4x4x4_cube._4x4x4_top & BITMASK_CUBE_FACE_SQUARE_02) >> 24)  | \
						((original_4x4x4_cube._4x4x4_top & BITMASK_CUBE_FACE_SQUARE_15) << 24)  | \
						((original_4x4x4_cube._4x4x4_top & BITMASK_CUBE_FACE_SQUARE_11) << 4)   | \
						((original_4x4x4_cube._4x4x4_top & BITMASK_CUBE_FACE_SQUARE_07) >> 16)  | \
						((original_4x4x4_cube._4x4x4_top & BITMASK_CUBE_FACE_SQUARE_03) >> 36)  | \
						((original_4x4x4_cube._4x4x4_top & BITMASK_CUBE_FACE_SQUARE_16) << 12)  | \
						((original_4x4x4_cube._4x4x4_top & BITMASK_CUBE_FACE_SQUARE_12) >> 8)   | \
						((original_4x4x4_cube._4x4x4_top & BITMASK_CUBE_FACE_SQUARE_08) >> 28)  | \
						((original_4x4x4_cube._4x4x4_top & BITMASK_CUBE_FACE_SQUARE_04) >> 48);

return new_cube;
}

The above executes the move U. It is only 6 lines of code (though the last one is long, it still executes quickly).

I have also been experimenting with the concept of the Compound Move. There is nothing that says you can't code how move pairs, triplets (or more) change the cube in one fell swoop. I am writing a bit monitoring routine that will write the C-code for me so that I can handle U R, U R', U R2, U F, U F', U F2.... U B, U B', U B2 etc as one move generator call. It complicates the dispatch function and the list of Procedure Pointers grows in proportion to the node count at the equivalent search depth, but in the case of move pairing you are guaranteed to double the speed of the move generator.

Edit:

Here are the numbers I get for the 4x4x4 "canonical sequences" possible as a function of depth.

 

[Christopher Mowla]

Can someone run this position through his solver? I'm curious what the upperbound is for this 4x4x4 position.

Note that the generating scramble is in old WCA notation!
L2 F r2 B2 U l2 U' l2 U l2 U' B2 r2 F' x l2 U F L U R2 F r2 F' R2 U' L' F' U' l2 x F2 U' l' r' U F' L U' F l r F' U L' F' x2 L2 x L' F d2 F' L U2 L' F d2 F' L U2 x' F2 d B2 R' f' R B2 R' f R d' F2

 

[rokicki]

Can someone run this position through his solver? I'm curious what the upperbound is for this 4x4x4 position.

Note that the generating scramble is in old WCA notation!
L2 F r2 B2 U l2 U' l2 U l2 U' B2 r2 F' x l2 U F L U R2 F r2 F' R2 U' L' F' U' l2 x F2 U' l' r' U F' L U' F l r F' U L' F' x2 L2 x L' F d2 F' L U2 L' F d2 F' L U2 x' F2 d B2 R' f' R B2 R' f R d' F2

What metric would you like? I can do outer block turn, single slice turn, or block turn.

 

[Christopher Mowla]

What metric would you like? I can do outer block turn, single slice turn, or block turn.

OBTM (since this is the metric you all are first shooting for with god's number). Thank you very much!

 

[rokicki]

Can someone run this position through his solver? I'm curious what the upperbound is for this 4x4x4 position.

Note that the generating scramble is in old WCA notation!
L2 F r2 B2 U l2 U' l2 U l2 U' B2 r2 F' x l2 U F L U R2 F r2 F' R2 U' L' F' U' l2 x F2 U' l' r' U F' L U' F l r F' U L' F' x2 L2 x L' F d2 F' L U2 L' F d2 F' L U2 x' F2 d B2 R' f' R B2 R' f R d' F2

Did I transcribe this correctly? Is this what it looks like in SiGN notation?

2L2 2F 2R2 B2 U 2L2 U' 2L2 U 2L2 U' B2 2R2 2F' x 2L2 U 2F 2L U 2R2 2F 2R2 2F' 2R2 U' 2L' 2F' U' 2L2 x 2F2 U' 2L' 2R' U 2F' 2L U' 2F 2L 2R 2F' U 2L' 2F' x2 2L2 x 2L' 2F 2D2 2F' 2L U2 2L' 2F 2D2 2F' 2L U2 x' 2F2 2D B2 2R' 2F' 2R B2 2R' 2F 2R 2D' 2F2

I notice the corners and four edges are fully solved.

 

[Christopher Mowla]

Did I transcribe this correctly? Is this what it looks like in SiGN notation?

2L2 2F 2R2 B2 U 2L2 U' 2L2 U 2L2 U' B2 2R2 2F' x 2L2 U 2F 2L U 2R2 2F 2R2 2F' 2R2 U' 2L' 2F' U' 2L2 x 2F2 U' 2L' 2R' U 2F' 2L U' 2F 2L 2R 2F' U 2L' 2F' x2 2L2 x 2L' 2F 2D2 2F' 2L U2 2L' 2F 2D2 2F' 2L U2 x' 2F2 2D B2 2R' 2F' 2R B2 2R' 2F 2R 2D' 2F2

I notice the corners and four edges are fully solved.

The corners and centers are fully solved. It's just a scramble of wings. Here is the correct translation:
L2 F 2R2 B2 U 2L2 U' 2L2 U 2L2 U' B2 2R2 F' x 2L2 U F L U R2 F 2R2 F' R2 U' L' F' U' 2L2 x F2 U' 2L' 2R' U F' L U' F 2L 2R F' U L' F' x2 L2 x L' F 2D2 F' L U2 L' F 2D2 F' L U2 x' F2 2D B2 R' 2F' R B2 R' 2F R 2D' F2

I got this translation immediately with a translator I wrote in Mathematica (I used this subroutine to convert all algorithms on the 4x4x4 parity algorithms page to SiGN to avoid human error), just in case you want to code it for future use.

Spoiler: 4x4x4 WCAToSiGN Translator

 

[rokicki]

The corners and centers are fully solved. It's just a scramble of wings. Here is the correct translation:
L2 F 2R2 B2 U 2L2 U' 2L2 U 2L2 U' B2 2R2 F' x 2L2 U F L U R2 F 2R2 F' R2 U' L' F' U' 2L2 x F2 U' 2L' 2R' U F' L U' F 2L 2R F' U L' F' x2 L2 x L' F 2D2 F' L U2 L' F 2D2 F' L U2 x' F2 2D B2 R' 2F' R B2 R' 2F R 2D' F2

I've run this through my OBTM reduction solver, and the shortest reduction is 14 moves. I've completed
searching through depths 14 and 15 without a total solution, which means it is at least 16 moves from
solved.

I've found solutions (by completing a reduction solve) of length 30. So the true distance is somewhere
between 16 and 30, inclusive.

This position gives my reduction solver a *bit* more difficulty than random positions do, because with
the middle solved in the starting position, my deepest table (the one for the middle cubies) is
made largely impotent.

Are you interested in the actual length-30 solves I have?

 

[Christopher Mowla]

Are you interested in the actual length-30 solves I have?

No, that's okay. Knowing that it is <=30 moves is sufficient. Thanks for your time.

 

[ch_ts]

Is there something special about this position? Is it for your method that you previously alluded to? Anything you can share with us about that?

 

[Waran]

Oh, absolutely! Ideally at some point our software will
reach the point where we can find near-optimal solutions
(I don't think we are quite there yet) and start finding
some actual candidates for antipodal positions.

Probably symmetric positions may be more fruitful, as
well as being easier to "prove hard" (less search
required).

It's early days yet. But let's see how good our solvers
can get.

I have a database with more then 670 symmetric positions.
They might be useful to get one or maybe two plys deeper.

All these positions are generated in 39 or less moves (btm).
Currently only about 80 positions require more then 29 moves.
So this makes them all potential candidates for antipodal positions.

Maybe someone can run the two hardest positions below through the solver?


Here are the original algorithms in SSE notation.

Deep Edge Hexagon
D B D' F2 SD WF U2 R' F' B2 D' F' U2 WR F' WR
TR2 F' TD2 L' F' MR2 TF2 R' TU2 F2 R
TU' L2 D L TU2 B SD'
TB' TU2 TR' TU2 TR' (39 btm)

2 Dual-Color Rings
L B' R' WF2 R' D2 WF2 L WF D2 R WF2 D' R' B' L'
TF2 TD2 D L U' TR2 U2 F2 L D2 U
B' U TB' D2 F' TU2 TB U
TU B' F' R2 (39 btm)


Translated in SiGN, the algorithms look like this:

Deep Edge Hexagon
D B D' F2 e' y' s U2 R' F' B2 D' F' U2 m' F' m'
Rw2 F' Dw2 L' F' 2R2 Fw2 R' Uw2 F2 R
Uw' L2 D L Uw2 B e y
Bw' Uw2 Rw' Uw2 Rw' (39 btm)

2 Dual-Color Rings
L B' R' s2 R' D2 s2 L s D2 R s2 D' R' B' L'
Fw2 Dw2 D L U' Rw2 U2 F2 L D2 U
B' U Bw' D2 F' Uw2 Bw U
Uw B' F' R2 (39 btm)