cs212 »

Unit 5 Code

Contents

pig.py

'''
States are represented as a tuple of (p, me, you, pending) where
p:       an int, 0 or 1, indicating which player's turn it is.
me:      an int, the player-to-move's current score
you:     an int, the other player's current score.
pending: an int, the number of points accumulated on current turn, not yet scored
'
'''

import random
from functools import update_wrapper
import itertools
import collections
import fractions

def decorator(d):
    "Make function d a decorator: d wraps a function fn."
    def _d(fn):
        return update_wrapper(d(fn), fn)
    update_wrapper(_d, d)
    return _d

@decorator
def memo(f):
    """Decorator that caches the return value for each call to f(args).
    Then when called again with same args, we can just look it up."""
    cache = {}
    def _f(*args):
        try:
            return cache[args]
        except KeyError:
            cache[args] = result = f(*args)
            return result
        except TypeError:
            # some element of args can't be a dict key
            return f(*args)
    _f.cache = cache
    return _f

################################################################################
## This defines the game of PIG — the "what"

def roll(state, d):
    """Apply the roll action to a state (and a die roll d) to yield a new state:
    If d is 1, get 1 point (losing any accumulated 'pending' points),
    and it is the other player's turn. If d > 1, add d to 'pending' points."""
    (p, me, you, pending) = state
    if d == 1:
        return (other[p], you, me+1, 0) # pig out; other player's turn
    else:
        return (p, me, you, pending+d)  # accumulate die roll in pending

def hold(state):
    """Apply the hold action to a state to yield a new state:
    Reap the 'pending' points and it becomes the other player's turn."""
    (p, me, you, pending) = state
    return (other[p], you, me+pending, 0)

def dierolls():
    "Generate die rolls."
    while True:
        yield random.randint(1, 6)

other = {1:0, 0:1}    # mapping from player to other player
goal  = 40

def play_pig(A, B, dierolls = dierolls()):
    """Play a game of pig between two players, represented by their strategies.
    Each time through the main loop we ask the current player for one decision,
    which must be 'hold' or 'roll', and we update the state accordingly.
    When one player's score exceeds the goal, return that player."""
    strategies = [A, B]
    state = (0, 0, 0, 0)
    while True:
        (p, me, you, pending) = state
        if me >= goal:
            return strategies[p]
        elif you >= goal:
            return strategies[other[p]]
        else:
            action = strategies[p](state)
            if action == 'hold':
                state = hold(state)
            elif action == 'roll':
                state = roll(state, next(dierolls))
            else: # Illegal action?  You lose!
                return strategies[other[p]]

################################################################################
## This defines strategies for playing Pig — the "how"

def bad_strategy(state):
    "A strategy that could never win, unless a player makes an illegal move"
    return 'hold'

def illegal_strategy(state):
    return 'I want to win pig please.'

def Q_pig(state, action, Pwin):
    "The expected value of choosing action in state."
    if action == 'hold':
        return 1 - Pwin(hold(state))
    if action == 'roll':
        return (1 - Pwin(roll(state, 1))
                + sum(Pwin(roll(state, d)) for d in (2, 3, 4, 5, 6))) / 6.
    raise ValueError

def best_action(state, actions, Q, U):
    "Return the optimal action for a state, given U."
    def EU(action): return Q(state, action, U)
    return max(actions(state), key = EU)

def pig_actions(state):
    "The legal actions from a state."
    _, _, _, pending = state
    return ['roll', 'hold'] if pending else ['roll']

@memo
def Pwin(state):
    """The utility of a state; here just the probability that an optimal player
    whose turn it is to move can win from the current state."""
    # Assumes opponent also plays with optimal strategy.
    (p, me, you, pending) = state
    if me + pending >= goal:
        return 1
    elif you >= goal:
        return 0
    else:
        return max(Q_pig(state, action, Pwin)
                   for action in pig_actions(state))

@memo
def win_diff(state):
    "The utility of a state: here the winning differential (pos or neg)."
    (p, me, you, pending) = state
    if me + pending >= goal or you >= goal:
        return (me + pending - you)
    else:
        return max(Q_pig(state, action, win_diff)
                   for action in pig_actions(state))

def max_diffs(state):
    """A strategy that maximizes the expected difference between my final score
    and my opponent's."""
    return best_action(state, pig_actions, Q_pig, win_diff)

def max_wins(state):
    "The optimal pig strategy chooses an action with the highest win probability."
    return best_action(state, pig_actions, Q_pig, Pwin)

