Welcome, guest | Sign In | My Account | Store | Cart

Framework for experimenting with guessing strategies in Master-mind style games.

Python, 187 lines
 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187``` ```import random from itertools import izip, imap from math import log digits = 4 trials = 100 fmt = '%0' + str(digits) + 'd' searchspace = tuple([tuple(map(int,fmt % i)) for i in range(0,10**digits)]) def compare(a, b, imap=imap, sum=sum, izip=izip, min=min): count1 =  * 10 count2 =  * 10 strikes = 0 for dig1, dig2 in izip(a,b): if dig1 == dig2: strikes += 1 count1[dig1] += 1 count2[dig2] += 1 balls = sum(imap(min, count1, count2)) - strikes return (strikes, balls) def rungame(target, strategy, verbose=True, maxtries=15): possibles = list(searchspace) for i in xrange(maxtries): g = strategy(i, possibles) if verbose: print "Out of %7d possibilities. I'll guess %r" % (len(possibles), g), score = compare(g, target) if verbose: print ' ---> ', score if score == digits: if verbose: print "That's it. After %d tries, I won." % (i+1,) break possibles = [n for n in possibles if compare(g, n) == score] return i+1 ############################################### Strategy support def info(seqn): bits = 0 s = float(sum(seqn)) for i in seqn: p = i / s bits -= p * log(p, 2) return bits def utility(play, possibles): b = {} for poss in possibles: score = compare(play, poss) b[score] = b.get(score, 0) + 1 return info(b.values()) def hasdup(play, set=set, digits=digits): return len(set(play)) != digits def nodup(play, set=set, digits=digits): return len(set(play)) == digits ################################################ Strategies def s_allrand(i, possibles): return random.choice(possibles) def s_trynodup(i, possibles): for j in xrange(20): g = random.choice(possibles) if nodup(g): break return g def s_bestinfo(i, possibles): if i == 0: return s_trynodup(i, possibles) plays = random.sample(possibles, min(20, len(possibles))) _, play = max([(utility(play, possibles), play) for play in plays]) return play def s_worstinfo(i, possibles): if i == 0: return s_trynodup(i, possibles) plays = random.sample(possibles, min(20, len(possibles))) _, play = min([(utility(play, possibles), play) for play in plays]) return play def s_samplebest(i, possibles): if i == 0: return s_trynodup(i, possibles) if len(possibles) > 150: possibles = random.sample(possibles, 150) plays = possibles[:20] elif len(possibles) > 20: plays = random.sample(possibles, 20) else: plays = possibles _, play = max([(utility(play, possibles), play) for play in plays]) return play ## Evaluate Strategies def average(seqn): return sum(seqn) / float(len(seqn)) def counts(seqn): limit = max(10, max(seqn)) + 1 tally =  * limit for i in seqn: tally[i] += 1 return tuple(tally[1:]) from time import clock print '-' * 60 ##for ss in searchspace, filter(hasdup, searchspace), filter(nodup, searchspace): ## print 'spacesize:', len(ss), ' = ', log(len(ss),2), 'bits' ##for play in [(1,2,3,4,5), (1,1,2,3,4), (1,1,1,2,3), (1,1,2,2,3), (1,1,1,2,2)]: ## print 'First play:', play, 'has info content', utility(play, searchspace) ## print 'First play:', play, 'has info content', utility(play, filter(hasdup, searchspace)), 'against dups' ## print 'First play:', play, 'has info content', utility(play, filter(nodup, searchspace)), 'against nodups' ## print for strategy in (s_bestinfo, s_samplebest, s_worstinfo, s_allrand, s_trynodup, s_bestinfo): start = clock() data = [rungame(random.choice(searchspace), strategy, verbose=False) for i in xrange(trials)] #print '[%d %d| median %.2f mean %.2f |%d %d] dig=%d n=%d %s' % (min(data), lq(data), median(data),average(data), uq(data), max(data), digits, len(data), strategy.__name__) print 'mean=%.2f %r %s n=%d dig=%d' % (average(data), counts(data), strategy.__name__, len(data), digits) print 'Time elapsed %.2f' % (clock() - start,) """ Analysis of strategies with four digit targets s_worstinfo [3 | median 7.00 mean 6.76 | 10] n=120 s_allrand [3 | median 6.00 mean 6.19 | 9] n=120 s_firstnodup [3 | median 6.00 mean 6.24 | 9] n=120 s_trynodup [3 | median 6.00 mean 5.99 | 9] n=120 s_bestinfo [2 | median 6.00 mean 5.75 | 10] n=120 s_worstinfo [3 | median 7.00 mean 6.86 | 10] n=200 s_allrand [4 | median 6.00 mean 6.52 | 10] n=200 s_firstnodup [1 | median 6.00 mean 6.19 | 10] n=200 s_firstdup_restnodup [3 | median 6.00 mean 6.13 | 10] n=200 s_trynodup [3 | median 6.00 mean 6.11 | 10] n=200 s_bestinfo [2 | median 6.00 mean 5.73 | 9] n=200 [3 6| median 7.00 mean 6.78 |8 11] dig=4 n=200 s_worstinfo 6.77 [3 5| median 6.00 mean 6.24 |7 10] dig=4 n=200 s_allrand 6.38 [2 6| median 6.00 mean 6.26 |7 9] dig=4 n=200 s_firstnodup 6.22 [2 5| median 6.00 mean 5.93 |7 9] dig=4 n=200 s_firstdup_restnodup 6.03 [4 5| median 6.00 mean 6.14 |7 9] dig=4 n=200 s_trynodup 6.12 [3 5| median 6.00 mean 5.87 |6 9] dig=4 n=200 s_bestinfo 5.74 [1 6| median 7.00 mean 6.93 |8 11] dig=4 n=500 s_worstinfo [2 5| median 6.00 mean 6.11 |7 10] dig=4 n=500 s_allrand [3 5| median 6.00 mean 6.12 |7 10] dig=4 n=500 s_firstnodup [2 5| median 6.00 mean 6.07 |7 10] dig=4 n=500 s_firstdup_restnodup [2 5| median 6.00 mean 6.03 |7 9] dig=4 n=500 s_trynodup [2 5| median 6.00 mean 5.82 |6 9] dig=4 n=500 s_bestinfo [2 5| median 6.00 mean 5.82 |6 9] dig=4 n=500 s_bestinfo_randfirst spacesize: 100000 = 16.6096404744 bits spacesize: 69760 = 16.0901124197 bits spacesize: 30240 = 14.8841705191 bits First play: (1, 2, 3, 4, 5) has info content 2.72731327592 First play: (1, 2, 3, 4, 5) has info content 2.54363363003 against dups First play: (1, 2, 3, 4, 5) has info content 2.77115216576 against nodups First play: (1, 1, 2, 3, 4) has info content 2.57287940403 First play: (1, 1, 2, 3, 4) has info content 2.51059435464 against dups First play: (1, 1, 2, 3, 4) has info content 2.56508152257 against nodups First play: (1, 1, 1, 2, 3) has info content 2.16683284403 First play: (1, 1, 1, 2, 3) has info content 2.11526590293 against dups First play: (1, 1, 1, 2, 3) has info content 2.13291456398 against nodups First play: (1, 1, 2, 2, 3) has info content 2.28656723529 First play: (1, 1, 2, 2, 3) has info content 2.28606417747 against dups First play: (1, 1, 2, 2, 3) has info content 2.14424289741 against nodups First play: (1, 1, 1, 2, 2) has info content 2.16683284403 First play: (1, 1, 1, 2, 2) has info content 2.11526590293 against dups First play: (1, 1, 1, 2, 2) has info content 2.13291456398 against nodups mean=6.22 (0, 0, 0, 4, 33, 130, 72, 9, 2, 0) s_samplebest n=250 dig=5 Time elapsed 1395.75 """ ```

