+/* -*-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 <ctype.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <time.h>
+
+#include <mLib/alloc.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 square sum. 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
+ * sum-of-squares value, we simply run through the possible codes before
+ * enumerating the prototype guesses.
+ */
+
+typedef struct cpc {
+ mm m; /* Game parameters */
+ 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 */
+ double bmax; /* Best guess least-squares score */
+ dig x, bx; /* Next unused symbol index */
+ size_t *v; /* (k + 1)^2 */ /* Bin counts for least-squares */
+ 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;
+ double 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++)
+ max += (double)*vp * (double)*vp;
+ if (c->bmax < 0 || max < c->bmax) {
+ memcpy(c->bg, g, k * sizeof(dig));
+ c->bmax = max;
+ c->bx = x;
+ }
+}
+
+static void best_guess(cpc *c)
+{
+ c->bmax = -1;
+ 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(what, how) do { \
+ clock_t _t0, _t1; \
+ fputs(what "...", stdout); \
+ fflush(stdout); \
+ _t0 = clock(); \
+ do how while (0); \
+ _t1 = clock(); \
+ printf(" done (%.2fs)\n", (_t1 - _t0)/(double)CLOCKS_PER_SEC); \
+} while (0)
+
+static cpc *cpc_new(const mm *m)
+{
+ cpc *c = CREATE(cpc);
+ 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("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) {
+ printf("Liar! All solutions ruled out.\n");
+ return (0);
+ }
+ if (c->ns == 1) {
+ fputs("Done! Solution is ", stdout);
+ print_guess(&c->m, c->s);
+ putchar('\n');
+ return (c->s);
+ }
+ 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("Pondering", {
+ best_guess(c);
+ });
+ return (c->bg);
+}
+
+static void cp_update(void *cc, const dig *g, unsigned b, unsigned w)
+{
+ cpc *c = cc;
+ fputs("My guess = ", stdout);
+ print_guess(&c->m, g);
+ printf("; rating = %u black, %u white\n", b, w);
+ THINK("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);
+ 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);
+}
+
+/*----- 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' },
+ { 0, 0, 0, 0 }
+ };
+ int i = mdwopt(argc, argv, "CHS", 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;
+ 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);
+ 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;
+ default:
+ abort();
+ }
+ if (n > 0)
+ printf("Solved in %d guesses\n", n);
+ else
+ die(1, "gave up");
+ return (0);
+}
+
+/*----- That's all, folks -------------------------------------------------*/
~mdw / mm / commitdiff