From ca85e2e72271e7ec90e9318c79aeda3eba629c09 Mon Sep 17 00:00:00 2001
From: Mark Wooding <mdw@distorted.org.uk>
Date: Sun, 12 Mar 2006 16:28:51 +0000
Subject: [PATCH] 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.
---
 mm.c | 20 +++++++++++---------
 1 file changed, 11 insertions(+), 9 deletions(-)

diff --git a/mm.c b/mm.c
index 7ed9b16..c4d6799 100644
--- 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;
-- 
2.11.0