cp: Tweak guess selection algorithm: minimize largest bin.

[mm] / mm.c

/* -*-c-*-
 *
 * $Id$
 *
 * Simple mastermind game
 *
 * (c) 2006 Mark Wooding
 */

/*----- Licensing notice --------------------------------------------------* 
 *
 * This file is part of mm: a simple Mastermind game.
 *
 * mm is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 * 
 * mm is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with mm; if not, write to the Free Software Foundation,
 * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 */

/*----- Header files ------------------------------------------------------*/

#include <assert.h>
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#include <mLib/alloc.h>
#include <mLib/darray.h>
#include <mLib/mdwopt.h>
#include <mLib/quis.h>
#include <mLib/report.h>
#include <mLib/sub.h>

/*----- Data structures ---------------------------------------------------*/

/* --- Digits --- *
 *
 * The symbols which make up the code to be guessed.
 */

typedef unsigned char dig;

/* --- The game parameters --- */

typedef struct mm {
  dig k;				/* Number of symbols in the code */
  dig n;				/* Number of distinct symbols */
} mm;

/*----- Rating guesses ----------------------------------------------------*/

/* --- Algorithm --- *
 *
 * Rating guesses efficiently is quite important.
 *
 * The rate context structure contains a copy of the game parameters, and
 * three arrays, @v@, @s@ and @t@ allocated from the same @malloc@ed block:
 *
 *   * %$v_i$% counts occurrences of the symbol %$i$% in the code.
 *   * %$s$% is a copy of the code.
 *   * %$t$% is temporary work space for the rating function.
 *
 * The rating function works by taking a pass over the guess, computing a
 * count table %$v'$%; but for each guess symbol which matches the
 * correspondng code symbol, decrementing the count %$v_i$% for that symbol
 * (in a temporary copy of the table %$v$%).  The black count is then the
 * number of such matches, and the white count is given by
 *
 *   %$w = \displaystyle \sum_{0<i\le n} \min(v_i, v'_i).$%
 *
 * Thus, the work is %$O(k + n)$%, rather than the %$O(k^2)$% for a
 * %%na\"\i{}ve%% implementation.
 */

typedef struct ratectx {
  mm m;
  dig *v;
  dig *s;
  dig *t;
} ratectx;

static ratectx *rate_alloc(const mm *m)
{
  ratectx *r;
  dig *v;

  r = CREATE(ratectx);
  v = xmalloc((3 * m->n + m->k) * sizeof(dig));
  r->m = *m;
  r->v = v;
  r->s = r->v + m->n;
  r->t = r->s + m->k;
  return (r);
}

static void rate_init(ratectx *r, const dig *s)
{
  unsigned i;

  memset(r->v, 0, r->m.n * sizeof(dig));
  for (i = 0; i < r->m.k; i++)
    r->v[s[i]]++;
  memcpy(r->s, s, r->m.k * sizeof(dig));
}

static ratectx *rate_new(const mm *m, const dig *s)
{
  ratectx *r = rate_alloc(m);

  rate_init(r, s);
  return (r);
}

static void rate(const ratectx *r, const dig *g, unsigned  *b, unsigned *w)
{
  unsigned i;
  unsigned k = r->m.k, n = r->m.n;
  dig *v = r->t;
  dig *vv = v + n;
  const dig *s = r->s;
  unsigned bb = 0, ww = 0;

  memset(v, 0, n * sizeof(dig));
  memcpy(vv, r->v, n * sizeof(dig));
  for (i = 0; i < k; i++) {
    if (g[i] != s[i])
      v[g[i]]++;
    else {
      vv[g[i]]--;
      bb++;
    }
  }
  for (i = 0; i < n; i++)
    ww += v[i] < vv[i] ? v[i] : vv[i];
  *b = bb;
  *w = ww;
}

static void rate_free(ratectx *r) { xfree(r->v); DESTROY(r); }

/*----- Computer player ---------------------------------------------------*/

