irontwig
Member
Well, those cases are exceptions and you can always do a cyclic shift if you find that kind of solution.
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.I too am interested to see if this solver can find a 9 mover.
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 hereI 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
The "distance" numbers indicates the actual goal value (desired solution length) for each step of the iterative deepening.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
OK, thanks.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.
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;
}
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.Are you using a bit-move generator, or matrices and arrays?
I'd like to compare code at one point.
The guts of my matrix version of the move generator showing the functions for R+ and R-.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.
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;
}
#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;
}
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);
}
This guy looks rather scrambling to me. Are you guys all seeing just a center-3-cycle when you play it?
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).as far as I know relatively recent, discovery of "pseudo-slice" commutators of the form [D b D', l'] and [(Uu) r (Uu)', l']
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.Well, at least [post=241223]from 2009[/post] (just clarifying cause "relatively recent" is rather vague and confused at least me).
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.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).
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).what would you suggest calling this case-that-should-probably-not-be-named "pseudo-slicing"?
Ooooooohh... I had the "twisty.js beta" checked. If I uncheck that, it looks good to me as well. Thanks.
I just compiled a much faster version of my program, thanks to the excellent advice I received from Jakube.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.
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.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, but for the sake of completeness, and the fact it takes no time, I just leave it in there.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, 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.)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.
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.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.
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).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.
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;
}
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;
}
new_bits = original_4x4x4_bitboard_cube.cube_left[0] >> 4;
new_bitboard_cube.cube_left[0] = (((new_bits & 0x0000FFFF) << 16) & 0xFFFF0000) | (new_bits & 0x0000FFFF);
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];
/*********************************************************/
/* */
/* 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 */
/*********************************************************/
/*********************************************************/
/* */
/* 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 */
/*********************************************************/
/*********************************************************/
/* 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 */
/*********************************************************/
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 thingAlso, 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.
It's a ways off yet. Once I do get it cranking, and fully parallel, it will be interesting!Be sure to let us know how much that speeds things up!
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 peaceIf 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.
Here is my home rig, running at -50 degrees Celsius = -58 degrees Fahrenheit @ 5.35 GHz on the Intel i7-3770K:The server looks sweet! You're right, I don't have anything like that at home.
No. Check out "The Cubie Level" in the Cube Explorer documentation suggested earlier:I am guessing by cubie you mean the 3x3x3?
Thread starter | Similar threads | Forum | Replies | Date |
---|---|---|---|---|
M | Announcing: Vintage Cube Sale/Store | Buy, Sell, Trade | 3 | |
Announcing our new Canadian collab channel, Cubing Province | Puzzle Video Gallery | 1 | ||
Announcing new online PLL Trainer | Software Area | 0 | ||
Announcing sundaycontest.com! | General Speedcubing Discussion | 135 | ||
C | Announcing 0Cube | Puzzle Building, Modding, & Designing | 78 |