Commits

Anonymous committed f36ee91

first pass at using depth % 3 for pruning tables. only 1 table per phase. still extremely sloppy, and slower than I'd like.

Comments (0)

Files changed (1)

 /* the co_ eo_ cp_ ep_ arrays are used to store the original cube state */
 uint8_t  co_[8],            eo_[12],           cp_[8],             ep_[12];
 uint16_t co_trans[2187][6], eo_trans[2048][6], cp_trans[40320][6], ep_trans[40320][6], ud1_trans[495][6], ud2_trans[24][6];
-uint8_t  coeo_prune[2187][2048], coud1_prune[2187][495], eoud1_prune[2048][495], cpud2_prune[40320][24], epud2_prune[40320][24];
+uint8_t  p1_prune[2187][2048][495/4+1], p2_prune[40320][40320/4];
+
+#define GET_P1_PRUNE(c, e, ud)   ((p1_prune[(c)][(e)][(ud)/4] >> ((ud) % 4 * 2)) & 0x03)
+#define SET_P1_PRUNE(c, e, ud, p) (p1_prune[(c)][(e)][(ud)/4] = (p1_prune[(c)][(e)][(ud)/4] & ~(0x03 << ((ud) % 4 * 2))) | ((p) << ((ud) % 4 * 2)))
+
+#define GET_P2_PRUNE(c, e)   ((p2_prune[(c)][(e)/4] >> ((e) % 4 * 2)) & 0x03)
+#define SET_P2_PRUNE(c, e, p) (p2_prune[(c)][(e)/4] = (p2_prune[(c)][(e)/4] & ~(0x03 << ((e) % 4 * 2))) | ((p) << ((e) % 4 * 2)))
 
 /*
  * phases are:
 	if (verbose) printf("done\n");
 }
 
-/*
- * generic pruning table initialization
- */
-void init_prune(int phase, int coordi, uint16_t trans_tablei[][6], int coordj, uint16_t trans_tablej[][6], int maxi, int maxj, uint8_t prune_table[maxi][maxj], int mdepth, int depth, int last)
+void init_p2_prune(void)
 {
-	int k, face, oldi = coordi, oldj = coordj;
+	int d, face, c, e, nc, ne, m, maxc, maxe;
 
-	if (depth == mdepth || prune_table[coordi][coordj] <= depth)
-		return;
+	maxc = maxe = 40320;
 
-	prune_table[coordi][coordj] = depth;
+	SET_P2_PRUNE(0, 0, 0);
 
-	for (face = 0; face < 6; face++, coordi = oldi, coordj = oldj) {
-		if (face == last) /* don't include turns on the same face as last time */
-			continue;
-		for (k = 0; k < 3; k++) {
-			coordi = trans_tablei[coordi][face];
-			coordj = trans_tablej[coordj][face];
-			init_prune(phase, coordi, trans_tablei, coordj, trans_tablej, maxi, maxj, prune_table, mdepth, depth + 1, last);
-			if (phase == PHASE2 && face > 1) /* only want double turns on F, B, R, L in G1 */
-				break;
+	if (verbose) printf("\nDepth: 0.");
+	for (d = 0; d < 13; d++) {
+		if (verbose) { printf("%d.", d + 1); fflush(stdout); }
+		for (c = 0; c < maxc; c++) {
+			for (e = 0; e < maxe; e++) {
+				if (GET_P2_PRUNE(c, e) != d % 3)
+					continue;
+				for (face = 0; face < 6; face++) {
+					for (m = 0, nc = c, ne = e; m < 3; m++) {
+						nc = cp_trans[nc][face];
+						ne = ep_trans[ne][face];
+						if (GET_P2_PRUNE(nc, ne) == 0x03)
+							SET_P2_PRUNE(nc, ne, (d + 1) % 3);
+						if (face > 1)
+							break;
+					}
+				}
+			}
+		}
+	}
+	for (d = 13; d < 18; d++) {
+		if (verbose) { printf("%d.", d + 1); fflush(stdout); }
+		for (c = 0; c < maxc; c++) {
+			for (e = 0; e < maxe; e++) {
+				if (GET_P2_PRUNE(c, e) == 0x03) {
+					for (face = 0; face < 6; face++) {
+						for (m = 0, nc = c, ne = e; m < 3; m++) {
+							nc = cp_trans[nc][face];
+							ne = ep_trans[ne][face];
+							if (GET_P2_PRUNE(nc, ne) == d % 3) {
+								SET_P2_PRUNE(c, e, (d + 1) % 3);
+								face = 6;
+								break;
+							}
+							if (face > 1)
+								break;
+						}
+					}
+				}
+			}
+		}
+	}
+}
+
+void init_p1_prune(void)
+{
+	int c, e, ud, nc, ne, nud, d, face, m, maxc, maxe, maxud;
+
+	maxc  = 2187;
+	maxe  = 2048;
+	maxud =  495;
+
+	SET_P1_PRUNE(0, 0, 0, 0);
+
+	if (verbose) printf("\nDepth: 0.");
+	for (d = 0; d < 9; d++) {
+		if (verbose) { printf("%d.", d + 1); fflush(stdout); }
+		for (c = 0; c < maxc; c++) {
+			for (e = 0; e < maxe; e++) {
+				for (ud = 0; ud < maxud; ud++) {
+					if (GET_P1_PRUNE(c, e, ud) != d % 3)
+						continue;
+					for (face = 0; face < 6; face++) {
+						for (m = 0, nc = c, ne = e, nud = ud; m < 3; m++) {
+							nc  =  co_trans[nc ][face];
+							ne  =  eo_trans[ne ][face];
+							nud = ud1_trans[nud][face];
+							if (GET_P1_PRUNE(nc, ne, nud) == 0x03)
+								SET_P1_PRUNE(nc, ne, nud, (d + 1) % 3);
+						}
+					}
+				}
+			}
+		}
+	}
+	for (d = 9; d < 12; d++) {
+		if (verbose) { printf("%d.", d + 1); fflush(stdout); }
+		for (c = 0; c < maxc; c++) {
+			for (e = 0; e < maxe; e++) {
+				for (ud = 0; ud < maxud; ud++) {
+					if (GET_P1_PRUNE(c, e, ud) == 0x03) {
+						for (face = 0; face < 6; face++) {
+							for (m = 0, nc = c, ne = e, nud = ud; m < 3; m++) {
+								nc  = co_trans [nc ][face];
+								ne  = eo_trans [ne ][face];
+								nud = ud1_trans[nud][face];
+								if (GET_P1_PRUNE(nc, ne, nud) == d % 3) {
+									SET_P1_PRUNE(c, e, ud, (d + 1) % 3);
+									face = 6;
+									break;
+								}
+							}
+						}
+					}
+				}
+			}
 		}
 	}
 }
  */
 void init_prune_tables(void)
 {
-	memset(coeo_prune, 0xff, sizeof(coeo_prune));
-	memset(coud1_prune, 0xff, sizeof(coud1_prune));
-	memset(eoud1_prune, 0xff, sizeof(eoud1_prune));
-	memset(cpud2_prune, 0xff, sizeof(cpud2_prune));
-	memset(epud2_prune, 0xff, sizeof(epud2_prune));
+	memset(p1_prune, 0xff, sizeof(p1_prune));
+	memset(p2_prune, 0xff, sizeof(p2_prune));
 
-	if (verbose) { printf("Initializing phase 1 pruning tables..."); fflush(stdout); }
-	init_prune(PHASE1, 0, co_trans, 0, eo_trans, 2187, 2048, coeo_prune, 10, 0, -1);
-	init_prune(PHASE1, 0, co_trans, 0, ud1_trans, 2187, 495, coud1_prune, 10, 0, -1);
-	init_prune(PHASE1, 0, eo_trans, 0, ud1_trans, 2048, 495, eoud1_prune, 10, 0, -1);
+	if (verbose) { printf("Initializing phase 1 pruning table..."); fflush(stdout); }
+	init_p1_prune();
 	if (verbose) printf("done\n");
 
-	if (verbose) { printf("Initializing phase 2 pruning tables..."); fflush(stdout); }
-	init_prune(PHASE2, 0, cp_trans, 0, ud2_trans, 40320, 24, cpud2_prune, 15, 0, -1);
-	init_prune(PHASE2, 0, ep_trans, 0, ud2_trans, 40320, 24, epud2_prune, 13, 0, -1);
+	if (verbose) { printf("Initializing phase 2 pruning table..."); fflush(stdout); }
+	init_p2_prune();
 	if (verbose) printf("done\n");
 }
 
 		memcpy(cp_, cp, sizeof(cp));
 		memcpy(ep_, ep, sizeof(ep));
 	}
-	int f = 0;
-	f |= memcmp(co_, co, sizeof(co));
-	f |= memcmp(eo_, eo, sizeof(eo));
-	f |= memcmp(cp_, cp, sizeof(cp));
-	f |= memcmp(ep_, ep, sizeof(ep));
-	if (f) { fprintf(stderr, "CUBES NOT EQUAL\n"); exit(EXIT_FAILURE); }
 }
 
 char *sprint_solution(char *str)
 	fflush(stdout);
 }
 
