Lab: Probability in Games

In this lab, you will use counting and probability to make informed decisions when playing games.

Instructions

You should complete this lab in a group of two to four. If you have a favorite board game or card game, consider bringing it to lab. Otherwise, we will use games from the board game library (located on the 2nd floor).

Step 1: Choose a Game

Choose a board game or card game for your team to analyze. Your are welcome to choose a game you are familiar with. The game must include a mix of:

• Skill: players must be able to make decisions that will affect the game’s outcome
• Randomness: dice, coin-flips, drawing from a shuffled deck, etc.

For example, you cannot choose chess, since it doesn’t include randomness. You also cannot choose Candy Land, since the outcome is completely determined by the cards, meaning there is no skill involved.

Next, familiarize yourselves with the rules, and start playing the game. As you play, take note of situations where understanding the probability of different outcomes would be helpful. Spend about 10 minutes playing the game.

Note: If you are playing with a standard deck of cards, you can refer to Bicycle’s guides, which are available online and in an iOS app.

Step 2: Analyze Probabilities

Next, analyze a situation where different outcomes are possible. You should restate the relevant rules, describe the game state, calculate probabilities, and decide what move to make.

If necessary, you can simplify your analysis, in which case you should explain the limitations of your analysis.

Example: Last Point in King of Tokyo

• Game: King of Tokyo
• Rules: To earn points, you must roll at least three 1s, 2s, or 3s. Dice have six sides: 1, 2, 3, heal, punch, energy. When you roll the dice, you can decide which dice to keep, and which to reroll. You are allowed up to two rerolls. To win the game, you must be the first player to 20 points.
• Game state: It is my turn, and I have 19 points, so I need just one more point to win. My initial roll:

• Strategies, and their probabilities:
  • Keep the 2s, and reroll the remaining four dice?
    • When I roll a die, it has a $\frac{5}{6}$ probability of not being a 2.
    • I can roll the remaining four dice twice each. The probability of getting no 2s in eight rolls is: $\left(\frac{5}{6}\right)^8$
    • So the probability of getting at least one 2 is: $1 - \left(\frac{5}{6}\right)^8 \approx 77\%$
  • Keep the 1s and 2s, and reroll the remaining two dice?
    • When I roll a die, it has a $\frac{4}{6}$ probability of not being a 1 or 2.
    • I can roll the remaining two dice twice each. The probability of getting no 1s or 2s in four rolls is: $\left(\frac{4}{6}\right)^4$
    • So the probability of getting at least one 1 or 2 is: $1 - \left(\frac{4}{6}\right)^4 \approx 80\%$
• Limitations: Using the first strategy, it is also possible to win by rolling at least three 1s or 3s. So the first strategy is slightly better than my calculations show.
• Decision: The probabilities are very close. As described below, I used a Monte Carlo simulation to confirm that the second strategy maximizes my chance of winning.

Optional: Monte Carlo Simulation

In cases where it is challenging to calculate probabilities, it may be easier to run simulations. This is known as the Monte Carlo method. Simulations are also useful for double-checking your math. For example, simulate.py simulates the King of Tokyo scenario described above, but also accounts for the edge-case described under “Limitations.”

> python simulate.py --n-simulations 100000
Keep twos strategy won: 79.2%
Keep ones and twos strategy won: 80.1%

If you have time, design a simulation to augment your analysis.

Submit

Create a single document with your team, and upload it to Gradescope. Upload the document once, and add your teammates to the submission. For full credit, you must:

• Write one analysis for each teammate. For example, a team of four should submit four analyses.
• Each analysis should follow the analysis template below

Analysis Template

• Rules:
• Game state:
• Strategies, and their probabilities:
• Limitations:
• Decision:

Learning Goals

• Analyze games using counting and probabilities
• Simulate outcomes using the Monte Carlo method