cp: Tweak guess selection algorithm: minimize largest bin.

The computer player analyses guesses by trying each possible guess
prototype and dividing the remaining code candidates into bins according
to the possible ratings for the guess.

Previously, we'd choose the guess which minimizes the square-sum of the
bin sizes.  This change makes it choose the guess which minimizes the
size of the largest bin.

This is simpler to compute (it can be done in integers -- the least
squares code used doubles to avoid overflow).  Unfortunately, the play
is somewhat poorer, even though it's often faster.

diff --git a/mm.c b/mm.c
index 7ed9b16ff0ca1bddd5ea28370d259f99b714f1a3..c4d6799cb31e105a26d22a8a6bacb55b4a5ff107 100644 (file)
--- a/mm.c
+++ b/mm.c
@@ -156,7 +156,7 @@ static void rate_free(ratectx *r) { xfree(r->v); DESTROY(r); }
  * At each stage, we attampt to choose the guess which will give us the most
  * information, regardless of the outcome.  For each guess candidate, we
  * count the remaining possible codes for each outcome, and choose the
- * candidate with the least square sum.  There are wrinkles.
+ * candidate with the least maxmimum bin size.  There are wrinkles.
  *
  * Firstly the number of possible guesses is large, and the number of
  * possible codes is huge too; and our algorithm takes time proportional to
@@ -170,7 +170,7 @@ static void rate_free(ratectx *r) { xfree(r->v); DESTROY(r); }
  * Secondly, when the number of possible codes become small, we want to bias
  * the guess selection algorithm towards possible codes (so that we win if
  * we're lucky).  Since the algorithm chooses the first guess with the lowest
- * sum-of-squares value, we simply run through the possible codes before
+ * max-bin-size value, we simply run through the possible codes before
  * enumerating the prototype guesses.
  */
 
@@ -182,9 +182,9 @@ typedef struct cpc {
   size_t ns;                           /* Number of remaining guesses */
   dig *bg; /* k */                     /* Current best guess */
   dig *t; /* k */                      /* Scratch-space for prototype */
-  double bmax;                         /* Best guess least-squares score */
+  size_t bmax;                         /* Best guess max partition size */
   dig x, bx;                           /* Next unused symbol index */
-  size_t *v; /* (k + 1)^2 */           /* Bin counts for least-squares */
+  size_t *v; /* (k + 1)^2 */           /* Bin counts */
   ratectx *r;                          /* Rate context for search */
 } cpc;
 
@@ -235,7 +235,7 @@ static void try_guess(cpc *c, const dig *g, unsigned x)
   unsigned k = c->m.k;
   size_t *v = c->v;
   size_t *vp;
-  double max;
+  size_t max;
 
   rate_init(c->r, g);
   memset(v, 0, (k + 1) * (k + 1) * sizeof(size_t));
@@ -244,9 +244,11 @@ static void try_guess(cpc *c, const dig *g, unsigned x)
     v[b * (k + 1) + w]++;
   }
   max = 0;
-  for (i = (k + 1) * (k + 1), vp = v; i; i--, vp++)
-    max += (double)*vp * (double)*vp;
-  if (c->bmax < 0 || max < c->bmax) {
+  for (i = (k + 1) * (k + 1), vp = v; i; i--, vp++) {
+    if (*vp > max)
+      max = *vp;
+  }
+  if (!c->bmax || max < c->bmax) {
     memcpy(c->bg, g, k * sizeof(dig));
     c->bmax = max;
     c->bx = x;
@@ -255,7 +257,7 @@ static void try_guess(cpc *c, const dig *g, unsigned x)
 
 static void best_guess(cpc *c)
 {
-  c->bmax = -1;
+  c->bmax = 0;
   if (c->ns < 1024) {
     unsigned k = c->m.k;
     const dig *s;