/* --- About the algorithms --- *
 *
 * 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 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
 * the product of the two.  However, a symbol we've never tried before is as
 * good as any other, so we can narrow the list of candidate guesses by
 * considering only %%\emph{prototypes}%% where we use only the smallest
 * untried symbol at any point to represent introducing any new symbol.  The
 * number of initial prototypes is quite small.  For the four-symbol game,
 * they are 0000, 0001, 0011, 0012, 0111, 0112, 0122, and 0123.
 *
 * 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
 * max-bin-size value, we simply run through the possible codes before
 * enumerating the prototype guesses.
 */

typedef struct cpc {
  mm m;					/* Game parameters */
  unsigned f;				/* Various flags */
#define CPCF_QUIET 1u			/*   Don't produce lots of output */
  dig *s; /* n^k * k */			/* Remaining guesses */
  size_t ns;				/* Number of remaining guesses */
  dig *bg; /* k */			/* Current best guess */
  dig *t; /* k */			/* Scratch-space for prototype */
  size_t bmax;				/* Best guess max partition size */
  dig x, bx;				/* Next unused symbol index */
  size_t *v; /* (k + 1)^2 */		/* Bin counts */
  ratectx *r;				/* Rate context for search */
} cpc;

static void print_guess(const mm *m, const dig *d)
{
  unsigned k = m->k, i;

  for (i = 0; i < k; i++) {
    if (i) putchar(' ');
    printf("%u", d[i]);
  }
}

static void dofep(cpc *c, void (*fn)(cpc *c, const dig *g, unsigned x),
		  unsigned k, unsigned n, unsigned i, unsigned x)
{
  unsigned j;
  dig *t = c->t;

  if (i == k)
    fn(c, c->t, x);
  else {
    for (j = 0; j < x; j++) {
      t[i] = j;
      dofep(c, fn, k, n, i + 1, x);
    }
    if (x < n) {
      t[i] = x;
      dofep(c, fn, k, n, i + 1, x + 1);
    }
  }
}

static void foreach_proto(cpc *c, void (*fn)(cpc *c,
					     const dig *g,
					     unsigned x))
{ 
  unsigned k = c->m.k, n = c->m.n;

  dofep(c, fn, k, n, 0, c->x);
}

static void try_guess(cpc *c, const dig *g, unsigned x)
{
  size_t i;
  unsigned b, w;
  const dig *s;
  unsigned k = c->m.k;
  size_t *v = c->v;
  size_t *vp;
  size_t max;

  rate_init(c->r, g);
  memset(v, 0, (k + 1) * (k + 1) * sizeof(size_t));
  for (i = c->ns, s = c->s; i; i--, s += k) {
    rate(c->r, s, &b, &w);
    v[b * (k + 1) + w]++;
  }
  max = 0;
  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;
  }
}

static void best_guess(cpc *c)
{
  c->bmax = 0;
  if (c->ns < 1024) {
    unsigned k = c->m.k;
    const dig *s;
    size_t i;

    for (i = c->ns, s = c->s; i; i--, s += k)
      try_guess(c, s, c->x);
  }
  foreach_proto(c, try_guess);
  c->x = c->bx;
}

static void filter_guesses(cpc *c, const dig *g, unsigned b, unsigned w)
{
  unsigned k = c->m.k;
  size_t i;
  const dig *s;
  unsigned bb, ww;
  dig *ss;

  rate_init(c->r, g);
  for (i = c->ns, s = ss = c->s; i; i--, s += k) {
    rate(c->r, s, &bb, &ww);
    if (b == bb && w == ww) {
      memmove(ss, s, k * sizeof(dig));
      ss += k;
    }
  }
  c->ns = (ss - c->s) / k;
}

static size_t ipow(size_t b, size_t x)
{
  size_t a = 1;
  while (x) {
    if (x & 1)
      a *= b;
    b *= b;
    x >>= 1;
  }
  return (a);
}

