• 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 35,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!

Announcing: New 4x4x4 Brute Force Solver

Status
Not open for further replies.

unsolved

Member
Joined
Mar 2, 2014
Messages
566
Location
Doylestown, PA
I too am interested to see if this solver can find a 9 mover.:)
So far, on the 8th ply with the 1-turn-from-solve (1-tfs) database being accessed at every leaf node. That means if a move sequence fails to return "solved," it checks the cube to see if it is 1-move away from being completed. So, it is kind of like a 8 and 9-ply search carried out in tandem. If it probes all leaf nodes at depth 8, and no solution is found, that means ply-9 can be skipped and it can go directly to ply-10. But it is already known that there is a 10-ply answer.

If you guys have 64-bit hardware, I can give you this specifically-compiled version of it to test on your own machines. It will only solve this hard-coded case though.

results so far.jpg
 

cuBerBruce

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
cuBerBruce
I tried my own optimal solver on cmhardw's position. I did not find any distance 9 solutions (single slice turn metric). Below is the output a third way through distance 10.

Code:
scramble: [10]  F  d  R2 d3 r3 d  R2 d3 r  F3
distance  1   node count          0   solved state checks          0
distance  2   node count          0   solved state checks          0
distance  3   node count          0   solved state checks          0
distance  4   node count        414   solved state checks        126
distance  5   node count      13014   solved state checks       3309
distance  6   node count     273291   solved state checks      60429
distance  7   node count    5007999   solved state checks    1049622
distance  8   node count   90199848   solved state checks   18065829
distance  9   node count 1607782779   solved state checks  311450757
Found solution: [10]  U  f3 l  F2 l3 f  l  F2 l3 U3
Found solution: [10]  U3 b3 R2 b  r  b3 R2 b  r3 U
Found solution: [10]  u  r3 F2 r  f  r3 F2 r  f3 u3
Found solution: [10]  u3 r3 f  R2 f3 r  f  R2 f3 u
 

unsolved

Member
Joined
Mar 2, 2014
Messages
566
Location
Doylestown, PA
I tried my own optimal solver on cmhardw's position. I did not find any distance 9 solutions (single slice turn metric). Below is the output a third way through distance 10.

Code:
scramble: [10]  F  d  R2 d3 r3 d  R2 d3 r  F3
distance  1   node count          0   solved state checks          0
distance  2   node count          0   solved state checks          0
distance  3   node count          0   solved state checks          0
distance  4   node count        414   solved state checks        126
distance  5   node count      13014   solved state checks       3309
distance  6   node count     273291   solved state checks      60429
distance  7   node count    5007999   solved state checks    1049622
distance  8   node count   90199848   solved state checks   18065829
distance  9   node count 1607782779   solved state checks  311450757
Found solution: [10]  U  f3 l  F2 l3 f  l  F2 l3 U3
Found solution: [10]  U3 b3 R2 b  r  b3 R2 b  r3 U
Found solution: [10]  u  r3 F2 r  f  r3 F2 r  f3 u3
Found solution: [10]  u3 r3 f  R2 f3 r  f  R2 f3 u
Can you explain your output up there Bruce? Like where the numbers come from and what the notation is? I don't recognize the f3 U3 stuff. Noob here :)
 

cuBerBruce

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
cuBerBruce
Can you explain your output up there Bruce? Like where the numbers come from and what the notation is? I don't recognize the f3 U3 stuff. Noob here :)
The "distance" numbers indicates the actual goal value (desired solution length) for each step of the iterative deepening.

"Node count" simply indicates how many positions are generated in the depth first search. There is a pruning table based on 8 centers for two opposite faces that indicates the initial position requires at least 4 moves to solve. So when the search goal is less than 4, it doesn't have to search at all. In the future, I will just start the iterative deepening with a goal of 4 moves (or whatever lower bound I get from the pruning tables).

"Solved state checks" indicates how many branches of the depth-first search tree actually reach the goal number of moves. When this happens I need to check if the cube is actually in a solved state.

"f3" should really be f'. Similarly for the other 3's in the move sequences. Rotating a layer 3 quarter turns clockwise is equivalent to rotating a layer one quarter turn counterclockwise. Upper case is for the face layer and lower case is for the next layer in.

The numbers in square brackets just indicate the length of the scramble or the solution.
 

unsolved

Member
Joined
Mar 2, 2014
Messages
566
Location
Doylestown, PA
The "distance" numbers indicates the actual goal value (desired solution length) for each step of the iterative deepening.

"Node count" simply indicates how many positions are generated in the depth first search. There is a pruning table based on 8 centers for two opposite faces that indicates the initial position requires at least 4 moves to solve. So when the search goal is less than 4, it doesn't have to search at all. In the future, I will just start the iterative deepening with a goal of 4 moves (or whatever lower bound I get from the pruning tables).

"Solved state checks" indicates how many branches of the depth-first search tree actually reach the goal number of moves. When this happens I need to check if the cube is actually in a solved state.

"f3" should really be f'. Similarly for the other 3's in the move sequences. Rotating a layer 3 quarter turns clockwise is equivalent to rotating a layer one quarter turn counterclockwise. Upper case is for the face layer and lower case is for the next layer in.

The numbers in square brackets just indicate the length of the scramble or the solution.
OK, thanks.

Are you using a bit-move generator, or matrices and arrays?

I'd like to compare code at one point.

I can send you my Commutator Prune Code and my 1-turn-from-solved code (a "0-position" database, all done with IF statements. Actually finds stuff 1 ply sooner, and even when it fails, you can increment 2 plies in iterative deepening rather than 1.)

My game tree is still prohibitively large, even with the parallel face pruning code:

Code:
unsigned short prune_parallel_rotations(unsigned short i, unsigned short j, unsigned short k)
{
	/****************************************************************/
	/* 3-ply prunes of moves such as :                              */
	/*                                  T+ B+ T+  (same as T2 B+)   */
	/*                                  T+ B+ T-  (same as B+)      */
	/*                                  T+ B+ T2  (same as T- B+)   */
	/****************************************************************/
	if((i >= T___PLUS____) && (i <= T___TWICE___))
	if(((j >= B___PLUS____) && (j <= B___TWICE___)) || ((j >= b___PLUS____) && (j <= b___TWICE___)))
	if((k >= T___PLUS____) && (k <= T___TWICE___)) return 1;

	if((i >= t___PLUS____) && (i <= t___TWICE___))
	if(((j >= B___PLUS____) && (j <= B___TWICE___)) || ((j >= b___PLUS____) && (j <= b___TWICE___)))
	if((k >= t___PLUS____) && (k <= t___TWICE___)) return 1;

	if((i >= B___PLUS____) && (i <= B___TWICE___))
	if(((j >= T___PLUS____) && (j <= T___TWICE___)) || ((j >= t___PLUS____) && (j <= t___TWICE___)))
	if((k >= B___PLUS____) && (k <= B___TWICE___)) return 1;

	if((i >= b___PLUS____) && (i <= b___TWICE___))
	if(((j >= T___PLUS____) && (j <= T___TWICE___)) || ((j >= t___PLUS____) && (j <= t___TWICE___)))
	if((k >= b___PLUS____) && (k <= b___TWICE___)) return 1;

	/****************************************************************/
	/* 3-ply prunes of moves such as :                              */
	/*                                  F+ K+ F+  (same as F2 K+)   */
	/*                                  F+ K+ F-  (same as K+)      */
	/*                                  F+ K+ F2  (same as F- K+)   */
	/****************************************************************/

	if((i >= F___PLUS____) && (i <= F___TWICE___))
	if(((j >= K___PLUS____) && (j <= K___TWICE___)) || ((j >= k___PLUS____) && (j <= k___TWICE___)))
	if((k >= F___PLUS____) && (k <= F___TWICE___)) return 1;

	if((i >= f___PLUS____) && (i <= f___TWICE___))
	if(((j >= K___PLUS____) && (j <= K___TWICE___)) || ((j >= k___PLUS____) && (j <= k___TWICE___)))
	if((k >= f___PLUS____) && (k <= f___TWICE___)) return 1;

	if((i >= K___PLUS____) && (i <= K___TWICE___))
	if(((j >= F___PLUS____) && (j <= F___TWICE___)) || ((j >= f___PLUS____) && (j <= f___TWICE___)))
	if((k >= K___PLUS____) && (k <= K___TWICE___)) return 1;

	if((i >= k___PLUS____) && (i <= k___TWICE___))
	if(((j >= F___PLUS____) && (j <= F___TWICE___)) || ((j >= f___PLUS____) && (j <= f___TWICE___)))
	if((k >= k___PLUS____) && (k <= k___TWICE___)) return 1;

	/****************************************************************/
	/* 3-ply prunes of moves such as :                              */
	/*                                  R+ L+ R+  (same as R2 L+)   */
	/*                                  R+ L+ R-  (same as L+)      */
	/*                                  R+ L+ R2  (same as R- L+)   */
	/****************************************************************/

	if((i >= R___PLUS____) && (i <= R___TWICE___))
	if(((j >= L___PLUS____) && (j <= L___TWICE___)) || ((j >= l___PLUS____) && (j <= l___TWICE___)))
	if((k >= R___PLUS____) && (k <= R___TWICE___)) return 1;

	if((i >= r___PLUS____) && (i <= r___TWICE___))
	if(((j >= L___PLUS____) && (j <= L___TWICE___)) || ((j >= l___PLUS____) && (j <= l___TWICE___)))
	if((k >= r___PLUS____) && (k <= r___TWICE___)) return 1;

	if((i >= L___PLUS____) && (i <= L___TWICE___))
	if(((j >= R___PLUS____) && (j <= R___TWICE___)) || ((j >= r___PLUS____) && (j <= r___TWICE___)))
	if((k >= L___PLUS____) && (k <= L___TWICE___)) return 1;

	if((i >= l___PLUS____) && (i <= l___TWICE___))
	if(((j >= R___PLUS____) && (j <= R___TWICE___)) || ((j >= r___PLUS____) && (j <= r___TWICE___)))
	if((k >= l___PLUS____) && (k <= l___TWICE___)) return 1;
	
	return 0;
}

unsigned short prune_parallel_rotations(unsigned short a, unsigned short b, unsigned short c, unsigned short d)
{
	if(((a >= T___PLUS____) && (a <= T___TWICE___)) || ((a >= B___PLUS____) && (a <= B___TWICE___)) || ((a >= t___PLUS____) && (a <= t___TWICE___)) || ((a >= b___PLUS____) && (a <= b___TWICE___)))
	if(((b >= T___PLUS____) && (b <= T___TWICE___)) || ((b >= B___PLUS____) && (b <= B___TWICE___)) || ((b >= t___PLUS____) && (b <= t___TWICE___)) || ((b >= b___PLUS____) && (b <= b___TWICE___)))
	if(((c >= T___PLUS____) && (c <= T___TWICE___)) || ((c >= B___PLUS____) && (c <= B___TWICE___)) || ((c >= t___PLUS____) && (c <= t___TWICE___)) || ((c >= b___PLUS____) && (c <= b___TWICE___)))
	if(((d >= T___PLUS____) && (d <= T___TWICE___)) || ((d >= B___PLUS____) && (d <= B___TWICE___)) || ((d >= t___PLUS____) && (d <= t___TWICE___)) || ((d >= b___PLUS____) && (d <= b___TWICE___)))
	return 1;

	if(((a >= F___PLUS____) && (a <= F___TWICE___)) || ((a >= K___PLUS____) && (a <= K___TWICE___)) || ((a >= f___PLUS____) && (a <= f___TWICE___)) || ((a >= k___PLUS____) && (a <= k___TWICE___)))
	if(((b >= F___PLUS____) && (b <= F___TWICE___)) || ((b >= K___PLUS____) && (b <= K___TWICE___)) || ((b >= f___PLUS____) && (b <= f___TWICE___)) || ((b >= k___PLUS____) && (b <= k___TWICE___)))
	if(((c >= F___PLUS____) && (c <= F___TWICE___)) || ((c >= K___PLUS____) && (c <= K___TWICE___)) || ((c >= f___PLUS____) && (c <= f___TWICE___)) || ((c >= k___PLUS____) && (c <= k___TWICE___)))
	if(((d >= F___PLUS____) && (d <= F___TWICE___)) || ((d >= K___PLUS____) && (d <= K___TWICE___)) || ((d >= f___PLUS____) && (d <= f___TWICE___)) || ((d >= k___PLUS____) && (d <= k___TWICE___)))
	return 1;

	if(((a >= R___PLUS____) && (a <= R___TWICE___)) || ((a >= L___PLUS____) && (a <= L___TWICE___)) || ((a >= r___PLUS____) && (a <= r___TWICE___)) || ((a >= l___PLUS____) && (a <= l___TWICE___)))
	if(((b >= R___PLUS____) && (b <= R___TWICE___)) || ((b >= L___PLUS____) && (b <= L___TWICE___)) || ((b >= r___PLUS____) && (b <= r___TWICE___)) || ((b >= l___PLUS____) && (b <= l___TWICE___)))
	if(((c >= R___PLUS____) && (c <= R___TWICE___)) || ((c >= L___PLUS____) && (c <= L___TWICE___)) || ((c >= r___PLUS____) && (c <= r___TWICE___)) || ((c >= l___PLUS____) && (c <= l___TWICE___)))
	if(((d >= R___PLUS____) && (d <= R___TWICE___)) || ((d >= L___PLUS____) && (d <= L___TWICE___)) || ((d >= r___PLUS____) && (d <= r___TWICE___)) || ((d >= l___PLUS____) && (d <= l___TWICE___)))
	return 1;
	
	return 0;
}

