Yahtzee Strategy Simulator [codeskulptor]

"""
Planner for Yahtzee
Simplifications:  only allow discard and roll, only score against upper level
"""
#http://www.codeskulptor.org/#user43_hIq8DOUzOePl1QE_4.py

# Used to increase the timeout, if necessary
import codeskulptor
codeskulptor.set_timeout(20)

def gen_all_sequences(outcomes, length):
    """
    Iterative function that enumerates the set of all sequences of
    outcomes of given length.
    """

    answer_set = set([()])
    for dummy_idx in range(length):
        temp_set = set()
        for partial_sequence in answer_set:
            for item in outcomes:
                new_sequence = list(partial_sequence)
                new_sequence.append(item)
                temp_set.add(tuple(new_sequence))
        answer_set = temp_set
    return answer_set


def score(hand):
    """
    Compute the maximal score for a Yahtzee hand according to the
    upper section of the Yahtzee score card.

    hand: full yahtzee hand

    Returns an integer score
    """
    scores = []
    for die_num in range(max(hand)+1)[1:]:
        num_dice = hand.count(die_num)
        scores.append(num_dice*die_num)
    return max(scores)


def expected_value(held_dice, num_die_sides, num_free_dice):
    """
    Compute the expected value based on held_dice given that there
    are num_free_dice to be rolled, each with num_die_sides.

    held_dice: dice that you will hold
    num_die_sides: number of sides on each die
    num_free_dice: number of dice to be rolled

    Returns a floating point expected value
    """
#    print "Holding dice ", held_dice
    poss_rolls = gen_all_sequences(range(num_die_sides+1)[1:], num_free_dice)
#    print len(poss_rolls), " possible outcomes for ", num_free_dice, "rolls"
    #poss_scores will store the scores of all possible hands (held_dice + each possible roll)
    poss_scores = []
    for roll in poss_rolls:
        held = list(held_dice)
#        print "Evaluating held ", held, " + outcome ", roll
        for rol in roll:
            held.append(rol)
        my_score = score(held)
#        print "Now holding ", held, " with score " , my_score
        poss_scores.append(my_score)
#        print "Possible scores is now", poss_scores
#        print

    return float(sum(poss_scores))/len(poss_rolls)


def gen_all_holds(hand):
    """
    Generate all possible choices of dice from hand to hold.

    hand: full yahtzee hand

    Returns a set of tuples, where each tuple is dice to hold
    """
    all_holds = set([()])
    hand_filters = gen_all_sequences([0,1], len(hand))
    for hand_filter in hand_filters:
        hold = []
        for dummy_i in range(len(hand_filter)):
            if hand_filter[dummy_i] == 1:
                hold.append(hand[dummy_i])
        #print hold
        all_holds.add(tuple(hold))

    return all_holds



def strategy(hand, num_die_sides):
    """
    Compute the hold that maximizes the expected value when the
    discarded dice are rolled.

    hand: full yahtzee hand
    num_die_sides: number of sides on each die

    Returns a tuple where the first element is the expected score and
    the second element is a tuple of the dice to hold
    """
    all_holds = list(gen_all_holds(hand))
    values = []
    for hold in all_holds:
        values.append(expected_value(hold, num_die_sides, len(hand)-len(hold)))
    best_hold = tuple(all_holds[values.index(max(values))])
    my_result = [expected_value(best_hold, num_die_sides, len(hand)-len(best_hold)), best_hold]
    print my_result

    return tuple(my_result)


def run_example():
    """
    Compute the dice to hold and expected score for an example hand
    """
    num_die_sides = 6
    hand = (1, 1, 1, 5, 6)
    hand_score, hold = strategy(hand, num_die_sides)
    print "Best strategy for hand", hand, "is to hold", hold, "with expected score", hand_score


#run_example()

#print score([1,1,3,3,3])
#print expected_value([], 6, 3)

#print gen_all_holds([1,2,2])

#print strategy([1,6],6)

#import poc_holds_testsuite
#poc_holds_testsuite.run_suite(gen_all_holds)