static void all_guesses(dig **ss, unsigned k, unsigned n,
			unsigned i, const dig *b)
{
  unsigned j;

  if (i == k) {
    (*ss) += k;
    return;
  }
  for (j = 0; j < n; j++) {
    dig *s = *ss;
    if (i)
      memcpy(*ss, b, i * sizeof(dig));
    s[i] = j;
    all_guesses(ss, k, n, i + 1, s);
  }
}

#define THINK(c, what, how) do {					\
  clock_t _t0 = 0, _t1;							\
  if (!(c->f & CPCF_QUIET)) {						\
    fputs(what "...", stdout);						\
    fflush(stdout);							\
    _t0 = clock();							\
  }									\
  do how while (0);							\
  if (!(c->f & CPCF_QUIET)) {						\
    _t1 = clock();							\
    printf(" done (%.2fs)\n", (_t1 - _t0)/(double)CLOCKS_PER_SEC);	\
  }									\
} while (0)

static cpc *cpc_new(const mm *m, unsigned f)
{
  cpc *c = CREATE(cpc);

  c->f = f;
  c->m = *m;
  c->ns = ipow(c->m.n, c->m.k);
  c->s = xmalloc((c->ns + 2) * c->m.k * sizeof(dig));
  c->bg = c->s + c->ns * c->m.k;
  c->t = c->bg + c->m.k;
  c->x = 0;
  c->v = xmalloc((c->m.k + 1) * (c->m.k + 1) * sizeof(size_t));
  c->r = rate_alloc(m);
  THINK(c, "Setting up", {
    dig *ss = c->s; all_guesses(&ss, c->m.k, c->m.n, 0, 0);
  });
  return (c);
}

static void cpc_free(cpc *c)
{
  xfree(c->s);
  xfree(c->v);
  rate_free(c->r);
  DESTROY(c);
}

static void cp_rate(void *r, const dig *g, unsigned *b, unsigned *w)
  { rate(r, g, b, w); }

static const dig *cp_guess(void *cc)
{
  cpc *c = cc;

  if (c->ns == 0) {
    if (!(c->f & CPCF_QUIET))
      printf("Liar!  All solutions ruled out.\n");
    return (0);
  }
  if (c->ns == 1) {
    if (!(c->f & CPCF_QUIET)) {
      fputs("Done!  Solution is ", stdout);
      print_guess(&c->m, c->s);
      putchar('\n');
    }
    return (c->s);
  }
  if (!(c->f & CPCF_QUIET)) {
    printf("(Possible solutions remaining = %lu)\n",
	   (unsigned long)c->ns);
    if (c->ns < 32) {
      const dig *s;
      size_t i;
      for (i = c->ns, s = c->s; i; i--, s += c->m.k) {
	printf("  %2lu: ", (unsigned long)(c->ns - i + 1));
	print_guess(&c->m, s);
	putchar('\n');
      }
    }
  }
  THINK(c, "Pondering", {
    best_guess(c);
  });
  return (c->bg);
}

static void cp_update(void *cc, const dig *g, unsigned b, unsigned w)
{
  cpc *c = cc;

  if (!(c->f & CPCF_QUIET)) {
    fputs("My guess = ", stdout);
    print_guess(&c->m, g);
    printf("; rating = %u black, %u white\n", b, w);
  }
  THINK(c, "Filtering", {
    filter_guesses(c, g, b, w);
  });
}

/*----- Human player ------------------------------------------------------*/

typedef struct hpc {
  mm m;
  dig *t;
} hpc;

static hpc *hpc_new(const mm *m)
{
  hpc *h = CREATE(hpc);
  h->t = xmalloc(m->k * sizeof(dig));
  h->m = *m;
  return (h);
}

static void hpc_free(hpc *h)
{
  xfree(h->t);
  DESTROY(h);
}

