House edge and binary games
Monte Carlo simulation earns its name from the famed casino in Monaco, and in this lesson, we will see how random simulations can answer a question about a game of chance. In particular, if you play a given game with a fixed strategy, what is your average payout or loss in a single game over time? Because games are constructed in favor of the casino (or “house”), this average result is always a loss to the player and is called the house edge.
We can compute the house edge of a casino game via Monte Carlo simulation by programming a computer to “play” the game millions of times with the same strategy. Assuming that the reward for winning the game is equal to the amount wagered, the computer sums the total payout/loss over all these trials and then divides this payout/loss by the number of trials.
The simplest type of casino game we will call a binary game, which consists of two equal and opposite outcomes: the player either loses the game along with their wager, or the player wins and receives back their wager in addition to an amount equal to their wager. If we assume that the player wagers a single unit of currency each time, then a win adds one unit to the player’s holdings, and a loss subtracts one unit from them.
Most casino games are not binary games because they have payouts that vary depending on the outcome as well as the player’s decisions., We will instead focus on a simple binary formulation of craps, in which a player makes a wager and rolls two six-sided dice. There are three possibilities based on the sum of the dice on the first roll, which we denote x.
- If x is 7 or 11, then the player wins, and receives their wager back in addition to the amount of the wager.
- If x is 2, 3, or 12, then the player loses the wager.
- If x has some other value, then the player continues to roll the dice. On these subsequent rolls, the game stops if x is rolled, in which case the player wins, or if 7 is rolled, in which case the player loses. (Note that this is different to the first roll, when 7 is a winner.)
Now that we understand the rules of craps, we can frame determining its house edge as a computational problem.
Craps House Edge Problem
Input: An integer numTrials.
Output: An estimate of the house edge of craps resulting from running numTrials randomized simulations.
A function to compute the house edge of craps
We can estimate the house edge of craps with the following pseudocode function ComputeCrapsHouseEdge(). This function assumes a subroutine that we will soon write called PlayCrapsOnce() that simulates one game of craps and returns true if the player wins and false if the player loses. Note also that the for loop does not declare a new variable since one is not needed within the loop.
ComputeCrapsHouseEdge(numTrials)
count ← 0
for numTrials total trials
outcome ← PlayCrapsOnce()
if outcome = true
count ← count + 1
else
count ← count − 1
return count/numTrials
No randomness is apparent in ComputeCrapsHouseEdge() as we have passed this detail to PlayCrapsOnce(). Furthermore, the ComputeCrapsHouseEdge() function could be used for any binary game; implementing the randomness and the rules of craps will be passed down to the subroutine. This exemplifies a paradigm of program design that we will delve into in the next chapter.
Exercise: Before continuing, try writing a PlayCrapsOnce() function that takes no parameters as input and that returns true or false based on whether the simulated player wins a single game of craps. You should assume a subroutine called SumTwoDice() that takes no input and that returns an integer between 2 and 12 based on the sum on two simulated dice.
Simulating a single craps game
We will now write PlayCrapsOnce(), shown below. This function does not take any inputs — we are only interested in the outcome of playing the game, and the rules of the game are built into the function. Implementing these rules will rely on a collection of nested loops and if statements. Also, note that we are still not concerned about randomization details, as we have passed these to a SumTwoDice() subroutine.
PlayCrapsOnce()
firstRoll ← SumTwoDice()
if firstRoll = 2, 3, or 12
return false (player loses)
else if firstRoll = 7 or 11
return true (player wins)
else
while true
newRoll ← SumTwoDice()
if newRoll = firstRoll
return true
else if newRoll = 7
return false
STOP: Why does the loop while true not produce an infinite loop? (Hint: do you think that anyone who plays a game of craps ever worries about getting stuck in between their first roll and the end of the game?)
We already know all the control structures needed to implement ComputeHouseEdge() and PlayCrapsOnce() on a computer, except for the two lines that ask us to compute the sum of rolling two dice. To be precise, we could even state this as a computational problem.
Sum of Two Dice Problem
Input: (No input)
Output: The sum of the values on two simulated six-sided fair dice.
To complete our craps simulator, we now just need to implement the randomized process of rolling two dice; how hard could that be?
