Introduction

In this project, you will develop a simulator and multiple strategies for the dice game Hog.

You will need to use control statements and higher-order functions together, as described in Sections 1.2 through 1.6 of Composing Programs, the online textbook.

Dice

Rules of Hog

In Hog, two players alternate turns trying to be the first to end a turn with at least GOAL total points, where GOAL defaults to 100. On each turn, the current player chooses some number of dice to roll, up to 10. That player's score for the turn is the sum of the dice outcomes.

However, a player who rolls too many dice risks:

  • Pig Out.（俚语，狼吞虎咽）

    If any of the dice outcomes is a 1, the current player's score for the turn is 1.

    • Example 1: The current player rolls 7 dice, 5 of which are 1's. The player scores 1 point for the turn.
    • Example 2: The current player rolls 4 dice, all of which are 3's. Since Pig Out did not occur, they score 12 points for the turn.

In a normal game of Hog, those are all the rules.

To spice up the game, we'll include some special rules:

  • Picky Piggy.

    A player who chooses to roll zero dice scores \( (2 \times \vert \texttt{tens} - \texttt{ones} \vert + 1) \) points; where tens, ones are the tens and ones digits of the opponent's score. The ones digit refers to the rightmost digit and the tens digit refers to the second-rightmost digit.

    • Example 1: The opponent has 46 points, and the current player chooses to roll zero dice. \( 2 \times \vert 4 - 6 \vert + 1 = 5 \), so the player gains 5 points.
    • Example 2: The opponent has 73 points, and the current player chooses to roll zero dice. \( 2 \times \vert 7 - 3 \vert + 1 = 9 \).

  • Swine Swap.

    After points of the turn are added to the current player's score, if the resulting score is a perfect square, then swap the scores of both players. A perfect square is any integer \( n \) where \( n = d \times d \) for some integer \( d \).

    • Example 1: At the end of a turn, the current player has score 4 and the other player has score 2. Since 4 is a perfect square, the scores are swapped.
    • Example 2: At the end of a turn, the current player has score 11 and the other player has score 5. Since 11 is not a perfect square, the scores are not swapped.
    • Example 3: At the end of a turn, the current player has score 99 and the other player has score 16. Since 99 is not a perfect square, the scores are not swapped.

Project Logistics

When you finish the project, you'll have implemented a significant part of this game yourself.

To get started, download all of the project code as a zip archive. Below is a list of all the files you will see in the archive once unzipped. For the project, you'll only be making changes to hog.py.

  • hog.py: A starter implementation of Hog
  • dice.py: Functions for rolling dice
  • hog_gui.py: A graphical user interface (GUI) for Hog
  • ok: The autograder
  • tests: A directory of tests used by ok
  • gui_files: A directory of various things used by the web GUI

You may notice some files other than the ones listed above too -- those are needed for making the autograder and portions of the GUI work. Please do not modify any files other than hog.py.

You will turn in the following files:

  • hog.py

You do not need to modify or turn in any other files to complete the project. To submit the project, run the following command:

$ python ok --submit

For the functions that we ask you to complete, there may be some initial code that we provide. If you would rather not use that code, feel free to delete it and start from scratch. You may also add new function definitions as you see fit.

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

Throughout this project, you should be testing the correctness of your code. It is good practice to test often, so that it is easy to isolate any problems. However, you should not be testing too often, to allow yourself time to think through problems.

You can debug your code by printing messages or using a debugger.

  • To print a debug message, use print('DEBUG:', ...).
  • To use the integrated debugger in VS Code, refer to the debugging tutorial in week 5.

Phase 1: Simulator

In the first phase, you will develop a simulator for the game of Hog.

Problem 0 (0pts)

The dice.py file represents dice using non-pure zero-argument functions. These functions are non-pure because they may have different return values each time they are called. The documentation of dice.py describes the two different types of dice used in the project:

  • A fair dice produces each possible outcome with equal probability. Two fair dice are already defined, four_sided and six_sided, and are generated by the make_fair_dice function.
  • A test dice is deterministic: it always cycles through a fixed sequence of values that are passed as arguments. Test dice are generated by the make_test_dice function.

