CS 451/LLC Lab 4: Dice and Discrete Probability Distributions

Let’s consider an example of a language with a simple product structure derived from the context of role-playing games, namely the language of dice rolls. In most games that make more than a passing use of dice (i.e., where different kinds and numbers of dice are used), dice rolls are indicated with a syntax like “2D6” or perhaps “3d6”, where a pair of numerals (representing natural numbers, i.e., non-negative integers) is provided, usually with a bit of punctuation between to indicate the particular interpretation as dice (here the letter “D”).

In games, the informal semantics of a dice roll specification is that one should pick up a certain number (the first numeral) of dice with a certain number of sides (the second numeral) and roll them together, adding up the pips on all the dice to get a total. Many modern games use dice with 4, 6, 8, 12 or 20 sides, since these correspond to the so-called Platonic solids, i.e., convex regular polyhedra (tetrahedron, cube, octahedron, dodecahedron and icosahedron). By combining different numbers of dice (usually, but not always, with the same number of sides) a variety of different “profiles” of results can be obtained, allowing game designers the ability to tailor the specification to a desired distribution of possible outcomes. In many role-playing games, certain dice roll combinations have gained an almost iconic status, for example the “3d6” often used to determine the defining physical and other play characteristics of new characters in the game.

But can we construe the semantics of the “language” of dice rolls more formally? We could try to capture randomness somehow, but there is a kind of non-determinism at play here, one which begs us to find a more holistic story: just as the meaning of a function is more than just the result of its call on a specific, individual value. When we roll those dice, we may get one of several outcomes (albeit still a discrete set of “crisp” alternatives). Furthermore, we also make a little “semantic abstraction”, in that we don't normally care about which die came up with which value, but rather only about their collective sum. So, for example, a roll of "3d6" will give us some (natural) number result between 3 and 18 inclusive; but it will also do so with varying probabilities. We can capture the meaning “as a whole” by considering the result to be a function ... and perhaps a little more. We can think of the results as a discrete probability distribution, or DPD.

Specifically, we can capture all the relevant information as a combination of the range of possible totals and a function from numbers within that range to a number result (the latter, in essence, the number of distinct possible combinations which would produce that argument number as a result of the throw). This suggests that we define a new datatype with a pair of components, one a natural number range and the other a function from numbers (well, numbers in that range) to number results, representing the combinations which will get us a particular number in a throw of the dice.

Now, we can't (easily, as beginners) put the restriction about the range of the results into a constraint about the domain of the function, but this is one reason for working with the range as part of the pair: we can at least dynamically, if not statically (as a part of the type) compute things of interest having to do with the range, for example, its size. Let’s agree that the function itself should return a 0 result for values outside the intended domain of the function; in fact, we can't yet easily restrict to just natural number arguments, so let's agree to return a 0 result for negative number inputs as well.

Another very useful thing is to be able to print out the DPD in a compelling, stylized fashion, say as a histogram, like this:

	3	*
	4	***
	5	******
	6	**********
	7	***************
	8	*********************
	9	*************************
	10	***************************
	11	***************************
	12	*************************
	13	*********************
	14	***************
	15	**********
	16	******
	17	***
	18	*
(Note that, if we didn't have information about the range stored as part of the structure of the DPD, we would have to at least go to some effort to discover for which values we should print a “bar” in the graph.)

In Haskell, we can make even have the system print such histograms as the “shown” results of a DPD value given as the result of computation: we just make the DPD type an instance of the Show class and provide a definition of a show (note: little “s”) function which turns any DPD into a String for display (the display above uses tabs and newlines in particular as pieces of the String result to this effect).

instance Show DPD where
  show = ...

We will probably (heh) also want to compute various things from a DPD, not the least of which might be a more standard probability (value between 0 and 1) for a result of a given magnitude. In fact, Haskell supports an exact rational number type (if we import the Ratio module at the top of our file) which we could use to express the sorts of exact rational probabilities we expect here (no “1-over-pi“ for us!). You can write rational numbers in Haskell (with the module loaded) in the form "n % m", where the percent sign was chosen (as a bit of culture-contextual sub-symbolic orthographic goodness) because of its similarity to the usual “slash” of fractions and computer-language division operators.

In fact, it's easy enough to generalize the idea of a (rational) probability away from the specifics of a particular number result to a predicate on numbers, so that we'll be able to inquire of a DPD: “What is the chance that I will get a result in the range 1-10?” or “What is the chance that I will roll an even number?” or “What is the chance I will get a number less than 5?” Each of these questions corresponds to a predicate, i.e., a function from numbers (say, Integers) to boolean results. Question: how do we determine how many possible roll results have the property and how many don't? How can we then determine the rational number probability of a roll meeting a given predicate?

Finally, you should also define an addition function on dice rolls (really: semantically on DPDs) so that you can merge together rolls of dice of different sizes, such as 2d6 `plus` 3d4. These tools, in combination, would allow a user (say a game designer) to explore the probability distributions associated with various combinations of dice of different sizes, interactively viewing the distributions themselves or testing various predicates to fit various game design goals.

Summary of requirements

In summary, you should write:

  1. A(n algebraic) datatype for DPDs (“discrete probability distributions”) built from pairs of intervals and functions. Intervals in turn should be pairs of numbers representing a range of possible values: you can declare a data type for these as well, if you wish, so that you can distinguish a range from some other pair of integers being used for a different purpose (e.g., ratios, complex numbers, etc.).
  2. A function which takes two integer values (a syntactic “dice roll”) and converts them into a DPD (say as roll :: Int -> Int -> DPD).
  3. A function which takes a predicate on integers and a DPD and computes the (discrete) probability of getting a result matching that predicate from a roll, perhaps sat :: (Int -> Bool) -> DPD -> Ratio Int (here "sat" is intended to abbreviate “satisfies”).
  4. A function which adds two discrete probability distributions together, so that dice rolls can be combined (perhaps plus :: DPD -> DPD -> DPD).
  5. A function and Show instance which converts a DPD into a histogram string for output, as shown above.