unsigned short prune_parallel_rotations(unsigned short a, unsigned short b, unsigned short c, unsigned short d, unsigned short e)
{
	if(((a >= T___PLUS____) && (a <= T___TWICE___)) || ((a >= B___PLUS____) && (a <= B___TWICE___)) || ((a >= t___PLUS____) && (a <= t___TWICE___)) || ((a >= b___PLUS____) && (a <= b___TWICE___)))
	if(((b >= T___PLUS____) && (b <= T___TWICE___)) || ((b >= B___PLUS____) && (b <= B___TWICE___)) || ((b >= t___PLUS____) && (b <= t___TWICE___)) || ((b >= b___PLUS____) && (b <= b___TWICE___)))
	if(((c >= T___PLUS____) && (c <= T___TWICE___)) || ((c >= B___PLUS____) && (c <= B___TWICE___)) || ((c >= t___PLUS____) && (c <= t___TWICE___)) || ((c >= b___PLUS____) && (c <= b___TWICE___)))
	if(((d >= T___PLUS____) && (d <= T___TWICE___)) || ((d >= B___PLUS____) && (d <= B___TWICE___)) || ((d >= t___PLUS____) && (d <= t___TWICE___)) || ((d >= b___PLUS____) && (d <= b___TWICE___)))
	if(((e >= T___PLUS____) && (e <= T___TWICE___)) || ((e >= B___PLUS____) && (e <= B___TWICE___)) || ((e >= t___PLUS____) && (e <= t___TWICE___)) || ((e >= b___PLUS____) && (e <= b___TWICE___)))
	return 1;

	if(((a >= F___PLUS____) && (a <= F___TWICE___)) || ((a >= K___PLUS____) && (a <= K___TWICE___)) || ((a >= f___PLUS____) && (a <= f___TWICE___)) || ((a >= k___PLUS____) && (a <= k___TWICE___)))
	if(((b >= F___PLUS____) && (b <= F___TWICE___)) || ((b >= K___PLUS____) && (b <= K___TWICE___)) || ((b >= f___PLUS____) && (b <= f___TWICE___)) || ((b >= k___PLUS____) && (b <= k___TWICE___)))
	if(((c >= F___PLUS____) && (c <= F___TWICE___)) || ((c >= K___PLUS____) && (c <= K___TWICE___)) || ((c >= f___PLUS____) && (c <= f___TWICE___)) || ((c >= k___PLUS____) && (c <= k___TWICE___)))
	if(((d >= F___PLUS____) && (d <= F___TWICE___)) || ((d >= K___PLUS____) && (d <= K___TWICE___)) || ((d >= f___PLUS____) && (d <= f___TWICE___)) || ((d >= k___PLUS____) && (d <= k___TWICE___)))
	if(((e >= F___PLUS____) && (e <= F___TWICE___)) || ((e >= K___PLUS____) && (e <= K___TWICE___)) || ((e >= f___PLUS____) && (e <= f___TWICE___)) || ((e >= k___PLUS____) && (e <= k___TWICE___)))
	return 1;

	if(((a >= R___PLUS____) && (a <= R___TWICE___)) || ((a >= L___PLUS____) && (a <= L___TWICE___)) || ((a >= r___PLUS____) && (a <= r___TWICE___)) || ((a >= l___PLUS____) && (a <= l___TWICE___)))
	if(((b >= R___PLUS____) && (b <= R___TWICE___)) || ((b >= L___PLUS____) && (b <= L___TWICE___)) || ((b >= r___PLUS____) && (b <= r___TWICE___)) || ((b >= l___PLUS____) && (b <= l___TWICE___)))
	if(((c >= R___PLUS____) && (c <= R___TWICE___)) || ((c >= L___PLUS____) && (c <= L___TWICE___)) || ((c >= r___PLUS____) && (c <= r___TWICE___)) || ((c >= l___PLUS____) && (c <= l___TWICE___)))
	if(((d >= R___PLUS____) && (d <= R___TWICE___)) || ((d >= L___PLUS____) && (d <= L___TWICE___)) || ((d >= r___PLUS____) && (d <= r___TWICE___)) || ((d >= l___PLUS____) && (d <= l___TWICE___)))
	if(((e >= R___PLUS____) && (e <= R___TWICE___)) || ((e >= L___PLUS____) && (e <= L___TWICE___)) || ((e >= r___PLUS____) && (e <= r___TWICE___)) || ((e >= l___PLUS____) && (e <= l___TWICE___)))
	return 1;
	
	return 0;
}
Etc., for each new level in the tree, I just add one line of code to the bottom, and one more variable to be based in for overloading.
 

cuBerBruce

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
cuBerBruce
Are you using a bit-move generator, or matrices and arrays?

I'd like to compare code at one point.
My program was hacked from my 5-phase solver program. Its got a lot of extra stuff from the other program that isn't used. I'll probably want to clean it up a lot before sharing it. Maybe I'll share pieces of it like you are doing.

My program uses arrays for each piece type, one element per piece. The elements in the corner array contain both permutation and orientation information. With depth-first searching, only the positions along the current search branch need to be stored, so storage required for the search tree isn't very much. The search uses a recursive procedure, one level for each move in the solution sequence.
 

unsolved

Member
Joined
Mar 2, 2014
Messages
566
Location
Doylestown, PA
My program was hacked from my 5-phase solver program. Its got a lot of extra stuff from the other program that isn't used. I'll probably want to clean it up a lot before sharing it. Maybe I'll share pieces of it like you are doing.

My program uses arrays for each piece type, one element per piece. The elements in the corner array contain both permutation and orientation information. With depth-first searching, only the positions along the current search branch need to be stored, so storage required for the search tree isn't very much. The search uses a recursive procedure, one level for each move in the solution sequence.
The guts of my matrix version of the move generator showing the functions for R+ and R-.

Code:
typedef struct cube_4x4x4__arrangement
{
	unsigned char cube_top[16];
	unsigned char cube_bottom[16];
	unsigned char cube_front[16];
	unsigned char cube_back[16];
	unsigned char cube_right[16];
	unsigned char cube_left[16];
}
CUBE_4x4_ARRANGEMENT, *CUBE_4x4_ARRANGEMENT_PTR;