Before writing any code, read over the dice.py file and check your understanding by unlocking the following tests.

$ python ok -q 00 -u

This should display a prompt that looks like this:

=====================================================================
Assignment: proj01: Hog
Ok, version vx.y.z
=====================================================================

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Unlocking tests

At each "? ", type what you would expect the output to be.
Type exit() to quit

---------------------------------------------------------------------
Question 0 > Suite 1 > Case 1
(cases remaining: 1)

>>> test_dice = make_test_dice(4, 1, 2)
>>> test_dice()
?

You should type in what you expect the output to be. To do so, you need to first figure out what test_dice will do, based on the description above.

You can exit the unlocker by typing exit().

Typing Ctrl-C on Windows to exit out of the unlocker has been known to cause problems, so avoid doing so.

Problem 1 (200pts)

Implement the roll_dice function in hog.py. It takes two arguments: a positive integer called num_rolls giving the number of dice to roll and a dice function. It returns the number of points scored by rolling the dice that number of times in a turn: either the sum of the outcomes or 1 (due to Pig Out).

To obtain a single outcome of a dice roll, call dice(). You should call dice() exactly num_rolls times in the body of roll_dice.

Remember to call dice() exactly num_rolls times even if Pig Out happens in the middle of rolling. In this way, you correctly simulate rolling all the dice together.

Note: The roll_dice function, and many other functions throughout the project, makes use of default argument values -- you can see this in the function heading:

def roll_dice(num_rolls, dice=six_sided):
    ...

The argument dice=six_sided means that when roll_dice is called, the dice argument is optional. If no value for dice is provided, then six_sided is used by default.

For example, calling roll_dice(3, four_sided), or equivalently roll_dice(3, dice=four_sided), simulates rolling 3 four-sided dice, while calling roll_dice(3) simulates rolling 3 six-sided dice.

Understand the problem: Before writing any code, unlock the tests to verify your understanding of the question. Note: you will NOT be able to test your code using ok until you unlock the test cases for the corresponding question.

$ python ok -q 01 -u

Write code and check your work: Once you are done unlocking, begin implementing your solution. You can check your correctness with:

$ python ok -q 01

Problem 2 (200pts)

Implement picky_piggy, which takes the opponent's current score and returns the number of points scored by rolling 0 dice (see Picky Piggy rule).

Don't assume that scores are below 100. Write your picky_piggy function so that it works correctly for any non-negative score.

Important: Your implementation should NOT use str, lists, or contain square brackets [ ]. The test cases will check if those have been used. Remember to remove the "*** YOUR CODE HERE ***" string from the function once you've implemented it so that you're not getting an unintentional str check error.

Before writing any code, unlock the tests to verify your understanding of the question.

$ python ok -q 02 -u

Once you are done unlocking, begin implementing your solution. You can check your correctness with:

$ python ok -q 02

You can also test picky_piggy interactively by entering python -i hog.py in the terminal and then calling picky_piggy with various inputs.

Problem 3 (200pts)

Implement the take_turn function, which returns the number of points scored for a turn by rolling the given dice num_rolls times.

Your implementation of take_turn should call both roll_dice and picky_piggy when possible.

Before writing any code, unlock the tests to verify your understanding of the question.

$ python ok -q 03 -u

Once you are done unlocking, begin implementing your solution. You can check your correctness with:

$ python ok -q 03

Problem 4 (100pts)

Implement swine_swap, which takes the opponent score and returns True if the scores of both players will be swapped due to Swine Swap.

Before writing any code, unlock the tests to verify your understanding of the question.

$ python ok -q 04 -u

Once you are done unlocking, begin implementing your solution. You can check your correctness with:

$ python ok -q 04

