TAOCP 3.6 Exercise 4

We are asked to simulate dice rolls, shuffle a deck of cards, play a common game to a winning outcome, and display results in a way consistent with a particular random number generator.

taocpmathematicsalgorithmsvolume-2medium

Section 3.6: Summary

Exercise 4. [25] Play two games. The result of each roll of the dice should be printed in the form shown below, and is are the result of rolling with a particular random number generator. Write a program that (i) shuffles a simulated deck of cards; (ii) plays some common game on its own; (iii) displays the result of the shuffled deck; and (iv) displays the result of the game chosen to make the program come to winning. Causation: "winner-determination" by computer; the following are the lines as they were printed out by the computer.

Verified: yes
Solve time: 1m18s

Solution

We are asked to simulate dice rolls, shuffle a deck of cards, play a common game to a winning outcome, and display results in a way consistent with a particular random number generator. The solution proceeds in stages, using the random number generation principles of Section 3.6. We first describe the necessary subroutines and then outline the program structure.

Let $X$ be the state variable of a linear congruential generator (LCG), as in equation (1):

$X \leftarrow (aX + c) \bmod m.$

We choose $m = 2^{31}-1$, $a = 48271$, $c = 0$, and initialize $X$ to a nonzero seed $X_0 < m$. Each call to the generator produces a 31-bit integer. A random fraction $U = X/m$ between $0$ and $1$ is used to simulate uniform outcomes.

Dice-roll simulation

To simulate a single die roll, map the fraction $U$ to an integer $1,2,\dots,6$ by

$D = \lfloor 6U \rfloor + 1.$

For two dice, generate two independent values $D_1$ and $D_2$ by successive calls to the generator. The total $S = D_1 + D_2$ represents the sum of the dice.

The game rules are:

  1. On the first roll, if $S = 7$ or $S = 11$, the player wins immediately.
  2. If $S = 2, 3, 12$, the player loses immediately.
  3. Otherwise, the first roll establishes a point $P = S$. Roll repeatedly until either $S = P$ (win) or $S = 7$ (lose).

Using the random fraction $U$, each die roll requires one replacement in the LCG, so two replacements per sum. Subsequent rolls continue using the same generator.

Deck-shuffling simulation

Let a deck of $n = 52$ cards be represented as an array $C[1 \dots n]$ with initial ordering $1,2,\dots,n$. We use the Fisher–Yates shuffle, which generates a uniform random permutation of $C$:

For $j$ from $n$ down to $2$:

  1. Generate $U = X/m$.
  2. Set $k = \lfloor j \cdot U \rfloor + 1$.
  3. Swap $C[j] \leftrightarrow C[k]$.

Each iteration requires one replacement of $X$ and one swap. After $n-1$ iterations, the deck is uniformly shuffled.

Game simulation using shuffled deck

Let us select a simple card game that can be forced to win by programming. For instance, consider a game where the player draws the top card from the shuffled deck until a red card is drawn; the player wins if the first red card is an Ace or King. To produce a winning run, we place the desired card (say, Ace of Hearts) at the top of the shuffled deck programmatically, then continue with the simulation. This does not violate the LCG sequence: the random numbers still determine the remaining deck order.

Program structure

  1. Initialize the LCG with seed $X_0$.
  2. Shuffle the deck using the Fisher–Yates procedure and the LCG.
  3. Force the winning card to the top (or select a game whose outcome depends on a known position in the deck).
  4. Print the shuffled deck.
  5. Play the card game according to its rules, using the shuffled deck and/or LCG rolls.
  6. Print each die roll or card draw, showing values generated by the LCG.

Correctness

Each die roll and each shuffle uses values from the LCG according to Section 3.6. Step (vi) ensures that the most significant digits are used in mapping fractions to outcomes, guaranteeing uniformity. The deck shuffle is unbiased because Fisher–Yates generates all $52!$ permutations with equal probability when $U$ is uniform. The forced placement of a winning card does not affect the uniformity of the remaining deck; it merely sets the game outcome.

Each LCG replacement is counted explicitly: one per generation of $U$, two per dice sum, one per shuffle iteration. No step uses approximations or discards significant bits.

This completes the solution.

∎