possible_moves = ['roll', 'hold']

def clueless(state):
    "A strategy that ignores the state and chooses at random from possible moves."
    return random.choice(possible_moves)

def always_roll(state):
    return 'roll'

def always_hold(state):
    return 'hold'

def hold_at(x):
    """Return a strategy that holds if and only if
    pending >= x or player reaches goal."""
    def strategy(state):
        (p, me, you, pending) = state
        return 'hold' if (pending >= x or me + pending >= goal) else 'roll'
    strategy.__name__ = 'hold_at(%d)' % x
    return strategy

################################################################################
## Simulation

strategies = [clueless, hold_at(goal/4), hold_at(1+goal/3), hold_at(goal/2),
              hold_at(goal), max_wins]

def play_tournament(strategies, series_length = 50):
    result = collections.defaultdict(int)
    for A, B in itertools.combinations(strategies, 2):
        for _ in range(series_length):
            if play_pig(A, B) == A:
                result[A, B] += 1
            else:
                result[B, A] += 1
            if play_pig(B, A) == A:
                result[A, B] += 1
            else:
                result[B, A] += 1
    result = dict(result)
    print(report_tournament(strategies, result))

def report_tournament(strategies, result):
    N = len(strategies)
    table = []
    for s in strategies:
        items = [result.get((s, t), 0) for t in strategies]
        items = ['{0:<15}'.format(s.__name__)]+map('{0:>5}'.format, items + [sum(items)])
        print(' '.join(items))

################################################################################
## Exploratory data analysis

states = [(0, me, you, pending)
          for me in range(goal+1)
          for you in range(goal+1)
          for pending in range(goal+1)
          if me + pending <= goal]

def compare_strategies(A, B):
    print(len(states))
    r = collections.defaultdict(int)
    for s in states:
        r[A(s), B(s)] += 1
    r = dict(r)
    print(r)

def story():
    r = collections.defaultdict(lambda: [0, 0])
    for s in states:
        w, d = max_wins(s), max_diffs(s)
        if w != d:
            _, _, _, pending = s
            i = 0 if (w == 'roll') else 1
            r[pending][i] += 1
    for (delta, (wrolls, drolls)) in sorted(r.items()):
        print('%4d: %3d %3d'%(delta, wrolls, drolls))

################################################################################
## Tests

def test():
    winner = play_pig(bad_strategy, illegal_strategy)
    assert winner.__name__ == 'bad_strategy'

    # The first three test cases are examples where max_wins and
    # max_diffs return the same action.
    assert max_diffs((1, 26, 21, 15)) == "hold"
    assert max_diffs((1, 23, 36, 7))  == "roll"
    assert max_diffs((0, 29, 4, 3))   == "roll"
    # The remaining test cases are examples where max_wins and
    # max_diffs return different actions.
    assert max_diffs((0, 36, 32, 5))  == "roll"
    assert max_diffs((1, 37, 16, 3))  == "roll"
    assert max_diffs((1, 33, 39, 7))  == "roll"
    assert max_diffs((0, 7, 9, 18))   == "hold"
    assert max_diffs((1, 0, 35, 35))  == "hold"
    assert max_diffs((0, 36, 7, 4))   == "roll"
    assert max_diffs((1, 5, 12, 21))  == "hold"
    assert max_diffs((0, 3, 13, 27))  == "hold"
    assert max_diffs((0, 0, 39, 37))  == "hold"

    assert max_wins((1, 5, 34, 4))   == "roll"
    assert max_wins((1, 18, 27, 8))  == "roll"
    assert max_wins((0, 23, 8, 8))   == "roll"
    assert max_wins((0, 31, 22, 9))  == "hold"
    assert max_wins((1, 11, 13, 21)) == "roll"
    assert max_wins((1, 33, 16, 6))  == "roll"
    assert max_wins((1, 12, 17, 27)) == "roll"
    assert max_wins((1, 9, 32, 5))   == "roll"
    assert max_wins((0, 28, 27, 5))  == "roll"
    assert max_wins((1, 7, 26, 34))  == "hold"
    assert max_wins((1, 20, 29, 17)) == "roll"
    assert max_wins((0, 34, 23, 7))  == "hold"
    assert max_wins((0, 30, 23, 11)) == "hold"
    assert max_wins((0, 22, 36, 6))  == "roll"
    assert max_wins((0, 21, 38, 12)) == "roll"
    assert max_wins((0, 1, 13, 21))  == "roll"
    assert max_wins((0, 11, 25, 14)) == "roll"
    assert max_wins((0, 22, 4, 7))   == "roll"
    assert max_wins((1, 28, 3, 2))   == "roll"
    assert max_wins((0, 11, 0, 24))  == "roll"

    A, B = hold_at(50), clueless
    rolls = iter([6]*9)
    assert play_pig(A, B, rolls) == A

    for _ in range(10):
        winner = play_pig(always_hold, always_roll)
        assert winner.__name__ == 'always_roll'

    global goal
    goal = 50
    assert hold_at(30)((1, 29, 15, 20)) == 'roll'
    assert hold_at(30)((1, 29, 15, 21)) == 'hold'
    assert hold_at(15)((0, 2, 30, 10))  == 'roll'
    assert hold_at(15)((0, 2, 30, 15))  == 'hold'

    assert hold((1, 10, 20, 7))    == (0, 20, 17, 0)
    assert hold((0, 5, 15, 10))    == (1, 15, 15, 0)
    assert roll((1, 10, 20, 7), 1) == (0, 20, 11, 0)
    assert roll((0, 5, 15, 10), 5) == (0, 5, 15, 15)
    goal = 40
    return 'tests pass'

