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.
Code and Codes 