The Hat Problem

I found an item describing an intriguing mathematical game, that I immediately 'got' for the size of problem described and decided to write a Python program to help me explore it.

In the source, you can create different strategy functions that take the same arguments
and return either a colour or the global name ipass.

Enjoy!

'''
The hat problem

From: http://www.msri.org/people/members/sara/articles/hat.html

The hat problem goes like this:
    Three players enter a room and a red or blue hat is placed on each
    person's head. The color of each hat is determined by a coin toss,
    with the outcome of one coin toss having no effect on the others. Each
    person can see the other players' hats but not his own.

    No communication of any sort is allowed, except for an initial
    strategy session before the game begins. Once they have had a chance
    to look at the other hats, the players must simultaneously guess the
    color of their own hats or pass. The group shares a hypothetical $3
    million prize if at least one player guesses correctly and no players
    guess incorrectly.
'''

import random

verbose = True
numplayers = 3
hatcolours = 'red blue'.split()
ipass = 'pass'

def otherhatcolour(hat):
    ''' not(hat) when hat can have two or more colours'''
    return hatcolours[(hatcolours.index(hat)+1) % len(hatcolours)]

def playerhats(n = numplayers):
    ''' generate all hat combinations for the players, but scrambled.'''
    if n:
        hats = hatcolours[:]
        random.shuffle(hats)
        for h1 in hats:
            for h2 in playerhats(n-1):
                yield [h1] + h2
    else:
        yield []

def strategy0(otherhats, hatcolours):
    '''
    If there is a clear max total of hat colours:
        Yours is a random choice from the hat colours occuring the least
    else:
        pass
    '''
    # Count the total hats in each colour
    colourcount = [otherhats.count(c) for c in hatcolours]
    # What hat colours are most/least prevalent
    mn = min(colourcount)
    mx = max(colourcount)
    #
    if colourcount.count(mx) == 1:
        # only one colour occurs as the maximum
        return hatcolours[random.choice([ index
                                          for index, count in enumerate(colourcount)
                                          if count == mn]) ]
    else:
        return ipass

def strategy1(otherhats, hatcolours):
    '''
    If there is a clear max and min total of hat colours,
    Yours is the min; otherwise pass.
    '''
    # Count the total hats in each colour
    colourcount = [otherhats.count(c) for c in hatcolours]
    # What hat colours are most/least prevalent
    mn = min(colourcount)
    mx = max(colourcount)
    #
    if mn != mx and (mn == 0 or colourcount.count(mx) == colourcount.count(mn) == 1):
        # only one colour occurs as the maximum, another as minimum
        # So guess the minimum
        return hatcolours[colourcount.index(mn)]
    else:
        return ipass

def scoreplayers(ph, strategy, _verbose = verbose):
    ''' Compute score and return 1 if players win otherwise zero'''
    n = len(ph)
    strat = []
    playerguessed = []
    for playernum,hat in enumerate(ph):
        strat = strategy([h for i,h in enumerate(ph) if i != playernum], hatcolours)
        if _verbose:
            print "%sPlayer%i:%s under a %6s hat replies: %6s" % (
                "  "*(playernum+1), playernum, "  "*(n-playernum-1), hat, strat
                ),
        if strat == hat:
            if _verbose:
                print "Correct"
            playerguessed.append(True)
        elif strat == ipass:
            if _verbose:
                print "-"
            playerguessed.append(ipass)
        else:
            if _verbose:
                print "Incorrect"
            playerguessed.append(False)
    if (True in playerguessed) and not( False in playerguessed):
        if _verbose:
            print "   Players WIN\n"
        return 1
    else:
        if _verbose:
            print "   Players LOSE\n"
        return 0



def run_stratagem(strategy, _verbose= verbose, _numplayers = numplayers,
                   _hatcolours = hatcolours):
    '''Applies a strategy function to all possible games of a hat problem.

    Prints either a verbose output of every trial, or a summary of
    all trials in csv format
    '''

    global verbose, numplayers, hatcolours
    verbose, numplayers, hatcolours = _verbose, _numplayers, _hatcolours

    totaltries = 0
    totalwins = 0
    if verbose:
        print "\nSTRATEGY"
        print strategy.__name__
        print strategy.__doc__
    for ph in playerhats():
        totaltries +=1
        totalwins += scoreplayers(ph, strategy, verbose)
    if verbose:
        print "\n\n Players won %i/%i = %.2g%% of the time by using %s\n" % (
                totalwins, totaltries, float(totalwins)/totaltries*100.0,
                strategy.__name__)
    else:
        print "Strategy,%s,Hats,%i,Players,%i,Games,%i,Wins,%i,Win%%,%.4f" % (
                strategy.__name__, len(hatcolours), numplayers,
                totaltries, totalwins, float(totalwins)/totaltries)


colours = 'red blue orange yellow green indigo violet'.split()
print
run_stratagem(strategy0, verbose)
run_stratagem(strategy1, verbose)