Project 1: The Game of Pig

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

Introduction

In this project, you will develop a simulator and strategy function for the game of Pig. You will need to implement some higher-order functions, experiment with random number generators, and generate some ASCII art. This project uses ideas from Chapter 1 of the lecture notes.

Pig is a dice game with simple rules: Two players race to reach 100 total points. Each turn, a player repeatedly rolls a die until either a 1 ("pig") is rolled or the player holds and scores the sum of the rolls. The sum of the rolls on a turn is called the turn total. At any time during a player's turn, the player is faced with two decisions:

Someone has posted a Pig instructional video. Note that they give 0 points to a turn that ends in a roll of 1, while we give 1 point.

In this project, you will create a variant of Pig that uses two different dice. Players roll a 6-sided die, unless the sum of the scores of both players is a multiple of 7 (0 included), in which case they roll a 4-sided die. This sum of scores does not include the turn total.

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.

pig.py

A starter implementation of Pig.

dice.py

Functions for rolling dice.

ucb.py

Utility functions for 61A.

Logistics

This is a two-week project. You'll work in a team of two people, person A and person B. In each part, you will do some of the work separately, but most of the problems together with your partner. For example, if a problem is marked A1, then it is a solo problem for person A. Both partners should read, think about, and understand the solution to all questions.

Start early! The amount of time it takes to complete a project (or any program) is unpredictable. Ask for help early and often -- the TAs and lab assistants are here to help.

In the end, you and your partner will submit one project. Person-specific problems are graded individually and do not affect your partner's score. There are 15 possible points for each person. If you choose to work alone, you must complete the entire project, including all of the questions designed for both partners.

The only file that you are required to submit is the file called "pig.py". You do not need to modify any other files in order to complete the project. To submit the project, change to the directory where the pig.py file is located and run submit proj1. The TA's will setup an autograder that runs your code through different test cases and sends out the results in an email.

Phase 1

In the first week, you will develop a simulator for the game and a basic strategy. Most of this week's problems will be solved in pairs.

The first step in implementing a Pig simulator is to specify the rules of the game. You will each implement one of the legal actions. Remember that a turn consists of a sequence of actions and ends either when a player rolls a 1 or holds. Read the comments of the functions you are implementing, as they specify the precise behavior expected.

Problem A1 (1 pt). Implement the roll function in pig.py, which computes the result of rolling a particular outcome. Remember that no points are scored unless the turn ends! On successful (greater than 1) rolls, points are only accumulated in the turn total.

Verify your work by checking that the doctest for roll passes when you run

python3 -m doctest pig.py

Problem B1 (1 pt). Implement the hold function in pig.py, which computes the result of holding. Holding actually doesn't care about the dice outcome. Nonetheless, this argument is provided so that hold has the same signature as roll. Similarly, hold must return a turn total even though the result is irrelevant to the game. Always return a turn total of 0.

Verify your work by checking that the doctest for hold passes when you run

python3 -m doctest pig.py

Note: The next two questions can be solved with your partner. However, we recommend that you each try to solve them on your own before collaborating to understand the project better.

Problem 2 (2 pt). Implement the take_turn function, which simulates a complete turn that may include multiple rolls. This function takes a plan argument, which itself is a function (see next paragraph). The return value of take_turn is the total number of points the player scored during that turn.

A plan is a function that takes one integer argument, the current turn_total, and returns one of the two legal actions: either roll or hold that you just implemented. A plan represents a player's decision of whether to roll or hold. It does not consider the total score for either player; only the current turn total.

