47ffa0c0bc4558c5f82bb7ca48847b920e0f0553
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'$%; 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
);
123 static void rate(const ratectx
*r
, const dig
*g
, unsigned *b
, unsigned *w
)
126 unsigned k
= r
->m
.k
, n
= r
->m
.n
;
130 unsigned bb
= 0, ww
= 0;
132 memset(v
, 0, n
* sizeof(dig
));
133 memcpy(vv
, r
->v
, n
* sizeof(dig
));
134 for (i
= 0; i
< k
; i
++) {
142 for (i
= 0; i
< n
; i
++)
143 ww
+= v
[i
] < vv
[i
] ? v
[i
] : vv
[i
];
148 static void rate_free(ratectx
*r
) { xfree(r
->v
); DESTROY(r
); }
150 /*----- Computer player ---------------------------------------------------*/
152 /* --- About the algorithms --- *
154 * At each stage, we attampt to choose the guess which will give us the most
155 * information, regardless of the outcome. For each guess candidate, we
156 * count the remaining possible codes for each outcome, and choose the
157 * candidate with the least square sum. There are wrinkles.
159 * Firstly the number of possible guesses is large, and the number of
160 * possible codes is huge too; and our algorithm takes time proportional to
161 * the product of the two. However, a symbol we've never tried before is as
162 * good as any other, so we can narrow the list of candidate guesses by
163 * considering only %%\emph{prototypes}%% where we use only the smallest
164 * untried symbol at any point to represent introducing any new symbol. The
165 * number of initial prototypes is quite small. For the four-symbol game,
166 * they are 0000, 0001, 0011, 0012, 0111, 0112, 0122, and 0123.
168 * Secondly, when the number of possible codes become small, we want to bias
169 * the guess selection algorithm towards possible codes (so that we win if
170 * we're lucky). Since the algorithm chooses the first guess with the lowest
171 * sum-of-squares value, we simply run through the possible codes before
172 * enumerating the prototype guesses.
176 mm m
; /* Game parameters */
177 unsigned f
; /* Various flags */
178 #define CPCF_QUIET 1u /* Don't produce lots of output */
179 dig
*s
; /* n^k * k */ /* Remaining guesses */
180 size_t ns
; /* Number of remaining guesses */
181 dig
*bg
; /* k */ /* Current best guess */
182 dig
*t
; /* k */ /* Scratch-space for prototype */
183 double bmax
; /* Best guess least-squares score */
184 dig x
, bx
; /* Next unused symbol index */
185 size_t *v
; /* (k + 1)^2 */ /* Bin counts for least-squares */
186 ratectx
*r
; /* Rate context for search */
189 static void print_guess(const mm
*m
, const dig
*d
)
191 unsigned k
= m
->k
, i
;
193 for (i
= 0; i
< k
; i
++) {
199 static void dofep(cpc
*c
, void (*fn
)(cpc
*c
, const dig
*g
, unsigned x
),
200 unsigned k
, unsigned n
, unsigned i
, unsigned x
)
208 for (j
= 0; j
< x
; j
++) {
210 dofep(c
, fn
, k
, n
, i
+ 1, x
);
214 dofep(c
, fn
, k
, n
, i
+ 1, x
+ 1);
219 static void foreach_proto(cpc
*c
, void (*fn
)(cpc
*c
,
223 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(c, what, how) do { \
319 clock_t _t0 = 0, _t1; \
320 if (!(c->f & CPCF_QUIET)) { \
321 fputs(what "...", stdout); \
326 if (!(c->f & CPCF_QUIET)) { \
328 printf(" done (%.2fs)\n", (_t1 - _t0)/(double)CLOCKS_PER_SEC); \
332 static cpc
*cpc_new(const mm
*m
, unsigned f
)
334 cpc
*c
= CREATE(cpc
);
338 c
->ns
= ipow(c
->m
.n
, c
->m
.k
);
339 c
->s
= xmalloc((c
->ns
+ 2) * c
->m
.k
* sizeof(dig
));
340 c
->bg
= c
->s
+ c
->ns
* c
->m
.k
;
341 c
->t
= c
->bg
+ c
->m
.k
;
343 c
->v
= xmalloc((c
->m
.k
+ 1) * (c
->m
.k
+ 1) * sizeof(size_t));
344 c
->r
= rate_alloc(m
);
345 THINK(c
, "Setting up", {
346 dig
*ss
= c
->s
; all_guesses(&ss
, c
->m
.k
, c
->m
.n
, 0, 0);
351 static void cpc_free(cpc
*c
)
359 static void cp_rate(void *r
, const dig
*g
, unsigned *b
, unsigned *w
)
360 { rate(r
, g
, b
, w
); }
362 static const dig
*cp_guess(void *cc
)
367 if (!(c
->f
& CPCF_QUIET
))
368 printf("Liar! All solutions ruled out.\n");
372 if (!(c
->f
& CPCF_QUIET
)) {
373 fputs("Done! Solution is ", stdout
);
374 print_guess(&c
->m
, c
->s
);
379 if (!(c
->f
& CPCF_QUIET
)) {
380 printf("(Possible solutions remaining = %lu)\n",
381 (unsigned long)c
->ns
);
385 for (i
= c
->ns
, s
= c
->s
; i
; i
--, s
+= c
->m
.k
) {
386 printf(" %2lu: ", (unsigned long)(c
->ns
- i
+ 1));
387 print_guess(&c
->m
, s
);
392 THINK(c
, "Pondering", {
398 static void cp_update(void *cc
, const dig
*g
, unsigned b
, unsigned w
)
402 if (!(c
->f
& CPCF_QUIET
)) {
403 fputs("My guess = ", stdout
);
404 print_guess(&c
->m
, g
);
405 printf("; rating = %u black, %u white\n", b
, w
);
407 THINK(c
, "Filtering", {
408 filter_guesses(c
, g
, b
, w
);
412 /*----- Human player ------------------------------------------------------*/
419 static hpc
*hpc_new(const mm
*m
)
421 hpc
*h
= CREATE(hpc
);
422 h
->t
= xmalloc(m
->k
* sizeof(dig
));
427 static void hpc_free(hpc
*h
)
433 static void hp_rate(void *mp
, const dig
*g
, unsigned *b
, unsigned *w
)
436 fputs("Guess = ", stdout
);
438 printf("; rating: ");
440 scanf("%u %u", b
, w
);
443 static const dig
*hp_guess(void *hh
)
448 fputs("Your guess: ", stdout
);
450 for (i
= 0; i
< h
->m
.k
; i
++) {
458 static void hp_update(void *cc
, const dig
*g
, unsigned b
, unsigned w
)
460 printf("Rating = %u black, %u white\n", b
, w
);
463 /*----- Solver player -----------------------------------------------------*/
471 static spc
*spc_new(const mm
*m
)
473 spc
*s
= CREATE(spc
);
474 s
->c
= cpc_new(m
, 0);
480 static void spc_free(spc
*s
)
487 static const dig
*sp_guess(void *ss
)
496 return (cp_guess(s
->c
));
498 fputs("Your guess (dot for end): ", stdout
);
500 do ch
= getchar(); while (isspace(ch
));
501 if (!isdigit(ch
)) { s
->i
= 1; goto again
; }
503 for (i
= 0; i
< h
->m
.k
; i
++) {
511 static void sp_update(void *ss
, const dig
*g
, unsigned b
, unsigned w
)
512 { spc
*s
= ss
; cp_update(s
->c
, g
, b
, w
); }
514 /*----- Full tournament stuff ---------------------------------------------*/
516 DA_DECL(uint_v
, unsigned);
518 typedef struct allstats
{
521 #define AF_VERBOSE 1u
528 static void dorunone(allstats
*a
, dig
*s
)
530 ratectx
*r
= rate_new(a
->m
, s
);
531 clock_t t
= 0, t0
, t1
;
537 if (a
->f
& AF_VERBOSE
) {
538 print_guess(a
->m
, s
);
543 c
= cpc_new(a
->m
, CPCF_QUIET
);
555 cp_update(c
, g
, b
, w
);
561 while (DA_LEN(&a
->gmap
) <= n
)
562 DA_PUSH(&a
->gmap
, 0);
567 if (a
->f
& AF_VERBOSE
)
568 printf("%2u (%5.2fs)\n", n
, t
/(double)CLOCKS_PER_SEC
);
571 static void dorunall(allstats
*a
, dig
*s
, unsigned i
)
579 for (j
= 0; j
< a
->m
->n
; j
++) {
581 dorunall(a
, s
, i
+ 1);
586 static void run_all(const mm
*m
)
588 dig
*s
= xmalloc(m
->k
* sizeof(dig
));
601 for (i
= 1; i
< DA_LEN(&a
.gmap
); i
++)
602 printf("%2u guesses: %5u games\n", i
, DA(&a
.gmap
)[i
]);
603 printf("Average: %.4f (%.2fs)\n",
604 (double)a
.g
/a
.n
, a
.t
/(a
.n
* (double)CLOCKS_PER_SEC
));
607 /*----- Main game logic ---------------------------------------------------*/
609 static int play(const mm
*m
,
610 void (*ratefn
)(void *rr
, const dig
*g
,
611 unsigned *b
, unsigned *w
),
613 const dig
*(*guessfn
)(void *gg
),
614 void (*updatefn
)(void *gg
, const dig
*g
,
615 unsigned b
, unsigned w
),
628 ratefn(rr
, g
, &b
, &w
);
631 updatefn(gg
, g
, b
, w
);
635 int main(int argc
, char *argv
[])
639 void (*ratefn
)(void *rr
, const dig
*g
, unsigned *b
, unsigned *w
) = 0;
645 static struct option opt
[] = {
646 { "computer", 0, 0, 'C' },
647 { "human", 0, 0, 'H' },
648 { "solver", 0, 0, 'S' },
649 { "all", 0, 0, 'a' },
652 int i
= mdwopt(argc
, argv
, "CHSa", opt
, 0, 0, 0);
656 case 'C': h
= 0; break;
657 case 'H': h
= 1; break;
658 case 'S': h
= 2; break;
659 case 'a': h
= 99; break;
664 if (argc
- optind
== 0) {
667 } else if (argc
- optind
< 2)
668 die(1, "bad parameters");
670 m
.k
= atoi(argv
[optind
++]);
671 m
.n
= atoi(argv
[optind
++]);
672 if (argc
- optind
>= m
.k
) {
673 dig
*s
= xmalloc(m
.k
* sizeof(dig
));
675 for (i
= 0; i
< m
.k
; i
++)
676 s
[i
] = atoi(argv
[optind
++]);
677 rr
= rate_new(&m
, s
);
682 die(1, "bad parameters");
687 hpc
*hh
= hpc_new(&m
);
689 dig
*s
= xmalloc(m
.k
* sizeof(dig
));
692 for (i
= 0; i
< m
.k
; i
++)
694 rr
= rate_new(&m
, s
);
698 n
= play(&m
, ratefn
, rr
, hp_guess
, hp_update
, hh
);
702 cpc
*cc
= cpc_new(&m
, 0);
704 n
= play(&m
, ratefn
, rr
, cp_guess
, cp_update
, cc
);
706 n
= play(&m
, hp_rate
, &m
, cp_guess
, cp_update
, cc
);
710 spc
*ss
= spc_new(&m
);
711 n
= play(&m
, hp_rate
, &m
, sp_guess
, sp_update
, ss
);
722 printf("Solved in %d guesses\n", n
);
728 /*----- That's all, folks -------------------------------------------------*/