static void hp_rate(void *mp, const dig *g, unsigned *b, unsigned *w)
{
  mm *m = mp;
  fputs("Guess = ", stdout);
  print_guess(m, g);
  printf("; rating: ");
  fflush(stdout);
  scanf("%u %u", b, w);
}

static const dig *hp_guess(void *hh)
{
  hpc *h = hh;
  unsigned i;

  fputs("Your guess: ", stdout);
  fflush(stdout);
  for (i = 0; i < h->m.k; i++) {
    unsigned x;
    scanf("%u", &x);
    h->t[i] = x;
  }
  return (h->t);
}

static void hp_update(void *cc, const dig *g, unsigned b, unsigned w)
{
  printf("Rating = %u black, %u white\n", b, w);
}

/*----- Solver player -----------------------------------------------------*/

typedef struct spc {
  cpc *c;
  hpc *h;
  int i;
} spc;

static spc *spc_new(const mm *m)
{
  spc *s = CREATE(spc);
  s->c = cpc_new(m, 0);
  s->h = hpc_new(m);
  s->i = 0;
  return (s);
}

static void spc_free(spc *s)
{
  cpc_free(s->c);
  hpc_free(s->h);
  DESTROY(s);
}

static const dig *sp_guess(void *ss)
{
  spc *s = ss;
  hpc *h = s->h;
  unsigned i;
  int ch;

again:
  if (s->i)
    return (cp_guess(s->c));

  fputs("Your guess (dot for end): ", stdout);
  fflush(stdout);
  do ch = getchar(); while (isspace(ch));
  if (!isdigit(ch)) { s->i = 1; goto again; }
  ungetc(ch, stdin);
  for (i = 0; i < h->m.k; i++) {
    unsigned x;
    scanf("%u", &x);
    h->t[i] = x;
  }
  return (h->t);    
}

static void sp_update(void *ss, const dig *g, unsigned b, unsigned w)
  { spc *s = ss; cp_update(s->c, g, b, w); }

/*----- Full tournament stuff ---------------------------------------------*/

DA_DECL(uint_v, unsigned);

typedef struct allstats {
  const mm *m;
  unsigned f;
#define AF_VERBOSE 1u
  uint_v gmap;
  unsigned long g;
  unsigned long n;
  clock_t t;
} allstats;

static void dorunone(allstats *a, dig *s)
{
  ratectx *r = rate_new(a->m, s);
  clock_t t = 0, t0, t1;
  cpc *c;
  int n = 0;
  const dig *g;
  unsigned b, w;

  if (a->f & AF_VERBOSE) {
    print_guess(a->m, s);
    fputs(": ", stdout);
    fflush(stdout);
  }
    
  c = cpc_new(a->m, CPCF_QUIET);
  for (;;) {
    t0 = clock();
    g = cp_guess(c);
    t1 = clock();
    t += t1 - t0;
    assert(g);
    n++;
    rate(r, g, &b, &w);
    if (b == a->m->k)
      break;
    t0 = clock();
    cp_update(c, g, b, w);
    t1 = clock();
    t += t1 - t0;    
  }
  a->t += t;
  a->g += n;
  while (DA_LEN(&a->gmap) <= n)
    DA_PUSH(&a->gmap, 0);
  DA(&a->gmap)[n]++;
  rate_free(r);
  cpc_free(c);

  if (a->f & AF_VERBOSE)
    printf("%2u (%5.2fs)\n", n, (double)t/CLOCKS_PER_SEC);
}

static void dorunall(allstats *a, dig *s, unsigned i)
{
  dig j;

  if (i >= a->m->k) {
    dorunone(a, s);
    a->n++;
  } else {
    for (j = 0; j < a->m->n; j++) {
      s[i] = j;
      dorunall(a, s, i + 1);
    }
  }
}

