irontwig
Member
Well, those cases are exceptions and you can always do a cyclic shift if you find that kind of solution.
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
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
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;
}
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.
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);
}
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).
what would you suggest calling this case-that-should-probably-not-be-named "pseudo-slicing"?
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, 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.
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 */
/*********************************************************/
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.
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!
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.
I am guessing by cubie you mean the 3x3x3?