CS61A Project 1
easterling
  2023-11-15 21:55:14 2023-11-15 21:55   2024-03-04 21:12:42  

Project 1: The Game of Hog hog.zip

image

I know! I’ll use my
Higher-order functions to
Order higher rolls.

Introduction

Important submission note: For full credit:

  • Submit with Phase 1 complete by Tuesday, Sept 6, worth 1 pt.
  • Submit the complete project by Friday, Sept 9.

Try to attempt the problems in order, as some later problems will depend on earlier problems in their implementation and therefore also when running ok tests.

You may complete the project with a partner.

You can get 1 bonus point by submitting the entire project by Thursday, Sept 8 You can receive extensions on the project deadline and checkpoint deadline, but not on the early deadline, unless you’re a DSP student with an accommodation for assignment extensions.

In this project, you will develop a simulator and multiple strategies for the dice game Hog. You will need to use control statements and higher-order functions together, as described in Sections 1.2 through 1.6 of Composing Programs, the online textbook.

When students in the past have tried to implement the functions without thoroughly reading the problem description, they’ve often run into issues. 😱 Read each description thoroughly before starting to code.

Rules

In Hog, two players alternate turns trying to be the first to end a turn with at least GOAL total points, where GOAL defaults to 100. On each turn, the current player chooses some number of dice to roll, up to 10. That player’s score for the turn is the sum of the dice outcomes. However, a player who rolls too many dice risks:

  • Sow Sad. If any of the dice outcomes is a 1, the current player’s score for the turn is 1.

In a normal game of Hog, those are all the rules. To spice up the game, we’ll include some special rules:

  • Pig Tail. A player who chooses to roll zero dice scores 2 * abs(tens - ones) + 1 points; where tens, ones are the tens and ones digits of the opponent’s score. The ones digit refers to the rightmost digit and the tens digit refers to the second-rightmost digit.

  • Square Swine. After a player gains points for their turn, if the resulting score is a perfect square, then increase their score to the next higher perfect square. A perfect square is any integer n where n = d * d for some integer d.

Phase 1: Rules of the Game

In the first phase, you will develop a simulator for the game of Hog.

Problem 1 (2 pt)

Implement the roll_dice function in hog.py. It takes two arguments: a positive integer called num_rolls giving the number of dice to roll and a dice function. It returns the number of points scored by rolling the dice that number of times in a turn: either the sum of the outcomes or 1 (Sow Sad).

  • Sow Sad. If any of the dice outcomes is a 1, the current player’s score for the turn is 1.

Examples

To obtain a single outcome of a dice roll, call dice(). You should call dice() exactly num_rolls times in the body of roll_dice.

Remember to call dice() exactly num_rolls times even if Sow Sad happens in the middle of rolling. By doing so, you will correctly simulate rolling all the dice together (and the user interface will work correctly).

Note: The roll_dice function, and many other functions throughout the project, makes use of default argument values—you can see this in the function heading:

1
def roll_dice(num_rolls, dice=six_sided): ...

The argument dice=six_sided means that when roll_dice is called, the dice argument is optional. If no value for dice is provided, then six_sided is used by default.

For example, calling roll_dice(3, four_sided), or equivalently roll_dice(3, dice=four_sided), simulates rolling 3 four-sided dice, while calling roll_dice(3) simulates rolling 3 six-sided dice.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def roll_dice(num_rolls, dice=six_sided):
    """Simulate rolling the DICE exactly NUM_ROLLS > 0 times. Return the sum of
    the outcomes unless any of the outcomes is 1. In that case, return 1.

    num_rolls:  The number of dice rolls that will be made.
    dice:       A function that simulates a single dice roll outcome.
    """
    # These assert statements ensure that num_rolls is a positive integer.
    assert type(num_rolls) == int, 'num_rolls must be an integer.'
    assert num_rolls > 0, 'Must roll at least once.'
    # BEGIN PROBLEM 1
    count = 0
    one = 0
    for i in range(num_rolls):
        dice_thistime = dice()
        if dice_thistime == 1:
            one = 1
        count = count + dice_thistime
    res = (1 if one == 1 else count)
    return res
    # END PROBLEM 1

Problem 2 (2 pt)

Implement tail_points, which takes the player’s opponent’s current score opponent_score, and returns the number of points scored by Pig Tail when the player rolls 0 dice.

  • Pig Tail. A player who chooses to roll zero dice scores 2 * abs(tens - ones) + 1 points; where tens, ones are the tens and ones digits of the opponent’s score. The ones digit refers to the rightmost digit and the tens digit refers to the second-rightmost digit.

Examples

Don’t assume that scores are below 100. Write your tail_points function so that it works correctly for any non-negative score.

Important: Your implementation should not use str, lists, or contain square brackets [ ]. The test cases will check if those have been used.

