From: Mark Wooding Date: Thu, 2 Mar 2006 14:58:22 +0000 (+0000) Subject: Initial import. X-Git-Tag: 0.9.0-dev~8 X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~mdw/git/mm/commitdiff_plain/7a869046513cff8cf3c3ccea0c28d2ccab29b868 Initial import. --- 7a869046513cff8cf3c3ccea0c28d2ccab29b868 diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..3201815 --- /dev/null +++ b/.gitignore @@ -0,0 +1,8 @@ +Makefile.in +aclocal.m4 +autom4te.cache +build +configure +depcomp +install-sh +missing diff --git a/.skelrc b/.skelrc new file mode 100644 index 0000000..f7afffd --- /dev/null +++ b/.skelrc @@ -0,0 +1,9 @@ +;;; -*-emacs-lisp-*- + +(setq skel-alist + (append + '((author . "Mark Wooding") + (full-title . "mm: a simple Mastermind game") + (program . "mm")) + skel-alist)) + diff --git a/Makefile.am b/Makefile.am new file mode 100644 index 0000000..c6df28a --- /dev/null +++ b/Makefile.am @@ -0,0 +1,34 @@ +## -*-makefile-*- +## +## $Id$ +## +## Makefile builder +## +## (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. + +AUTOMAKE_OPTIONS = foreign + +bin_PROGRAMS = mm + +mm_SOURCES = mm.c + +##----- That's all, folks --------------------------------------------------- diff --git a/configure.in b/configure.in new file mode 100644 index 0000000..8199932 --- /dev/null +++ b/configure.in @@ -0,0 +1,35 @@ +dnl -*-fundamental-*- +dnl +dnl $Id$ +dnl +dnl Configuration script for mm +dnl +dnl (c) 2006 Mark Wooding +dnl + +dnl ----- Licensing notice -------------------------------------------------- +dnl +dnl This file is part of mm: a simple Mastermind game. +dnl +dnl mm is free software; you can redistribute it and/or modify +dnl it under the terms of the GNU General Public License as published by +dnl the Free Software Foundation; either version 2 of the License, or +dnl (at your option) any later version. +dnl +dnl mm is distributed in the hope that it will be useful, +dnl but WITHOUT ANY WARRANTY; without even the implied warranty of +dnl MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +dnl GNU General Public License for more details. +dnl +dnl You should have received a copy of the GNU General Public License +dnl along with mm; if not, write to the Free Software Foundation, +dnl Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. + +AC_INIT([mm.c]) +AM_INIT_AUTOMAKE([mm], [1.0.0]) +AC_PROG_CC +mdw_GCC_FLAGS +mdw_MLIB([2.0.3]) +AC_OUTPUT([Makefile]) + +dnl ----- That's all, folks ------------------------------------------------- diff --git a/mm.c b/mm.c new file mode 100644 index 0000000..e25f5d4 --- /dev/null +++ b/mm.c @@ -0,0 +1,620 @@ +/* -*-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 +#include +#include +#include +#include + +#include +#include +#include +#include +#include + +/*----- 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_{0n + 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 -------------------------------------------------*/