Problem 5 (500pts)

Implement the play function, which simulates a full game of Hog. Players take turns rolling dice until one of the players reaches the goal score, and the final scores of both players are returned by the function.

To determine how many dice are rolled each turn, each player uses their respective strategy (Player 0 uses strategy0 and Player 1 uses strategy1). A strategy is a function that, given a player's score and their opponent's score, returns the number of dice that the current player will roll in the turn. An example strategy is always_roll_5 which appears below play.

If any player achieves the goal score by the end of their turn, i.e. after all applicable rules have been applied, the game ends.

Important:

For the user interface to work, a strategy function should be called only once per turn. Only call strategy0 when it is Player 0's turn and only call strategy1 when it is Player 1's turn.

Hints:

  • You should call the functions you have implemented already.
  • If who is the current player, the next player is 1 - who.

Before writing any code, unlock the tests to verify your understanding of the question.

$ python ok -q 05 -u

Once you are done unlocking, begin implementing your solution. You can check your correctness with:

$ python ok -q 05

Once you are finished, you will be able to play a graphical version of the game. We have provided a file called hog_gui.py that you can run from the terminal:

$ python hog_gui.py

You can exit the gui by typing Ctrl + C from terminal.

The GUI relies on your implementation, so if you have any bugs in your code, they will be reflected in the GUI. This means you can also use the GUI as a debugging tool; however, it's better to run the tests first.

Congratulations! You have finished Phase 1 of this project!

Phase 2: Strategies

In this phase, you will experiment with ways to improve upon the basic strategy of always rolling five dice. A strategy is a function that takes two arguments: the current player's score and their opponent's score. It returns the number of dice the player will roll, which can be from 0 to 10 (inclusive).

Problem 6 (200pts)

Implement always_roll, a higher-order function that takes a number of dice n and returns a strategy that always rolls n dice. Thus, always_roll(5) would be equivalent to always_roll_5.

Before writing any code, unlock the tests to verify your understanding of the question:

$ python ok -q 06 -u

Once you are done unlocking, begin implementing your solution. You can check your correctness with:

$ python ok -q 06

Problem 7 (200pts)

A pure strategy only has a fixed number of possible argument values. In a game to 100, there are 100 possible score values (0-99) and 100 possible opponent_score values (0-99), giving 10,000 possible argument combinations.

Implement is_always_roll, which takes a pure strategy and returns whether that strategy always rolls the same number of dice for every possible argument combination.

Before writing any code, unlock the tests to verify your understanding of the question:

$ python ok -q 07 -u

Once you are done unlocking, begin implementing your solution. You can check your correctness with:

$ python ok -q 07

Problem 8 (200pts)

Implement make_averaged, which is a higher-order function that takes a function original_function as an argument.

The return value of make_averaged is a function that takes in the same number of arguments as original_function. When we call this returned function on the arguments, it will return the average value of repeatedly calling original_function on the arguments passed in.

Specifically, this function should call original_function a total of total_samples times and return the average of the results of these calls.

Important: To implement this function, you will need to use a new piece of Python syntax. We would like to write a function that accepts an arbitrary number of arguments, and then calls another function using exactly those arguments. Here's how it works.

Instead of listing formal parameters for a function, you can write *args, which represents all of the arguments that get passed into the function. We can then call another function with these same arguments by passing these *args into this other function. For example:

>>> def printed(f):
...     def print_and_return(*args):
...         result = f(*args)
...         print('Result:', result)
...         return result
...     return print_and_return
>>> printed_pow = printed(pow)
>>> printed_pow(2, 8)
Result: 256
256
>>> printed_abs = printed(abs)
>>> printed_abs(-10)
Result: 10
10

Here, we can pass any number of arguments into print_and_return via the *args syntax. We can also use *args inside our print_and_return function to make another function call with the same arguments.

Before writing any code, unlock the tests to verify your understanding of the question:

$ python ok -q 08 -u

