Category: Coding

So one mini-project I’ve been working on recently is a project for berkeley’s cs61a class. The goal of this project is to implement the game of hog, which is described below:

In Hog, two players alternate turns trying to reach 100 points first. On each turn, the current player chooses some number of dice to roll, up to 10. Her turn score is the sum of the dice outcomes, unless any of the dice come up a 1, in which case the score for her turn is only 1 point (the Pig out rule).

To spice up the game, we will play with some special rules:

Free bacon. If a player chooses to roll zero dice, she scores one more than the largest digit in her opponent’s score. For example, if Player 1 has 42 points, Player 0 gains 1 + max(4, 2) = 5 points by rolling zero dice. If Player 1 has 48 points, Player 0 gains 1 + max(4, 8) = 9 points.
Hog wild. If the sum of both players’ total scores is a multiple of seven (e.g., 14, 21, 35), then the current player rolls four-sided dice instead of the usual six-sided dice.
Swine swap. If at the end of a turn one of the player’s total score is exactly double the other’s, then the players swap total scores. Example 1: Player 0 has 20 points and Player 1 has 5; it is Player 1’s turn. She scores 5 more, bringing her total to 10. The players swap scores: Player 0 now has 10 points and Player 1 has 20. It is now Player 0’s turn. Example 2: Player 0 has 90 points and Player 1 has 50; it is Player 0’s turn. She scores 10 more, bringing her total to 100. The players swap scores, and Player 1 wins the game 100 to 50.

Most of the project is just implementing the guts of the game. The berkeley TAs were nice enough to implement the rest of the plumbing, including the test apparatus and gui. The last question, however, provided the most interesting question, and was definitely the most fun to work on and think about.

Essentially, the last question asks you to implement a strategy to try to beat another strategy that rolls 5 every time. To get full credit for the problem, your strategy needs to beat the always_roll(5) strategy 59% of the time or better. I’m at 60.5% currently, and still looking for ways to improve.

Essentially I did four things:

I then put these into a python dictionary keyed to the total value of the roll (based on hog rules), and figured out the number of combinations that would pertain to the value. I then converted these into percentages so I could reference them later on. See my algorithm below, completely unoptimized! I couldn’t even run all combinations for rolling 10 dice because my computer started to overheat and sizzle. In any case, I just needed a quick and dirty answer:

# this function tries to roll a ____, based on the best way to do it
def compute_probabilities(num_rolls, dice=six_sided):
    #compute possibilities
    k = 1
    global possibilities
    def f(dice, k):
        if (dice == six_sided):
            return pow(6,k)
        return pow(4,k)

    while (k <= num_rolls):
        print("Rolling {} dice possibilities.".format(k))
        possibilities = list()
        get_possibilities("", k, dice)
        convert_possibilities_to_matrix(possibilities, f(dice, k))
        k += 1
    
possibilities = list()
def get_possibilities(total, num_rolls, dice):
    i = 1
    global possibilities
    if (num_rolls == 0):
        return total

    if (dice == six_sided):
        sides = 6
    else:
        sides = 4
    while (i <= sides):
        mystr = get_possibilities(str(total) + str(i), num_rolls-1, dice)
        if (not mystr == None):
            possibilities.append(mystr)
        i += 1

I basically stored the expected values of rolling 1 through 10 in a list. Whichever index contained the highest expected value represented the move I wanted to take. Under this framework, I was simply able to modify the values in the list whenever I came across a more optimal solution.

        #adjust based on swine swap 
        def adjust_swine_swap(score, opponent_score, eplist):
            if (score > opponent_score or opponent_score % 2 == 1):    #never want to swine swap if our score is bigger
                return eplist   

            ineed = (opponent_score / 2) - score #what i need to trigger swine swap
            if (ineed <= 0): #if i would need a neg, not possible
                return eplist

            ineed = int(ineed)
            difference = opponent_score - (score + ineed) #the benefit

            if ineed == getBaconScore(opponent_score):  #roll zero, a sure thing
                eplist[0] = max(eplist[0], difference) 

            if ineed == 1:  #roll 1
                eplist[10] = max(eplist[10], difference * percentages.get(ineed)) 

            if ((ineed >= 2 and ineed <= 6 and dice == six_sided) or 
                (ineed >= 2 and ineed <= 4 and dice == four_sided)): 
                eplist[1] = max(eplist[1], difference * percentages.get(ineed))

            return eplist

