Project 1: The Game of Hog

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

Introduction

In this project, you will develop a simulator and multiple strategies for the dice game Hog. You will need to implement some higher-order functions, experiment with random number generators, and generate some ASCII art.

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. She scores the sum of the dice outcomes, unless any of the dice come up a 1 (Pig out), in which case she scores only 1 point for the turn.

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

  1. Hog Tied. If the sum of both players' scores ends in a seven (e.g., 17, 27, 57), then the current player can roll at most one die.
  2. Hog Wild. If the sum of both players' 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.
  3. Free Bacon. If a player chooses to roll zero dice, she scores one more than the tens digit of her opponent's score. E.g., if the first player has 32 points, the second player can score four by rolling zero dice. If the opponent has fewer than 10 points (tens digit is zero), then the player scores one.
  4. Touchdown. If a player's score for the turn is a multiple of 6, then the current player gains additional points equal to the turn score divided by 6. E.g., if the original turn score is 12, the player will earn 14 (12 + 2) points total for the turn, after the Touchdown rule.
  5. Hogtimus Prime. If a player's score for the turn is a prime number, then the turn score is increased to the next largest prime number. Note: 1 is not prime. E.g., if the original turn score is 19, the player earns 23 points total for the turn. If the original turn score is 6, then the player earns 11 points total from the Touchdown and Hogtimus Prime rules.

This project includes three files, but all of your changes will be made to the first one. You can download all of the project code as a zip archive.

hog.py

A starter implementation of Hog.

dice.py

Functions for rolling dice.

ucb.py

Utility functions for CS61A.

Logistics

This is a one-week project. You are encouraged to complete this project with a partner, although you may complete it alone.

Start early! The amount of time it takes to complete a project (or any program) is unpredictable.

You are not alone! Ask for help early and often -- the TAs, lab assistants, and your fellow students are here to help.

In the end, you and your partner will submit one project. The project is worth 20 points. 17 points are assigned for correctness, and 3 points for the overall composition of your program.

The only file that you are required to submit is the file called hog.py. You do not need to modify or turn in any other files to complete the project. To submit the project, change to the directory where the hog.py file is located and run submit proj1. Expect a response via email whenever you submit.

For the functions that we ask you to complete, there may be some initial code that we provide. If you would rather not use that code, feel free to delete it and start from scratch. You may also add new function definitions as you see fit.

However, please do not modify any other functions. Doing so may result in your code failing our autograder tests. Also, do not change any function signatures (names, argument order, or number of arguments).

Phase 1: Simulator

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, which returns the number of points scored by rolling a fixed positive number of dice. To obtain a single outcome of a dice roll, call dice(). You should call this function exactly num_rolls times. You do not need to consider the special rules for this problem.

As you work, you can add print statements to see what is happening in your program.

You can call interact() anywhere in your code to start an interactive session in the current environment. That way, you can test how different names and expressions will evaluate.

Problem 2 (1 pt). Implement the take_turn function, which returns the number of points scored by choosing to roll zero or more dice. To score zero dice correctly, see the Free Bacon special rule. For more than zero dice, call roll_dice.

You should also implement the Touchdown and Hogtimus Prime special rules here. Don't forget that they apply to both regular turns and Free Bacon turns! Touchdown should be applied first, followed by Hogtimus Prime.

To implement the Hogtimus Prime rule, write your own prime functions above the take_turn function. One way to do this is to write two functions, is_prime and next_prime. Remember, 1 isn't prime!

To check your work so far, run the take_turn_test function by entering the following line into your terminal:

      python3 hog.py -t

This function first tests roll_dice using deterministic test dice that always give predictable outcomes. Then, it tests take_turn. These tests are not exhaustive; you may still have errors in your functions even if they pass. You may add additional tests to take_turn_test if you wish.

Problem 3 (1 pt). You can now implement commentary for turns, which has two parts. First, update your roll_dice implementation to call announce every time dice are rolled, if commentary is True. The name commentary is bound in the global frame (and can be found at the top of hog.py). You will need to read the docstring of announce to call it correctly.

Second, implement draw_number, which draws the outcome of a roll using text symbols. Such pictures are called ASCII art. Note: The sides with 2 and 3 dots have two possible depictions due to rotation. Please use the forward-diagonal (/) representations.

A function to draw dice is actually written for you in draw_dice. However, it uses Python syntax that we haven't yet covered! You'll have to use this function as a black box, just by reading its docstring. Programming often involves using other people's code by reading the documentation.

You can check your work by running doctests for your whole program, entering the following line into your terminal:

      python3 -m doctest -v hog.py

Tests for later questions will not pass yet, but you should verify that the tests for draw_number do pass. Somewhere in the output, you should see:

Trying:
    print(draw_number(3))
Expecting:
     -------
    |     * |
    |   *   |
    | *     |
     -------
ok
Trying:
    print(draw_number(5))