1
2
3
4
5
6
7
8
9
10
11
def tail_points(opponent_score):
    """Return the points scored by rolling 0 dice according to Pig Tail.

    opponent_score:   The total score of the other player.

    """
    # BEGIN PROBLEM 2
    ones = opponent_score%10
    tens = opponent_score%100//10
    return 2*abs(tens-ones)+1
    # END PROBLEM 2

You can also test tail_points interactively by running python3 -i hog.py from the terminal and calling tail_points on various inputs.

Problem 3 (2 pt)

Implement the take_turn function, which returns the number of points scored for a turn by rolling the given dice num_rolls times.

Your implementation of take_turn should call both roll_dice and tail_points rather than repeating their implementations.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def take_turn(num_rolls, opponent_score, dice=six_sided):
    """Return the points scored on a turn rolling NUM_ROLLS dice when the
    opponent has OPPONENT_SCORE points.

    num_rolls:       The number of dice rolls that will be made.
    opponent_score:  The total score of the other player.
    dice:            A function that simulates a single dice roll outcome.
    """
    # Leave these assert statements here; they help check for errors.
    assert type(num_rolls) == int, 'num_rolls must be an integer.'
    assert num_rolls >= 0, 'Cannot roll a negative number of dice in take_turn.'
    assert num_rolls <= 10, 'Cannot roll more than 10 dice.'
    # BEGIN PROBLEM 3
    if num_rolls==0:
        return tail_points(opponent_score)
    else:
        return roll_dice(num_rolls,dice)
    # END PROBLEM 3

Problem 4 (1 pt)

Add functions perfect_square and next_perfect_square so that square_update returns a player’s total score after they roll num_rolls. You do not need to edit the body of square_update.

  • Square Swine. After a player gains points for their turn, if the resulting score is a perfect square, then increase their score to the next higher perfect square. A perfect square is any integer n where n = d * d for some integer d.
1
2
3
4
5
6
7
# BEGIN PROBLEM 4
def perfect_square(score):
    return score ** 0.5 % 1 == 0
 
def next_perfect_square(score):
    return int((score ** 0.5 + 1)**2)
# END PROBLEM 4

Problem 5 (5 pt)

Implement the play function, which simulates a full game of Hog. Players take turns rolling dice until one of the players reaches the goal score, and the final scores of both players are returned by the function.

To determine how many dice are rolled each turn, call the current player’s strategy function (Player 0 uses strategy0 and Player 1 uses strategy1). A strategy is a function that, given a player’s score and their opponent’s score, returns the number of dice that the current player will roll in the turn. An example strategy is always_roll_5 which appears above play.

To determine the updated score for a player after they take a turn, call the update function. An update function takes the number of dice to roll, the current player’s score, the opponent’s score, and the dice function used to simulate rolling dice. It returns the updated score of the current player after they take their turn. Two examples of update functions are simple_update andsquare_update.

If a player achieves the goal score by the end of their turn, i.e. after all applicable rules have been applied, the game ends. play will then return the final total scores of both players, with Player 0’s score first and Player 1’s score second.

Some example calls to play are:

  • play(always_roll_5, always_roll_5, simple_update) simulates two players that both always roll 5 dice each turn, playing with just the Sow Sad and Pig Tail rules.
  • play(always_roll_5, always_roll_5, square_update) simulates two players that both always roll 5 dice each turn, playing with the Square Swine rule in addition to the Sow Sad and Pig Tail rules (i.e. all the rules).

Important: For the user interface to work, a strategy function should be called only once per turn. Only call strategy0 when it is Player 0’s turn and only call strategy1 when it is Player 1’s turn.

Hints:

  • If who is the current player, the next player is 1 - who.
  • To call play(always_roll_5, always_roll_5, square_update) and print out what happens each turn, run python3 hog_ui.py from the terminal.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
def play(strategy0, strategy1, update,
         score0=0, score1=0, dice=six_sided, goal=GOAL):
    """Simulate a game and return the final scores of both players, with
    Player 0's score first and Player 1's score second.

    E.g., play(always_roll_5, always_roll_5, square_update) simulates a game in
    which both players always choose to roll 5 dice on every turn and the Square
    Swine rule is in effect.

    A strategy function, such as always_roll_5, takes the current player's
    score and their opponent's score and returns the number of dice the current
    player chooses to roll.

    An update function, such as square_update or simple_update, takes the number
    of dice to roll, the current player's score, the opponent's score, and the
    dice function used to simulate rolling dice. It returns the updated score
    of the current player after they take their turn.

    strategy0: The strategy for player0.
    strategy1: The strategy for player1.
    update:    The update function (used for both players).
    score0:    Starting score for Player 0
    score1:    Starting score for Player 1
    dice:      A function of zero arguments that simulates a dice roll.
    goal:      The game ends and someone wins when this score is reached.
    """
    who = 0  # Who is about to take a turn, 0 (first) or 1 (second)
    # BEGIN PROBLEM 5
    while score0 < goal and score1 < goal:
        if who == 0:
            score0 = update(strategy0(score0, score1), score0, score1, dice)
        else:
            score1 = update(strategy1(score1, score0), score1, score0, dice)
        who = 1 - who
    # END PROBLEM 5
    return score0, score1

