Hog Wild!

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:

  • 1. First, I wrote a recursive algorithm to figure out all the possibilities of rolls and their respective point values

  • 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
    

  • 2. Second, armed with this knowledge and the expected value of rolling 1 through 10 dice (an earlier question for the project), I was able to establish a framework for representing the best choice.

  • 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.

  • 3. Third, I wrote several functions to adjust the values based on the context of the game. I’ve listed them below.
  •         #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.

    Advertisements

    Functioning Properly

    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.