3 * Simple mastermind game
5 * (c) 2006 Mark Wooding
8 /*----- Licensing notice --------------------------------------------------*
10 * This file is part of mm: a simple Mastermind game.
12 * mm is free software; you can redistribute it and/or modify
13 * it under the terms of the GNU General Public License as published by
14 * the Free Software Foundation; either version 2 of the License, or
15 * (at your option) any later version.
17 * mm is distributed in the hope that it will be useful,
18 * but WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 * GNU General Public License for more details.
22 * You should have received a copy of the GNU General Public License
23 * along with mm; if not, write to the Free Software Foundation,
24 * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
27 /*----- Header files ------------------------------------------------------*/
36 #include <mLib/alloc.h>
37 #include <mLib/darray.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'$%. The black count %$b$% is then the number of such
74 * matches, and the white count is given by
76 * %$w = \displaystyle \sum_{0<i\le n} \min(v_i, v'_i) - b.$%
78 * Thus, the work is %$O(k + n)$%, rather than the %$O(k^2)$% for a
79 * %%na\"\i{}ve%% implementation.
82 typedef struct ratectx
{
89 static ratectx
*rate_alloc(const mm
*m
)
95 v
= xmalloc((2 * m
->n
+ m
->k
) * sizeof(dig
));
103 static void rate_init(ratectx
*r
, const dig
*s
)
107 memset(r
->v
, 0, r
->m
.n
* sizeof(dig
));
108 for (i
= 0; i
< r
->m
.k
; i
++)
110 memcpy(r
->s
, s
, r
->m
.k
* sizeof(dig
));
113 static ratectx
*rate_new(const mm
*m
, const dig
*s
)
115 ratectx
*r
= rate_alloc(m
);
121 static void rate(const ratectx
*r
, const dig
*g
, unsigned *b
, unsigned *w
)
124 unsigned k
= r
->m
.k
, n
= r
->m
.n
;
127 unsigned bb
= 0, ww
= 0;
129 memset(v
, 0, n
* sizeof(dig
));
130 for (i
= 0; i
< k
; i
++) {
131 if (g
[i
] == s
[i
]) bb
++;
134 for (i
= 0; i
< n
; i
++)
135 ww
+= v
[i
] < r
->v
[i
] ? v
[i
] : r
->v
[i
];
140 static void rate_free(ratectx
*r
) { xfree(r
->v
); DESTROY(r
); }
142 /*----- Computer player ---------------------------------------------------*/
144 /* --- About the algorithms --- *
146 * At each stage, we attampt to choose the guess which will give us the most
147 * information, regardless of the outcome. For each guess candidate, we
148 * count the remaining possible codes for each outcome, and choose the
149 * candidate with the least square sum. There are wrinkles.
151 * Firstly the number of possible guesses is large, and the number of
152 * possible codes is huge too; and our algorithm takes time proportional to
153 * the product of the two. However, a symbol we've never tried before is as
154 * good as any other, so we can narrow the list of candidate guesses by
155 * considering only %%\emph{prototypes}%% where we use only the smallest
156 * untried symbol at any point to represent introducing any new symbol. The
157 * number of initial prototypes is quite small. For the four-symbol game,
158 * they are 0000, 0001, 0011, 0012, 0111, 0112, 0122, and 0123.
160 * Secondly, when the number of possible codes become small, we want to bias
161 * the guess selection algorithm towards possible codes (so that we win if
162 * we're lucky). Since the algorithm chooses the first guess with the lowest
163 * sum-of-squares value, we simply run through the possible codes before
164 * enumerating the prototype guesses.
168 mm m
; /* Game parameters */
169 unsigned f
; /* Various flags */
170 #define CPCF_QUIET 1u /* Don't produce lots of output */
171 dig
*s
; /* n^k * k */ /* Remaining guesses */
172 size_t ns
; /* Number of remaining guesses */
173 dig
*bg
; /* k */ /* Current best guess */
174 dig
*t
; /* k */ /* Scratch-space for prototype */
175 double bmax
; /* Best guess least-squares score */
176 dig x
, bx
; /* Next unused symbol index */
177 size_t *v
; /* (k + 1)^2 */ /* Bin counts for least-squares */
178 ratectx
*r
; /* Rate context for search */
181 static void print_guess(const mm
*m
, const dig
*d
)
183 unsigned k
= m
->k
, i
;
185 for (i
= 0; i
< k
; i
++) {
191 static void dofep(cpc
*c
, void (*fn
)(cpc
*c
, const dig
*g
, unsigned x
),
192 unsigned k
, unsigned n
, unsigned i
, unsigned x
)
200 for (j
= 0; j
< x
; j
++) {
202 dofep(c
, fn
, k
, n
, i
+ 1, x
);
206 dofep(c
, fn
, k
, n
, i
+ 1, x
+ 1);
211 static void foreach_proto(cpc
*c
, void (*fn
)(cpc
*c
,
215 unsigned k
= c
->m
.k
, n
= c
->m
.n
;
217 dofep(c
, fn
, k
, n
, 0, c
->x
);
220 static void try_guess(cpc
*c
, const dig
*g
, unsigned x
)
231 memset(v
, 0, (k
+ 1) * (k
+ 1) * sizeof(size_t));
232 for (i
= c
->ns
, s
= c
->s
; i
; i
--, s
+= k
) {
233 rate(c
->r
, s
, &b
, &w
);
234 v
[b
* (k
+ 1) + w
]++;
237 for (i
= (k
+ 1) * (k
+ 1), vp
= v
; i
; i
--, vp
++)
238 max
+= (double)*vp
* (double)*vp
;
239 if (c
->bmax
< 0 || max
< c
->bmax
) {
240 memcpy(c
->bg
, g
, k
* sizeof(dig
));
246 static void best_guess(cpc
*c
)
254 for (i
= c
->ns
, s
= c
->s
; i
; i
--, s
+= k
)
255 try_guess(c
, s
, c
->x
);
257 foreach_proto(c
, try_guess
);
261 static void filter_guesses(cpc
*c
, const dig
*g
, unsigned b
, unsigned w
)
270 for (i
= c
->ns
, s
= ss
= c
->s
; i
; i
--, s
+= k
) {
271 rate(c
->r
, s
, &bb
, &ww
);
272 if (b
== bb
&& w
== ww
) {
273 memmove(ss
, s
, k
* sizeof(dig
));
277 c
->ns
= (ss
- c
->s
) / k
;
280 static size_t ipow(size_t b
, size_t x
)
292 static void all_guesses(dig
**ss
, unsigned k
, unsigned n
,
293 unsigned i
, const dig
*b
)
301 for (j
= 0; j
< n
; j
++) {
304 memcpy(*ss
, b
, i
* sizeof(dig
));
306 all_guesses(ss
, k
, n
, i
+ 1, s
);
310 #define THINK(c, what, how) do { \
311 clock_t _t0 = 0, _t1; \
312 if (!(c->f & CPCF_QUIET)) { \
313 fputs(what "...", stdout); \
318 if (!(c->f & CPCF_QUIET)) { \
320 printf(" done (%.2fs)\n", (_t1 - _t0)/(double)CLOCKS_PER_SEC); \
324 static cpc
*cpc_new(const mm
*m
, unsigned f
)
326 cpc
*c
= CREATE(cpc
);
330 c
->ns
= ipow(c
->m
.n
, c
->m
.k
);
331 c
->s
= xmalloc((c
->ns
+ 2) * c
->m
.k
* sizeof(dig
));
332 c
->bg
= c
->s
+ c
->ns
* c
->m
.k
;
333 c
->t
= c
->bg
+ c
->m
.k
;
335 c
->v
= xmalloc((c
->m
.k
+ 1) * (c
->m
.k
+ 1) * sizeof(size_t));
336 c
->r
= rate_alloc(m
);
337 THINK(c
, "Setting up", {
338 dig
*ss
= c
->s
; all_guesses(&ss
, c
->m
.k
, c
->m
.n
, 0, 0);
343 static void cpc_free(cpc
*c
)
351 static void cp_rate(void *r
, const dig
*g
, unsigned *b
, unsigned *w
)
352 { rate(r
, g
, b
, w
); }
354 static const dig
*cp_guess(void *cc
)
359 if (!(c
->f
& CPCF_QUIET
))
360 printf("Liar! All solutions ruled out.\n");
364 if (!(c
->f
& CPCF_QUIET
)) {
365 fputs("Done! Solution is ", stdout
);
366 print_guess(&c
->m
, c
->s
);
371 if (!(c
->f
& CPCF_QUIET
)) {
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
);
384 THINK(c
, "Pondering", {
390 static void cp_update(void *cc
, const dig
*g
, unsigned b
, unsigned w
)
394 if (!(c
->f
& CPCF_QUIET
)) {
395 fputs("My guess = ", stdout
);
396 print_guess(&c
->m
, g
);
397 printf("; rating = %u black, %u white\n", b
, w
);
399 THINK(c
, "Filtering", {
400 filter_guesses(c
, g
, b
, w
);
404 /*----- Human player ------------------------------------------------------*/
411 static hpc
*hpc_new(const mm
*m
)
413 hpc
*h
= CREATE(hpc
);
414 h
->t
= xmalloc(m
->k
* sizeof(dig
));
419 static void hpc_free(hpc
*h
)
425 static void hp_rate(void *mp
, const dig
*g
, unsigned *b
, unsigned *w
)
428 fputs("Guess = ", stdout
);
430 printf("; rating: ");
432 scanf("%u %u", b
, w
);
435 static const dig
*hp_guess(void *hh
)
440 fputs("Your guess: ", stdout
);
442 for (i
= 0; i
< h
->m
.k
; i
++) {
450 static void hp_update(void *cc
, const dig
*g
, unsigned b
, unsigned w
)
452 printf("Rating = %u black, %u white\n", b
, w
);
455 /*----- Solver player -----------------------------------------------------*/
463 static spc
*spc_new(const mm
*m
)
465 spc
*s
= CREATE(spc
);
466 s
->c
= cpc_new(m
, 0);
472 static void spc_free(spc
*s
)
479 static const dig
*sp_guess(void *ss
)
488 return (cp_guess(s
->c
));
490 fputs("Your guess (dot for end): ", stdout
);
492 do ch
= getchar(); while (isspace(ch
));
493 if (!isdigit(ch
)) { s
->i
= 1; goto again
; }
495 for (i
= 0; i
< h
->m
.k
; i
++) {
503 static void sp_update(void *ss
, const dig
*g
, unsigned b
, unsigned w
)
504 { spc
*s
= ss
; cp_update(s
->c
, g
, b
, w
); }
506 /*----- Full tournament stuff ---------------------------------------------*/
508 DA_DECL(uint_v
, unsigned);
510 typedef struct allstats
{
513 #define AF_VERBOSE 1u
520 static void dorunone(allstats
*a
, dig
*s
)
522 ratectx
*r
= rate_new(a
->m
, s
);
523 clock_t t
= 0, t0
, t1
;
529 if (a
->f
& AF_VERBOSE
) {
530 print_guess(a
->m
, s
);
535 c
= cpc_new(a
->m
, CPCF_QUIET
);
547 cp_update(c
, g
, b
, w
);
553 while (DA_LEN(&a
->gmap
) <= n
)
554 DA_PUSH(&a
->gmap
, 0);
559 if (a
->f
& AF_VERBOSE
)
560 printf("%2u (%5.2fs)\n", n
, t
/(double)CLOCKS_PER_SEC
);
563 static void dorunall(allstats
*a
, dig
*s
, unsigned i
)
571 for (j
= 0; j
< a
->m
->n
; j
++) {
573 dorunall(a
, s
, i
+ 1);
578 static void run_all(const mm
*m
)
580 dig
*s
= xmalloc(m
->k
* sizeof(dig
));
593 for (i
= 1; i
< DA_LEN(&a
.gmap
); i
++)
594 printf("%2u guesses: %5u games\n", i
, DA(&a
.gmap
)[i
]);
595 printf("Average: %.4f (%.2fs)\n",
596 (double)a
.g
/a
.n
, a
.t
/(a
.n
* (double)CLOCKS_PER_SEC
));
599 /*----- Main game logic ---------------------------------------------------*/
601 static int play(const mm
*m
,
602 void (*ratefn
)(void *rr
, const dig
*g
,
603 unsigned *b
, unsigned *w
),
605 const dig
*(*guessfn
)(void *gg
),
606 void (*updatefn
)(void *gg
, const dig
*g
,
607 unsigned b
, unsigned w
),
620 ratefn(rr
, g
, &b
, &w
);
623 updatefn(gg
, g
, b
, w
);
627 int main(int argc
, char *argv
[])
631 void (*ratefn
)(void *rr
, const dig
*g
, unsigned *b
, unsigned *w
) = 0;
637 static struct option opt
[] = {
638 { "computer", 0, 0, 'C' },
639 { "human", 0, 0, 'H' },
640 { "solver", 0, 0, 'S' },
641 { "all", 0, 0, 'a' },
644 int i
= mdwopt(argc
, argv
, "CHSa", opt
, 0, 0, 0);
648 case 'C': h
= 0; break;
649 case 'H': h
= 1; break;
650 case 'S': h
= 2; break;
651 case 'a': h
= 99; break;
656 if (argc
- optind
== 0) {
659 } else if (argc
- optind
< 2)
660 die(1, "bad parameters");
662 m
.k
= atoi(argv
[optind
++]);
663 m
.n
= atoi(argv
[optind
++]);
664 if (argc
- optind
>= m
.k
) {
665 dig
*s
= xmalloc(m
.k
* sizeof(dig
));
667 for (i
= 0; i
< m
.k
; i
++)
668 s
[i
] = atoi(argv
[optind
++]);
669 rr
= rate_new(&m
, s
);
674 die(1, "bad parameters");
679 hpc
*hh
= hpc_new(&m
);
681 dig
*s
= xmalloc(m
.k
* sizeof(dig
));
684 for (i
= 0; i
< m
.k
; i
++)
686 rr
= rate_new(&m
, s
);
690 n
= play(&m
, ratefn
, rr
, hp_guess
, hp_update
, hh
);
694 cpc
*cc
= cpc_new(&m
, 0);
696 n
= play(&m
, ratefn
, rr
, cp_guess
, cp_update
, cc
);
698 n
= play(&m
, hp_rate
, &m
, cp_guess
, cp_update
, cc
);
702 spc
*ss
= spc_new(&m
);
703 n
= play(&m
, hp_rate
, &m
, sp_guess
, sp_update
, ss
);
714 printf("Solved in %d guesses\n", n
);
720 /*----- That's all, folks -------------------------------------------------*/