## 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:

• roll - If the player rolls a

• 1: the player scores 1 point and it becomes the opponent's turn.

• anything else: the roll is added to the player's turn total, and the turn continues.

• hold - The player scores the turn total and it becomes the opponent's turn.

Someone has posted a Pig instructional video. Our rules differ somewhat from those in the video: 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. 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.

The project is worth 15 points. To avoid fractions, however, we have assigned "inflated" points that add up to 25. We'll simply weight the grading calculation by multiplying the nominal score you receive by 0.6.

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`. We will set up 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. The first step in implementing a Pig simulator is to specify the rules of the game. You will implement two of the legal actions: `roll` and `hold`. 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. 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
```

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). Now 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). 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.

`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`. `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`. 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. 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:

• Think about what happens when you only need 10 more points to win, but are using a roll-until-20 strategy. Can you improve end-game performance?
• Roll-until-20 is a very bad idea when given a 4-sided die. Can you give your opponent more bad dice?

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:Richard Lan and John DeNero developd this project. The suggestion of using Pig as a CS project and the dice image came from Todd Neller.