The basic part of the framework takes only about 30 lines. They rest is an implementation of various search strategies and an engine to gather statistics on how well each strategy performs:

• Randomly pick any one of the remaining possibilities
• If possible, only make guesses that do not have duplicated digits.
• Make the guess that provides the most information (the one that most evenly divides-up the remaining possibilities).

To make it run fast, use psyco. To make it even faster, implement the compare function in C:

`````` /* ------------- C version of the compare() function ----------------*/

#include "Python.h"

PyObject *
compare(PyObject *self, PyObject *args)
{
PyObject *t1, *t2, *elem;
int len, i, j, c1, c2;
int balls=0, strikes=0;

if (!PyArg_ParseTuple(args, "O!O!:compare", &PyTuple_Type, &t1, &PyTuple_Type, &t2))
return NULL;

len = PyTuple_Size(t1);
if (PyTuple_Size(t2) != len)
return NULL;
for (i=0 ; i<len ; i++) {
elem = PyTuple_GET_ITEM(t1, i);
for (c1=0, j=0 ; j<len ; j++) {
if (j<i && PyTuple_GET_ITEM(t1, j) == elem)
break;
if (PyTuple_GET_ITEM(t1, j) == elem)
c1 += 1;
}
for (c2=0, j=0 ; j<len ; j++) {
if (PyTuple_GET_ITEM(t2, j) == elem)
c2 += 1;
}
balls += (c1 < c2) ? c1 : c2;
if (PyTuple_GetItem(t2, i) == elem)
strikes += 1;
}

return Py_BuildValue("(ii)", strikes, balls-strikes);
}

static PyMethodDef mmfuncs[] = {
{"compare", (PyCFunction)compare,       METH_VARARGS, "score two positions"},
{NULL}
};

void
initmm(void)
{
Py_InitModule3("mm", mmfuncs, "mastermind helper functions module");
}
`````` Created by Raymond Hettinger on Tue, 25 Jul 2006 (PSF)