Proj01

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 multiple strategies for the game of Pig. You will need to implement some higher-order functions, experiment with random number generators, and generate some ASCII art.

Pig is a dice game with simple rules: Two players take turns rolling dice and scoring points until one player reaches 100 points. Each turn has a turn total, which is a tentative number of points the player has accumulated so far during the turn (this is different from the turn score, which is what the player actually scores at the end of the turn). A player's turn consists of a sequence of actions. There are two legal actions:

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.

A player's turn will end if (a) the player rolls a 1, or (b) the player holds. Otherwise, the outcome of each roll will be added to the turn total, and the player can once again choose to roll or hold.

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.

In the later parts of this project, you will be creating various plans to play the game. We will use two terms: strategy and tactic. Think of a strategy as a plan for the entire game. In contrast, a tactic is a plan for a single turn; it determines what actions the player should choose in that specific turn. A strategy is essentially a repertoire of tactics; each player enters the game with a single strategy, and each turn a player picks a suitable tactic from their strategy.

In terms of code, a strategy is a higher-order function that returns a tactic function to respond to the current game state. A tactic is itself a higher-order function that returns an action (either a roll function or a hold function).

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 CS61A.

Logistics

This is a two-week project. You are expected to complete this project individually - no partners are allowed. However, you will have a project partner for the final two projects.

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 will 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 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 e-mail.

For the functions that we ask you to complete, there may be some initial code that we give you. This is solely designed to help you get started: if you would rather not use the provided code snippet, feel free to delete it and start from scratch.

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

Phase 1: Simulator

In the first phase, 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 each 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 1 (2 pt). First, 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.

Then, 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.

You can verify your work by checking that the doctests for roll and hold pass. To do this, run the following line from your terminal:

      python3 -m doctest pig.py

Notice that roll and hold are not the only functions checked. In future problems, you can check your work on problems that provide doctests by running the line of code above in your terminal.

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

A tactic is a higher-order function that takes one integer argument, the current turn_total, and returns one of the two functions: either roll or hold, both of which you implemented in Problem 1. A tactic is a turn-specific plan that determines which action the player will choose based on 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 always 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.

Try testing your take_turn (via take_turn_test) by issuing the following command at the terminal:

    python3 pig.py --take_turn_test

In shorthand, you can also issue:

    python3 pig.py -t

Note: This is not the doctest, but a convenient tool to help run tests. You still need to run doctests to debug your code.

The tactic 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 tactic scores exactly 10 points when rolling a 4, 6, 1. Add additional tests to ensure that the tactic 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 comments 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, which 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 5 (2 pt). You will 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 set to True.

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

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

Note: The sides with 2 and 3 dots have 2 possible depictions due to rotation. Either representation is acceptable.

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 7 (2 pt). First, implement make_roll_until_strategy. This is a higher-order function that returns ("makes") a strategy.

Strategies: Recall that a strategy is like a "game plan" that holds a set of tactics. Depending on the player's score and the opponent's score (i.e. if the player is winning or not), the player will choose a specific tactic to use during this turn. In terms of code, a strategy is a higher-order function that takes two arguments: the player's score and the opponent's score, and returns a tactic function.

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 will return a very simple strategy: so simple that it will effectively ignore its two arguments. This simple strategy will return a tactic that always chooses to roll unless the specified turn_total goal has been reached. In other words, the strategy that make_roll_until_strategy returns will roll until it reaches a certain turn_total.

Run the doctest to verify your work.

Problem 8 (3 pt). Finally, implement the play function, which simulates a full game of Pig. Players alternate turns, each using the tactic 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.

IMPORTANT: Remember that you must supply the correct die to the take_turn function. For every turn, check if the sum of both players' scores is divisible by 7. If it is, you must supply a 4-sided die. If not, you supply a 6-sided die as usual.

As you work, you can add print statements and use @trace to see what is happening in your code.

To test your implementation, enter the following line from your terminal to start an interactive game of Pig:

      python3 pig.py --play

Congratulations! You have finished Phase 1 of this project!

Phase 2: Strategies

In this final phase, you will experiment with ways to improve upon the basic strategy. 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 comments back to False in the definition of take_turn, so that you are not overwhelmed with output.

Problem 9 (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 not a pure function (for instance, the random function), then make_average will also not be a pure function.

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

Problem 10 (2 pt). This problem is about understanding code and designing your first experiment. Read compare_strategies and eval_strategy_range and understand what it is doing. You will use these functions to answer the following question:

Recall that a roll_until strategy (from Problem 6) will keep choosing the roll action until it reaches its turn_goal. Within the range 15 to 25 (inclusive), which value of turn_goal achieves the best win rate?

In run_strategy_experiments, use eval_strategy_range to find the best turn_total. You should compare your roll_until strategies against the baseline strategy, which eval_strategy_range already does. Print out what eval_strategy_range determined was the best value.

To test run_strategy_experiments(), go to the terminal and enter the following:

      python3 pig.py --run_strat_exps

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 make_average to speed up experiments.

Tip: If you forgot to change the comments to False in take_turn, running run_strategy_experiments will result in hundreds of lines of output to the terminal, which may result in the process taking much longer. You can terminate the Python process by doing Ctrl-C. In general, issuing a Ctrl-C will try to terminate the active process.

Problem 11 (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 tactic 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 12 (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 13 (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?
Rolling 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. You can test this entering the following line in your terminal:

      python3 pig.py --final_strat_test

Note: This test can take a couple of seconds to complete.

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

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