if __name__ == '__main__':
    print test()

    # play_tournament(strategies)
    '''
    |               |  0 |  1 |  2 |  3 |  4 |  5 | total |
    |---------------+----+----+----+----+----+----+-------|
    | clueless 0    |  0 |  2 |  2 |  4 |  6 |  9 |    23 |
    | hold_at(10) 1 | 98 |  0 | 44 | 27 | 43 | 27 |   239 |
    | hold_at(14) 2 | 98 | 56 |  0 | 55 | 43 | 36 |   288 |
    | hold_at(20) 3 | 96 | 73 | 45 |  0 | 50 | 50 |   314 |
    | hold_at(40) 4 | 94 | 57 | 57 | 50 |  0 | 53 |   311 |
    | max_wins 5    | 91 | 73 | 64 | 50 | 47 |  0 |   325 |
    '''

    # play_tournament(strategies, 2000)
    '''
    |               |    0 |    1 |    2 |     3 |    4 |    5 | total |
    |---------------+------+------+------+-------+------+------+-------|
    | clueless 0    |    0 |  120 |  115 |   123 |  231 |  178 |   767 |
    | hold_at(10) 1 | 3880 |    0 | 1559 |  1230 | 1467 | 1333 |  9469 |
    | hold_at(14) 2 | 3885 | 2441 |    0 | 01605 | 1705 | 1549 | 11185 |
    | hold_at(20) 3 | 3877 | 2770 | 2395 |     0 | 2004 | 1860 | 12906 |
    | hold_at(40) 4 | 3769 | 2533 | 2295 |  1996 |    0 | 1974 | 12567 |
    | max_wins 5    | 3822 | 2667 | 2451 |  2140 | 2026 |    0 | 13106 |

    '''

    # compare_strategies(max_wins, max_diffs)
    '''
    {('hold', 'hold'): 1204,  ('hold', 'roll'): 381,
     ('roll', 'roll'): 29741, ('roll', 'hold'): 3975}
    '''

    # story()
    '''
       2:   0  40
       3:   0  40
       4:   0  40
       5:   0  40
       6:   0  40
       7:   0  40
       8:   0  40
       9:   0  40
      10:   0  28
      11:   0  19
      12:   0  12
      13:   0   2
      16:  11   0
      17:  68   0
      18: 128   0
      19: 201   0
      20: 287   0
      21: 327   0
      22: 334   0
      23: 322   0
      24: 307   0
      25: 290   0
      26: 281   0
      27: 253   0
      28: 243   0
      29: 213   0
      30: 187   0
      31: 149   0
      32: 125   0
      33:  95   0
      34:  66   0
      35:  31   0
      36:  22   0
      37:  16   0
      38:  11   0
      39:   7   0
      40:   1   0
    '''

conditional.py

import itertools
import fractions

def conditional_prob():
    print(two_kids)
    # ['BB', 'BG', 'GB', 'GG']
    print(condP(two_boys, one_boy))
    # 1/3

def product(*variables):
    "The cartesian product (as a str) of the possibilities for each variable."
    return map(''.join, itertools.product(*variables))

def condP(predicate, event):
    """Conditional probability: P(predicate(s) | s in event).
    The proportion of states in event for which predicate is true."""
    pred = [s for s in event if predicate(s)]
    return fractions.Fraction(len(pred), len(event))

