ref: cca302c01b7b331c280ec885d783d673a0c951c3
parent: 202e7fecfdac09b791b204cde464f09f9165f55b
author: Simon Tatham <anakin@pobox.com>
date: Thu Jan 15 15:21:05 EST 2015
Improve the Flood solver. Previously it simply chose every move based on the static evaluation function 'minimise the pair (longest shortest-path to any square, number of squares at that distance)'. Now it looks three moves ahead recursively, and I've also adjusted the evaluation function to tie- break based on the number of squares brought to distance zero (i.e. actually in control). The result isn't an unconditional improvement on the old solver; in a test run based on 'flood --generate 1000 12x12c6m0#12345' I found that 57 out of 1000 grids tested now had longer solutions. However, about three quarters had shorter ones, and solutions are more than a move shorter on average.
--- a/flood.c
+++ b/flood.c
@@ -27,6 +27,7 @@
#include <stdio.h>
#include <stdlib.h>
+#include <stdarg.h>
#include <string.h>
#include <assert.h>
#include <ctype.h>
@@ -221,21 +222,54 @@
return NULL;
}
+#if 0
+/*
+ * Bodge to permit varying the recursion depth for testing purposes.
+
+To test two Floods against each other:
+
+paste <(./flood.1 --generate 100 12x12c6m0#12345 | cut -f2 -d,) <(./flood.2 --generate 100 12x12c6m0#12345 | cut -f2 -d,) | awk '{print $2-$1}' | sort -n | uniq -c | awk '{print $2,$1}' | tee z+
+and then run gnuplot and plot "z".
+
+ */
+static int rdepth = 0;
+#define RECURSION_DEPTH (rdepth)
+void check_recursion_depth(void)
+{+ if (!rdepth) {+ const char *depthstr = getenv("FLOOD_DEPTH");+ rdepth = depthstr ? atoi(depthstr) : 1;
+ rdepth = rdepth > 0 ? rdepth : 1;
+ }
+}
+#else
+/*
+ * Last time I empirically checked this, depth 3 was a noticeable
+ * improvement on 2, but 4 only negligibly better than 3.
+ */
+#define RECURSION_DEPTH 3
+#define check_recursion_depth() (void)0
+#endif
+
struct solver_scratch {int *queue[2];
int *dist;
- char *grid, *grid2, *sparegrid;
+ char *grid, *grid2;
+ char *rgrids;
};
static struct solver_scratch *new_scratch(int w, int h)
{+ int wh = w*h;
struct solver_scratch *scratch = snew(struct solver_scratch);
- scratch->queue[0] = snewn(w*h, int);
- scratch->queue[1] = snewn(w*h, int);
- scratch->dist = snewn(w*h, int);
- scratch->grid = snewn(w*h, char);
- scratch->grid2 = snewn(w*h, char);
- scratch->sparegrid = snewn(w*h, char);
+ check_recursion_depth();
+ scratch->queue[0] = snewn(wh, int);
+ scratch->queue[1] = snewn(wh, int);
+ scratch->dist = snewn(wh, int);
+ scratch->grid = snewn(wh, char);
+ scratch->grid2 = snewn(wh, char);
+ scratch->rgrids = snewn(wh * RECURSION_DEPTH, char);
return scratch;
}
@@ -246,16 +280,24 @@
sfree(scratch->dist);
sfree(scratch->grid);
sfree(scratch->grid2);
- sfree(scratch->sparegrid);
+ sfree(scratch->rgrids);
sfree(scratch);
}
#if 0
/* Diagnostic routines you can uncomment if you need them */
-void dump_grid(int w, int h, const char *grid, const char *title)
+void dump_grid(int w, int h, const char *grid, const char *titlefmt, ...)
{int x, y;
- printf("%s:\n", title ? title : "Grid");+ if (titlefmt) {+ va_list ap;
+ va_start(ap, titlefmt);
+ vprintf(titlefmt, ap);
+ va_end(ap);
+ printf(":\n");+ } else {+ printf("Grid:\n");+ }
for (y = 0; y < h; y++) { printf(" "); for (x = 0; x < w; x++) {@@ -265,10 +307,18 @@
}
}
-void dump_dist(int w, int h, const int *dists, const char *title)
+void dump_dist(int w, int h, const int *dists, const char *titlefmt, ...)
{int x, y;
- printf("%s:\n", title ? title : "Distances");+ if (titlefmt) {+ va_list ap;
+ va_start(ap, titlefmt);
+ vprintf(titlefmt, ap);
+ va_end(ap);
+ printf(":\n");+ } else {+ printf("Distances:\n");+ }
for (y = 0; y < h; y++) { printf(" "); for (x = 0; x < w; x++) {@@ -281,10 +331,12 @@
/*
* Search a grid to find the most distant square(s). Return their
- * distance and the number of them.
+ * distance and the number of them, and also the number of squares in
+ * the current controlled set (i.e. at distance zero).
*/
static void search(int w, int h, char *grid, int x0, int y0,
- struct solver_scratch *scratch, int *rdist, int *rnumber)
+ struct solver_scratch *scratch,
+ int *rdist, int *rnumber, int *rcontrol)
{int wh = w*h;
int i, qcurr, qhead, qtail, qnext, currdist, remaining;
@@ -304,6 +356,8 @@
while (1) { if (qtail == qhead) {/* Switch queues. */
+ if (currdist == 0)
+ *rcontrol = qhead;
currdist++;
qcurr ^= 1; /* switch queues */
qhead = qnext;
@@ -351,6 +405,8 @@
*rdist = currdist;
*rnumber = qhead;
+ if (currdist == 0)
+ *rcontrol = qhead;
}
/*
@@ -389,64 +445,104 @@
}
/*
+ * Detect a completed grid.
+ */
+static int completed(int w, int h, char *grid)
+{+ int wh = w*h;
+ int i;
+
+ for (i = 1; i < wh; i++)
+ if (grid[i] != grid[0])
+ return FALSE;
+
+ return TRUE;
+}
+
+/*
* Try out every possible move on a grid, and choose whichever one
* reduced the result of search() by the most.
*/
-static char choosemove(int w, int h, char *grid, int x0, int y0,
- int maxmove, struct solver_scratch *scratch)
+static char choosemove_recurse(int w, int h, char *grid, int x0, int y0,
+ int maxmove, struct solver_scratch *scratch,
+ int depth, int *rbestdist, int *rbestnumber, int *rbestcontrol)
{int wh = w*h;
char move, bestmove;
- int dist, number, bestdist, bestnumber;
+ int dist, number, control, bestdist, bestnumber, bestcontrol;
+ char *tmpgrid;
+ assert(0 <= depth && depth < RECURSION_DEPTH);
+ tmpgrid = scratch->rgrids + depth*wh;
+
bestdist = wh + 1;
bestnumber = 0;
+ bestcontrol = 0;
bestmove = -1;
#if 0
- dump_grid(w, h, grid, "before choosemove");
+ dump_grid(w, h, grid, "before choosemove_recurse %d", depth);
#endif
for (move = 0; move < maxmove; move++) {- char buf[256];
- sprintf(buf, "after move %d", move);
if (grid[y0*w+x0] == move)
continue;
- memcpy(scratch->sparegrid, grid, wh * sizeof(*grid));
- fill(w, h, scratch->sparegrid, x0, y0, move, scratch->queue[0]);
+ memcpy(tmpgrid, grid, wh * sizeof(*grid));
+ fill(w, h, tmpgrid, x0, y0, move, scratch->queue[0]);
+ if (completed(w, h, tmpgrid)) {+ /*
+ * A move that wins is immediately the best, so stop
+ * searching. Record what depth of recursion that happened
+ * at, so that higher levels will choose a move that gets
+ * to a winning position sooner.
+ */
+ *rbestdist = -1;
+ *rbestnumber = depth;
+ *rbestcontrol = wh;
+ return move;
+ }
+ if (depth < RECURSION_DEPTH-1) {+ choosemove_recurse(w, h, tmpgrid, x0, y0, maxmove, scratch,
+ depth+1, &dist, &number, &control);
+ } else {#if 0
- dump_grid(w, h, scratch->sparegrid, buf);
+ dump_grid(w, h, tmpgrid, "after move %d at depth %d",
+ move, depth);
#endif
- search(w, h, scratch->sparegrid, x0, y0, scratch, &dist, &number);
+ search(w, h, tmpgrid, x0, y0, scratch, &dist, &number, &control);
#if 0
- dump_dist(w, h, scratch->dist, buf);
- printf("move %d: %d at %d\n", move, number, dist);+ dump_dist(w, h, scratch->dist, "after move %d at depth %d",
+ move, depth);
+ printf("move %d at depth %d: %d at %d\n",+ depth, move, number, dist);
#endif
- if (dist < bestdist || (dist == bestdist && number < bestnumber)) {+ }
+ if (dist < bestdist ||
+ (dist == bestdist &&
+ (number < bestnumber ||
+ (number == bestnumber &&
+ (control > bestcontrol))))) {bestdist = dist;
bestnumber = number;
+ bestcontrol = control;
bestmove = move;
}
}
#if 0
- printf("best was %d\n", bestmove);+ printf("best at depth %d was %d (%d at %d, %d controlled)\n",+ depth, bestmove, bestnumber, bestdist, bestcontrol);
#endif
+ *rbestdist = bestdist;
+ *rbestnumber = bestnumber;
+ *rbestcontrol = bestcontrol;
return bestmove;
}
-
-/*
- * Detect a completed grid.
- */
-static int completed(int w, int h, char *grid)
+static char choosemove(int w, int h, char *grid, int x0, int y0,
+ int maxmove, struct solver_scratch *scratch)
{- int wh = w*h;
- int i;
-
- for (i = 1; i < wh; i++)
- if (grid[i] != grid[0])
- return FALSE;
-
- return TRUE;
+ int tmp0, tmp1, tmp2;
+ return choosemove_recurse(w, h, grid, x0, y0, maxmove, scratch,
+ 0, &tmp0, &tmp1, &tmp2);
}
static char *new_game_desc(const game_params *params, random_state *rs,
@@ -470,6 +566,7 @@
*/
memcpy(scratch->grid2, scratch->grid, wh * sizeof(*scratch->grid2));
moves = 0;
+ check_recursion_depth();
while (!completed(w, h, scratch->grid2)) {char move = choosemove(w, h, scratch->grid2, FILLX, FILLY,
params->colours, scratch);
@@ -610,6 +707,7 @@
nmoves = 0;
scratch = new_scratch(w, h);
memcpy(scratch->grid2, currstate->grid, wh * sizeof(*scratch->grid2));
+ check_recursion_depth();
while (!completed(w, h, scratch->grid2)) {char move = choosemove(w, h, scratch->grid2, FILLX, FILLY,
currstate->colours, scratch);