CUBE_4x4_ARRANGEMENT plus_right_face_move(CUBE_4x4_ARRANGEMENT original_4x4x4_cube)
{
	CUBE_4x4_ARRANGEMENT new_cube;

	new_cube = original_4x4x4_cube;

	new_cube.cube_top[4-1] = original_4x4x4_cube.cube_front[4-1];
	new_cube.cube_top[8-1] = original_4x4x4_cube.cube_front[8-1];
	new_cube.cube_top[12-1] = original_4x4x4_cube.cube_front[12-1];
	new_cube.cube_top[16-1] = original_4x4x4_cube.cube_front[16-1];

	new_cube.cube_front[4-1] = original_4x4x4_cube.cube_bottom[4-1];
	new_cube.cube_front[8-1] = original_4x4x4_cube.cube_bottom[8-1];
	new_cube.cube_front[12-1] = original_4x4x4_cube.cube_bottom[12-1];
	new_cube.cube_front[16-1] = original_4x4x4_cube.cube_bottom[16-1];

	new_cube.cube_bottom[4-1] = original_4x4x4_cube.cube_back[13-1];
	new_cube.cube_bottom[8-1] = original_4x4x4_cube.cube_back[9-1];
	new_cube.cube_bottom[12-1] = original_4x4x4_cube.cube_back[5-1];
	new_cube.cube_bottom[16-1] = original_4x4x4_cube.cube_back[1-1];

	new_cube.cube_back[1-1] = original_4x4x4_cube.cube_top[16-1];
	new_cube.cube_back[5-1] = original_4x4x4_cube.cube_top[12-1];
	new_cube.cube_back[9-1] = original_4x4x4_cube.cube_top[8-1];
	new_cube.cube_back[13-1] = original_4x4x4_cube.cube_top[4-1];

	/*********************************/
	/*       *       *       *       */
	/*  01   *  02   *  03   *   04  */
	/*       *       *       *       */
	/*********************************/
	/*       *       *       *       */
	/*  05   *  06   *  07   *   08  */
	/*       *       *       *       */
	/*********************************/
	/*       *       *       *       */
	/*  09   *  10   *  11   *   12  */
	/*       *       *       *       */
	/*********************************/
	/*       *       *       *       */
	/*  13   *  14   *  15   *   16  */
	/*       *       *       *       */
	/*********************************/


	/*********************************/
	/*       *       *       *       */
	/*  13   *  09   *  05   *   01  */
	/*       *       *       *       */
	/*********************************/
	/*       *       *       *       */
	/*  14   *  10   *  06   *   02  */
	/*       *       *       *       */
	/*********************************/
	/*       *       *       *       */
	/*  15   *  11   *  07   *   03  */
	/*       *       *       *       */
	/*********************************/
	/*       *       *       *       */
	/*  16   *  12   *  08   *   04  */
	/*       *       *       *       */
	/*********************************/

	new_cube.cube_right[1-1] = original_4x4x4_cube.cube_right[13-1];
	new_cube.cube_right[2-1] = original_4x4x4_cube.cube_right[9-1];
	new_cube.cube_right[3-1] = original_4x4x4_cube.cube_right[5-1];
	new_cube.cube_right[4-1] = original_4x4x4_cube.cube_right[1-1];

	new_cube.cube_right[5-1] = original_4x4x4_cube.cube_right[14-1];
	new_cube.cube_right[6-1] = original_4x4x4_cube.cube_right[10-1];
	new_cube.cube_right[7-1] = original_4x4x4_cube.cube_right[6-1];
	new_cube.cube_right[8-1] = original_4x4x4_cube.cube_right[2-1];

	new_cube.cube_right[9-1] = original_4x4x4_cube.cube_right[15-1];
	new_cube.cube_right[10-1] = original_4x4x4_cube.cube_right[11-1];
	new_cube.cube_right[11-1] = original_4x4x4_cube.cube_right[7-1];
	new_cube.cube_right[12-1] = original_4x4x4_cube.cube_right[3-1];

	new_cube.cube_right[13-1] = original_4x4x4_cube.cube_right[16-1];
	new_cube.cube_right[14-1] = original_4x4x4_cube.cube_right[12-1];
	new_cube.cube_right[15-1] = original_4x4x4_cube.cube_right[8-1];
	new_cube.cube_right[16-1] = original_4x4x4_cube.cube_right[4-1];

	return new_cube;
}



CUBE_4x4_ARRANGEMENT minus_right_face_move(CUBE_4x4_ARRANGEMENT original_4x4x4_cube)
{
	CUBE_4x4_ARRANGEMENT new_cube;

	new_cube = original_4x4x4_cube;

	new_cube.cube_top[4-1] = original_4x4x4_cube.cube_back[13-1];
	new_cube.cube_top[8-1] = original_4x4x4_cube.cube_back[9-1];
	new_cube.cube_top[12-1] = original_4x4x4_cube.cube_back[5-1];
	new_cube.cube_top[16-1] = original_4x4x4_cube.cube_back[1-1];

	new_cube.cube_back[13-1] = original_4x4x4_cube.cube_bottom[4-1];
	new_cube.cube_back[9-1] = original_4x4x4_cube.cube_bottom[8-1];
	new_cube.cube_back[5-1] = original_4x4x4_cube.cube_bottom[12-1];
	new_cube.cube_back[1-1] = original_4x4x4_cube.cube_bottom[16-1];

	new_cube.cube_bottom[4-1] = original_4x4x4_cube.cube_front[4-1];
	new_cube.cube_bottom[8-1] = original_4x4x4_cube.cube_front[8-1];
	new_cube.cube_bottom[12-1] = original_4x4x4_cube.cube_front[12-1];
	new_cube.cube_bottom[16-1] = original_4x4x4_cube.cube_front[16-1];

	new_cube.cube_front[4-1] = original_4x4x4_cube.cube_top[4-1];
	new_cube.cube_front[8-1] = original_4x4x4_cube.cube_top[8-1];
	new_cube.cube_front[12-1] = original_4x4x4_cube.cube_top[12-1];
	new_cube.cube_front[16-1] = original_4x4x4_cube.cube_top[16-1];

	/*********************************/
	/*       *       *       *       */
	/*  01   *  02   *  03   *   04  */
	/*       *       *       *       */
	/*********************************/
	/*       *       *       *       */
	/*  05   *  06   *  07   *   08  */
	/*       *       *       *       */
	/*********************************/
	/*       *       *       *       */
	/*  09   *  10   *  11   *   12  */
	/*       *       *       *       */
	/*********************************/
	/*       *       *       *       */
	/*  13   *  14   *  15   *   16  */
	/*       *       *       *       */
	/*********************************/


	/*********************************/
	/*       *       *       *       */
	/*  04   *  08   *  12   *   16  */
	/*       *       *       *       */
	/*********************************/
	/*       *       *       *       */
	/*  03   *  07   *  11   *   15  */
	/*       *       *       *       */
	/*********************************/
	/*       *       *       *       */
	/*  02   *  06   *  10   *   14  */
	/*       *       *       *       */
	/*********************************/
	/*       *       *       *       */
	/*  01   *  05   *  09   *   13  */
	/*       *       *       *       */
	/*********************************/

	new_cube.cube_right[1-1] = original_4x4x4_cube.cube_right[4-1];
	new_cube.cube_right[2-1] = original_4x4x4_cube.cube_right[8-1];
	new_cube.cube_right[3-1] = original_4x4x4_cube.cube_right[12-1];
	new_cube.cube_right[4-1] = original_4x4x4_cube.cube_right[16-1];

	new_cube.cube_right[5-1] = original_4x4x4_cube.cube_right[3-1];
	new_cube.cube_right[6-1] = original_4x4x4_cube.cube_right[7-1];
	new_cube.cube_right[7-1] = original_4x4x4_cube.cube_right[11-1];
	new_cube.cube_right[8-1] = original_4x4x4_cube.cube_right[15-1];

	new_cube.cube_right[9-1] = original_4x4x4_cube.cube_right[2-1];
	new_cube.cube_right[10-1] = original_4x4x4_cube.cube_right[6-1];
	new_cube.cube_right[11-1] = original_4x4x4_cube.cube_right[10-1];
	new_cube.cube_right[12-1] = original_4x4x4_cube.cube_right[14-1];

	new_cube.cube_right[13-1] = original_4x4x4_cube.cube_right[1-1];
	new_cube.cube_right[14-1] = original_4x4x4_cube.cube_right[5-1];
	new_cube.cube_right[15-1] = original_4x4x4_cube.cube_right[9-1];
	new_cube.cube_right[16-1] = original_4x4x4_cube.cube_right[13-1];

	return new_cube;
}
To call the function, I just pass in an index to an array of function pointers.

Code:
#define T___PLUS____ 0
#define T___MINUS___ 1
#define T___TWICE___ 2

#define F___PLUS____ 3
#define F___MINUS___ 4
#define F___TWICE___ 5

#define R___PLUS____ 6
#define R___MINUS___ 7
#define R___TWICE___ 8

....

#define l___PLUS____ 33
#define l___MINUS___ 34
#define l___TWICE___ 35