def tuesday():
    """Out of all families with two kids with at least one boy born on a
    Tuesday, what is the probability of two boys?
    """
    print(two_kids_bday)
    print(condP(two_boys, boy_tuesday))
    # 13/27

sex = 'BG'
two_kids = product(sex, sex)
one_boy = [s for s in two_kids if 'B' in s]
def two_boys(s): return s.count('B') == 2
day = 'SMTWtFs'
two_kids_bday = product(sex, day, sex, day)
boy_tuesday = [s for s in two_kids_bday if 'BT' in s]
boy_anyday = [s for s in two_kids_bday if 'B' in s]
month = 'JFMAmjLaSOND'
two_kids_bmonth = product(sex, month, sex, month)
boy_december = [s for s in two_kids_bmonth if 'BD' in s]

def report(verbose = False, predicate = two_boys, predname = '2 boys',
           cases = [('2 kids', two_kids), ('2 kids born any day', two_kids_bday),
                    ('at least 1 boy', one_boy),
                    ('at least 1 boy born any day', boy_anyday),
                    ('at least 1 boy born on Tuesday', boy_tuesday),
                    ('at least 1 boy born in December', boy_december)]):
    import textwrap
    for (name, event) in cases:
        print('P(%s | %s) = %s' % (predname, name, condP(predicate, event)))
        if verbose:
            print('Reason:\n"%s" has %d elements:\n%s' %(
                name, len(event), textwrap.fill(' '.join(event), 85)))
            good = [s for s in event if predicate(s)]
            print('of those, %d are %s:\n%s\n\n' % (
                len(good), predname, textwrap.fill(' '.join(good), 85)))

