• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 40,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

4x4x4 God's Number Position Hunt

Status
Not open for further replies.

rokicki

Member
Joined
Oct 31, 2008
Messages
301
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

Member
Joined
Mar 2, 2014
Messages
566
Location
Doylestown, PA
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:

Code:
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.

total_4x4x4_positions_per_depth.png
 
Last edited:

Christopher Mowla

Premium Member
Joined
Sep 17, 2009
Messages
1,184
Location
Earth
YouTube
Visit Channel
Last edited:

rokicki

Member
Joined
Oct 31, 2008
Messages
301
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.
 

rokicki

Member
Joined
Oct 31, 2008
Messages
301

Christopher Mowla

Premium Member
Joined
Sep 17, 2009
Messages
1,184
Location
Earth
YouTube
Visit Channel
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. :)
QqUV5Va.png
 

rokicki

Member
Joined
Oct 31, 2008
Messages
301

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?
 

ch_ts

Member
Joined
Apr 25, 2008
Messages
251
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

Member
Joined
May 17, 2012
Messages
7
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)
 
Status
Not open for further replies.
Top