adjust_swine_swap modifies the expected values of rolling dice based on whether there is a beneficial swine_swap. I started out with the known case of rolling zero dice, which results in a guaranteed swine_swap. I then recognized that this process could be repeated for when swine_swap could be triggered with a roll resulting in a value of 1. 1 is pretty common in “hog” since the player is able to roll up to 10 dice. Hence, not rolling a 1 (with a six-sided dice) would simply be 1 – (5/6)^10. Likewise, for a four-sided dice, it would be 1 – (3/4)^10. I didn’t need to prove this, but if you look at the results generated from step 1, it’s cool that it’s verified. I also noticed from the percentiles that the best chance of rolling a 2 through 6 or a 2 through 4 was with one dice. Thus, I didn’t really need to calculate the percentiles for all possible combinations of 1 through 10 dice, since they just get worse with more than one die.

        #adjust based on trying to force a four dice
        def adjust_try_four(score, opponent_score, eplist):
            score_with_zero = score + getBaconScore(opponent_score)
            score_with_one = score + 1

            #if we can cause opponent to have to roll a four_sided dice, calc the benefit
            if ((score_with_zero + opponent_score) % 7 == 0):
                eplist[0] = max(eplist[0], eplist[0] + 4.25)

            if ((score_with_one + opponent_score) % 7 == 0):
                eplist[10] = max(eplist[10], eplist[10] + (4.25 * percentages.get(1)))

            return eplist

adjust_try_four tries to do a similar thing by adjusting the values based on whether the current player can force the other player to use a four-sided dice (i.e., if the player’s score and the opponent’s score % 7 == 0). This doesn’t always result in a more optimal move than swine_swap, but again, the function only updates with the max expected value. I had to approximate the benefit of forcing the other player to roll with four-sided dice based on the findings from earlier. Because the other player always rolls a 5, the expected value of rolling a 6-sided dice versus a 4-sided dice is approximately 4.25 higher.

        #adjust based on almost guaranteed victory
        def take_guaranteed_victory(score, opponent_score, eplist):
            score_with_zero = score + (getBaconScore(opponent_score) * 2)
            #try more conservative approach

            if (score_with_zero >= GOAL_SCORE): #guaranteed victory by rolling a 0
                if (not causes_swine_swap(score_with_zero, opponent_score)):
                    eplist[0] = 100 #set to arbitrary high # so always rolls this
            return eplist

Lastly, take_guaranteed_victory will roll zero dice if there is an almost guaranteed victory (i.e. after rolling a zero, the player’s score is >= 100). I at first applied this function only in scenarios where there was an actual guaranteed victory. However, with some empirical testing, I was able to get a slightly better result after multiplying the roll zero dice score by two. I guess being conservative pays off near the end of a hog game.

Anyway, I’m still looking for ways to improve the strategy. I really love this about programming. It’s the kind of problem that challenges oneself. There are bad and good answers, but the best answer is either unknown or elusive.

So as part of my grand plan to get back into coding, I’ve been helping out a friend with some assignments for school.  I thought at first that it would be easy, you know, basic algorithm type of work, object-oriented design, data structures, etc.  Much to my surprise, the homeworks have been really challenging.  Maybe my software foundation could be stronger, but it turns out that this intro-level programming class is teaching functional programming.  No wonder my friend was having so much trouble.  It would be frustratingly difficult to be taught this introduction to programming.  Maybe it speaks to my age, but object-oriented design and functions returning values just made more intuitive sense, or at least came to me more quickly.

In summary, I’ve had to keep up with the readings and homework just to stay afloat.  I didn’t think I was that out of practice … In any case, this class is studying Python.  An interesting first choice.  Once I figured out why my friend was having so much trouble, I started to delve into the language myself.  And serendipitously, I’ve begun to understand why functional programming and the greater potential for abstraction is so powerful.  Take a look at this for instance:

def accumulate(combiner, start, n, term):
    """Return the result of combining the first n terms in a sequence."""
    """ Combiner = a function
        term = a function
        start = base value to use to start the accumulation
        n = n terms to accumulate
    """
    k, result = 1, start
    while (k <= n):
        result = combiner(result, term(k))
        k = next(k)
    return result

def summation_using_accumulate(n, term):
    """An implementation of summation using accumulate."""
    return accumulate(add, 0, n, term)

def product_using_accumulate(n, term):
    """An implementation of product using accumulate."""
    return accumulate(mul, 1, n, term)

This is pretty sick. You can define a universe of summation functions or product summation functions just by passing in type of function you want to execute. For example:

def identity(x):
    """
    >>> summation_using_accumulate(5, identity)
    15

    >>> product_using_accumulate(4, identity)
    24
    """
    return x    

By making either of these calls, you can add add the first n integers together, or multiply the first n integers together (i.e. factorial) and return the result. Really cool. I didn’t expect when I agreed to help out my friend that I would actually learn something new. I thought that at best, I would get a rough rehashing of my software fundamentals which would just help me remember some of the things I had forgotten. It turns out that I’m learning a new programming paradigm altogether. /mind blown.