chiark - git - mdw - mm/blob - mm.c

   1 /* -*-c-*-
   2  *
   3  * $Id$
   4  *
   5  * Simple mastermind game
   6  *
   7  * (c) 2006 Mark Wooding
   8  */
   9
  10 /*----- Licensing notice --------------------------------------------------*
  11  *
  12  * This file is part of mm: a simple Mastermind game.
  13  *
  14  * mm is free software; you can redistribute it and/or modify
  15  * it under the terms of the GNU General Public License as published by
  16  * the Free Software Foundation; either version 2 of the License, or
  17  * (at your option) any later version.
  18  *
  19  * mm is distributed in the hope that it will be useful,
  20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  22  * GNU General Public License for more details.
  23  *
  24  * You should have received a copy of the GNU General Public License
  25  * along with mm; if not, write to the Free Software Foundation,
  26  * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  27  */
  28
  29 /*----- Header files ------------------------------------------------------*/
  30
  31 #include <assert.h>
  32 #include <ctype.h>
  33 #include <stdio.h>
  34 #include <stdlib.h>
  35 #include <string.h>
  36 #include <time.h>
  37
  38 #include <mLib/alloc.h>
  39 #include <mLib/darray.h>
  40 #include <mLib/mdwopt.h>
  41 #include <mLib/quis.h>
  42 #include <mLib/report.h>
  43 #include <mLib/sub.h>
  44
  45 /*----- Data structures ---------------------------------------------------*/
  46
  47 /* --- Digits --- *
  48  *
  49  * The symbols which make up the code to be guessed.
  50  */
  51
  52 typedef unsigned char dig;
  53
  54 /* --- The game parameters --- */
  55
  56 typedef struct mm {
  57   dig k;                                /* Number of symbols in the code */
  58   dig n;                                /* Number of distinct symbols */
  59 } mm;
  60
  61 /*----- Rating guesses ----------------------------------------------------*/
  62
  63 /* --- Algorithm --- *
  64  *
  65  * Rating guesses efficiently is quite important.
  66  *
  67  * The rate context structure contains a copy of the game parameters, and
  68  * three arrays, @v@, @s@ and @t@ allocated from the same @malloc@ed block:
  69  *
  70  *   * %$v_i$% counts occurrences of the symbol %$i$% in the code.
  71  *   * %$s$% is a copy of the code.
  72  *   * %$t$% is temporary work space for the rating function.
  73  *
  74  * The rating function works by taking a pass over the guess, computing a
  75  * count table %$v'$%; but for each guess symbol which matches the
  76  * correspondng code symbol, decrementing the count %$v_i$% for that symbol
  77  * (in a temporary copy of the table %$v$%).  The black count is then the
  78  * number of such matches, and the white count is given by
  79  *
  80  *   %$w = \displaystyle \sum_{0<i\le n} \min(v_i, v'_i).$%
  81  *
  82  * Thus, the work is %$O(k + n)$%, rather than the %$O(k^2)$% for a
  83  * %%na\"\i{}ve%% implementation.
  84  */
  85
  86 typedef struct ratectx {
  87   mm m;
  88   dig *v;
  89   dig *s;
  90   dig *t;
  91 } ratectx;
  92
  93 static ratectx *rate_alloc(const mm *m)
  94 {
  95   ratectx *r;
  96   dig *v;
  97
  98   r = CREATE(ratectx);
  99   v = xmalloc((3 * m->n + m->k) * sizeof(dig));
 100   r->m = *m;
 101   r->v = v;
 102   r->s = r->v + m->n;
 103   r->t = r->s + m->k;
 104   return (r);
 105 }
 106
 107 static void rate_init(ratectx *r, const dig *s)
 108 {
 109   unsigned i;
 110
 111   memset(r->v, 0, r->m.n * sizeof(dig));
 112   for (i = 0; i < r->m.k; i++)
 113     r->v[s[i]]++;
 114   memcpy(r->s, s, r->m.k * sizeof(dig));
 115 }
 116
 117 static ratectx *rate_new(const mm *m, const dig *s)
 118 {
 119   ratectx *r = rate_alloc(m);
 120
 121   rate_init(r, s);
 122   return (r);
 123 }
 124
 125 static void rate(const ratectx *r, const dig *g, unsigned  *b, unsigned *w)
 126 {
 127   unsigned i;
 128   unsigned k = r->m.k, n = r->m.n;
 129   dig *v = r->t;
 130   dig *vv = v + n;
 131   const dig *s = r->s;
 132   unsigned bb = 0, ww = 0;
 133
 134   memset(v, 0, n * sizeof(dig));
 135   memcpy(vv, r->v, n * sizeof(dig));
 136   for (i = 0; i < k; i++) {
 137     if (g[i] != s[i])
 138       v[g[i]]++;
 139     else {
 140       vv[g[i]]--;
 141       bb++;
 142     }
 143   }
 144   for (i = 0; i < n; i++)
 145     ww += v[i] < vv[i] ? v[i] : vv[i];
 146   *b = bb;
 147   *w = ww;
 148 }
 149
 150 static void rate_free(ratectx *r) { xfree(r->v); DESTROY(r); }
 151
 152 /*----- Computer player ---------------------------------------------------*/
 153
 154 /* --- About the algorithms --- *
 155  *
 156  * At each stage, we attampt to choose the guess which will give us the most
 157  * information, regardless of the outcome.  For each guess candidate, we
 158  * count the remaining possible codes for each outcome, and choose the
 159  * candidate with the least square sum.  There are wrinkles.
 160  *
 161  * Firstly the number of possible guesses is large, and the number of
 162  * possible codes is huge too; and our algorithm takes time proportional to
 163  * the product of the two.  However, a symbol we've never tried before is as
 164  * good as any other, so we can narrow the list of candidate guesses by
 165  * considering only %%\emph{prototypes}%% where we use only the smallest
 166  * untried symbol at any point to represent introducing any new symbol.  The
 167  * number of initial prototypes is quite small.  For the four-symbol game,
 168  * they are 0000, 0001, 0011, 0012, 0111, 0112, 0122, and 0123.
 169  *
 170  * Secondly, when the number of possible codes become small, we want to bias
 171  * the guess selection algorithm towards possible codes (so that we win if
 172  * we're lucky).  Since the algorithm chooses the first guess with the lowest
 173  * sum-of-squares value, we simply run through the possible codes before
 174  * enumerating the prototype guesses.
 175  */
 176
 177 typedef struct cpc {
 178   mm m;                                 /* Game parameters */
 179   unsigned f;                           /* Various flags */
 180 #define CPCF_QUIET 1u                   /*   Don't produce lots of output */
 181   dig *s; /* n^k * k */                 /* Remaining guesses */
 182   size_t ns;                            /* Number of remaining guesses */
 183   dig *bg; /* k */                      /* Current best guess */
 184   dig *t; /* k */                       /* Scratch-space for prototype */
 185   double bmax;                          /* Best guess least-squares score */
 186   dig x, bx;                            /* Next unused symbol index */
 187   size_t *v; /* (k + 1)^2 */            /* Bin counts for least-squares */
 188   ratectx *r;                           /* Rate context for search */
 189 } cpc;
 190
 191 static void print_guess(const mm *m, const dig *d)
 192 {
 193   unsigned k = m->k, i;
 194
 195   for (i = 0; i < k; i++) {
 196     if (i) putchar(' ');
 197     printf("%u", d[i]);
 198   }
 199 }
 200
 201 static void dofep(cpc *c, void (*fn)(cpc *c, const dig *g, unsigned x),
 202                   unsigned k, unsigned n, unsigned i, unsigned x)
 203 {
 204   unsigned j;
 205   dig *t = c->t;
 206
 207   if (i == k)
 208     fn(c, c->t, x);
 209   else {
 210     for (j = 0; j < x; j++) {
 211       t[i] = j;
 212       dofep(c, fn, k, n, i + 1, x);
 213     }
 214     if (x < n) {
 215       t[i] = x;
 216       dofep(c, fn, k, n, i + 1, x + 1);
 217     }
 218   }
 219 }
 220
 221 static void foreach_proto(cpc *c, void (*fn)(cpc *c,
 222                                              const dig *g,
 223                                              unsigned x))
 224 {
 225   unsigned k = c->m.k, n = c->m.n;
 226
 227   dofep(c, fn, k, n, 0, c->x);
 228 }
 229
 230 static void try_guess(cpc *c, const dig *g, unsigned x)
 231 {
 232   size_t i;
 233   unsigned b, w;
 234   const dig *s;
 235   unsigned k = c->m.k;
 236   size_t *v = c->v;
 237   size_t *vp;
 238   double max;
 239
 240   rate_init(c->r, g);
 241   memset(v, 0, (k + 1) * (k + 1) * sizeof(size_t));
 242   for (i = c->ns, s = c->s; i; i--, s += k) {
 243     rate(c->r, s, &b, &w);
 244     v[b * (k + 1) + w]++;
 245   }
 246   max = 0;
 247   for (i = (k + 1) * (k + 1), vp = v; i; i--, vp++)
 248     max += (double)*vp * (double)*vp;
 249   if (c->bmax < 0 || max < c->bmax) {
 250     memcpy(c->bg, g, k * sizeof(dig));
 251     c->bmax = max;
 252     c->bx = x;
 253   }
 254 }
 255
 256 static void best_guess(cpc *c)
 257 {
 258   c->bmax = -1;
 259   if (c->ns < 1024) {
 260     unsigned k = c->m.k;
 261     const dig *s;
 262     size_t i;
 263
 264     for (i = c->ns, s = c->s; i; i--, s += k)
 265       try_guess(c, s, c->x);
 266   }
 267   foreach_proto(c, try_guess);
 268   c->x = c->bx;
 269 }
 270
 271 static void filter_guesses(cpc *c, const dig *g, unsigned b, unsigned w)
 272 {
 273   unsigned k = c->m.k;
 274   size_t i;
 275   const dig *s;
 276   unsigned bb, ww;
 277   dig *ss;
 278
 279   rate_init(c->r, g);
 280   for (i = c->ns, s = ss = c->s; i; i--, s += k) {
 281     rate(c->r, s, &bb, &ww);
 282     if (b == bb && w == ww) {
 283       memmove(ss, s, k * sizeof(dig));
 284       ss += k;
 285     }
 286   }
 287   c->ns = (ss - c->s) / k;
 288 }
 289
 290 static size_t ipow(size_t b, size_t x)
 291 {
 292   size_t a = 1;
 293   while (x) {
 294     if (x & 1)
 295       a *= b;
 296     b *= b;
 297     x >>= 1;
 298   }
 299   return (a);
 300 }
 301
 302 static void all_guesses(dig **ss, unsigned k, unsigned n,
 303                         unsigned i, const dig *b)
 304 {
 305   unsigned j;
 306
 307   if (i == k) {
 308     (*ss) += k;
 309     return;
 310   }
 311   for (j = 0; j < n; j++) {
 312     dig *s = *ss;
 313     if (i)
 314       memcpy(*ss, b, i * sizeof(dig));
 315     s[i] = j;
 316     all_guesses(ss, k, n, i + 1, s);
 317   }
 318 }
 319
 320 #define THINK(c, what, how) do {                                        \
 321   clock_t _t0 = 0, _t1;                                                 \
 322   if (!(c->f & CPCF_QUIET)) {                                           \
 323     fputs(what "...", stdout);                                          \
 324     fflush(stdout);                                                     \
 325     _t0 = clock();                                                      \
 326   }                                                                     \
 327   do how while (0);                                                     \
 328   if (!(c->f & CPCF_QUIET)) {                                           \
 329     _t1 = clock();                                                      \
 330     printf(" done (%.2fs)\n", (_t1 - _t0)/(double)CLOCKS_PER_SEC);      \
 331   }                                                                     \
 332 } while (0)
 333
 334 static cpc *cpc_new(const mm *m, unsigned f)
 335 {
 336   cpc *c = CREATE(cpc);
 337
 338   c->f = f;
 339   c->m = *m;
 340   c->ns = ipow(c->m.n, c->m.k);
 341   c->s = xmalloc((c->ns + 2) * c->m.k * sizeof(dig));
 342   c->bg = c->s + c->ns * c->m.k;
 343   c->t = c->bg + c->m.k;
 344   c->x = 0;
 345   c->v = xmalloc((c->m.k + 1) * (c->m.k + 1) * sizeof(size_t));
 346   c->r = rate_alloc(m);
 347   THINK(c, "Setting up", {
 348     dig *ss = c->s; all_guesses(&ss, c->m.k, c->m.n, 0, 0);
 349   });
 350   return (c);
 351 }
 352
 353 static void cpc_free(cpc *c)
 354 {
 355   xfree(c->s);
 356   xfree(c->v);
 357   rate_free(c->r);
 358   DESTROY(c);
 359 }
 360
 361 static void cp_rate(void *r, const dig *g, unsigned *b, unsigned *w)
 362   { rate(r, g, b, w); }
 363
 364 static const dig *cp_guess(void *cc)
 365 {
 366   cpc *c = cc;
 367
 368   if (c->ns == 0) {
 369     if (!(c->f & CPCF_QUIET))
 370       printf("Liar!  All solutions ruled out.\n");
 371     return (0);
 372   }
 373   if (c->ns == 1) {
 374     if (!(c->f & CPCF_QUIET)) {
 375       fputs("Done!  Solution is ", stdout);
 376       print_guess(&c->m, c->s);
 377       putchar('\n');
 378     }
 379     return (c->s);
 380   }
 381   if (!(c->f & CPCF_QUIET)) {
 382     printf("(Possible solutions remaining = %lu)\n",
 383            (unsigned long)c->ns);
 384     if (c->ns < 32) {
 385       const dig *s;
 386       size_t i;
 387       for (i = c->ns, s = c->s; i; i--, s += c->m.k) {
 388         printf("  %2lu: ", (unsigned long)(c->ns - i + 1));
 389         print_guess(&c->m, s);
 390         putchar('\n');
 391       }
 392     }
 393   }
 394   THINK(c, "Pondering", {
 395     best_guess(c);
 396   });
 397   return (c->bg);
 398 }
 399
 400 static void cp_update(void *cc, const dig *g, unsigned b, unsigned w)
 401 {
 402   cpc *c = cc;
 403
 404   if (!(c->f & CPCF_QUIET)) {
 405     fputs("My guess = ", stdout);
 406     print_guess(&c->m, g);
 407     printf("; rating = %u black, %u white\n", b, w);
 408   }
 409   THINK(c, "Filtering", {
 410     filter_guesses(c, g, b, w);
 411   });
 412 }
 413
 414 /*----- Human player ------------------------------------------------------*/
 415
 416 typedef struct hpc {
 417   mm m;
 418   dig *t;
 419 } hpc;
 420
 421 static hpc *hpc_new(const mm *m)
 422 {
 423   hpc *h = CREATE(hpc);
 424   h->t = xmalloc(m->k * sizeof(dig));
 425   h->m = *m;
 426   return (h);
 427 }
 428
 429 static void hpc_free(hpc *h)
 430 {
 431   xfree(h->t);
 432   DESTROY(h);
 433 }
 434
 435 static void hp_rate(void *mp, const dig *g, unsigned *b, unsigned *w)
 436 {
 437   mm *m = mp;
 438   fputs("Guess = ", stdout);
 439   print_guess(m, g);
 440   printf("; rating: ");
 441   fflush(stdout);
 442   scanf("%u %u", b, w);
 443 }
 444
 445 static const dig *hp_guess(void *hh)
 446 {
 447   hpc *h = hh;
 448   unsigned i;
 449
 450   fputs("Your guess: ", stdout);
 451   fflush(stdout);
 452   for (i = 0; i < h->m.k; i++) {
 453     unsigned x;
 454     scanf("%u", &x);
 455     h->t[i] = x;
 456   }
 457   return (h->t);
 458 }
 459
 460 static void hp_update(void *cc, const dig *g, unsigned b, unsigned w)
 461 {
 462   printf("Rating = %u black, %u white\n", b, w);
 463 }
 464
 465 /*----- Solver player -----------------------------------------------------*/
 466
 467 typedef struct spc {
 468   cpc *c;
 469   hpc *h;
 470   int i;
 471 } spc;
 472
 473 static spc *spc_new(const mm *m)
 474 {
 475   spc *s = CREATE(spc);
 476   s->c = cpc_new(m, 0);
 477   s->h = hpc_new(m);
 478   s->i = 0;
 479   return (s);
 480 }
 481
 482 static void spc_free(spc *s)
 483 {
 484   cpc_free(s->c);
 485   hpc_free(s->h);
 486   DESTROY(s);
 487 }
 488
 489 static const dig *sp_guess(void *ss)
 490 {
 491   spc *s = ss;
 492   hpc *h = s->h;
 493   unsigned i;
 494   int ch;
 495
 496 again:
 497   if (s->i)
 498     return (cp_guess(s->c));
 499
 500   fputs("Your guess (dot for end): ", stdout);
 501   fflush(stdout);
 502   do ch = getchar(); while (isspace(ch));
 503   if (!isdigit(ch)) { s->i = 1; goto again; }
 504   ungetc(ch, stdin);
 505   for (i = 0; i < h->m.k; i++) {
 506     unsigned x;
 507     scanf("%u", &x);
 508     h->t[i] = x;
 509   }
 510   return (h->t);
 511 }
 512
 513 static void sp_update(void *ss, const dig *g, unsigned b, unsigned w)
 514   { spc *s = ss; cp_update(s->c, g, b, w); }
 515
 516 /*----- Full tournament stuff ---------------------------------------------*/
 517
 518 DA_DECL(uint_v, unsigned);
 519
 520 typedef struct allstats {
 521   const mm *m;
 522   unsigned f;
 523 #define AF_VERBOSE 1u
 524   uint_v gmap;
 525   unsigned long g;
 526   unsigned long n;
 527   clock_t t;
 528 } allstats;
 529
 530 static void dorunone(allstats *a, dig *s)
 531 {
 532   ratectx *r = rate_new(a->m, s);
 533   clock_t t = 0, t0, t1;
 534   cpc *c;
 535   int n = 0;
 536   const dig *g;
 537   unsigned b, w;
 538
 539   if (a->f & AF_VERBOSE) {
 540     print_guess(a->m, s);
 541     fputs(": ", stdout);
 542     fflush(stdout);
 543   }
 544
 545   c = cpc_new(a->m, CPCF_QUIET);
 546   for (;;) {
 547     t0 = clock();
 548     g = cp_guess(c);
 549     t1 = clock();
 550     t += t1 - t0;
 551     assert(g);
 552     n++;
 553     rate(r, g, &b, &w);
 554     if (b == a->m->k)
 555       break;
 556     t0 = clock();
 557     cp_update(c, g, b, w);
 558     t1 = clock();
 559     t += t1 - t0;
 560   }
 561   a->t += t;
 562   a->g += n;
 563   while (DA_LEN(&a->gmap) <= n)
 564     DA_PUSH(&a->gmap, 0);
 565   DA(&a->gmap)[n]++;
 566   rate_free(r);
 567   cpc_free(c);
 568
 569   if (a->f & AF_VERBOSE)
 570     printf("%2u (%5.2fs)\n", n, (double)t/CLOCKS_PER_SEC);
 571 }
 572
 573 static void dorunall(allstats *a, dig *s, unsigned i)
 574 {
 575   dig j;
 576
 577   if (i >= a->m->k) {
 578     dorunone(a, s);
 579     a->n++;
 580   } else {
 581     for (j = 0; j < a->m->n; j++) {
 582       s[i] = j;
 583       dorunall(a, s, i + 1);
 584     }
 585   }
 586 }
 587
 588 static void run_all(const mm *m)
 589 {
 590   dig *s = xmalloc(m->k * sizeof(dig));
 591   allstats a;
 592   unsigned i;
 593
 594   a.m = m;
 595   a.f = AF_VERBOSE;
 596   DA_CREATE(&a.gmap);
 597   a.n = 0;
 598   a.g = 0;
 599   a.t = 0;
 600   dorunall(&a, s, 0);
 601   xfree(s);
 602
 603   for (i = 1; i < DA_LEN(&a.gmap); i++)
 604     printf("%2u guesses: %5u games\n", i, DA(&a.gmap)[i]);
 605   printf("Average: %.4f (%.2fs)\n",
 606          (double)a.g/a.n, (double)a.t/(a.n * CLOCKS_PER_SEC));
 607 }
 608
 609 /*----- Main game logic ---------------------------------------------------*/
 610
 611 static int play(const mm *m,
 612                 void (*ratefn)(void *rr, const dig *g,
 613                                unsigned *b, unsigned *w),
 614                 void *rr,
 615                 const dig *(*guessfn)(void *gg),
 616                 void (*updatefn)(void *gg, const dig *g,
 617                                  unsigned b, unsigned w),
 618                 void *gg)
 619 {
 620   unsigned b, w;
 621   const dig *g;
 622   unsigned i;
 623
 624   i = 0;
 625   for (;;) {
 626     i++;
 627     g = guessfn(gg);
 628     if (!g)
 629       return (-1);
 630     ratefn(rr, g, &b, &w);
 631     if (b == m->k)
 632       return (i);
 633     updatefn(gg, g, b, w);
 634   }
 635 }
 636
 637 int main(int argc, char *argv[])
 638 {
 639   unsigned h = 0;
 640   void *rr = 0;
 641   void (*ratefn)(void *rr, const dig *g, unsigned *b, unsigned *w) = 0;
 642   mm m;
 643   int n;
 644
 645   ego(argv[0]);
 646   for (;;) {
 647     static struct option opt[] = {
 648       { "computer",     0,      0,      'C' },
 649       { "human",        0,      0,      'H' },
 650       { "solver",       0,      0,      'S' },
 651       { "all",          0,      0,      'a' },
 652       { 0,              0,      0,      0 }
 653     };
 654     int i = mdwopt(argc, argv, "CHSa", opt, 0, 0, 0);
 655     if (i < 0)
 656       break;
 657     switch (i) {
 658       case 'C': h = 0; break;
 659       case 'H': h = 1; break;
 660       case 'S': h = 2; break;
 661       case 'a': h = 99; break;
 662       default:
 663         exit(1);
 664     }
 665   }
 666   if (argc - optind == 0) {
 667     m.k = 4;
 668     m.n = 6;
 669   } else if (argc - optind < 2)
 670     die(1, "bad parameters");
 671   else {
 672     m.k = atoi(argv[optind++]);
 673     m.n = atoi(argv[optind++]);
 674     if (argc - optind >= m.k) {
 675       dig *s = xmalloc(m.k * sizeof(dig));
 676       int i;
 677       for (i = 0; i < m.k; i++)
 678         s[i] = atoi(argv[optind++]);
 679       rr = rate_new(&m, s);
 680       ratefn = cp_rate;
 681       xfree(s);
 682     }
 683     if (argc != optind)
 684       die(1, "bad parameters");
 685   }
 686
 687   switch (h) {
 688     case 1: {
 689       hpc *hh = hpc_new(&m);
 690       if (!rr) {
 691         dig *s = xmalloc(m.k * sizeof(dig));
 692         int i;
 693         srand(time(0));
 694         for (i = 0; i < m.k; i++)
 695           s[i] = rand() % m.n;
 696         rr = rate_new(&m, s);
 697         ratefn = cp_rate;
 698         xfree(s);
 699       }
 700       n = play(&m, ratefn, rr, hp_guess, hp_update, hh);
 701       hpc_free(hh);
 702     } break;
 703     case 0: {
 704       cpc *cc = cpc_new(&m, 0);
 705       if (rr)
 706         n = play(&m, ratefn, rr, cp_guess, cp_update, cc);
 707       else
 708         n = play(&m, hp_rate, &m, cp_guess, cp_update, cc);
 709       cpc_free(cc);
 710     } break;
 711     case 2: {
 712       spc *ss = spc_new(&m);
 713       n = play(&m, hp_rate, &m, sp_guess, sp_update, ss);
 714       spc_free(ss);
 715     } break;
 716     case 99:
 717       run_all(&m);
 718       return (0);
 719       break;
 720     default:
 721       abort();
 722   }
 723   if (n > 0)
 724     printf("Solved in %d guesses\n", n);
 725   else
 726     die(1, "gave up");
 727   return (0);
 728 }
 729
 730 /*----- That's all, folks -------------------------------------------------*/