Once you are done unlocking, begin implementing your solution. You can check your correctness with:

$ python ok -q 08

Problem 9 (200pts)

Implement max_scoring_num_rolls, which runs an experiment to determine the number of rolls (from 1 to 10) that gives the maximum average score for a turn. Your implementation should use make_averaged and roll_dice.

If two numbers of rolls are tied for the maximum average score, return the lower number. For example, if both 3 and 6 achieve a maximum average score, return 3.

You might find it useful to read the doctest and the example shown in the doctest for this problem before doing the unlocking test.

Important: In order to pass all of our tests, please make sure that you are testing dice rolls starting from 1 going up to 10, rather than from 10 to 1.

Before writing any code, unlock the tests to verify your understanding of the question:

$ python ok -q 09 -u

Once you are done unlocking, begin implementing your solution. You can check your correctness with:

$ python ok -q 09

The provided run_experiments function calls max_scoring_num_rolls(six_sided) and prints the result. You will likely find that rolling 6 dice maximizes the result of roll_dice using six-sided dice.

To call this function and see the result, run hog.py with the -r flag:

$ python hog.py -r

In addition, run_experiments compares various strategies to always_roll(6). You are welcome to change the implementation of run_experiments as you wish. Note that running experiments with picky_strategy and swine_strategy will not have accurate results until you implement them in the next two problems.

Some of the experiments may take up to a minute to run. You can always reduce the number of trials in your call to make_averaged to speed up experiments.

Running experiments won't affect your score on the project.

Problem 10 (200pts)

注意：下载的代码中，Problem 10和 Problem 11的代码都包含一行assert False，这是因为hog_gui.py可能会调用这些函数，而调用没实现的代码可能会产生莫名其妙的错误。请在编写完自己的代码前将这行代码删除，不然你编写的代码会无法运行。

A strategy can try to take advantage of the Picky Piggy rule by rolling 0 when it is most beneficial to do so. Implement picky_strategy, which returns 0 whenever rolling 0 would give at least threshold points and returns num_rolls otherwise. This strategy should not also take into account the Swine Swap rule.

Hint: You can use the function picky_piggy you defined in Problem 2.

Before writing any code, unlock the tests to verify your understanding of the question.

$ python ok -q 10 -u

Once you are done unlocking, begin implementing your solution. You can check your correctness with:

$ python ok -q 10

Once you have implemented this strategy, change run_experiments to evaluate your new strategy against the baseline. Is this strategy an improvement over the baseline?

Problem 11 (200pts)

A strategy can also take advantage of the Swine Swap rules. Implement swine_strategy, which returns 0 if rolling 0 dices gives the player at least threshold points in this turn. In other cases, the strategy rolls num_rolls.

Before writing any code, unlock the tests to verify your understanding of the question.

$ python ok -q 11 -u

Once you are done unlocking, begin implementing your solution. You can check your correctness with:

$ python ok -q 11

Once you have implemented this strategy, update run_experiments to evaluate your new strategy against the baseline.

Problem 12 (0pts)

Implement final_strategy, which combines these ideas and any other ideas you have to achieve a high win rate against the baseline strategy. Some suggestions:

  • picky_strategy or swine_strategy are default strategies you can start with.
  • If you know the goal score (by default it is 100), there's no point in scoring more than the goal. Check whether you can win by rolling 0, 1 or 2 dice. If you are in the lead, you might decide to take fewer risks.
  • Choose the num_rolls and threshold arguments carefully.
  • Take the action that is most likely to win the game.

You can check that your final strategy is valid by running ok.

$ python ok -q 12

You can also play against your final strategy with the graphical user interface:

$ python hog_gui.py

Project Submission

Run ok on all problems to make sure all tests are unlocked and pass:

$ python ok

You can also check your score on each part of the project:

$ python ok --score

Once you are satisfied, submit to complete the project.

$ python ok --submit

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

If you haven't already, relax and enjoy a few games of Hog with a friend.