Nice Dice in Haskell

Carrying on my theme of (board/card) game design, I recently wanted to play around with probabilities and dice. I wanted to find out the frequencies of the outcomes for various combinations of dice, and things like the probability of getting a repeated result on that combination. I began to envisage a neat way to represent dice in Haskell — and then a quick google led to discovering that the representation had already been thought of, published and released on Hackage. That saves a fair bit of work, at least. I lightly wrapped the probability library with the API that I wanted, and just released my game-probability library/EDSL on Hackage. The library has documentation and examples; I will focus more on looking at the design rationale in this post.

The Dice API

The central type is EventM a, which is a probabilistic event with outcomes of type a: each EventM a contains one or more outcomes of type a, each with an associated probability stored as a Rational. That means we get exact fractions, so 1/6th really is stored as 1/6th, not the nearest approximation that a Double can manage. For those who are interested in how EventM relates to the underlying probability library, it builds on the data-type from Numeric.Probability.Distribution:

import Numeric.Probability.Distribution (T, decons, norm, uniform)

newtype EventM a = EventM (T Rational a)

type DieRoll = EventM Int

With the aid of a helper function we can immediately define lots of standard dice:

makeEvent :: [a] -> EventM a
makeEvent = EventM . uniform

d4, d6, d8, z10, d10, d12, d20, d100 :: DieRoll
d4 = makeEvent [1..4]
d6 = makeEvent [1..6]
d8 = makeEvent [1..8]
z10 = makeEvent [0..9]
d10 = makeEvent [1..10]
d12 = makeEvent [1..12]
d20 = makeEvent [1..20]
d100 = makeEvent [1..100]

For those who don’t know their dice, d6 is a standard abbreviation for a 6-sided die. d10s have 0 to 9 written on the faces, and depending on the game the zero may either be read as 0 or as 10: d10 is the 1-10 interpretation, while z10 is the 0-9 interpretation. This is consistent with dice notation (wikipedia really does have a page for everything!).

When you try to show a die you get a faithful but not super-readable representation of a die:

> d6
fromFreqs [(1,1 % 6),(2,1 % 6),(3,1 % 6),(4,1 % 6),(5,1 % 6),(6,1 % 6)]

We can improve on that by customising the Show instance for our EventM wrapper. What would be really nice is a more visual representation of the chances associated with each event. To that end, I’ve chosen to display a horizontal bar-chart of outcomes with their associated probabilities. We find a common denominator for all the different probabilities, scale them up to integers and print them out with the corresponding bars. Now when we ask to see a die, we get a nicer visualisation:

> d6
1: #
2: #
3: #
4: #
5: #
6: #

Of course all the standard dice above have an equal chance of getting each number, so they’re quite dull. What we really want it for is more complex combinations, like for example the sum of a d4 and a d6:

> d4 + d6
2 : #
3 : ##
4 : ###
5 : ####
6 : ####
7 : ####
8 : ###
9 : ##
10: #

Note that we added two dice together there! The DieRoll type has a Num instance which allows dice to be added together. Intuitively, adding two dice adds their outcomes, and works out the corresponding probability for each summed outcome. We’ll come back to the details of the Num instance later, but we can also add constant factors to the dice:

> d4 + 1
2: #
3: #
4: #
5: #

And we can multiply by a constant:

> d6 * 2
2 : #
4 : #
6 : #
8 : #
10: #
12: #

Note that 2 * d6 is the same as d6 + d6, while d6 * 2 scales the outcome of the d6 by 2. So multiplication of dice is not commutative! This fits with how dice are usually written, and saves some confusion at the expense of causing other confusion (we’ll come back to this aspect later as well):

> 2 * d6
2 : #
3 : ##
4 : ###
5 : ####
6 : #####
7 : ######
8 : #####
9 : ####
10: ###
11: ##
12: #

We can actually allow rolling of the dice using a small roll :: DieRoll -> IO Int function:

> replicateM 10 (roll d6) 
[6,5,6,2,5,5,2,3,5,3]

With a little bit of point-free Haskell (which I’ll leave you to dig through if you’re interested) we can check that the frequencies roughly pan out if we roll lots of times:

> map (head &&& length) . group . sort <$> replicateM 10000 (roll d6)
[(1,1701),(2,1681),(3,1669),(4,1619),(5,1667),(6,1663)]

So that sorts out rolling the dice. However, the benefit of a reified probability representation is that we can also perform queries on the resulting distributions.

Equality

A DieRoll stores probabilities associated with each outcome. We can use these to prove equality of different dice rolls. A simple example:

> d6 + d6 + d6 == 3 * d6
True

Returning to our earlier mention of d10 and z10, one way to get from a z10 to a d10 is simply to add one to the former:

> z10 + 1 == d10
True

That’s not actually the way we tend to map between the two with real dice, though. We’ll define a handy helper function, subst, which changes one specific outcome to another, and use this to show that reading a 0 on the low die as a 10 accomplishes the same effect:

subst :: Eq a => a -> a -> EventM a -> EventM a
subst tgt rep = fmap (\x -> if x == tgt then rep else x)

> replace 0 10 z10 == d10
True

We can also check various ways for converting two d10/z10 to a d100, for example:

> z10 * 10 + d10 == d100
True
> subst 0 100 (z10 * 10 + z10) == d100
True

Further Queries

As well as checking equality of the entire roll, we can query specific probabilities. The chancePred function checks the chance of a particular predicate being satisfied:

> chancePred (>= 16) (3*d6)
5 % 108

So 5/108 chance of getting 16 or higher when rolling 3 six-sided dice. You can use the similar function chanceRel to check the chance that a particular relation between two events is satisfied. For example, you might want to know the chance of a d20 beating 3d6:

> chanceRel (>) d20 (3*d6)
19 % 40

The Full Monad

EventM is a monad (and functor and applicative functor, of course). This means you can perform all sorts of complicated combinations of dice — for example, if you want to prototype a game involving dice, you can write your rules in Haskell and see the chances of various outcomes. To demonstrate this, I’m going to borrow an example from the library documentation. Bonus points if you spot which game this comes from without looking at the library docs.

You roll a given number of 10-sided dice, rolling one extra die for every 10 you score if you are specialised in that skill. The number of 1s on the original roll are subtracted from the total number of dice that equal or exceed the difficulty target:

successes :: Int -> Int -> Bool -> EventM Int
successes target dice specialised
   = do initial <- replicateM dice d10
        extra <- if specialised
                   then replicateM (count (== 10) initial) d10
                   else return []
        return (count (>= target) (initial ++ extra) - count (== 1) initial)
   where
     count f xs = length (filter f xs)

The exact mechanics of that system caused much dispute back in the day with other players. I still may not have it correct now, but I can tell you that an unambiguous description like the above would have prevented much confusion! I wonder if we could get all game-writers to write down their intricate dice-based systems in Haskell.

The Inner Workings — Num

Finally, I’ll explain the inner workings of the probability type. You can think of EventM a as being a synonym for Map a Rational, where the Rational type represents a probability as explained earlier. (Due to some problems with type-class constraints, it has to be held in a list, but same idea.) We can imagine fromList and toList functions (like those for Map) to help us in this section:

toList :: EventM a -> [(a, Rational)]
fromList :: [(a, Rational)] -> EventM a

We’ll assume that fromList adds the probabilities associated with any duplicates in the list, i.e. it acts like Map.fromListWith (+). Armed with these, I’ll explore the Num instance for EventM Int (aka DieRoll).

Addition and subtraction

Let’s start with: what does it mean to add two dice? Each combination of the two dice must have their probabilities multiplied, with their outcomes added, and any duplicate outcomes (e.g. 1 and 6 gives the same outcome as 2 and 5) must be added together at the end (which we’ve said fromList will do):

