Faster ptable generation (but I can make it faster)

3 files changed, 66 insertions, 11 deletions

diff --git a/TODO.md b/TODO.md
index 7ab3287..f6c464b 100644
--- 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
index 8dae0c0..f559b2e 100755
--- a/nissy
+++ b/nissy
diff --git a/src/pruning.c b/src/pruning.c
index 5073d69..716379e 100644
--- 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++;