Friday, May 18, 2007

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)