Phase 2: Strategies

In this phase, you will experiment with ways to improve upon the basic strategy of always rolling five dice. A strategy is a function that takes two arguments: the current player’s score and their opponent’s score. It returns the number of dice the player will roll, which can be from 0 to 10 (inclusive).

Problem 6 (2 pt)

Implement always_roll, a higher-order function that takes a number of dice n and returns a strategy that always rolls n dice. Thus, always_roll(5) would be equivalent to always_roll_5.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def always_roll(n):
    """Return a player strategy that always rolls N dice.

    A player strategy is a function that takes two total scores as arguments
    (the current player's score, and the opponent's score), and returns a
    number of dice that the current player will roll this turn.

    >>> strategy = always_roll(3)
    >>> strategy(0, 0)
    3
    >>> strategy(99, 99)
    3
    """
    assert n >= 0 and n <= 10
    # BEGIN PROBLEM 6
    return lambda score, opponent_score : n
    # END PROBLEM 6

Problem 7 (2 pt)

A strategy only has a fixed number of possible argument values. In a game to 100, there are 100 possible score values (0-99) and 100 possible opponent_score values (0-99), giving 10,000 possible argument combinations.

Implement is_always_roll, which takes a strategy and returns whether that strategy always rolls the same number of dice for every possible argument combination.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def is_always_roll(strategy, goal=GOAL):
    """Return whether strategy always chooses the same number of dice to roll.

    >>> is_always_roll(always_roll_5)
    True
    >>> is_always_roll(always_roll(3))
    True
    >>> is_always_roll(catch_up)
    False
    """
    # BEGIN PROBLEM 7
    start = strategy(0,0)
    for m in range(goal):
        for n in range(goal):
            if strategy(m,n)!=start:
                return False
    return True
    # END PROBLEM 7

Problem 8 (2 pt)

Implement make_averaged, which is a higher-order function that takes a function original_function as an argument.

The return value of make_averaged is a function that takes in the same number of arguments as original_function. When we call this returned function on the arguments, it will return the average value of repeatedly calling original_function on the arguments passed in.

Specifically, this function should call original_function a total of total_samples times and return the average of the results of these calls.

Important: To implement this function, you will need to use a new piece of Python syntax. We would like to write a function that accepts an arbitrary number of arguments, and then calls another function using exactly those arguments. Here’s how it works.

Instead of listing formal parameters for a function, you can write *args, which represents all of the arguments that get passed into the function. We can then call another function with these same arguments by passing these *args into this other function. For example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
>>> def printed(f):
...     def print_and_return(*args):
...         result = f(*args)
...         print('Result:', result)
...         return result
...     return print_and_return
>>> printed_pow = printed(pow)
>>> printed_pow(2, 8)
Result: 256
256
>>> printed_abs = printed(abs)
>>> printed_abs(-10)
Result: 10
10

Here, we can pass any number of arguments into print_and_return via the *args syntax. We can also use *args inside our print_and_return function to make another function call with the same arguments.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def make_averaged(original_function, total_samples=1000):
    """Return a function that returns the average value of ORIGINAL_FUNCTION
    called TOTAL_SAMPLES times.

    To implement this function, you will have to use *args syntax.

    >>> dice = make_test_dice(4, 2, 5, 1)
    >>> averaged_dice = make_averaged(roll_dice, 40)
    >>> averaged_dice(1, dice)  # The avg of 10 4's, 10 2's, 10 5's, and 10 1's
    3.0
    """
    # BEGIN PROBLEM 8
    def new_function(*args):
        count = 0
        for i in range(total_samples):
            count += original_function(*args)
        return count/total_samples
    
    return new_function
    # END PROBLEM 8

Problem 9 (2 pt)

Implement max_scoring_num_rolls, which runs an experiment to determine the number of rolls (from 1 to 10) that gives the maximum average score for a turn. Your implementation should use make_averaged and roll_dice.

If two numbers of rolls are tied for the maximum average score, return the lower number. For example, if both 3 and 6 achieve a maximum average score, return 3.

You might find it useful to read the doctest and the example shown in the doctest for this problem before doing the unlocking test.

