I know! I'll use my
Higher-order functions to
Order higher rolls.
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.
A starter implementation of Pig. |
|
Functions for rolling dice. |
|
Utility functions for 61A. |
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.
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!
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.
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:
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.