typedef CUBE_4x4_ARRANGEMENT (*cube_move_ptr)(CUBE_4x4_ARRANGEMENT);
cube_move_ptr cube_move_array[GLOBAL_TOTAL_LEGAL_MOVES_PER_POSITION];

void init_function_pointers(void)
{

	cube_move_array[R___PLUS____] = plus_right_face_move;
	cube_move_array[R___MINUS___] = minus_right_face_move;
	cube_move_array[R___TWICE___] = double_right_face_move;
}
The move generator is just lame for loop execution, nothing fancy:

Code:
for(i = FIRST_MOVE; i <= LAST_MOVE; i++)
for(j = FIRST_MOVE; j<= LAST_MOVE; j++)
{
	if((i/3) == (j/3)) continue;// never do the same triplet move twice in a row

	modified_cube = cube_move_array[i](original_cube);
	modified_cube = cube_move_array[j](modified_cube);
	g_total_nodes++;
	
	solved_info = solved_distance(modified_cube);
}
 

Stefan

Member
Joined
May 7, 2006
Messages
7,287
WCA
2003POCH01
YouTube
StefanPochmann
This guy looks rather scrambling to me. Are you guys all seeing just a center-3-cycle when you play it?

as far as I know relatively recent, discovery of "pseudo-slice" commutators of the form [D b D', l'] and [(Uu) r (Uu)', l']
Well, at least [post=241223]from 2009[/post] (just clarifying cause "relatively recent" is rather vague and confused at least me). I btw don't really see "pseudo" in it, I've read [post=483950]this[/post] but I just see it as normal "[affect one l-piece, turn l]" commutator, with the l-piece Dlb stepping out of the way with D so it's not affected when Rub steps into the l-slice with b. Similar to how a beginner can solve the 3x3 first layer corner UFR with b R b' (where the corner steps into the first layer with R, and the b temporarily gets two pieces out of the way that would otherwise be affected by the R).
 
Last edited:

cmhardw

Premium Member
Joined
Apr 5, 2006
Messages
4,106
Location
Atlanta, Georgia
WCA
2003HARD01
Well, at least [post=241223]from 2009[/post] (just clarifying cause "relatively recent" is rather vague and confused at least me).
That was longer ago than I remembered it being, but that is the post I was thinking of when referring to that type of commutator.

I btw don't really see "pseudo" in it, I've read [post=483950]this[/post] but I just see it as normal "[affect one l-piece, turn l]" commutator, with the l-piece Dlb stepping out of the way with D so it's not affected when Rub steps into the l-slice with b. Similar to how a beginner can solve the 3x3 first layer corner UFR with b R b' (where the corner steps into the first layer with R, and the b temporarily gets two pieces out of the way that would otherwise be affected by the R).
Yeah it does make more sense to view the l slice as being temporarily broken up to do the b move to affect only Ubl. I prefer to have a name for each commutator type, so what would you suggest calling this case-that-should-probably-not-be-named "pseudo-slicing" ? I will think on this too.
 

Stefan

Member
Joined
May 7, 2006
Messages
7,287
WCA
2003POCH01
YouTube
StefanPochmann
what would you suggest calling this case-that-should-probably-not-be-named "pseudo-slicing"?
Hmm, it's hard, what have I gotten myself into now :). Maybe something with "isolation" or "left alone", as Ulb gets isolated (from all other l-pieces) so that it can move alone (with the b-turn).

Ooooooohh... I had the "twisty.js beta" checked. If I uncheck that, it looks good to me as well. Thanks.
 

unsolved

Member
Joined
Mar 2, 2014
Messages
566
Location
Doylestown, PA
That was longer ago than I remembered it being, but that is the post I was thinking of when referring to that type of commutator.
I just compiled a much faster version of my program, thanks to the excellent advice I received from Jakube.

I changed the 1-tfs database (1 turn-from-solution) into 12 pieces of logic that are accessed much more quickly than probing my bloated database :)

As a result, here is an 8-ply solution (U and F centers switched) that was found in just 7 plies (since a 1-tfs position was identified 1 ply early).

lightningcloudcomputing.com/4x4x4_depth_7.zip

And, because of the search extension code, it jumps from ply 5 to 7 with "authority," since every possible 1-tfs position from ply 5 did was not encountered, it means there cannot possibly be a 6-ply solution.
Watch how fast this one is solved!
 
Last edited:

cuBerBruce

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
cuBerBruce
And, because of the search extension code, it jumps from ply 5 to 7 with "authority," since every possible 1-tfs position from ply 5 did was not encountered, it means there cannot possibly be a 6-ply solution.
Yes, it seems to me (from what I understand about your solver), it is valid to skip "depth 6" (which in my mind is really a depth 7 search) in the iterative deepening. In fact, it seems to me you could skip "depth 2," "depth 4", and any other "even depth" searches.

However, suppose the scramble had a 7-move solution instead of 8. You would likely find the solution quicker with a "depth 6" (in my view, really a depth (6+1) search), than with a depth (7+1) search. Further, the depth (7+1) search might find many suboptimal 8-move solutions before finding an optimal 7-move solution. By having skipped the depth (6+1) search (which should be much quicker than a depth (7+1) search), when you find an 8-move solution, you won't immediately know if it's optimal or not, and you must continue the search until all 7-move possiblilities have been checked if you want a proven optimal solution.

I note that I've run your solver and my own solver on the same computer. For that scramble your solver took close to 2 minutes. My solver took about 6 seconds to find the first solution, and about 40 seconds to completely search for all 8-move solutions. And I don't consider my program to be very well optimized yet.

If you haven't read Jaap's Computer Puzzling page yet, I strongly suggest reading that before doing any more work on your solver.
 

unsolved

Member
Joined
Mar 2, 2014
Messages
566
Location
Doylestown, PA
Yes, it seems to me (from what I understand about your solver), it is valid to skip "depth 6" (which in my mind is really a depth 7 search) in the iterative deepening. In fact, it seems to me you could skip "depth 2," "depth 4", and any other "even depth" searches.
Yes, but for the sake of completeness, and the fact it takes no time, I just leave it in there.

However, suppose the scramble had a 7-move solution instead of 8. You would likely find the solution quicker with a "depth 6" (in my view, really a depth (6+1) search), than with a depth (7+1) search. Further, the depth (7+1) search might find many suboptimal 8-move solutions before finding an optimal 7-move solution. By having skipped the depth (6+1) search (which should be much quicker than a depth (7+1) search), when you find an 8-move solution, you won't immediately know if it's optimal or not, and you must continue the search until all 7-move possiblilities have been checked if you want a proven optimal solution.
Yes, indeed, a situation I have seen myself. With the pre-knowledge of the supposed optimal solution, I have a user setting to address that (Skip odd/even searches, with/without a probe of the tfs databases.)

I have even seen an "over-scramble" solution appear: Where the cube was solved, then made an additional turn, and the 1-tfs database said "Hey, look, this is one move away from being solved" without realizing the program already solved it, then made an additional move!