addDice :: DieRoll -> DieRoll -> DieRoll
addDice a b = fromList [(ax+bx, ap*bp) | (ax,ap)<-toList a, (bx,bp)<-toList b]

Subtracting one die from another is trivially similar. So how do we add constants to a die? Well, one way to do it — and perhaps in a sense the most obvious way — is to use EventM’s functor instance. Using fmap on EventM a applies a pure function to all the outcomes of the die, so fmap (+3) would add the constant value 3 to each outcome. However, there is another way. We can convert 3 to a die by making it a certain outcome:

certain:: a -> EventM a
certain x = fromList [(x, 1)]

So every time you roll the “die” certain 3, it will come up with a 3 (talk about a loaded die!) Now think about the result of addDice (certain 3) d; all the probabilities of the second die will be multiplied by 1, leaving them untouched, while the outcomes will have 3 added to them: exactly the effect we wanted. So hopefully you can see that we can form a Num instance for our dice (which we’ve used throughout this post), where (+) = addDice, negate = fmap negate, and fromInteger = certain . fromInteger. But what about multiplication?

Multiplication

From a user’s perspective, multiplication of, say, 2 and d6 could be taken to mean one of two things — either: roll one d6 and multiply all outcomes by two, or: roll two d6 and add them together. We can implement the former using our certain function and a trivial modification to addDice:

multDice :: DieRoll -> DieRoll -> DieRoll
multDice a b = fromList [(ax*bx, ap*bp) | (ax,ap)<-toList a, (bx,bp)<- toList b]

It should be obvious from the definition that this function is commutative. multDice (certain 2) d6 multiplies all outcomes of the d6 by 2, and multDice d6 (certain 2) does the same. multDice (certain 3) (certain 4) is the certain outcome 12, and multDice d4 d4 rolls two d4 and multiplies their outcomes, giving this interesting distribution:

1 : #
2 : ##
3 : ##
4 : ###
6 : ##
8 : ##
9 : #
12: ##
16: #

The multDice function is a consistent, commutative definition of multiplication. But it holds a hidden surprise for the user if we use this for our definition of (*): 2 * d6 is not the same as d6 + d6! The former doubles the outcome of one d6 (if we use multDice), whereas the latter adds the outcomes of two d6. I think this is sufficiently surprising that it is worth exploring the other alternative: what if we define a function that takes its first argument and rolls that many of its second argument (summing the outcomes):

rollN :: DieRoll -> DieRoll -> DieRoll
rollN a b = do n <- a
               sum <$> replicateM n b

That uses the monad instance, which I haven’t got into much in this post, but hopefully its meaning is clear: find out the result of the first die roll, then roll that many of the second die, summing the results. We can work out that rollN (certain 2) d6 is the same as d6 + d6. What do you think the result will be of rollN d6 (certain 2)? Well, we roll the d6, then that many times we receive the certain outcome 2, and add all these together… which means we effectively scale the d6 result by 2 — the other behaviour we were using earlier! rollN (certain 3) (certain 4) is still the certain outcome 12, while rollN d4 d4 rolls one d4 to determine how many further d4 to roll, giving a rather complex distribution!

This rollN function has a nice parallel to dice notation where 2d6 means roll two d6, whereas d6 * 2 means double the result of a single d6. So even though it’s not commutative, I prefer this multiplication operator for our dice EDSL. (I believe that rollN is associative, but I don’t have a proof for this.) So (*) = rollN in my library, as being the most useful of two potentially-confusing options. The documentation tries to make clear how it works.

Summary

The library/EDSL is up on Hackage now for you to experiment with. I mainly intend it to be played with using ghci or small Haskell files for experimenting with dice combinations and calculating odds, but there’s nothing stopping it being used for concisely specified actual dice in some RPG-related program. The library uses some functionality from the the probability library developed by Martin Erwig, Steve Kollmansberger and maintaing by Henning Thielemann. The title of this post no doubt invites disagreement, but I couldn’t resist the rhyme.