How To Become A Hog Champion

I know that there were a few people curious about my Hog strategy so I wanted to do a quick writeup explaining how my strategy worked (I am cs61a-axu, by the way. http://inst.eecs.berkeley.edu/~cs61a-axu). I haven't really written many technical blog posts (really no blog posts at all) and I threw this one together pretty quickly (with homework and midterms coming up, I don't have time to do the careful editing I would have loved to do) so give me some grace if it isn't perfect :). If I keep it up, maybe one day I'll make it into the top 10 on Hacker News!

An aside to non-CS61A readers: Hog is a modified version of the dice game Pig. The original rules for Hog can be found in the first couple paragraphs of this document. These rules were modified slightly for the Hog Contest. The modifications and a short explanation of what the Hog Contest is can be found here.

So the first thing I did was make sure I had functions to represent the effect of each of the rules of Hog: Hog Wild, Free Bacon, and Swine Swap. You probably already wrote something similar when working on your project and Professor DeNero asked me not to include solutions to the base project (in order to limit the number of answers floating around the internet so that the project can be reused in the future) so I'll just include the function headers with docstrings explaining exactly what they do:

def hog_wild(score, opponent_score):
    """ Returns true if the hog wild rule applies (sum of scores is a multiple
    of seven) and the dice need to be swapped.
    >>> hog_wild(7,0)
    True
    >>> hog_wild(29, 70)
    False
    >>> hog_wild(0, 0)
    True
    >>> hog_wild(62, 1)
    True
    """
    return #...

def free_bacon_score(opponent_score):
    """ Return the points scored from the free bacon rule.

    >>> free_bacon_score(19)
    10
    >>> free_bacon_score(2)
    3
    >>> free_bacon_score(52)
    6
    """
    return #...

def should_apply_swap(score, opponent_score):
    """ Returns True if swine swap should be applied (i.e. one of the scores is
    double the other).

    >>> should_apply_swap(10, 20)
    True
    >>> should_apply_swap(11, 20)
    False
    >>> should_apply_swap(10, 10)
    False
    """
    return #...

My initial strategy solved only the original game because the game with the modified rules is unsolvable. I'll explain how I dealt with the modified rules at the end. The first component of my strategy function was best_num_dice_to_roll(score, opponent_score) because, well, my goal was to compute the optimal number of dice rolls to lead me toward a win, right? Now I needed to think about how I could implement this function. I started off by assuming that I had another function, probability_of_winning_by_rolling_n(score, opponent_score, n), which returned the probability that I would win the game if my score was score, my opponent's score opponent_score, and I choose to roll n dice. (Hurray for abstraction!). Now implementing best_num_dice_to_roll(score, opponent_score) was easy. I just wrote a loop which goes through each possible number of dice to role and returns how many dice gives the highest probability of me winning:

from decimal import *
#Tell the Decimal class to use 100 digits of precision
getcontext().prec = 100

MAX_DICE = 10

def best_num_dice_to_roll(score, opponent_score):
    """ Returns the optimal number of dice to roll given score and opponent_score
    assuming it is the beginning of your turn.
    """
    score = Decimal(score)
    opponent_score = Decimal(opponent_score)
    best_probability, best_n = Decimal(0), 1
    #Iterate through each number of dice that can be rolled
    for n in range(0, MAX_DICE + 1):
        probability = probability_of_winning_by_rolling_n(score, opponent_score, n)
        if probability > best_probability:
            best_probability, best_n = probability, n
    return best_n

Note: throughout my strategy I convert all numbers to Decimals, a Class which allows an arbitrary number of digits of precision. I'm sure I could have done this in a more elegant way and I'm not sure if doing so was even necessary but I added this feature in at the last minute just to make sure my strategy wouldn't be hurt by rounding errors.

Alright now that I had that function out of the way it was time to implement probability_of_winning_by_rolling_n(score, opponent_score, n). For this function I needed to make a couple more assumptions. First, I assumed I had a function probability_of_scoring(k, n, s) which told me the exact probability of scoring k points with n, s sided dice. Next, I assumed that there was a function probability_of_winning_with_turn_end_scores(score, opponent_score) that returns the probability that I would win if I ended my turn with score and my opponent had opponent_score. With these assumptions probability_of_winning_by_rolling_n(score, opponent_score, n) was now easy to implement. All I had to do was go through each possible outcome of my dice roll and sum up the product of the probability of winning with a particular outcome and the probability of that outcome occurring:

def probability_of_winning_by_rolling_n(score, opponent_score, n):
    """ Returns probability that you will win if you roll n dice assuming it is
    your turn now.
    """
    sides = 6
    #Hog wild
    if hog_wild(score, opponent_score):
        sides = 4
    probability_of_winning = 0
    if n == 0:
        #Free Bacon
        turn_score = free_bacon_score(opponent_score)
        probability_of_winning = probability_of_winning_with_turn_end_scores(
                score + turn_score, opponent_score)
    else:
        #Iterate over each possible outcome for rolling n dice
        for possible_score in range(1, (sides * n) + 1):
            probability_of_winning += probability_of_scoring(possible_score, n,
                    sides) * probability_of_winning_with_turn_end_scores(
                    score + possible_score, opponent_score)
    return probability_of_winning

Ok so now there were two more functions I had to take care of implementing. probability_of_winning_by_rolling_n(score, opponent_score, n) was easy. It's basically a slight modification of DeNero's function ways_to_roll_at_least(k, n) which is explained here: http://www.youtube.com/watch?v=xqRosBPbUXI.

def number_of_ways_to_score(k, n, s):
    """ Returns the number of ways that k can be scored by rolling n
    s sided dice without pigging out.
    
    k: goal score
    n: number of dice to use
    s: number of sides on dice
    
    >>> number_of_ways_to_score(4, 1, 6)
    1
    >>> number_of_ways_to_score(12, 2, 6)
    1
    >>> number_of_ways_to_score(11, 2, 6)
    2
    >>> number_of_ways_to_score(7, 3, 6)
    3
    >>> number_of_ways_to_score(8, 3, 4)
    6
    """
    if k < 0:
        return 0
    if k == 0 and n == 0:
        return 1
    if n == 0:
        return 0
    total = 0
    for i in range(2, s + 1):
        total += number_of_ways_to_score(k - i, n - 1, s)
    return total

def probability_of_scoring(k, n, s):
    """ Returns the chance that at least k will be scored by rolling n s sided
    dice without pigging out.
    
    k: goal score
    n: number of dice to use
    s: number of sides on dice
    
    >>> almost_equal = lambda x, y: abs(x - y) < 1e-10
    >>> almost_equal(probability_of_scoring(4, 1, 6), 1/6)
    True
    >>> almost_equal(probability_of_scoring(7, 3, 6), 3/216)
    True
    >>> almost_equal(probability_of_scoring(1, 2, 6), 11/36)
    True
    >>> almost_equal(probability_of_scoring(2, 3, 6), 0)
    True
    >>> almost_equal(probability_of_scoring(11, 10, 6), 0)
    True
    """
    if k == 1:
        return Decimal(1) - Decimal((pow(s - 1, n) / pow(s, n)))
    return Decimal(number_of_ways_to_score(k, n, s)) / Decimal(pow(s, n))

The other function, probability_of_winning_with_turn_end_scores(score, opponent_score), was slightly tricker. I implemented using recursion. There were two base cases: if my score was greater than the goal, I definitely won so my chance of winning was 100%. Conversely, If my opponent's was greater than the goal, I definitely lost so my chance of winning was 0%. For the recursive call I merely assumed my opponent was also playing optimally then calculated their chance of winning. 100% - probability_of_opponent_winning gives the probability of me winning the game.

def probability_of_winning_with_turn_end_scores(score, opponent_score):
    """ Returns the chance that you will win the game if the scores are those
    passed in when your turn is complete.
    """
    $Swine swap
    if should_apply_swap(score, opponent_score):
        score, opponent_score = opponent_score, score
    if score >= GOAL_SCORE:
        return 1
    elif opponent_score >= GOAL_SCORE:
        return 0
    opponent_num_rolls = best_num_dice_to_roll(opponent_score, score)
    probability_of_opponent_winning = probability_of_winning_by_rolling_n(
            opponent_score, score, opponent_num_rolls)
    return 1 - probability_of_opponent_winning

Great. So I had come up with an optimal solution to the base game. The last three things I had still had to deal with were runtime (if you ran the strategy as is it would take a very very long time to run since it uses tree recursion of right now it computes an answer to the same problem over and over again), making sure I didn't exceed the maximum recursion depth, and the new Ham Hijinks rule. Runtime was easy. I just wrote a basic memoize function which supported functions with arbitrary numbers of arguments:

def memoized(f):
    data = {}
    def lookup(*args):
        key = (f, args)
        if not key in data:
            data[key] = f(*args)
        return data[key]
    return lookup

All I had to do after that was decorate each recursive function with @memoized. Dealing with maximum recursion depth was also easy. I just imported the sys module then added the following lines in the beginning of the probability_of_winning_by_rolling_n(score, opponent_score, n) function to increase the max recursion depth to something I knew would always be safe:

    if sys.getrecursionlimit() < MAX_RECURSION_DPETH:
        sys.setrecursionlimit(MAX_RECURSION_DPETH)

This left only one problem: how to deal with Ham Hijinks. I spent a good deal of time thinking about the Ham Hijinks problem and working on solutions until I came to my final conclusion: given the contraint that strategies had to be a pure function of score and opponent_core, solving Ham Hijinks was impossible. I decided that rather than hurt myself by incorrectly guessing how many times the dice had been swapped, it would be beneficial in the long run to ignore the Ham Hijinks rule except for one condition: when my opponent's score was exactly one. If my opponent had a score of exactly one, I knew that there was a good chance that they had used their first turn to swap the dice. If so, I would swap them back and hope for the best (i.e. that six sided dice would be used the rest of the game). And I guess my assumption worked (because my strategy was undefeated). Implementing this change  required adding just two lines of code near the beginning of my best_num_dice_to_roll(score, opponent_score) function:

if opponent_score == 1:
        """There is a good chance the opponent just hijinksed. Swap and pray!"""
        return -1

And that's it. That's my whole strategy. If you have any questions feel free to comment. I'll include the completed code code below for reference. Also, I would like to say great job to everyone else who competed in the contest. Like I pointed out above, the fact that I won was, at least impart, based on me getting lucky by making the correct prediction of your strategy's weakness.

def final_strategy(score, opponent_score):
    return best_num_dice_to_roll(score, opponent_score)
      
import sys
from decimal import *
#Tell the Decimal class to use 100 digits of precision
getcontext().prec = 100

MAX_DICE = 10
MAX_RECURSION_DPETH = 2000
GOAL_SCORE = 100 # The goal of Hog is to score 100 points.

def memoized(f):
    data = {}
    def lookup(*args):
        key = (f, args)
        if not key in data:
            data[key] = f(*args)
        return data[key]
    return lookup

@memoized
def best_num_dice_to_roll(score, opponent_score):
    """ Returns the optimal number of dice to roll given score and opponent_score
    assuming it is the beginning of your turn.
    """
    if sys.getrecursionlimit() < MAX_RECURSION_DPETH:
        sys.setrecursionlimit(MAX_RECURSION_DPETH)
    if opponent_score == 1:
        #There is a good chance the opponent just hijinksed. Swap and pray!
        return -1
    score = Decimal(score)
    opponent_score = Decimal(opponent_score)
    best_probability, best_n = Decimal(0), 1
    #Iterate through each number of dice that can be rolled
    for n in range(0, MAX_DICE + 1):
        probability = probability_of_winning_by_rolling_n(score, opponent_score, n)
        if probability > best_probability:
            best_probability, best_n = probability, n
    return best_n

@memoized
def probability_of_winning_by_rolling_n(score, opponent_score, n):
    """ Returns probability that you will win if you roll n dice assuming it is
    your turn now.
    """
    sides = 6
    #Hog wild
    if hog_wild(score, opponent_score):
        sides = 4
    probability_of_winning = 0
    if n == 0:
        #Free Bacon
        turn_score = free_bacon_score(opponent_score)
        probability_of_winning = probability_of_winning_with_turn_end_scores(
                score + turn_score, opponent_score)
    else:
        #Iterate over each possible outcome for rolling n dice
        for possible_score in range(1, (sides * n) + 1):
            probability_of_winning += probability_of_scoring(possible_score, n,
                    sides) * probability_of_winning_with_turn_end_scores(
                    score + possible_score, opponent_score)
    return probability_of_winning
   
@memoized 
def probability_of_winning_with_turn_end_scores(score, opponent_score):
    """ Returns the chance that you will win the game if the scores are those
    passed in when your turn is complete.
    """
    #Swine swap
    if should_apply_swap(score, opponent_score):
        score, opponent_score = opponent_score, score
    if score >= GOAL_SCORE:
        return 1
    elif opponent_score >= GOAL_SCORE:
        return 0
    opponent_num_rolls = best_num_dice_to_roll(opponent_score, score)
    probability_of_opponent_winning = probability_of_winning_by_rolling_n(
            opponent_score, score, opponent_num_rolls)
    return 1 - probability_of_opponent_winning
        
@memoized
def number_of_ways_to_score(k, n, s):
    """ Returns the number of ways that k can be scored by rolling n
    s sided dice without pigging out.
    
    k: goal score
    n: number of dice to use
    s: number of sides on dice
    
    >>> number_of_ways_to_score(4, 1, 6)
    1
    >>> number_of_ways_to_score(12, 2, 6)
    1
    >>> number_of_ways_to_score(11, 2, 6)
    2
    >>> number_of_ways_to_score(7, 3, 6)
    3
    >>> number_of_ways_to_score(8, 3, 4)
    6
    """
    if k < 0:
        return 0
    if k == 0 and n == 0:
        return 1
    if n == 0:
        return 0
    total = 0
    for i in range(2, s + 1):
        total += number_of_ways_to_score(k - i, n - 1, s)
    return total

@memoized
def probability_of_scoring(k, n, s):
    """ Returns the chance that at least k will be scored by rolling n s sided
    dice without pigging out.
    
    k: goal score
    n: number of dice to use
    s: number of sides on dice
    
    >>> almost_equal = lambda x, y: abs(x - y) < 1e-10
    >>> almost_equal(probability_of_scoring(4, 1, 6), 1/6)
    True
    >>> almost_equal(probability_of_scoring(7, 3, 6), 3/216)
    True
    >>> almost_equal(probability_of_scoring(1, 2, 6), 11/36)
    True
    >>> almost_equal(probability_of_scoring(2, 3, 6), 0)
    True
    >>> almost_equal(probability_of_scoring(11, 10, 6), 0)
    True
    """
    if k == 1:
        return Decimal(1) - Decimal((pow(s - 1, n) / pow(s, n)))
    return Decimal(number_of_ways_to_score(k, n, s)) / Decimal(pow(s, n))