I know! I'll use my
Higher-order functions to
Order higher rolls.
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
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.
A starter implementation of Pig.
Functions for rolling dice.
Utility functions for CS61A.
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
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).
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
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
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
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
hold pass. To do this, run the
following line from your terminal:
python3 -m doctest pig.py
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
Problem 2 (2 pt). Implement the
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.
tactic is a higher-order function that takes one
integer argument, the current
turn_total, and returns
one of the two functions: either
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
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
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
comments, which you will use later.
Try testing your
take_turn_test) by issuing the following command at
python3 pig.py --take_turn_testIn shorthand, you can also issue:
python3 pig.py -tNote: 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
the turn total reaches at least 10, and then
Hint: We have provided some tools in
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
then the current line number will be printed. Finally, if you call
then you will receive an interactive prompt in the current
Problem 3 (1 pt). Implement a better
which validates the correctness of your
implementation. To do so, read the
which provides a function called
dice are not random like regular dice. Instead, you can specify the
exact sequence of outcomes returned by successive rolls. The
make_test_die shows examples.
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
Problem 4 (1 pt). Change the default value for
commentate after the result of each action
is computed, whenever
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
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
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
the commentator should announce that an illegal action was taken.
When you are finished, the doctest for
should pass, and your commentary should have informative action
messages when you run
Hint: You can figure out what a function is without calling
Problem 6 (2 pt). You will now implement
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
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
should pass, and your commentary should produce ASCII dice pictures
when you call
You're almost ready to implement a full game of Pig!
Problem 7 (2 pt). First, implement
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
strategy is a higher-order function that takes
two arguments: the player's score and the opponent's score, and
make_roll_until_strategy itself is not the
strategy, but a function that returns a strategy.
Your implementation of
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
make_roll_until_strategy returns will
roll until it reaches a certain
Run the doctest to verify your work.
Problem 8 (3 pt). Finally, implement the
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
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
@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!
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
as a baseline upon which we hope to improve.
Falsein the definition of
take_turn, so that you are not overwhelmed with output.
Problem 9 (2 pt). Implement the
function. This higher-order function takes a function
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
fn on its arguments. This function should call
a total of
num_samples times and return the average of
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
To call another function using exactly those arguments, we call it
*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.
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
turn_goal. Within the range
15 to 25 (inclusive), which value of
achieves the best win rate?
eval_strategy_range to find the best
You should compare your
roll_until strategies against the
baseline strategy, which
eval_strategy_range already does.
Print out what
determined was the best value.
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
to speed up experiments.
Tip: If you forgot to change the
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
will try to terminate the active process.
Problem 11 (2 pt). Implement the
function. This function takes two turn goals,
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
evaluates different turn goals for a 4-sided die, in the range 5 to
Problem 12 (2 pt). Implement the
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
evaluates different margins for your new strategy, in the range 0 to
Problem 13 (2 pt). Implement
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
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.