nissy-classic

commit 131428b913a3d42f26714b8e5e873d8112db10c0
parent 2bbd9cd6024e32009ddee908b5328918601ff9f8
Author: Sebastiano Tronto <sebastiano.tronto@gmail.com>
Date:   Wed,  8 Dec 2021 10:49:44 +0100

Faster ptable generation (but I can make it faster)

Diffstat:
M
TODO.md
 | 
23
+++++++++++++++++++++--
M
nissy
 | 
0

M
src/pruning.c
 | 
54
+++++++++++++++++++++++++++++++++++++++++++++---------

3 files changed, 66 insertions(+), 11 deletions(-)
diff --git a/TODO.md b/TODO.md
@@ -42,11 +42,31 @@ It's more of a personal reminder than anything else.
   in non-posix systems
 * better man page
 * find a better way to distribute the large tables, especially khuge
+(or just generate them quickly, see below)
 * webapp (cgi)
 
 ## Technical stuff
 
-### Better pruning tables
+## Performance (optimal solver)
+* Khuge optimal solver: change direction of search when doing so leads to
+less branching (like nxopt). Need to add some info to EstimateData or to
+DfsData (like last moves on inverse/other scramble) and to change some of
+the logic of niss (allow for switching multiple times).
+* Light optimal solver: use drud table instead of khuge, with tricks as above
+and one more trick: if the last move is 180° avoid computing inverse cube
+and just use previous values for all 3 axes.
+
+## Coordinates, symmetries, pruning tables
+* use multiple threads to search for solutions in parallel
+* Faster pruning table generation: keep track of which positions are "nasty"
+(i.e. self-symmetric with respect to the base symmetry coordinate but not
+self-symmetric overall) by adding a function to struct coord and some datafield
+to struct symdata.
+* Faster pruning table generation: multithreading (divide table into large
+sections and use one mutex for each section to avoid too much locking)
+* Cleanup symcoord.c: some coordinates and symdata are never actually used;
+remove also sd_eofbepos and just use sd_coud for khuge (this changes the
+coordinate so the whole table must be generated again!)
 * Use pruning values mod 4 instead of mod 16 (or maybe not, I like the
 current system)
 
@@ -60,4 +80,3 @@ current system)
 * client/server architecture: run a server process in the background so that
   multiple client processess can send it queries and get results; this would
   open up the door for a web-based version or graphical clients
-* use multiple threads to search for solutions in parallel
diff --git a/nissy b/nissy
Binary files differ.
diff --git a/src/pruning.c b/src/pruning.c
@@ -144,7 +144,25 @@ genptable(PruneData *pd)
 static void
 genptable_bfs(PruneData *pd, int d, Move *ms)
 {
+	int j;
 	uint64_t i;
+	Cube c, cc;
+
+	for (i = 0; i < pd->coord->max; i++) {
+		/*
+		 * TODO: only do this if the position is "nasty",
+		 * i.e. self-symmetrical with respect to the base
+		 * coordinate but not overall.
+		 */
+		 if (ptableval_index(pd, i) == d) {
+			c = pd->coord->cube(i);
+			for (j = 0; j < pd->coord->ntrans; j++) {
+				cc = apply_trans(pd->coord->trans[j], c);
+				if (ptableval(pd, cc) > d)
+					ptable_update(pd, cc, d);
+			}
+		}
+	}
 
 	for (i = 0; i < pd->coord->max; i++)
 		if (ptableval_index(pd, i) == d)
@@ -154,11 +172,6 @@ genptable_bfs(PruneData *pd, int d, Move *ms)
 static void
 genptable_branch(PruneData *pd, uint64_t ind, int d, Move *ms)
 {
-	int i, j;
-	Cube ci, cc, c;
-
-	ci = pd->coord->cube(ind);
-
 	/*
 	 * Here we deal with the following problem:
 	 * The set of positions reached by applying each move to
@@ -186,6 +199,15 @@ genptable_branch(PruneData *pd, uint64_t ind, int d, Move *ms)
 	 * efficient and allows for removing the ntrans and trans
 	 * field from struct coordinate.
 	 */
+	/* Work in progress, first attempt */
+
+	/*
+	int i, j;
+	Cube ci, cc, c;
+
+
+	ci = pd->coord->cube(ind);
+
 	for (i = 0; i < pd->coord->ntrans; i++) {
 		c = i == 0 ? ci :
 			     apply_trans(pd->coord->trans[i], ci);
@@ -195,6 +217,18 @@ genptable_branch(PruneData *pd, uint64_t ind, int d, Move *ms)
 				ptable_update(pd, cc, d+1);
 		}
 	}
+	*/
+
+	int i;
+	Cube c, cc;
+
+	c = pd->coord->cube(ind);
+
+	for (i = 0; ms[i] != NULLMOVE; i++) {
+		cc = apply_move(ms[i], c);
+		if (ptableval(pd, cc) > d+1)
+			ptable_update(pd, cc, d+1);
+	}
 }
 
 void
@@ -225,15 +259,17 @@ ptablesize(PruneData *pd)
 static void
 ptable_update(PruneData *pd, Cube cube, int n)
 {
-	uint64_t ind = pd->coord->index(cube);
-	ptable_update_index(pd, ind, n);
+	ptable_update_index(pd, pd->coord->index(cube), n);
 }
 
 static void
 ptable_update_index(PruneData *pd, uint64_t ind, int n)
 {
-	uint8_t oldval2 = pd->ptable[ind/2];
-	int other = (ind % 2) ? oldval2 % 16 : oldval2 / 16;
+	uint8_t oldval2;
+	int other;
+
+	oldval2 = pd->ptable[ind/2];
+	other = (ind % 2) ? oldval2 % 16 : oldval2 / 16;
 
 	pd->ptable[ind/2] = (ind % 2) ? 16*n + other : 16*other + n;
 	pd->n++;