/*----- Header files ------------------------------------------------------*/
+#include <assert.h>
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <mLib/alloc.h>
+#include <mLib/darray.h>
#include <mLib/mdwopt.h>
#include <mLib/quis.h>
#include <mLib/report.h>
static ratectx *rate_new(const mm *m, const dig *s)
{
ratectx *r = rate_alloc(m);
+
rate_init(r, s);
return (r);
}
*w = ww;
}
-static void rate_free(ratectx *r)
-{
- xfree(r->v);
- DESTROY(r);
-}
+static void rate_free(ratectx *r) { xfree(r->v); DESTROY(r); }
/*----- Computer player ---------------------------------------------------*/
typedef struct cpc {
mm m; /* Game parameters */
+ unsigned f; /* Various flags */
+#define CPCF_QUIET 1u /* Don't produce lots of output */
dig *s; /* n^k * k */ /* Remaining guesses */
size_t ns; /* Number of remaining guesses */
dig *bg; /* k */ /* Current best guess */
unsigned x))
{
unsigned k = c->m.k, n = c->m.n;
+
dofep(c, fn, k, n, 0, c->x);
}
}
}
-#define THINK(what, how) do { \
- clock_t _t0, _t1; \
- fputs(what "...", stdout); \
- fflush(stdout); \
- _t0 = clock(); \
+#define THINK(c, what, how) do { \
+ clock_t _t0 = 0, _t1; \
+ if (!(c->f & CPCF_QUIET)) { \
+ fputs(what "...", stdout); \
+ fflush(stdout); \
+ _t0 = clock(); \
+ } \
do how while (0); \
- _t1 = clock(); \
- printf(" done (%.2fs)\n", (_t1 - _t0)/(double)CLOCKS_PER_SEC); \
+ if (!(c->f & CPCF_QUIET)) { \
+ _t1 = clock(); \
+ printf(" done (%.2fs)\n", (_t1 - _t0)/(double)CLOCKS_PER_SEC); \
+ } \
} while (0)
-static cpc *cpc_new(const mm *m)
+static cpc *cpc_new(const mm *m, unsigned f)
{
cpc *c = CREATE(cpc);
+
+ c->f = f;
c->m = *m;
c->ns = ipow(c->m.n, c->m.k);
c->s = xmalloc((c->ns + 2) * c->m.k * sizeof(dig));
c->x = 0;
c->v = xmalloc((c->m.k + 1) * (c->m.k + 1) * sizeof(size_t));
c->r = rate_alloc(m);
- THINK("Setting up", {
+ THINK(c, "Setting up", {
dig *ss = c->s; all_guesses(&ss, c->m.k, c->m.n, 0, 0);
});
return (c);
}
static void cp_rate(void *r, const dig *g, unsigned *b, unsigned *w)
-{
- rate(r, g, b, w);
-}
+ { rate(r, g, b, w); }
static const dig *cp_guess(void *cc)
{
cpc *c = cc;
if (c->ns == 0) {
- printf("Liar! All solutions ruled out.\n");
+ if (!(c->f & CPCF_QUIET))
+ printf("Liar! All solutions ruled out.\n");
return (0);
}
if (c->ns == 1) {
- fputs("Done! Solution is ", stdout);
- print_guess(&c->m, c->s);
- putchar('\n');
+ if (!(c->f & CPCF_QUIET)) {
+ fputs("Done! Solution is ", stdout);
+ print_guess(&c->m, c->s);
+ putchar('\n');
+ }
return (c->s);
}
- printf("(Possible solutions remaining = %lu)\n",
- (unsigned long)c->ns);
- if (c->ns < 32) {
- const dig *s;
- size_t i;
- for (i = c->ns, s = c->s; i; i--, s += c->m.k) {
- printf(" %2lu: ", (unsigned long)(c->ns - i + 1));
- print_guess(&c->m, s);
- putchar('\n');
+ if (!(c->f & CPCF_QUIET)) {
+ printf("(Possible solutions remaining = %lu)\n",
+ (unsigned long)c->ns);
+ if (c->ns < 32) {
+ const dig *s;
+ size_t i;
+ for (i = c->ns, s = c->s; i; i--, s += c->m.k) {
+ printf(" %2lu: ", (unsigned long)(c->ns - i + 1));
+ print_guess(&c->m, s);
+ putchar('\n');
+ }
}
}
- THINK("Pondering", {
+ THINK(c, "Pondering", {
best_guess(c);
});
return (c->bg);
static void cp_update(void *cc, const dig *g, unsigned b, unsigned w)
{
cpc *c = cc;
- fputs("My guess = ", stdout);
- print_guess(&c->m, g);
- printf("; rating = %u black, %u white\n", b, w);
- THINK("Filtering", {
+
+ if (!(c->f & CPCF_QUIET)) {
+ fputs("My guess = ", stdout);
+ print_guess(&c->m, g);
+ printf("; rating = %u black, %u white\n", b, w);
+ }
+ THINK(c, "Filtering", {
filter_guesses(c, g, b, w);
});
}
static spc *spc_new(const mm *m)
{
spc *s = CREATE(spc);
- s->c = cpc_new(m);
+ s->c = cpc_new(m, 0);
s->h = hpc_new(m);
s->i = 0;
return (s);
}
static void sp_update(void *ss, const dig *g, unsigned b, unsigned w)
+ { spc *s = ss; cp_update(s->c, g, b, w); }
+
+/*----- Full tournament stuff ---------------------------------------------*/
+
+DA_DECL(uint_v, unsigned);
+
+typedef struct allstats {
+ const mm *m;
+ unsigned f;
+#define AF_VERBOSE 1u
+ uint_v gmap;
+ unsigned long g;
+ unsigned long n;
+ clock_t t;
+} allstats;
+
+static void dorunone(allstats *a, dig *s)
{
- spc *s = ss;
- cp_update(s->c, g, b, w);
+ ratectx *r = rate_new(a->m, s);
+ clock_t t = 0, t0, t1;
+ cpc *c;
+ int n = 0;
+ const dig *g;
+ unsigned b, w;
+
+ if (a->f & AF_VERBOSE) {
+ print_guess(a->m, s);
+ fputs(": ", stdout);
+ fflush(stdout);
+ }
+
+ c = cpc_new(a->m, CPCF_QUIET);
+ for (;;) {
+ t0 = clock();
+ g = cp_guess(c);
+ t1 = clock();
+ t += t1 - t0;
+ assert(g);
+ n++;
+ rate(r, g, &b, &w);
+ if (b == a->m->k)
+ break;
+ t0 = clock();
+ cp_update(c, g, b, w);
+ t1 = clock();
+ t += t1 - t0;
+ }
+ a->t += t;
+ a->g += n;
+ while (DA_LEN(&a->gmap) <= n)
+ DA_PUSH(&a->gmap, 0);
+ DA(&a->gmap)[n]++;
+ rate_free(r);
+ cpc_free(c);
+
+ if (a->f & AF_VERBOSE)
+ printf("%2u (%5.2fs)\n", n, (double)t/CLOCKS_PER_SEC);
+}
+
+static void dorunall(allstats *a, dig *s, unsigned i)
+{
+ dig j;
+
+ if (i >= a->m->k) {
+ dorunone(a, s);
+ a->n++;
+ } else {
+ for (j = 0; j < a->m->n; j++) {
+ s[i] = j;
+ dorunall(a, s, i + 1);
+ }
+ }
+}
+
+static void run_all(const mm *m)
+{
+ dig *s = xmalloc(m->k * sizeof(dig));
+ allstats a;
+ unsigned i;
+
+ a.m = m;
+ a.f = AF_VERBOSE;
+ DA_CREATE(&a.gmap);
+ a.n = 0;
+ a.g = 0;
+ a.t = 0;
+ dorunall(&a, s, 0);
+ xfree(s);
+
+ for (i = 1; i < DA_LEN(&a.gmap); i++)
+ printf("%2u guesses: %5u games\n", i, DA(&a.gmap)[i]);
+ printf("Average: %.4f (%.2fs)\n",
+ (double)a.g/a.n, (double)a.t/(a.n * CLOCKS_PER_SEC));
}
/*----- Main game logic ---------------------------------------------------*/
{ "computer", 0, 0, 'C' },
{ "human", 0, 0, 'H' },
{ "solver", 0, 0, 'S' },
+ { "all", 0, 0, 'a' },
{ 0, 0, 0, 0 }
};
- int i = mdwopt(argc, argv, "CHS", opt, 0, 0, 0);
+ int i = mdwopt(argc, argv, "CHSa", opt, 0, 0, 0);
if (i < 0)
break;
switch (i) {
case 'C': h = 0; break;
case 'H': h = 1; break;
case 'S': h = 2; break;
+ case 'a': h = 99; break;
default:
exit(1);
}
hpc_free(hh);
} break;
case 0: {
- cpc *cc = cpc_new(&m);
+ cpc *cc = cpc_new(&m, 0);
if (rr)
n = play(&m, ratefn, rr, cp_guess, cp_update, cc);
else
n = play(&m, hp_rate, &m, sp_guess, sp_update, ss);
spc_free(ss);
} break;
+ case 99:
+ run_all(&m);
+ return (0);
+ break;
default:
abort();
}
~mdw / mm / blobdiff