Welcome, guest | Sign In | My Account | Store | Cart
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 = [0] * 10
    count2 = [0] * 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[0] == 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 = [0] * 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

"""

History

  • revision 2 (11 years ago)
  • previous revisions are not available