Important: In order to pass all of our tests, please make sure that you are testing dice rolls starting from 1 going up to 10, rather than from 10 to 1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def max_scoring_num_rolls(dice=six_sided, total_samples=1000):
    """Return the number of dice (1 to 10) that gives the highest average turn score
    by calling roll_dice with the provided DICE a total of TOTAL_SAMPLES times.
    Assume that the dice always return positive outcomes.

    >>> dice = make_test_dice(1, 6)
    >>> max_scoring_num_rolls(dice)
    1
    """
    # BEGIN PROBLEM 9
    max_score = 0
    bestnum=0
    averaged_dice = make_averaged(roll_dice, total_samples)
    the_dice = dice
    for i in range (1,11):
        score = averaged_dice(i, the_dice)
        if score > max_score:
            bestnum = i
            max_score = score
    return bestnum
    # END PROBLEM 9

Problem 10 (2 pt)

A strategy can try to take advantage of the Pig Tail rule by rolling 0 when it is most beneficial to do so. Implement tail_strategy, which returns 0 whenever rolling 0 would give at least threshold points and returns num_rolls otherwise. This strategy should not also take into account the Square Swine rule.

Hint: You can use the tail_points function you defined in Problem 2.

1
2
3
4
5
6
7
8
9
def tail_strategy(score, opponent_score, threshold=12, num_rolls=6):
    """This strategy returns 0 dice if Pig Tail gives at least THRESHOLD
    points, and returns NUM_ROLLS otherwise. Ignore score and Square Swine.
    """
    # BEGIN PROBLEM 10
    if tail_points(opponent_score)>=threshold:
        return 0
    return num_rolls  # Remove this line once implemented.
    # END PROBLEM 10

Problem 11 (2 pt)

A better strategy will take advantage of both Pig Tail and Square Swine in combination. Even a small number of pig tail points can lead to large gains. For example, if a player has 31 points and their opponent has 42, rolling 0 would bring them to 36 which is a perfect square, and so they would end the turn with 49 points: a gain of 49 - 31 = 18!

The square_strategy returns 0 whenever rolling 0 would result in a score that is at least threshold points more than the player’s score at the start of turn.

Hint: You can use the square_update function.

1
2
3
4
5
6
7
def square_strategy(score, opponent_score, threshold=12, num_rolls=6):
    """This strategy returns 0 dice when your score would increase by at least threshold."""
    # BEGIN PROBLEM 11
    if square_update(0, score, opponent_score)-score >= threshold:
        return 0
    return num_rolls  # Remove this line once implemented.
    # END PROBLEM 11

You should find that running python3 hog.py -r now shows a win rate for square_strategy close to 62%.

Optional: Problem 12 (0 pt)

Implement final_strategy, which combines these ideas and any other ideas you have to achieve a high win rate against the baseline strategy. Some suggestions:

  • If you know the goal score (by default it is 100), there’s no benefit to scoring more than the goal. Check whether you can win by rolling 0, 1 or 2 dice. If you are in the lead, you might decide to take fewer risks.
  • Instead of using a threshold, roll 0 whenever it would give you more points on average than rolling 6.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def final_strategy(score, opponent_score):
    """Write a brief description of your final strategy.

    *** YOUR DESCRIPTION HERE ***
    """
    # BEGIN PROBLEM 12
    averaged_dice = make_averaged(roll_dice, 100)
    if square_update(0, score, opponent_score)-score >= averaged_dice(6):
        return 0
    elif 100 - score < averaged_dice(1):
        return 1
    elif 100 - score < averaged_dice(2):
        return 2
    elif 100 - score < averaged_dice(3):
        return 3
    elif 100 - score < averaged_dice(4):
        return 4
    elif 100 - score < averaged_dice(5):
        return 5
    else :
        return 6
    # END PROBLEM 12
CS61A Project 1
2023/11/15/CS61A Project 1/
Author
easterling
Published
2023-11-15 21:55
License
 Comments
Comment plugin failed to load
Loading comment plugin
  1. 1. Project 1: The Game of Hog hog.zip
    1. 1.1. Introduction
      1. 1.1.1. Rules
    2. 1.2. Phase 1: Rules of the Game
      1. 1.2.1. Problem 1 (2 pt)
      2. 1.2.2. Problem 2 (2 pt)
      3. 1.2.3. Problem 3 (2 pt)
      4. 1.2.4. Problem 4 (1 pt)
      5. 1.2.5. Problem 5 (5 pt)
    3. 1.3. Phase 2: Strategies
      1. 1.3.1. Problem 6 (2 pt)
      2. 1.3.2. Problem 7 (2 pt)
      3. 1.3.3. Problem 8 (2 pt)
      4. 1.3.4. Problem 9 (2 pt)
      5. 1.3.5. Problem 10 (2 pt)
      6. 1.3.6. Problem 11 (2 pt)
      7. 1.3.7. Optional: Problem 12 (0 pt)