+int find_p1_depth(int c, int e, int ud)
+{
+	int i, j, face, c_tmp, e_tmp, ud_tmp;
+
+	for (i = 0; c || e || ud; i++) {
+		for (face = 0; face < 6; face++) {
+			c_tmp  = c;
+			e_tmp  = e;
+			ud_tmp = ud;
+			for (j = 0; j < 3; j++) {
+				c_tmp  = co_trans [c_tmp ][face];
+				e_tmp  = eo_trans [e_tmp ][face];
+				ud_tmp = ud1_trans[ud_tmp][face];
+				if ((GET_P1_PRUNE(c_tmp, e_tmp, ud_tmp) + 1) % 3 == GET_P1_PRUNE(c, e, ud)) {
+					c  = c_tmp;
+					e  = e_tmp;
+					ud = ud_tmp;
+					face = 6;
+					break;
+				}
+			}
+		}
+	}
+	return i;
+}
+
+int find_p2_depth(int c, int e)
+{
+	int i, j, face, c_tmp, e_tmp;
+
+	for (i = 0; c || e; i++) {
+		for (face = 0; face < 6; face++) {
+			c_tmp = c;
+			e_tmp = e;
+			for (j = 0; j < 3; j++) {
+				c_tmp = cp_trans[c_tmp][face];
+				e_tmp = ep_trans[e_tmp][face];
+				if ((GET_P2_PRUNE(c_tmp, e_tmp) + 1) % 3 == GET_P2_PRUNE(c, e)) {
+					c = c_tmp;
+					e = e_tmp;
+					face = 6;
+					break;
+				}
+				if (face > 1)
+					break;
+			}
+		}
+	}
+	return i;
+}
+
 int begin_phase2(int last)
 {
-	int i, solved;
+	int i, solved = 0, prune_depth;
 
 	copy_cube(1, co_, eo_, cp_, ep_);
 	for (i = 20 - p1_len; i < 20; i++)
 		do_move(sol[i]);
 
-	for (p2_len = 0; (!all_sol && p2_len + p1_len < len) || (all_sol && p2_len + p1_len <= len); p2_len++)
-		if ((solved = solve(PHASE2, get_ep_coord(), get_cp_coord(), get_ud2_coord(), p2_len, last)) || optimal)
+	prune_depth = find_p2_depth(get_cp_coord(), get_ep_coord());
+	for (p2_len = prune_depth; (!all_sol && p2_len + p1_len < len) || (all_sol && p2_len + p1_len <= len); p2_len++) {
+		if ((solved = solve(PHASE2, get_cp_coord(), get_ep_coord(), get_ud2_coord(), p2_len, prune_depth, last)) || optimal)
 			break;
+	}
 	if (solved <= 0)
 		return solved;
 	if ((!all_sol && p2_len + p1_len < len) || (all_sol && p2_len + p1_len <= len)) {
 /*
  * phase solver
  */
-int solve(int phase, int e_coord, int c_coord, int ud_coord, int depth, int last)
+int solve(int phase, int c_coord, int e_coord, int ud_coord, int depth, int prune_depth, int last)
 {
 	int i, e_tmp, c_tmp, ud_tmp, face, solved;
+	int np, cp;
+	int dp[3] = { 0, -1, 1 };
 
 	if (sigtstp || (timeout && num)) return -1;
 	if (e_coord == 0 && c_coord == 0 && ud_coord == 0) { /* found a solution */
 		else if (depth != 0) return 0;
 		else return begin_phase2(last);
 	}
-	if (phase == PHASE1 && (depth == 0 || coeo_prune [c_coord][e_coord ] > depth || coud1_prune[c_coord][ud_coord] > depth || eoud1_prune[e_coord][ud_coord] > depth)) return 0;
-	if (phase == PHASE2 && (depth == 0 || cpud2_prune[c_coord][ud_coord] > depth || epud2_prune[e_coord][ud_coord] > depth)) return 0;
+	/* would it make sense to move these checks down to _before_ a call to solve? didn't notice a big improvement */
+	if (depth == 0 || prune_depth > depth) return 0;
+
+	if (phase == PHASE1) cp = GET_P1_PRUNE(c_coord, e_coord, ud_coord);
+	else                 cp = GET_P2_PRUNE(c_coord, e_coord);
 
 	for (face = 0; face < 6; face++) {
 		/* no two moves in a row on same face, no move on same axis after U, F, R */
 			if (phase == PHASE1) sol[20 - depth] = face * 3 + i;
 			else                 sol[38 - depth] = face * 3 + ((face > 1) ? 1 : i);
 
-			if ((solved = solve(phase, e_tmp, c_tmp, ud_tmp, depth - 1, face))) return solved;
+			if (phase == PHASE1) np = prune_depth + dp[(cp - GET_P1_PRUNE(c_tmp, e_tmp, ud_tmp) + 3) % 3];
+			else                 np = prune_depth + dp[(cp - GET_P2_PRUNE(c_tmp, e_tmp) + 3) % 3];
+
+			if ((solved = solve(phase, c_tmp, e_tmp, ud_tmp, depth - 1, np, face))) return solved;
 			if (phase == PHASE2 && face > 1) break;
 		}
 	}
 
 void write_all(int fd, void *buf, size_t count)
 {
-	int wrote;
+	ssize_t wrote;
 	void *start = buf;
 
 	while (count) {
 
 void read_all(int fd, void *buf, size_t count)
 {
-	int red;
+	ssize_t red;
 	void *start = buf;
 
 	while (count) {
 	write_all(fd, cp_trans, sizeof(cp_trans));
 	write_all(fd, ep_trans, sizeof(ep_trans));
 	write_all(fd, ud2_trans, sizeof(ud2_trans));
-	write_all(fd, coeo_prune, sizeof(coeo_prune));
-	write_all(fd, coud1_prune, sizeof(coud1_prune));
-	write_all(fd, eoud1_prune, sizeof(eoud1_prune));
-	write_all(fd, cpud2_prune, sizeof(cpud2_prune));
-	write_all(fd, epud2_prune, sizeof(epud2_prune));
+
+	write_all(fd, p1_prune, sizeof(p1_prune));
+	write_all(fd, p2_prune, sizeof(p2_prune));
 
 	if (close(fd) < 0) {
 		printf("failed to close table file\n");
 	read_all(fd, cp_trans, sizeof(cp_trans));
 	read_all(fd, ep_trans, sizeof(ep_trans));
 	read_all(fd, ud2_trans, sizeof(ud2_trans));
-	read_all(fd, coeo_prune, sizeof(coeo_prune));
-	read_all(fd, coud1_prune, sizeof(coud1_prune));
-	read_all(fd, eoud1_prune, sizeof(eoud1_prune));
-	read_all(fd, cpud2_prune, sizeof(cpud2_prune));
-	read_all(fd, epud2_prune, sizeof(epud2_prune));
+
+	read_all(fd, p1_prune, sizeof(p1_prune));
+	read_all(fd, p2_prune, sizeof(p2_prune));
 
 	if (close(fd) < 0) {
 		printf("failed to close table file\n");
 		exit(EXIT_FAILURE);
 	}
 }
-
-struct cbuf {
-	int beg, end, size;
-	char nums[1001];
-};
-void add_num(struct cbuf *nums, int n)
-{
-	nums->end = (nums->end + 1) % nums->size;
-	if (nums->end == nums->beg)
-		nums->beg = (nums->beg + 1) % nums->size;
-	nums->nums[nums->end] = n;
-}
-
-double get_avg(struct cbuf *nums, int size)
-{
-	int i, j, sum = 0;
-
-	for (i = nums->end, j = size; j; i--, j--) {
-		if (i < 0) i = nums->size - 1;
-		if (i == nums->beg) break;
-		sum += nums->nums[i];
-	}
-	return (double)sum / (double)(size - j);
-}
-
-#define member_size(x,y) sizeof(((struct x*)0)->y)
 int main(int argc, char **argv)
 {
 	struct sigaction s = { .sa_handler = signal_handler };
 
 	char buf[128];
-	int i, oold_len;
+	int i, oold_len, prune_depth;
 	int total_solves = 0;
 	int total_moves = 0;
-	double tiny_avg, small_avg, big_avg, avg_len;
-	double otiny_avg, osmall_avg, obig_avg;
-	double tiny_avgd, small_avgd, big_avgd;
-	struct cbuf lens = { 0, 0, member_size(cbuf, nums) };
-	struct cbuf dlens = { 0, 0, member_size(cbuf, nums) };
 
 	while ((i = getopt(argc, argv, "1ad:gil:m:n:or:s:t:v")) != -1) {
 		switch (i) {
 		read_tables();
 	}
 
-	if (target) {
-		one_sol = 1;
-		timeout = 100;
-		avg_len = tiny_avg = small_avg = big_avg = target;
-		otiny_avg = osmall_avg = obig_avg = oold_len = target;
-		tiny_avgd = small_avgd = big_avgd = 0;
-		if (sigaction(SIGVTALRM, &s, NULL) < 0) {
-			printf("sigaction failed\n");
-			exit(EXIT_FAILURE);
-		}
-	}
 	if (timeout || num_cps) {
 		//if (sigaction(SIGVTALRM, &s, NULL) < 0) {
 		if (sigaction(SIGALRM, &s, NULL) < 0) {
 			}
 		}
 
-		for (p1_len = 0; p1_len <= len && (!max_p1d || p1_len <= max_p1d); p1_len++) {
-			if (solve(PHASE1, get_eo_coord(), get_co_coord(), get_ud1_coord(), p1_len, -1))
+		prune_depth = find_p1_depth(get_co_coord(), get_eo_coord(), get_ud1_coord());
+		for (p1_len = prune_depth; p1_len <= len && (!max_p1d || p1_len <= max_p1d); p1_len++) {
+			if (solve(PHASE1, get_co_coord(), get_eo_coord(), get_ud1_coord(), p1_len, prune_depth, -1))
 				break;
 			if (verbose) { printf("finished phase 1 search depth %d\n", p1_len); fflush(stdout); }
 			copy_cube(1, co_, eo_, cp_, ep_);
 		}
 		if (one_sol) print_solution(1);
-		if (target) {
-			struct timeval dif, res;
-			double td, sd, bd, od;
-			int	us = 0;
-
-			// all of our statistics to work with
-			add_num(&lens, old_len);
-			tiny_avg  = get_avg(&lens,   10);
-			small_avg = get_avg(&lens,  100);
-			big_avg   = get_avg(&lens, 1000);
-
-			/*
-			add_num(&dlens, old_len - oold_len);
-			tiny_avgd  = get_avg(&dlens,   10);
-			small_avgd = get_avg(&dlens,  100);
-			big_avgd   = get_avg(&dlens, 1000);
-			*/
-
-			// scale exponentially
-			if (++total_solves % 10 == 0) {
-				us = tiny_avg * 10 - target * 10;
-				if (us < 0) us = - (1 << -((us < -10) ? -10 : us));
-				else        us =    1 <<  ((us >  10) ?  10 : us) ;
-				fprintf(stderr, "*");
-			} else
-				fprintf(stderr, " ");
-
-			// scale to 0-25% of timeout
-			int to;
-			to = iv.it_value.tv_sec * 1000000 + iv.it_value.tv_usec;
-			us = (double)to/4.0/1024.0 * (double)us;
-
-
-			// apply the difference to the timeout
-			if (us < 0) timersub(&iv.it_value, &((struct timeval){-us / 1000000,-us % 1000000 }), &res);
-			else        timeradd(&iv.it_value, &((struct timeval){ us / 1000000, us % 1000000 }), &res);
-			if (timercmp(&res, &((struct timeval){ 0, 0 }), <=)) res = (struct timeval){ 0, 1 };
-			iv.it_value = res;
-			fprintf(stderr, "now: %d(% d) tny: %f sml: %f big: %f dt: % 7.7d timeout: %d.%.6d\n",
-					old_len, old_len - oold_len, tiny_avg, small_avg, big_avg, us, iv.it_value.tv_sec, iv.it_value.tv_usec);
-			/*
-			fprintf(stderr, "now: %d(% d) tny: %f(% f) sml: %f(% f) big: %f(% f) dt: % 7.7d timeout: %d.%.6d\n",
-					old_len, old_len - oold_len, tiny_avg, tiny_avgd, small_avg, small_avgd, big_avg, big_avgd, us, iv.it_value.tv_sec, iv.it_value.tv_usec);
-					*/
-			fflush(stderr);
-
-			oold_len = old_len;
-		}
 		if (verbose) printf("----------\n");
 	}
 	return 0;