michaelsnowden / hog Goto Github PK

Hog

How the game works

1. score, and opponent_score are given
2. if the sum of score and opponent_score is divisible by 7, the current player rolls a four-sided dice this turn (hog wild)
3. strategy determines the number of rolls for the player (strategy(score, opponent_score) -> n)
4. given the number of rolls, n, the dice are rolled
5. if n is 0, the player's turn score is one more than the largest digit in the opponent's total score (free bacon)
6. if n > 0 and the player rolled a 1, they score 0 (pig out)
7. if n > 0 and the player didn't roll any 1s, their turn score is the sum of their rolls
8. if the player's score for this turn is a prime number, it becomes the next prime number (hogtimus prime)
9. score is increased by turn score
10. if the last two digits of each player's score are the reverse of each other, the players swap total scores (swine swap)
11. if someone has won, end the game
12. if no one has won yet, repeat step 1 for the opponent's strategy with score and opponent_score reversed

How the algorithm works

Because there are optimal substructures, we can use dynamic programming.

This is the first example of a (trivial) optimal substructure.

score, opponent_score = 90, 99 => n = 0

I get a guaranteed win if I choose to roll 0 because then I score 10, as part of free bacon.

In general, this is true for any (score, opponent_score) where 100 - score <= free_bacon(opponent_score)

Now we know the best move and the probability of winning for a number of cases. Next, we examine game states (score, opponent_score) that aren't in this set of known game states. For example, let's examine (89, 99)

For any given number of rolls n, any given sum p, any given number of sides s, we want to know what the odds are of getting p.

    def f(p, n, s):
        1 / s ** n * sum([(-1) ** k * ncr(n, k) * ncr(p - s * k - 1, n - 1) for k in range(0, int((p - n) / s) + 1)])

Unfortunately, this does not account for a roll of a 1-sided dice occurring, so we have to augment the formula slightly.

def g(p, n, s):
        return ((s - 1) / s) ** n * f(p - n, n, s - 1)

Now that we have a formula for finding the chance of

from hog import get_probability, prob_rolling_1

score, opponent_score = 89, 99
if (score + opponent_score) % 7 == 0:
    s = 4
else:
    s = 6
print("%-6s %-6s %-6s" % ("sum", "#rolls", "probability"))


def row(p, n, g):
    print("%-6s %-6s %-6.3f" % (p, n, g))


if __name__ == '__main__':
    for n in range(1, 11):
        p = 0
        row(0, n, prob_rolling_1(n, s))
        for p in range(n * 2, s * n + 1):
            row(p, n, get_probability(p, n, s, ignore_file=True))