Expecting:
     -------
    | *   * |
    |   *   |
    | *   * |
     -------
ok
Trying:
    print(draw_number(6, '$'))
Expecting:
     -------
    | $   $ |
    | $   $ |
    | $   $ |
     -------
ok

Problem 4 (1 pt). Implement num_allowed_dice and select_dice, two functions that will simplify the implementation of play below. The function num_allowed_dice helps enforce special rule #1 (Hog Tied). The function select_dice helps enforce special rule #2 (Hog Wild). Both of these functions take two arguments: the scores for the current and opposing players. Make sure that doctests for these functions pass before moving on.

Problem 5 (3 pt). Finally, implement the play function, which simulates a full game of Hog. Players alternate turns, each using the strategy originally supplied, until one of the players reaches the goal score. When the game ends, play should return 0 if player 0 wins, and 1 otherwise. Some hints:

To simulate a single game in which player 0 always wants to roll 5 dice, while player 1 always wants to roll 6 dice, enter the following line into your terminal:

      python3 hog.py -b

To play an interactive game of Hog against an opponent that always wants to roll 5 dice, enter the following line into your terminal:

      python3 hog.py -p

Congratulations! You have finished Phase 1 of this project!

Phase 2: Strategies

In the second phase, you will experiment with ways to improve upon the basic strategy of always rolling a fixed number of dice. First, you need to develop some tools to evaluate strategies.

Problem 6 (2 pt). Implement the make_average function. This higher-order function takes a function fn as an argument, and returns another function that takes the same number of arguments as the original. It is different from the original function in that it returns the average value of repeatedly calling fn on its arguments. This function should call fn a total of num_samples times and return the average of their results.

Note: If the input function fn is a non-pure function (for instance, the random function), then make_average will also be a non-pure function.

To implement this function, you need a new element of Python syntax! You must write a function that accepts an arbitrary number of arguments, then calls another function using exactly those arguments. Here's how it works.

Instead of listing formal parameters for a function, we write *args. To call another function using exactly those arguments, we call it again with *args. For example,

      >>> def printed(fn):
      ...     def print_and_return(*args):
      ...         result = fn(*args)
      ...         print('Result:', result)
      ...         return result
      ...     return print_and_return
      >>> printed_pow = printed(pow)
      >>> printed_pow(2, 8)
      Result: 256
      256

Read the docstring for make_average carefully to understand how it is meant to work. Make sure that the doctests pass.

Using this function, you should now be able to call run_experiments successfully. Spend some time to read this function and all of the functions it calls, so that you understand the experimental setup for the following questions.

To run a series of strategy experiments, which play many games of Hog and print the average results, enter the following line into your terminal:

      python3 hog.py -r

Each game is played against the "baseline", which is the basic strategy of always rolling 5 dice. These experiments test strategies that always roll some other number of dice (the value). Most should be worse than always rolling 5.

Some of the experiments may take up to a minute to run. You can always reduce the number of random samples in make_average to speed up experiments. Update run_experiments when you are done testing the always_roll strategy.

Problem 7 (2 pt). It can be advantageous to take risks if you are behind in Hog. The "comeback" strategy rolls extra dice when losing. Implement make_comeback_strategy, which returns the following strategy function: If the player is losing to the opponent by at least margin points, then roll num_rolls + 1; otherwise, if the player is not losing by margin, roll num_rolls.

Note: make_comeback_strategy and make_mean_strategy (problem 8) are not strategies themselves -- they make (i.e. return) strategies. Take a look at always_roll for an example.

Once you have implemented this strategy, change run_experiments to evaluate your new strategy against the baseline. You should find that it wins more than half of the time.

Problem 8 (2 pt). It can also be advantageous to be mean, by taking advantage of the special rules in combination to the detriment of your opponent. Implement make_mean_strategy, which returns a strategy that rolls 0 whenever two conditions are true:

  1. The points received from the Free Bacon rule (and if applicable, the Touchdown and Hogtimus Prime rules) are at least min_points, and
  2. After receiving these points, the sum of player and opponent's current score will be a multiple of 7 (triggering Hog Wild), or end in 7 (triggering Hog Tied), or both.

Otherwise, roll num_rolls.

Once you have implemented this strategy, update run_experiments to evaluate your new strategy against the baseline. You should find that it wins more than half of the time.

Problem 9 (3 pt). Implement final_strategy, which combines these ideas and any other ideas you have to achieve a win rate of at least 0.60 against the baseline always_roll(5) strategy. Some ideas:

You are implementing a strategy function directly, as opposed to a function that returns a strategy. If your win rate is above 0.60, you have answered the question successfully. You can compute an approximate win rate by entering the following line in your terminal:

      python3 hog.py -f

Note: You may want to increase the number of samples to improve the approximation of your win rate. The course autograder will compute your exact win rate for you once you submit your project, and it will send it to you in an email.

Congratulations, you have reached the end of your first CS61A project!