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 ------------------------------------------------------*/
37 #include <mLib/alloc.h>
38 #include <mLib/mdwopt.h>
39 #include <mLib/quis.h>
40 #include <mLib/report.h>
43 /*----- Data structures ---------------------------------------------------*/
47 * The symbols which make up the code to be guessed.
50 typedef unsigned char dig
;
52 /* --- The game parameters --- */
55 dig k
; /* Number of symbols in the code */
56 dig n
; /* Number of distinct symbols */
59 /*----- Rating guesses ----------------------------------------------------*/
61 /* --- Algorithm --- *
63 * Rating guesses efficiently is quite important.
65 * The rate context structure contains a copy of the game parameters, and
66 * three arrays, @v@, @s@ and @t@ allocated from the same @malloc@ed block:
68 * * %$v_i$% counts occurrences of the symbol %$i$% in the code.
69 * * %$s$% is a copy of the code.
70 * * %$t$% is temporary work space for the rating function.
72 * The rating function works by taking a pass over the guess, computing a
73 * count table %$v'$%; but for each guess symbol which matches the
74 * correspondng code symbol, decrementing the count %$v_i$% for that symbol
75 * (in a temporary copy of the table %$v$%). The black count is then the
76 * number of such matches, and the white count is given by
78 * %$w = \displaystyle \sum_{0<i\le n} \min(v_i, v'_i).$%
80 * Thus, the work is %$O(k + n)$%, rather than the %$O(k^2)$% for a
81 * %%na\"\i{}ve%% implementation.
84 typedef struct ratectx
{
91 static ratectx
*rate_alloc(const mm
*m
)
97 v
= xmalloc((3 * m
->n
+ m
->k
) * sizeof(dig
));
105 static void rate_init(ratectx
*r
, const dig
*s
)
109 memset(r
->v
, 0, r
->m
.n
* sizeof(dig
));
110 for (i
= 0; i
< r
->m
.k
; i
++)
112 memcpy(r
->s
, s
, r
->m
.k
* sizeof(dig
));
115 static ratectx
*rate_new(const mm
*m
, const dig
*s
)
117 ratectx
*r
= rate_alloc(m
);
122 static void rate(const ratectx
*r
, const dig
*g
, unsigned *b
, unsigned *w
)
125 unsigned k
= r
->m
.k
, n
= r
->m
.n
;
129 unsigned bb
= 0, ww
= 0;
131 memset(v
, 0, n
* sizeof(dig
));
132 memcpy(vv
, r
->v
, n
* sizeof(dig
));
133 for (i
= 0; i
< k
; i
++) {
141 for (i
= 0; i
< n
; i
++)
142 ww
+= v
[i
] < vv
[i
] ? v
[i
] : vv
[i
];
147 static void rate_free(ratectx
*r
)
153 /*----- Computer player ---------------------------------------------------*/
155 /* --- About the algorithms --- *
157 * At each stage, we attampt to choose the guess which will give us the most
158 * information, regardless of the outcome. For each guess candidate, we
159 * count the remaining possible codes for each outcome, and choose the
160 * candidate with the least square sum. There are wrinkles.
162 * Firstly the number of possible guesses is large, and the number of
163 * possible codes is huge too; and our algorithm takes time proportional to
164 * the product of the two. However, a symbol we've never tried before is as
165 * good as any other, so we can narrow the list of candidate guesses by
166 * considering only %%\emph{prototypes}%% where we use only the smallest
167 * untried symbol at any point to represent introducing any new symbol. The
168 * number of initial prototypes is quite small. For the four-symbol game,
169 * they are 0000, 0001, 0011, 0012, 0111, 0112, 0122, and 0123.
171 * Secondly, when the number of possible codes become small, we want to bias
172 * the guess selection algorithm towards possible codes (so that we win if
173 * we're lucky). Since the algorithm chooses the first guess with the lowest
174 * sum-of-squares value, we simply run through the possible codes before
175 * enumerating the prototype guesses.
179 mm m
; /* Game parameters */
180 dig
*s
; /* n^k * k */ /* Remaining guesses */
181 size_t ns
; /* Number of remaining guesses */
182 dig
*bg
; /* k */ /* Current best guess */
183 dig
*t
; /* k */ /* Scratch-space for prototype */
184 double bmax
; /* Best guess least-squares score */
185 dig x
, bx
; /* Next unused symbol index */
186 size_t *v
; /* (k + 1)^2 */ /* Bin counts for least-squares */
187 ratectx
*r
; /* Rate context for search */
190 static void print_guess(const mm
*m
, const dig
*d
)
192 unsigned k
= m
->k
, i
;
194 for (i
= 0; i
< k
; i
++) {
200 static void dofep(cpc
*c
, void (*fn
)(cpc
*c
, const dig
*g
, unsigned x
),
201 unsigned k
, unsigned n
, unsigned i
, unsigned x
)
209 for (j
= 0; j
< x
; j
++) {
211 dofep(c
, fn
, k
, n
, i
+ 1, x
);
215 dofep(c
, fn
, k
, n
, i
+ 1, x
+ 1);
220 static void foreach_proto(cpc
*c
, void (*fn
)(cpc
*c
,
224 unsigned k
= c
->m
.k
, n
= c
->m
.n
;
225 dofep(c
, fn
, k
, n
, 0, c
->x
);
228 static void try_guess(cpc
*c
, const dig
*g
, unsigned x
)
239 memset(v
, 0, (k
+ 1) * (k
+ 1) * sizeof(size_t));
240 for (i
= c
->ns
, s
= c
->s
; i
; i
--, s
+= k
) {
241 rate(c
->r
, s
, &b
, &w
);
242 v
[b
* (k
+ 1) + w
]++;
245 for (i
= (k
+ 1) * (k
+ 1), vp
= v
; i
; i
--, vp
++)
246 max
+= (double)*vp
* (double)*vp
;
247 if (c
->bmax
< 0 || max
< c
->bmax
) {
248 memcpy(c
->bg
, g
, k
* sizeof(dig
));
254 static void best_guess(cpc
*c
)
262 for (i
= c
->ns
, s
= c
->s
; i
; i
--, s
+= k
)
263 try_guess(c
, s
, c
->x
);
265 foreach_proto(c
, try_guess
);
269 static void filter_guesses(cpc
*c
, const dig
*g
, unsigned b
, unsigned w
)
278 for (i
= c
->ns
, s
= ss
= c
->s
; i
; i
--, s
+= k
) {
279 rate(c
->r
, s
, &bb
, &ww
);
280 if (b
== bb
&& w
== ww
) {
281 memmove(ss
, s
, k
* sizeof(dig
));
285 c
->ns
= (ss
- c
->s
) / k
;
288 static size_t ipow(size_t b
, size_t x
)
300 static void all_guesses(dig
**ss
, unsigned k
, unsigned n
,
301 unsigned i
, const dig
*b
)
309 for (j
= 0; j
< n
; j
++) {
312 memcpy(*ss
, b
, i
* sizeof(dig
));
314 all_guesses(ss
, k
, n
, i
+ 1, s
);
318 #define THINK(what, how) do { \
320 fputs(what "...", stdout); \
325 printf(" done (%.2fs)\n", (_t1 - _t0)/(double)CLOCKS_PER_SEC); \
328 static cpc
*cpc_new(const mm
*m
)
330 cpc
*c
= CREATE(cpc
);
332 c
->ns
= ipow(c
->m
.n
, c
->m
.k
);
333 c
->s
= xmalloc((c
->ns
+ 2) * c
->m
.k
* sizeof(dig
));
334 c
->bg
= c
->s
+ c
->ns
* c
->m
.k
;
335 c
->t
= c
->bg
+ c
->m
.k
;
337 c
->v
= xmalloc((c
->m
.k
+ 1) * (c
->m
.k
+ 1) * sizeof(size_t));
338 c
->r
= rate_alloc(m
);
339 THINK("Setting up", {
340 dig
*ss
= c
->s
; all_guesses(&ss
, c
->m
.k
, c
->m
.n
, 0, 0);
345 static void cpc_free(cpc
*c
)
353 static void cp_rate(void *r
, const dig
*g
, unsigned *b
, unsigned *w
)
358 static const dig
*cp_guess(void *cc
)
363 printf("Liar! All solutions ruled out.\n");
367 fputs("Done! Solution is ", stdout
);
368 print_guess(&c
->m
, c
->s
);
372 printf("(Possible solutions remaining = %lu)\n",
373 (unsigned long)c
->ns
);
377 for (i
= c
->ns
, s
= c
->s
; i
; i
--, s
+= c
->m
.k
) {
378 printf(" %2lu: ", (unsigned long)(c
->ns
- i
+ 1));
379 print_guess(&c
->m
, s
);
389 static void cp_update(void *cc
, const dig
*g
, unsigned b
, unsigned w
)
392 fputs("My guess = ", stdout
);
393 print_guess(&c
->m
, g
);
394 printf("; rating = %u black, %u white\n", b
, w
);
396 filter_guesses(c
, g
, b
, w
);
400 /*----- Human player ------------------------------------------------------*/
407 static hpc
*hpc_new(const mm
*m
)
409 hpc
*h
= CREATE(hpc
);
410 h
->t
= xmalloc(m
->k
* sizeof(dig
));
415 static void hpc_free(hpc
*h
)
421 static void hp_rate(void *mp
, const dig
*g
, unsigned *b
, unsigned *w
)
424 fputs("Guess = ", stdout
);
426 printf("; rating: ");
428 scanf("%u %u", b
, w
);
431 static const dig
*hp_guess(void *hh
)
436 fputs("Your guess: ", stdout
);
438 for (i
= 0; i
< h
->m
.k
; i
++) {
446 static void hp_update(void *cc
, const dig
*g
, unsigned b
, unsigned w
)
448 printf("Rating = %u black, %u white\n", b
, w
);
451 /*----- Solver player -----------------------------------------------------*/
459 static spc
*spc_new(const mm
*m
)
461 spc
*s
= CREATE(spc
);
468 static void spc_free(spc
*s
)
475 static const dig
*sp_guess(void *ss
)
484 return (cp_guess(s
->c
));
486 fputs("Your guess (dot for end): ", stdout
);
488 do ch
= getchar(); while (isspace(ch
));
489 if (!isdigit(ch
)) { s
->i
= 1; goto again
; }
491 for (i
= 0; i
< h
->m
.k
; i
++) {
499 static void sp_update(void *ss
, const dig
*g
, unsigned b
, unsigned w
)
502 cp_update(s
->c
, g
, b
, w
);
505 /*----- Main game logic ---------------------------------------------------*/
507 static int play(const mm
*m
,
508 void (*ratefn
)(void *rr
, const dig
*g
,
509 unsigned *b
, unsigned *w
),
511 const dig
*(*guessfn
)(void *gg
),
512 void (*updatefn
)(void *gg
, const dig
*g
,
513 unsigned b
, unsigned w
),
526 ratefn(rr
, g
, &b
, &w
);
529 updatefn(gg
, g
, b
, w
);
533 int main(int argc
, char *argv
[])
537 void (*ratefn
)(void *rr
, const dig
*g
, unsigned *b
, unsigned *w
) = 0;
543 static struct option opt
[] = {
544 { "computer", 0, 0, 'C' },
545 { "human", 0, 0, 'H' },
546 { "solver", 0, 0, 'S' },
549 int i
= mdwopt(argc
, argv
, "CHS", opt
, 0, 0, 0);
553 case 'C': h
= 0; break;
554 case 'H': h
= 1; break;
555 case 'S': h
= 2; break;
560 if (argc
- optind
== 0) {
563 } else if (argc
- optind
< 2)
564 die(1, "bad parameters");
566 m
.k
= atoi(argv
[optind
++]);
567 m
.n
= atoi(argv
[optind
++]);
568 if (argc
- optind
>= m
.k
) {
569 dig
*s
= xmalloc(m
.k
* sizeof(dig
));
571 for (i
= 0; i
< m
.k
; i
++)
572 s
[i
] = atoi(argv
[optind
++]);
573 rr
= rate_new(&m
, s
);
578 die(1, "bad parameters");
583 hpc
*hh
= hpc_new(&m
);
585 dig
*s
= xmalloc(m
.k
* sizeof(dig
));
588 for (i
= 0; i
< m
.k
; i
++)
590 rr
= rate_new(&m
, s
);
594 n
= play(&m
, ratefn
, rr
, hp_guess
, hp_update
, hh
);
598 cpc
*cc
= cpc_new(&m
);
600 n
= play(&m
, ratefn
, rr
, cp_guess
, cp_update
, cc
);
602 n
= play(&m
, hp_rate
, &m
, cp_guess
, cp_update
, cc
);
606 spc
*ss
= spc_new(&m
);
607 n
= play(&m
, hp_rate
, &m
, sp_guess
, sp_update
, ss
);
614 printf("Solved in %d guesses\n", n
);
620 /*----- That's all, folks -------------------------------------------------*/