Assignment 1: Holy Craps! (30 marks)

Due Date: Thursday, January 30, 2019 (11:59pm)

The purpose of this assignment is to gain experience with experimental methods, analytical methods, and simulation methods as used in computer systems performance evaluation. You will do so in the context of a simple casino game called Craps.

Background

Craps is a simple dice game that is popular in casinos around the world. It uses two six-sided dice, which are rolled one or more times in succession to determine the outcome of the game (win or lose) based on the sum of the dice values rolled.

The rules for Craps are extremely simple. If the opening roll by a player is 7 or 11, then the player wins. If the opening roll is 2, 3, or 12, then the player loses. If any other value occurs during the opening roll, then this value is recorded as the point value, which becomes the target value for subsequent rolls. The goal of the player is then to roll the target point value again, before rolling a 7. If they roll the point value, then they win, but if they roll a 7, they lose. If any other value is rolled, it is ignored, and the game continues with successive rolls until either the point value (win) or a 7 (lose) occur. Note that a game of Craps requires at least one roll of the dice, but might need many more rolls to determine the final outcome of the game.

There are several aspects of the Craps game that make it appealing. First, it is an extremely simple game of chance that is easy to learn and understand, with minimal or no strategy involved. Second, it is well-suited for wagering, both by players themselves (i.e., betting that they will win) and by spectators (i.e., betting whether the player will win or lose). Third, and perhaps most important, the winning probablity is ≈ 0.493. These odds are much better than most casino games, and tantalizingly close to the 50% level at which a player could expect to break even (or win) in the long run. In short, the odds are still in favour of the casino, but not by much.

The latter observation is the primary motivation for this assignment. In particular, we are interested in finding out how much cheating is required in order to turn the odds in favour of the Craps player, rather than the casino. More specifically, we consider the possibility of loaded dice, which are biased to produce certain roll outcomes slightly more frequently than expected with fair dice.

Your Task

Your task in this assignment is to use your skills as a performance analyst to answer the following questions about how best to cheat at Craps:

• If biased dice are used, which outcomes are preferable?
• Should both dice be biased, or only one?
• If two biased dice are used, should they have homogenous bias to the same preferred outcome, or should they be different?
• What is the minimal level of cheating (i.e., bias level) required in order to achieve a 50% winning probability?

You will do so using three different performance evaluation methodologies, namely experimentation, mathematical modeling, and simulation modeling. Each approach is worth 10 marks, and you can do them in any order, since they are largely independent of each other.

For the experimental component of the assignment (10 marks), please do the following:

• (1 mark) Borrow the "big dice" from Carey, roll it randomly exactly 120 times (no more, and no less!), and record the outcome from each roll (in order) in a file. Email this file to Carey as soon as it is ready, making sure to indicate that it is for the big dice.
• (1 mark) Borrow the "small dice" from Carey, and repeat the same experiments, recording (in order) the outcome of each of the 120 random rolls into a file. Email this file to Carey as soon as it is ready, making sure to indicate that it is for the small dice.
• (2 marks) Use your own empirical data to estimate the probability of winning at Craps. You can do so either by manually analyzing your data files, or by writing a simple program to process your data files. Start by reading one roll from each file ("big" and "small"), and then applying the rules of Craps, and using as many additional rolls as needed from the file until each game is complete. Your data should be sufficient for 30-40 games of Craps. State the empirically observed winning probability on your sample data.
• (2 marks) Formulate the null hypothesis that the big dice is fair, and conduct some statistical analysis on your big dice data set to either accept or reject this hypothesis. Some tests you might consider are mean, variance, chi-square, scatterplot, run lengths, and autocorrelation. State the conclusion from your tests, with justification based on the empirical evidence.
• (2 marks) Repeat similar tests to see if the small dice is fair. State the conclusions from your tests, with justification.
• (2 marks) Obtain from the course Web site the class data set with the dice rolls from all students in CPSC 641. Repeat your tests to see if the big dice (N=8x120=960) is fair, and if the small dice (N=8x120=960) is fair. State the conclusions from your tests, giving justifications as needed.

For the analytical component of the assignment (10 marks), please do the following:

• (3 marks) Construct a Markov chain (somewhat analagous to a finite state machine from theoretical CS courses) to represent the states and state transitions involved in a game of Craps with fair dice. Label the arcs with probabilities. Simplify the Markov chain as you deem appropriate, making sure to identify merged states, as well as absorbing states (if any). Use your Markov chain to estimate the winning probability for Craps. State any observations or insights that you have about this Markov chain.
• (3 marks) Construct a Markov chain to represent the game of Craps with a single biased dice. In particular, consider a dice that has probability p (where 0 ≤ p ≤ 1) of landing on value v (where v ∈ {1, 2, 3, 4, 5, 6}) and probability q=(1-p)/5 for each of the other possible face values. Label the arcs with probabilities. Again, simplify the Markov chain as you deem appropriate. Then use your Markov chain to estimate the winning probability for Craps as a function of p and v. State any observations or insights that you have about this Markov chain, and its differences (if any) from the previous Markov chain.
• (4 marks) Construct a Markov chain to represent the game of Craps with two homogeneous biased dice. In particular, consider the biased dice model described above, but for which the two dice are configured the same. That is, the p and v values for the big dice are the same as those for the small dice. Label the arcs with probabilities, and simplify the Markov chain as you deem appropriate. Then use your Markov chain to estimate the winning probability for Craps as a function of p and v. State any observations or insights that you have about this Markov chain, and its differences (if any) from the (most recent) previous Markov chain.

For the simulation component of the assignment (10 marks), please do the following:

• (3 marks) Write a simulation model of the Craps dice game, using a programming language of your choice (e.g., C, C++, Java, Python, Matlab). You can do so either as a Monte Carlo simulation, or as a discrete-event simulation (your choice). Assume fair dice in your initial implementation. You should also design your simulation to use either trace files as input (for small runs), or the built-in pseudo-random number generator (PRNG) as input (for long runs).
• (1 mark) Run your simulation in trace-driven mode using your own empirical "big" and "small" dice roll data files as input. Validate your simulation results against your earlier experimental results.
• (1 mark) Run your simulation in trace-driven mode using the class data files for "big" and "small" dice rolls as input. Compare these simulation results with your earlier experimental estimate.
• (1 mark) Run your simulation in PRNG mode to simulate 1,000,000 games of Craps with fair dice. Compare these simulation results with the known analytical results for Craps.
• (4 marks) Extend your simulation to model biased dice, and then run it in PRNG mode to simulate 1,000,000 games of Craps with biased dice. Use either one or two biased dice, depending on your analytical results, and choose values of p and v for each dice that you deem appropriate. Use your simulation to identify settings that provide winning probabilities at or above 50%, with as little cheating as possible. Use your results to answer the four questions posed near the beginning of the assignment description (Your Task).

Optional Bonus (3 marks)

Construct a Markov chain to represent the game of Craps with two heterogeneous biased dice. In particular, consider the same biased dice model as described above, but for which the two dice are independent. That is, the p and v values for the big dice could be different from those for the small dice. Label the arcs with probabilities, and simplify the Markov chain as you deem appropriate. Then use your Markov chain to estimate the winning probability for Craps as a function of p and v. State any observations or insights that you have about this Markov chain, and its differences (if any) from the Markov chain for two homogeneous biased dice. Feel free to use your simulation to validate your analytical results.

Assignment Submission

When you are finished, please submit your assignment solution in hardcopy form to your instructor, on or before the stated deadline.