A dice is also a function (we would call it a "die", but that's too morbid). It takes no arguments and returns an integer: the outcome of a die roll.

Important: Your implementation of take_turn should call the dice function exactly once for every action, including hold. If you don't do this, various tests will break later in the project!

For now, you can ignore the arguments who, and comments, which you will use later.

The run function at the bottom of pig.py is currently set up to call take_turn (via take_turn_test) and print the result. Hence, you can experiment with your implementation simply by running

python3 pig.py

The plan that is provided by default will roll until the turn total reaches at least 10, and then hold.

Hint: We have provided some tools in ucb.py to help you understand what is happening in your code. If you decorate a function with @trace, then a line of output will be printed every time that function is called. If you call log_current_line(), then the current line number will be printed. Finally, if you call interact(), then you will receive an interactive prompt in the current environment.

Problem 3 (1 pt). Implement a better take_turn_test, which validates the correctness of your take_turn implementation. To do so, read the dice.py file, which provides a function called make_test_die. Test dice are not random like regular dice. Instead, you can specify the exact sequence of outcomes returned by successive rolls. The docstring for make_test_die shows examples.

Using assert statements, test that the default plan scores exactly 10 points when rolling a 4, 6, 1. Add additional tests to ensure that the plan gives expected outcomes with various roll sequences.

Problem 4 (1 pt). Change the default value for comments in take_turn from False to True. Then, call commentate after the result of each action is computed, whenever comment is True. You will need to read the docstring for commentate to make this call correctly.

After you start calling the commentate function, you should see a transcript of events when you run pig.py that includes statements like, "Someone did something... Someone now has a turn total of 7 points." Details of the game events are currently rather vague.

Problem A5 (2 pt). Person A, now you will implement describe_action, which takes an action function and returns a string describing that action. Edit the body of describe_action so that its doctest passes. For any action that is not roll or hold, the commentator should announce that an illegal action was taken.

When you are finished, the doctest for describe_action should pass, and your commentary should have informative action messages when you run take_turn with comments equal to True.

Hint: You can figure out what a function is without calling it, using ==.

Problem B5 (2 pt). Person B, now you will implement draw_number, which draws the outcome of a die using text symbols. Such pictures are called ASCII art.

The drawing facility is actually written for you in draw_die. However, it uses a bunch of 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.

When you are finished, the doctest for draw_number should pass, and your commentary should produce ASCII dice pictures when you call take_turn with comments equal to True.

You're almost ready to implement a full game of Pig!

Problem 6 (1 pt). First, implement make_roll_until_strategy. This is a function that returns a strategy. Strategies are functions that return plans. Plans are functions that return actions. Actions are functions too. Yikes! This project just got complicated. Fortunately, our functional abstractions will alleviate us from ever having to write quadruple-nested def statements. In fact, this question requires very little code, but lots of description.

Plans: A plan is a function that takes one integer argument, the current turn_total, and returns an action (hold or roll). We have already been using plans to test take_turn. In take_turn_test, we created a plan using the make_roll_until_plan function, which takes a turn_goal and returns a plan to roll until that goal is met. Go read the implementation of make_roll_until_plan. Your strategy functions will use it.

Strategies: A strategy is a function that takes two arguments: the player's score and the opponent's score. It returns a plan. A strategy is used to pick a plan each turn, based on the players' current scores in the game.

Note that make_roll_until_strategy itself is not the strategy, but a function that returns a strategy.

Your implementation of make_roll_until_strategy should return a very simple strategy: one that always returns the same plan regardless of its two arguments. The plan it returns always chooses to roll unless the specified turn_total goal has been reached.

Call make_roll_until_strategy_test to verify your work.

Problem 7 (3 pt). Finally, implement the play function, which simulates a full game of pig. Players alternate turns, each using the plan returned by their own strategy function, until one of the players reaches the goal score. When the game ends, play should return 0 if the first player wins and 1 otherwise.

Remember that you must supply the correct die to the take_turn function, according to the rules stated at the beginning of the project. As you work, remember to add print statements and use @trace to see what is happening in your code.

To test your implementation, follow the instructions in the run function at the bottom of the project to play an interactive game.

Congratulations! You've finished phase 1 of this project!

Phase 2

In the second week, you will experiment with ways to improve upon the basic strategy. In order to do this, you will first implement a small framework for testing strategy functions against the roll-until strategy. We will use the strategy returned by make_roll_until_strategy(20) as a baseline upon which we hope to improve.

Note: You will want to set the default of comment back to False in the definition of take_turn, so that you're not overwhelmed with output.

Problem 8 (1 pt). Implement the average_value function. This function takes two arguments, a non-pure target function fn and an integer num_samples that indicates how many times the target function should be called. The return value of the target function should be a number. Call fn repeatedly, num_sample times, and return the average result. Assume that fn takes no arguments. Make sure that the doctest passes before you move on.

Problem 9 (2 pt). Implement the averaged function. This higher-order function takes a function fn as argument, and creates another function that takes the same number of arguments as the original. It is different from the original in that it returns the average value of repeatedly calling fn on its arguments.

To implement this function, you need a new piece 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. Note that args is actually just another name in the environment, but changing that name is unconventional. 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 averaged carefully to understand how it is meant to work. Your implementation can use the average_value function you already implemented, but this is not required.

Problem 10 (2 pt). This problem is about understanding code. Read compare_strategies and eval_strategy_range and discuss them with your partner. Then, in run_strategy_experiments, use eval_strategy_range to evaluate different roll-until strategies, for turn_goal values from 15 to 25 inclusive. Print out what eval_strategy_range determined was the best value.

Now you will implement three strategies that improve upon the baseline. The first two are divided between partners. Some of the experiments may take up to a minute to run. You can always reduce the number of random samples in averaged to speed up experiments.

Problem 11A (2 pt). Implement the make_die_specific_strategy function. This function takes two turn goals, four_side_goal and six_side_goal, and returns a new strategy that checks to see which die is being used (either 4-sided or 6-sided) and returns a roll-until plan that stops at the corresponding turn goal. Keep in mind that a four-sided die is only used when the sum of your score and your opponent's score is divisible by 7. The idea here is that holding early with a 4-sided die avoids 1's.

Add an experiment to run_strategy_experiments that evaluates different turn goals for a 4-sided die, in the range 5 to 15.

Problem 11B (2 pt). Implement the make_pride_strategy, which only stops rolling when two conditions are true: the turn total is at least turn_goal and the player's score after holding is at least margin greater than the opponent. The idea here is that riskier rolling is justified when a player is behind.

Add an experiment to run_strategy_experiments that evaluates different margins for your new strategy, in the range 0 to 10.

Problem 12 (2 pt). Implement final_strategy, which combines these ideas and others to achieve a win rate of at least 0.60 against the baseline roll-until-20 strategy. Here are some hints:

You're implementing a strategy function directly here, as opposed to a function that returns a strategy. If your win rate is usually (i.e., half the time) above 0.60, you have answered the question successfully.

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

Acknowledgements: The suggestion of using Pig as a CS project and the dice image came from Todd Neller.