I note that I've run your solver and my own solver on the same computer. For that scramble your solver took close to 2 minutes. My solver took about 6 seconds to find the first solution, and about 40 seconds to completely search for all 8-move solutions. And I don't consider my program to be very well optimized yet.
This project is doing fine for being a week old :) I have no delusions about where it happens to be, performance-wise. You should have seen it before, it was only averaging 8- or 9-million nodes/second on my hardware initially, now it is 120 million nodes/second per core. That is also "part of my problem" -- I have access to really fast hardware. The solve that you mentioned taking 2 minutes takes 12 seconds on my computer.

The real enemy seems to be the branching factor. Think about this: even if you and I made our programs 1,000 times as fast, it would only add 2-ply to the search depth with the branching factor so high! As far as I can tell, you are doing something to prune the heck out of the tree, whereas I only have the filtering mechanism suggested by Jakube implemented (plus the tfs databases).

I did implement a Non-Commutator Prune which works awesome if you know a solution is of that form, however, the real gold nugget would be to design a Non-Commutator Move Generator, which is next on my list of things to do.

Believe it or not, I have written some high performance chess and checkers programs, have more than one paper that was published by the Internal Computer Games Association Journal, and one of my papers appears in a book by Springer-Verlag. But I am new to cubing, so to speak, and I fully acknowledge that I must crawl before I can walk, and I have all of you really awesome folks offering great tips and advice, so how can I possibly go wrong?

:)
 
Last edited:

rokicki

Member
Joined
Oct 31, 2008
Messages
270
Sounds like you have a lot of useful experience, some that may not be that common in the computer
cubing world! There are a lot of incredible tricks that originated in the gaming (especially chess)
world, and I'm sure we'll all benefit from your ideas.

Would you be willing to take a look at the code we used to prove "20"? It's on

http://cube20.org/src/

Maybe you can come up with some good ideas on how to speed it up even further? I'm always
looking for new magic.

Also, you keep mentioning this "fast hardware" you have access to. Can you elaborate? What
processor, what motherboard, etc.? I'm always interested in getting the fastest hardware I can
for this sort of thing.
 

unsolved

Member
Joined
Mar 2, 2014
Messages
566
Location
Doylestown, PA
Sounds like you have a lot of useful experience, some that may not be that common in the computer
cubing world! There are a lot of incredible tricks that originated in the gaming (especially chess)
world, and I'm sure we'll all benefit from your ideas.

Would you be willing to take a look at the code we used to prove "20"? It's on

http://cube20.org/src/

Maybe you can come up with some good ideas on how to speed it up even further? I'm always
looking for new magic.
I think it would help if I showcase how "simple" my program is right now (and by that, I mean, lacking any kind of sophistication).

Here is the code that generates my U' move, for example (in the code I say "top" to talk about "U").

Code:
CUBE_4x4_ARRANGEMENT minus_top_face_move(CUBE_4x4_ARRANGEMENT original_4x4x4_cube)
{
	CUBE_4x4_ARRANGEMENT new_cube;

	new_cube = original_4x4x4_cube;

	new_cube.cube_front[0] = original_4x4x4_cube.cube_left[0];
	new_cube.cube_front[1] = original_4x4x4_cube.cube_left[1];
	new_cube.cube_front[2] = original_4x4x4_cube.cube_left[2];
	new_cube.cube_front[3] = original_4x4x4_cube.cube_left[3];

	new_cube.cube_right[0] = original_4x4x4_cube.cube_front[0];
	new_cube.cube_right[1] = original_4x4x4_cube.cube_front[1];
	new_cube.cube_right[2] = original_4x4x4_cube.cube_front[2];
	new_cube.cube_right[3] = original_4x4x4_cube.cube_front[3];

	new_cube.cube_back[0] = original_4x4x4_cube.cube_right[0];
	new_cube.cube_back[1] = original_4x4x4_cube.cube_right[1];
	new_cube.cube_back[2] = original_4x4x4_cube.cube_right[2];
	new_cube.cube_back[3] = original_4x4x4_cube.cube_right[3];

	new_cube.cube_left[0] = original_4x4x4_cube.cube_back[0];
	new_cube.cube_left[1] = original_4x4x4_cube.cube_back[1];
	new_cube.cube_left[2] = original_4x4x4_cube.cube_back[2];
	new_cube.cube_left[3] = original_4x4x4_cube.cube_back[3];

	/*********************************/
	/*       *       *       *       */
	/*  01   *  02   *  03   *   04  */
	/*       *       *       *       */
	/*********************************/
	/*       *       *       *       */
	/*  05   *  06   *  07   *   08  */
	/*       *       *       *       */
	/*********************************/
	/*       *       *       *       */
	/*  09   *  10   *  11   *   12  */
	/*       *       *       *       */
	/*********************************/
	/*       *       *       *       */
	/*  13   *  14   *  15   *   16  */
	/*       *       *       *       */
	/*********************************/


	/*********************************/
	/*       *       *       *       */
	/*  04   *  08   *  12   *   16  */
	/*       *       *       *       */
	/*********************************/
	/*       *       *       *       */
	/*  03   *  07   *  11   *   15  */
	/*       *       *       *       */
	/*********************************/
	/*       *       *       *       */
	/*  02   *  06   *  10   *   14  */
	/*       *       *       *       */
	/*********************************/
	/*       *       *       *       */
	/*  01   *  05   *  09   *   13  */
	/*       *       *       *       */
	/*********************************/

	new_cube.cube_top[1-1] = original_4x4x4_cube.cube_top[4-1];
	new_cube.cube_top[2-1] = original_4x4x4_cube.cube_top[8-1];
	new_cube.cube_top[3-1] = original_4x4x4_cube.cube_top[12-1];
	new_cube.cube_top[4-1] = original_4x4x4_cube.cube_top[16-1];

	new_cube.cube_top[5-1] = original_4x4x4_cube.cube_top[3-1];
	new_cube.cube_top[6-1] = original_4x4x4_cube.cube_top[7-1];
	new_cube.cube_top[7-1] = original_4x4x4_cube.cube_top[11-1];
	new_cube.cube_top[8-1] = original_4x4x4_cube.cube_top[15-1];

	new_cube.cube_top[9-1] = original_4x4x4_cube.cube_top[2-1];
	new_cube.cube_top[10-1] = original_4x4x4_cube.cube_top[6-1];
	new_cube.cube_top[11-1] = original_4x4x4_cube.cube_top[10-1];
	new_cube.cube_top[12-1] = original_4x4x4_cube.cube_top[14-1];

	new_cube.cube_top[13-1] = original_4x4x4_cube.cube_top[1-1];
	new_cube.cube_top[14-1] = original_4x4x4_cube.cube_top[5-1];
	new_cube.cube_top[15-1] = original_4x4x4_cube.cube_top[9-1];
	new_cube.cube_top[16-1] = original_4x4x4_cube.cube_top[13-1];

	return new_cube;
}
As you can see, the cube is treated as 16 "cells" on each face, which is NOT the way to write high performance code!

This is my Bitboard Move Generator (experiment, not verified as working nor fully tested) which I am currently writing to speed things up:

Code:
CUBE_4x4_BITBOARD_ARRANGEMENT minus_top_face_bitboard_move(CUBE_4x4_BITBOARD_ARRANGEMENT original_4x4x4_bitboard_cube)
{
		CUBE_4x4_BITBOARD_ARRANGEMENT new_bitboard_cube;
		unsigned long new_bits, top_row[4];

		/**************************************************/
		/* Part I: Shift the bitboard 4 bits to the right */
		/**************************************************/
		
		new_bitboard_cube = original_4x4x4_bitboard_cube;
		new_bits = original_4x4x4_bitboard_cube.cube_left[0] >> 4;

		/******************************************************/
		/* Part II: Copy the lower-16 bits to the top-16 bits */
		/*          of the 32-bit structure. Then bit-OR the  */
		/*          lower-16 bits to the whole 32-bits, which */
		/*          basically makes a perfect copy. This is   */
		/*          so the bits never "fall off" the bitboard */
		/******************************************************/

		new_bitboard_cube.cube_left[0] = (((new_bits & 0x0000FFFF) << 16) & 0xFFFF0000)   |   (new_bits & 0x0000FFFF);

		/*****************************************************/
		/* Part III: Rotate the top.                         */
		/*****************************************************/

		top_row[0] = original_4x4x4_bitboard_cube.cube_top[0] & 0x00F000F0;
		top_row[1] = original_4x4x4_bitboard_cube.cube_top[1] & 0x00F000F0;
		top_row[2] = original_4x4x4_bitboard_cube.cube_top[2] & 0x00F000F0;
		top_row[3] = original_4x4x4_bitboard_cube.cube_top[3] & 0x00F000F0;

		/*********************************************************/
		/*                                                       */
		/* TOP BITBOARD LAYOUT = 0x00F000F0 for each row         */
		/*                                                       */
		/*********************************************************/
		/*   B  *   L  *   T  *   R  *   B  *   L  *  T   *  R   */
		/*********************************************************/
		/* 0000 * 0000 * 1111 * 0000 * 0000 * 0000 * 1111 * 0000 */
		/* 0000 * 0000 * 1111 * 0000 * 0000 * 0000 * 1111 * 0000 */
		/* 0000 * 0000 * 1111 * 0000 * 0000 * 0000 * 1111 * 0000 */
		/* 0000 * 0000 * 1111 * 0000 * 0000 * 0000 * 1111 * 0000 */
		/*********************************************************/

/******************************/     /******************************/     /******************************/     /******************************/
/*  cube 04 moved to cube 01  */     /*  cube 08 moved to cube 02  */     /*  cube 12 moved to cube 03  */     /*  cube 16 moved to cube 04  */
/******************************/     /******************************/     /******************************/     /******************************/
		new_bitboard_cube.cube_top[0] = ((top_row[0] & 0x00100010) << 3)  |  ((top_row[1] & 0x00100010) << 2)  |  ((top_row[2] & 0x00100010) << 1)  |  (top_row[3] & 0x00100010);

/******************************/     /******************************/     /******************************/     /******************************/
/*  cube 03 moved to cube 05  */     /*  cube 07 moved to cube 06  */     /*  cube 11 moved to cube 07  */     /*  cube 15 moved to cube 08  */
/******************************/     /******************************/     /******************************/     /******************************/
		new_bitboard_cube.cube_top[1] = ((top_row[0] & 0x00200020) << 2)  |  ((top_row[1] & 0x00200020) << 1)  |  (top_row[2] & 0x00200020)         |  ((top_row[3] & 0x00200020) >> 1);


/******************************/     /******************************/     /******************************/     /******************************/
/*  cube 02 moved to cube 09  */     /*  cube 06 moved to cube 10  */     /*  cube 10 moved to cube 11  */     /*  cube 14 moved to cube 12  */
/******************************/     /******************************/     /******************************/     /******************************/
		new_bitboard_cube.cube_top[2] = ((top_row[0] & 0x00400040) << 1)  |  (top_row[1] & 0x00400040)         |  ((top_row[2] & 0x00400040) >> 1)  |  ((top_row[3] & 0x00400040) >> 2);



/******************************/     /******************************/     /******************************/     /******************************/
/*  cube 01 moved to cube 13  */     /*  cube 05 moved to cube 14  */     /*  cube 09 moved to cube 15  */     /*  cube 13 moved to cube 16  */
/******************************/     /******************************/     /******************************/     /******************************/
		new_bitboard_cube.cube_top[3] = (top_row[0] & 0x00800080)         |  ((top_row[1] & 0x00800080) >> 1)  |  ((top_row[2] & 0x00800080) >> 2)  |  ((top_row[3] & 0x00800080) >> 3);


		/*********************************/             /*********************************/
		/*  01   *  02   *  03   *   04  */             /*  04   *  08   *  12   *   16  */
		/*********************************/             /*********************************/
		/*  05   *  06   *  07   *   08  */             /*  03   *  07   *  11   *   15  */
		/*********************************/             /*********************************/
		/*  09   *  10   *  11   *   12  */             /*  02   *  06   *  10   *   14  */
		/*********************************/             /*********************************/
		/*  13   *  14   *  15   *   16  */             /*  01   *  05   *  09   *   13  */
		/*********************************/             /*********************************/


		/*****************************************************************/
		/* Part IV: Do the same for each wrap-around 4-face linked list  */
		/*          that involves the TOP bits.                          */
		/*****************************************************************/	

		top_row[0] = original_4x4x4_bitboard_cube.cube_bottom[0] & 0xF000F000;
		top_row[1] = original_4x4x4_bitboard_cube.cube_bottom[1] & 0xF000F000;
		top_row[2] = original_4x4x4_bitboard_cube.cube_bottom[2] & 0xF000F000;
		top_row[3] = original_4x4x4_bitboard_cube.cube_bottom[3] & 0xF000F000;
	
		/*********************************************************/
		/*                                                       */
		/* BOTTOM BITBOARD LAYOUT = 0xF000F000 for each row      */
		/*                                                       */
		/*********************************************************/
		/*   T  *   L  *   B  *   R  *   T  *   L  *  B   *  R   */
		/*********************************************************/
		/* 1111 * 0000 * 0000 * 0000 * 1111 * 0000 * 0000 * 0000 */
		/* 1111 * 0000 * 0000 * 0000 * 1111 * 0000 * 0000 * 0000 */
		/* 1111 * 0000 * 0000 * 0000 * 1111 * 0000 * 0000 * 0000 */
		/* 1111 * 0000 * 0000 * 0000 * 1111 * 0000 * 0000 * 0000 */
		/*********************************************************/	

		new_bitboard_cube.cube_top[0] = ((top_row[0] & 0x10001000) << 3)  |  ((top_row[1] & 0x10001000) << 2)  |  ((top_row[2] & 0x10001000) << 1)  |  (top_row[3] & 0x10001000);
		new_bitboard_cube.cube_top[1] = ((top_row[0] & 0x20002000) << 2)  |  ((top_row[1] & 0x20002000) << 1)  |  (top_row[2] & 0x20002000)         |  ((top_row[3] & 0x20002000) >> 1);
		new_bitboard_cube.cube_top[2] = ((top_row[0] & 0x30003000) << 1)  |  (top_row[1] & 0x30003000)         |  ((top_row[2] & 0x30003000) >> 1)  |  ((top_row[3] & 0x30003000) >> 2);
		new_bitboard_cube.cube_top[3] = (top_row[0] & 0x40004000)         |  ((top_row[1] & 0x40004000) >> 1)  |  ((top_row[2] & 0x40004000) >> 2)  |  ((top_row[3] & 0x40004000) >> 3);

		return new_bitboard_cube;
}
A very big difference in thinking. For example, this part alone:

Code:
		new_bits = original_4x4x4_bitboard_cube.cube_left[0] >> 4;
		new_bitboard_cube.cube_left[0] = (((new_bits & 0x0000FFFF) << 16) & 0xFFFF0000)   |   (new_bits & 0x0000FFFF);
...does all of this from the other code...

Code:
	new_cube.cube_front[0] = original_4x4x4_cube.cube_left[0];
	new_cube.cube_front[1] = original_4x4x4_cube.cube_left[1];
	new_cube.cube_front[2] = original_4x4x4_cube.cube_left[2];
	new_cube.cube_front[3] = original_4x4x4_cube.cube_left[3];

	new_cube.cube_right[0] = original_4x4x4_cube.cube_front[0];
	new_cube.cube_right[1] = original_4x4x4_cube.cube_front[1];
	new_cube.cube_right[2] = original_4x4x4_cube.cube_front[2];
	new_cube.cube_right[3] = original_4x4x4_cube.cube_front[3];

	new_cube.cube_back[0] = original_4x4x4_cube.cube_right[0];
	new_cube.cube_back[1] = original_4x4x4_cube.cube_right[1];
	new_cube.cube_back[2] = original_4x4x4_cube.cube_right[2];
	new_cube.cube_back[3] = original_4x4x4_cube.cube_right[3];

	new_cube.cube_left[0] = original_4x4x4_cube.cube_back[0];
	new_cube.cube_left[1] = original_4x4x4_cube.cube_back[1];
	new_cube.cube_left[2] = original_4x4x4_cube.cube_back[2];
	new_cube.cube_left[3] = original_4x4x4_cube.cube_back[3];
I came up with the idea to place all 4 rotated faces together, side-by-side, then copy them again, side by side, like this:

Code:
		/*********************************************************/
		/*                                                       */
		/* TOP BITBOARD LAYOUT = 0x00F000F0 for each row         */
		/*                                                       */
		/*********************************************************/
		/*   B  *   L  *   T  *   R  *   B  *   L  *  T   *  R   */
		/*********************************************************/
		/* 0000 * 0000 * 1111 * 0000 * 0000 * 0000 * 1111 * 0000 */
		/* 0000 * 0000 * 1111 * 0000 * 0000 * 0000 * 1111 * 0000 */
		/* 0000 * 0000 * 1111 * 0000 * 0000 * 0000 * 1111 * 0000 */
		/* 0000 * 0000 * 1111 * 0000 * 0000 * 0000 * 1111 * 0000 */
		/*********************************************************/
Bottom, Left, Top, Right, Bottom, Left, Top, Right

A "0" indicates there is no "top" piece present. A "1" indicates there is a top piece present.

There will be one of these bitboards for EVERY face, so 6 all in total.

The beauty of this approach is, a bit never "falls off" the board, no matter how many times you rotate the cube, IF... you do one little trick.

Code:
	/*********************************************************/
	/*                                                       */
	/* LEFT BITBOARD LAYOUT, WRAP-AROUND 4-FACE LINKED LIST  */
	/*                                                       */
	/* 32 bits for each horizontal row of the 4x4x4 cube. No */
	/* way to shift bits off of the bitboard, even after more*/
	/* than one doube-turn of the same face, IF the bits are */
	/* copied from one half to the other half after each one */
	/* of the shifting operations (turn of the cube) is done.*/
	/*********************************************************/
	/*   R  *   K  *   L  *   F  *   R  *   K  *   L  *  F   */
	/*********************************************************/
	/* 0000 * 0000 * 1111 * 0000 * 0000 * 0000 * 1111 * 0000 */
	/* 0000 * 0000 * 1111 * 0000 * 0000 * 0000 * 1111 * 0000 */
	/* 0000 * 0000 * 1111 * 0000 * 0000 * 0000 * 1111 * 0000 */
	/* 0000 * 0000 * 1111 * 0000 * 0000 * 0000 * 1111 * 0000 */
	/*********************************************************/
Consider that U' rotates L to F to R to K (what I call "back") to L.

All I have to do is shift all of these bits 4 to the right after such a move:

Code:
	/*********************************************************/
	/*   R  *   K  *   L  *   F  *   R  *   K  *   L  *  F   */
	/*********************************************************/
	/* 0000 * 0000 * 0000 * 1111 * 0000 * 0000 * 0000 * 1111 */
	/* 0000 * 0000 * 0000 * 1111 * 0000 * 0000 * 0000 * 1111 */
	/* 0000 * 0000 * 0000 * 1111 * 0000 * 0000 * 0000 * 1111 */
	/* 0000 * 0000 * 0000 * 1111 * 0000 * 0000 * 0000 * 1111 */
	/*********************************************************/
And, with the exception of the rotated face, I am done! What could be quicker?

Now, the "trick" is to copy the RIGHT-MOST cluster of R K L F and "stamp" those bits to the LEFT-MOST cluster,
and then all "off the board" bit shifts to the right are taken care of, forever.

Once I get all of these details worked out, you can see how this will be so-called "magic."

Also, you keep mentioning this "fast hardware" you have access to. Can you elaborate? What
processor, what motherboard, etc.? I'm always interested in getting the fastest hardware I can
for this sort of thing.
Oh, I am talking about a $145,000 cluster of 40 CPU cores running at 5.40 GHz each. Probably not the kind of thing you have at home. I haven't tapped all of the cores yet, but I will once I write the Linux version of this thing :)

5400_MHz_Ivy_Server.jpg
 
Last edited:

rokicki

Member
Joined
Oct 31, 2008
Messages
270
Be sure to let us know how much that speeds things up!

If you switch to a cubie representation, your piece count goes down from 6*16=96 to 8+24+24=56.
This may provide substantial speedup as well.

The server looks sweet! You're right, I don't have anything like that at home.

Thanks for keeping us all up to date on your progress.
 

unsolved

Member
Joined
Mar 2, 2014
Messages
566
Location
Doylestown, PA
Be sure to let us know how much that speeds things up!
It's a ways off yet. Once I do get it cranking, and fully parallel, it will be interesting!

But, as I mentioned in a prior post, even if it were 1,000 times faster, it would only search 2 moves more deeply than it does now. Why? The branching factor of the 4x4x4 cube is roughly 30x per depth, which means 30 times as many positions for each 1 move additionally searched. So 30x30 = 900 times as long to search 2 more moves ahead, etc.

That is why I need to focus on ways to reduce the size of the tree more than speeding up the search speed. Even a speedup of 1,000,000 times is only worth 4 more moves of search!

If you switch to a cubie representation, your piece count goes down from 6*16=96 to 8+24+24=56.
This may provide substantial speedup as well.
I am guessing by cubie you mean the 3x3x3? There are so many solvers out there for that now, I am letting them enjoy their peace :)

I want to concentrate on 4x4x4 for now, and when/if I get a fast bitboard engine up and running with large enough pruning databases, I'll switch to 5x5x5.

The server looks sweet! You're right, I don't have anything like that at home.
Here is my home rig, running at -50 degrees Celsius = -58 degrees Fahrenheit @ 5.35 GHz on the Intel i7-3770K:


http://lightningcloudcomputing.com/lightning__box.jpg
 
Status
Not open for further replies.
Top