if __name__ == '__main__':
    conditional_prob()
    tuesday()
    report()
    '''
    P(2 boys | 2 kids) = 1/4
    P(2 boys | 2 kids born any day) = 1/4
    P(2 boys | at least 1 boy) = 1/3
    P(2 boys | at least 1 boy born any day) = 1/3
    P(2 boys | at least 1 boy born on Tuesday) = 13/27
    P(2 boys | at least 1 boy born in December) = 23/47
    '''

    report(verbose = True)
    '''
    P(2 boys | 2 kids) = 1/4
    Reason:
    "2 kids" has 4 elements:
    BB BG GB GG
    of those, 1 are 2 boys:
    BB

    P(2 boys | 2 kids born any day) = 1/4
    Reason:
    "2 kids born any day" has 196 elements:
    BSBS BSBM BSBT BSBW BSBt BSBF BSBs BSGS BSGM BSGT BSGW BSGt BSGF BSGs BMBS BMBM BMBT
    BMBW BMBt BMBF BMBs BMGS BMGM BMGT BMGW BMGt BMGF BMGs BTBS BTBM BTBT BTBW BTBt BTBF
    BTBs BTGS BTGM BTGT BTGW BTGt BTGF BTGs BWBS BWBM BWBT BWBW BWBt BWBF BWBs BWGS BWGM
    BWGT BWGW BWGt BWGF BWGs BtBS BtBM BtBT BtBW BtBt BtBF BtBs BtGS BtGM BtGT BtGW BtGt
    BtGF BtGs BFBS BFBM BFBT BFBW BFBt BFBF BFBs BFGS BFGM BFGT BFGW BFGt BFGF BFGs BsBS
    BsBM BsBT BsBW BsBt BsBF BsBs BsGS BsGM BsGT BsGW BsGt BsGF BsGs GSBS GSBM GSBT GSBW
    GSBt GSBF GSBs GSGS GSGM GSGT GSGW GSGt GSGF GSGs GMBS GMBM GMBT GMBW GMBt GMBF GMBs
    GMGS GMGM GMGT GMGW GMGt GMGF GMGs GTBS GTBM GTBT GTBW GTBt GTBF GTBs GTGS GTGM GTGT
    GTGW GTGt GTGF GTGs GWBS GWBM GWBT GWBW GWBt GWBF GWBs GWGS GWGM GWGT GWGW GWGt GWGF
    GWGs GtBS GtBM GtBT GtBW GtBt GtBF GtBs GtGS GtGM GtGT GtGW GtGt GtGF GtGs GFBS GFBM
    GFBT GFBW GFBt GFBF GFBs GFGS GFGM GFGT GFGW GFGt GFGF GFGs GsBS GsBM GsBT GsBW GsBt
    GsBF GsBs GsGS GsGM GsGT GsGW GsGt GsGF GsGs
    of those, 49 are 2 boys:
    BSBS BSBM BSBT BSBW BSBt BSBF BSBs BMBS BMBM BMBT BMBW BMBt BMBF BMBs BTBS BTBM BTBT
    BTBW BTBt BTBF BTBs BWBS BWBM BWBT BWBW BWBt BWBF BWBs BtBS BtBM BtBT BtBW BtBt BtBF
    BtBs BFBS BFBM BFBT BFBW BFBt BFBF BFBs BsBS BsBM BsBT BsBW BsBt BsBF BsBs

    P(2 boys | at least 1 boy) = 1/3
    Reason:
    "at least 1 boy" has 3 elements:
    BB BG GB
    of those, 1 are 2 boys:
    BB

    P(2 boys | at least 1 boy born any day) = 1/3
    Reason:
    "at least 1 boy born any day" has 147 elements:
    BSBS BSBM BSBT BSBW BSBt BSBF BSBs BSGS BSGM BSGT BSGW BSGt BSGF BSGs BMBS BMBM BMBT
    BMBW BMBt BMBF BMBs BMGS BMGM BMGT BMGW BMGt BMGF BMGs BTBS BTBM BTBT BTBW BTBt BTBF
    BTBs BTGS BTGM BTGT BTGW BTGt BTGF BTGs BWBS BWBM BWBT BWBW BWBt BWBF BWBs BWGS BWGM
    BWGT BWGW BWGt BWGF BWGs BtBS BtBM BtBT BtBW BtBt BtBF BtBs BtGS BtGM BtGT BtGW BtGt
    BtGF BtGs BFBS BFBM BFBT BFBW BFBt BFBF BFBs BFGS BFGM BFGT BFGW BFGt BFGF BFGs BsBS
    BsBM BsBT BsBW BsBt BsBF BsBs BsGS BsGM BsGT BsGW BsGt BsGF BsGs GSBS GSBM GSBT GSBW
    GSBt GSBF GSBs GMBS GMBM GMBT GMBW GMBt GMBF GMBs GTBS GTBM GTBT GTBW GTBt GTBF GTBs
    GWBS GWBM GWBT GWBW GWBt GWBF GWBs GtBS GtBM GtBT GtBW GtBt GtBF GtBs GFBS GFBM GFBT
    GFBW GFBt GFBF GFBs GsBS GsBM GsBT GsBW GsBt GsBF GsBs
    of those, 49 are 2 boys:
    BSBS BSBM BSBT BSBW BSBt BSBF BSBs BMBS BMBM BMBT BMBW BMBt BMBF BMBs BTBS BTBM BTBT
    BTBW BTBt BTBF BTBs BWBS BWBM BWBT BWBW BWBt BWBF BWBs BtBS BtBM BtBT BtBW BtBt BtBF
    BtBs BFBS BFBM BFBT BFBW BFBt BFBF BFBs BsBS BsBM BsBT BsBW BsBt BsBF BsBs

    P(2 boys | at least 1 boy born on Tuesday) = 13/27
    Reason:
    "at least 1 boy born on Tuesday" has 27 elements:
    BSBT BMBT BTBS BTBM BTBT BTBW BTBt BTBF BTBs BTGS BTGM BTGT BTGW BTGt BTGF BTGs BWBT
    BtBT BFBT BsBT GSBT GMBT GTBT GWBT GtBT GFBT GsBT
    of those, 13 are 2 boys:
    BSBT BMBT BTBS BTBM BTBT BTBW BTBt BTBF BTBs BWBT BtBT BFBT BsBT

    P(2 boys | at least 1 boy born in December) = 23/47
    Reason:
    "at least 1 boy born in December" has 47 elements:
    BJBD BFBD BMBD BABD BmBD BjBD BLBD BaBD BSBD BOBD BNBD BDBJ BDBF BDBM BDBA BDBm BDBj
    BDBL BDBa BDBS BDBO BDBN BDBD BDGJ BDGF BDGM BDGA BDGm BDGj BDGL BDGa BDGS BDGO BDGN
    BDGD GJBD GFBD GMBD GABD GmBD GjBD GLBD GaBD GSBD GOBD GNBD GDBD
    of those, 23 are 2 boys:
    BJBD BFBD BMBD BABD BmBD BjBD BLBD BaBD BSBD BOBD BNBD BDBJ BDBF BDBM BDBA BDBm BDBj
    BDBL BDBa BDBS BDBO BDBN BDBD
    '''