5 * Simple mastermind game
7 * (c) 2006 Mark Wooding
10 /*----- Licensing notice --------------------------------------------------*
12 * This file is part of mm: a simple Mastermind game.
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.
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.
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.
29 /*----- Header files ------------------------------------------------------*/
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>
45 /*----- Data structures ---------------------------------------------------*/
49 * The symbols which make up the code to be guessed.
52 typedef unsigned char dig
;
54 /* --- The game parameters --- */
57 dig k
; /* Number of symbols in the code */
58 dig n
; /* Number of distinct symbols */
61 /*----- Rating guesses ----------------------------------------------------*/
63 /* --- Algorithm --- *
65 * Rating guesses efficiently is quite important.
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:
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.
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
80 * %$w = \displaystyle \sum_{0<i\le n} \min(v_i, v'_i).$%
82 * Thus, the work is %$O(k + n)$%, rather than the %$O(k^2)$% for a
83 * %%na\"\i{}ve%% implementation.
86 typedef struct ratectx
{
93 static ratectx
*rate_alloc(const mm
*m
)
99 v
= xmalloc((3 * m
->n
+ m
->k
) * sizeof(dig
));
107 static void rate_init(ratectx
*r
, const dig
*s
)
111 memset(r
->v
, 0, r
->m
.n
* sizeof(dig
));
112 for (i
= 0; i
< r
->m
.k
; i
++)
114 memcpy(r
->s
, s
, r
->m
.k
* sizeof(dig
));
117 static ratectx
*rate_new(const mm
*m
, const dig
*s
)
119 ratectx
*r
= rate_alloc(m
);
125 static void rate(const ratectx
*r
, const dig
*g
, unsigned *b
, unsigned *w
)
128 unsigned k
= r
->m
.k
, n
= r
->m
.n
;
132 unsigned bb
= 0, ww
= 0;
134 memset(v
, 0, n
* sizeof(dig
));
135 memcpy(vv
, r
->v
, n
* sizeof(dig
));
136 for (i
= 0; i
< k
; i
++) {
144 for (i
= 0; i
< n
; i
++)
145 ww
+= v
[i
] < vv
[i
] ? v
[i
] : vv
[i
];
150 static void rate_free(ratectx
*r
) { xfree(r
->v
); DESTROY(r
); }
152 /*----- Computer player ---------------------------------------------------*/
154 /* --- About the algorithms --- *
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.
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.
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.
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 */
191 static void print_guess(const mm
*m
, const dig
*d
)
193 unsigned k
= m
->k
, i
;
195 for (i
= 0; i
< k
; i
++) {
201 static void dofep(cpc
*c
, void (*fn
)(cpc
*c
, const dig
*g
, unsigned x
),
202 unsigned k
, unsigned n
, unsigned i
, unsigned x
)
210 for (j
= 0; j
< x
; j
++) {
212 dofep(c
, fn
, k
, n
, i
+ 1, x
);
216 dofep(c
, fn
, k
, n
, i
+ 1, x
+ 1);
221 static void foreach_proto(cpc
*c
, void (*fn
)(cpc
*c
,
225 unsigned k
= c
->m
.k
, n
= c
->m
.n
;
227 dofep(c
, fn
, k
, n
, 0, c
->x
);
230 static void try_guess(cpc
*c
, const dig
*g
, unsigned x
)
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
]++;
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
));
256 static void best_guess(cpc
*c
)
264 for (i
= c
->ns
, s
= c
->s
; i
; i
--, s
+= k
)
265 try_guess(c
, s
, c
->x
);
267 foreach_proto(c
, try_guess
);
271 static void filter_guesses(cpc
*c
, const dig
*g
, unsigned b
, unsigned w
)
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
));
287 c
->ns
= (ss
- c
->s
) / k
;
290 static size_t ipow(size_t b
, size_t x
)
302 static void all_guesses(dig
**ss
, unsigned k
, unsigned n
,
303 unsigned i
, const dig
*b
)
311 for (j
= 0; j
< n
; j
++) {
314 memcpy(*ss
, b
, i
* sizeof(dig
));
316 all_guesses(ss
, k
, n
, i
+ 1, s
);
320 #define THINK(c, what, how) do { \
321 clock_t _t0 = 0, _t1; \
322 if (!(c->f & CPCF_QUIET)) { \
323 fputs(what "...", stdout); \
328 if (!(c->f & CPCF_QUIET)) { \
330 printf(" done (%.2fs)\n", (_t1 - _t0)/(double)CLOCKS_PER_SEC); \
334 static cpc
*cpc_new(const mm
*m
, unsigned f
)
336 cpc
*c
= CREATE(cpc
);
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
;
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);
353 static void cpc_free(cpc
*c
)
361 static void cp_rate(void *r
, const dig
*g
, unsigned *b
, unsigned *w
)
362 { rate(r
, g
, b
, w
); }
364 static const dig
*cp_guess(void *cc
)
369 if (!(c
->f
& CPCF_QUIET
))
370 printf("Liar! All solutions ruled out.\n");
374 if (!(c
->f
& CPCF_QUIET
)) {
375 fputs("Done! Solution is ", stdout
);
376 print_guess(&c
->m
, c
->s
);
381 if (!(c
->f
& CPCF_QUIET
)) {
382 printf("(Possible solutions remaining = %lu)\n",
383 (unsigned long)c
->ns
);
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
);
394 THINK(c
, "Pondering", {
400 static void cp_update(void *cc
, const dig
*g
, unsigned b
, unsigned w
)
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
);
409 THINK(c
, "Filtering", {
410 filter_guesses(c
, g
, b
, w
);
414 /*----- Human player ------------------------------------------------------*/
421 static hpc
*hpc_new(const mm
*m
)
423 hpc
*h
= CREATE(hpc
);
424 h
->t
= xmalloc(m
->k
* sizeof(dig
));
429 static void hpc_free(hpc
*h
)
435 static void hp_rate(void *mp
, const dig
*g
, unsigned *b
, unsigned *w
)
438 fputs("Guess = ", stdout
);
440 printf("; rating: ");
442 scanf("%u %u", b
, w
);
445 static const dig
*hp_guess(void *hh
)
450 fputs("Your guess: ", stdout
);
452 for (i
= 0; i
< h
->m
.k
; i
++) {
460 static void hp_update(void *cc
, const dig
*g
, unsigned b
, unsigned w
)
462 printf("Rating = %u black, %u white\n", b
, w
);
465 /*----- Solver player -----------------------------------------------------*/
473 static spc
*spc_new(const mm
*m
)
475 spc
*s
= CREATE(spc
);
476 s
->c
= cpc_new(m
, 0);
482 static void spc_free(spc
*s
)
489 static const dig
*sp_guess(void *ss
)
498 return (cp_guess(s
->c
));
500 fputs("Your guess (dot for end): ", stdout
);
502 do ch
= getchar(); while (isspace(ch
));
503 if (!isdigit(ch
)) { s
->i
= 1; goto again
; }
505 for (i
= 0; i
< h
->m
.k
; i
++) {
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
); }
516 /*----- Full tournament stuff ---------------------------------------------*/
518 DA_DECL(uint_v
, unsigned);
520 typedef struct allstats
{
523 #define AF_VERBOSE 1u
530 static void dorunone(allstats
*a
, dig
*s
)
532 ratectx
*r
= rate_new(a
->m
, s
);
533 clock_t t
= 0, t0
, t1
;
539 if (a
->f
& AF_VERBOSE
) {
540 print_guess(a
->m
, s
);
545 c
= cpc_new(a
->m
, CPCF_QUIET
);
557 cp_update(c
, g
, b
, w
);
563 while (DA_LEN(&a
->gmap
) <= n
)
564 DA_PUSH(&a
->gmap
, 0);
569 if (a
->f
& AF_VERBOSE
)
570 printf("%2u (%5.2fs)\n", n
, (double)t
/CLOCKS_PER_SEC
);
573 static void dorunall(allstats
*a
, dig
*s
, unsigned i
)
581 for (j
= 0; j
< a
->m
->n
; j
++) {
583 dorunall(a
, s
, i
+ 1);
588 static void run_all(const mm
*m
)
590 dig
*s
= xmalloc(m
->k
* sizeof(dig
));
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
));
609 /*----- Main game logic ---------------------------------------------------*/
611 static int play(const mm
*m
,
612 void (*ratefn
)(void *rr
, const dig
*g
,
613 unsigned *b
, unsigned *w
),
615 const dig
*(*guessfn
)(void *gg
),
616 void (*updatefn
)(void *gg
, const dig
*g
,
617 unsigned b
, unsigned w
),
630 ratefn(rr
, g
, &b
, &w
);
633 updatefn(gg
, g
, b
, w
);
637 int main(int argc
, char *argv
[])
641 void (*ratefn
)(void *rr
, const dig
*g
, unsigned *b
, unsigned *w
) = 0;
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' },
654 int i
= mdwopt(argc
, argv
, "CHSa", opt
, 0, 0, 0);
658 case 'C': h
= 0; break;
659 case 'H': h
= 1; break;
660 case 'S': h
= 2; break;
661 case 'a': h
= 99; break;
666 if (argc
- optind
== 0) {
669 } else if (argc
- optind
< 2)
670 die(1, "bad parameters");
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
));
677 for (i
= 0; i
< m
.k
; i
++)
678 s
[i
] = atoi(argv
[optind
++]);
679 rr
= rate_new(&m
, s
);
684 die(1, "bad parameters");
689 hpc
*hh
= hpc_new(&m
);
691 dig
*s
= xmalloc(m
.k
* sizeof(dig
));
694 for (i
= 0; i
< m
.k
; i
++)
696 rr
= rate_new(&m
, s
);
700 n
= play(&m
, ratefn
, rr
, hp_guess
, hp_update
, hh
);
704 cpc
*cc
= cpc_new(&m
, 0);
706 n
= play(&m
, ratefn
, rr
, cp_guess
, cp_update
, cc
);
708 n
= play(&m
, hp_rate
, &m
, cp_guess
, cp_update
, cc
);
712 spc
*ss
= spc_new(&m
);
713 n
= play(&m
, hp_rate
, &m
, sp_guess
, sp_update
, ss
);
724 printf("Solved in %d guesses\n", n
);
730 /*----- That's all, folks -------------------------------------------------*/