static void run_all(const mm *m)
{
  dig *s = xmalloc(m->k * sizeof(dig));
  allstats a;
  unsigned i;

  a.m = m;
  a.f = AF_VERBOSE;
  DA_CREATE(&a.gmap);
  a.n = 0;
  a.g = 0;
  a.t = 0;
  dorunall(&a, s, 0);
  xfree(s);

  for (i = 1; i < DA_LEN(&a.gmap); i++)
    printf("%2u guesses: %5u games\n", i, DA(&a.gmap)[i]);
  printf("Average: %.4f (%.2fs)\n",
	 (double)a.g/a.n, (double)a.t/(a.n * CLOCKS_PER_SEC));
}

/*----- Main game logic ---------------------------------------------------*/

static int play(const mm *m,
		void (*ratefn)(void *rr, const dig *g,
			       unsigned *b, unsigned *w),
		void *rr,
		const dig *(*guessfn)(void *gg),
		void (*updatefn)(void *gg, const dig *g,
				 unsigned b, unsigned w),
		void *gg)
{
  unsigned b, w;
  const dig *g;
  unsigned i;

  i = 0;
  for (;;) {
    i++;
    g = guessfn(gg);
    if (!g)
      return (-1);
    ratefn(rr, g, &b, &w);
    if (b == m->k)
      return (i);
    updatefn(gg, g, b, w);
  }
}

int main(int argc, char *argv[])
{
  unsigned h = 0;
  void *rr = 0;
  void (*ratefn)(void *rr, const dig *g, unsigned *b, unsigned *w) = 0;
  mm m;
  int n;

  ego(argv[0]);
  for (;;) {
    static struct option opt[] = {
      { "computer",	0,	0,	'C' },
      { "human",	0,	0,	'H' },
      { "solver",	0,	0,	'S' },
      { "all",		0,	0,	'a' },
      { 0,		0,	0,	0 }
    };
    int i = mdwopt(argc, argv, "CHSa", opt, 0, 0, 0);
    if (i < 0)
      break;
    switch (i) {
      case 'C': h = 0; break;
      case 'H': h = 1; break;
      case 'S': h = 2; break;
      case 'a': h = 99; break;
      default:
	exit(1);
    }
  }
  if (argc - optind == 0) {
    m.k = 4;
    m.n = 6;
  } else if (argc - optind < 2)
    die(1, "bad parameters");
  else {
    m.k = atoi(argv[optind++]);
    m.n = atoi(argv[optind++]);
    if (argc - optind >= m.k) {
      dig *s = xmalloc(m.k * sizeof(dig));
      int i;
      for (i = 0; i < m.k; i++)
	s[i] = atoi(argv[optind++]);
      rr = rate_new(&m, s);
      ratefn = cp_rate;
      xfree(s);
    }
    if (argc != optind)
      die(1, "bad parameters");
  }

  switch (h) {
    case 1: {
      hpc *hh = hpc_new(&m);
      if (!rr) {
	dig *s = xmalloc(m.k * sizeof(dig));
	int i;
	srand(time(0));
	for (i = 0; i < m.k; i++)
	  s[i] = rand() % m.n;
	rr = rate_new(&m, s);
	ratefn = cp_rate;
	xfree(s);
      }
      n = play(&m, ratefn, rr, hp_guess, hp_update, hh);
      hpc_free(hh);
    } break;
    case 0: {
      cpc *cc = cpc_new(&m, 0);
      if (rr) 
	n = play(&m, ratefn, rr, cp_guess, cp_update, cc);
      else
	n = play(&m, hp_rate, &m, cp_guess, cp_update, cc);
      cpc_free(cc);
    } break;
    case 2: {
      spc *ss = spc_new(&m);
      n = play(&m, hp_rate, &m, sp_guess, sp_update, ss);
      spc_free(ss);
    } break;
    case 99:
      run_all(&m);
      return (0);
      break;
    default:
      abort();
  }
  if (n > 0)
    printf("Solved in %d guesses\n", n);
  else
    die(1, "gave up");
  return (0);
}

/*----- That's all, folks -------------------------------------------------*/