In the board game Shadespire by Games Workshop there are three types of faces on each die. Misses, successes and critical successes (“crits”). (The dice have many different symbols on the different faces but the context reduces it down to which symbols counts as misses and hits for a particular action.)
Opposed actions are determined by both sides rolling one or more dice, and first comparing crits. If one side has more crits, that side wins that action. If crits are tied (for example, neither side rolled any crits), then successes are compared.
We develop a fast, non-random way of calculating probabilities of a given outcome using a new data structure and two new operations.
We will use Chicken Scheme and the libraries srfi-42, numbers, and lookup-table.
(use srfi-42 numbers lookup-table)
The new data structure represents dice sets. It’s implemented with an alist where each entry is a result. The key to the entry is the outcome in the form of a three-element list with the of number of misses, number of successes, and number of critical success. The value of the entry is the probability for that outcome.
For example, a “swords” die has four misses, one success and one critical success.
It can be represented with the following alist.
;; M H C P
'(((1 0 0) . 2/3)
((0 1 0) . 1/6)
((0 0 1) . 1/6))
To quickly define the various dice, we implement and apply an implicitly renaming macro that injects the name of the dice into the REPL environment. We can take advantage of the facts that each die used has exactly six sides, and exactly one of those sides is a critical success, to simplify our code to only require one single-digit number in order to fully specify a die. For example, a shield die has two successes, and it follows that it also has three misses and one critical success.
(define (actionize . lis)
`(((1 0 0) . ,(/ (first lis) 6))
((0 1 0) . ,(/ (second lis) 6))
((0 0 1) . ,(/ (third lis) 6))))
(define-syntax define-with-hits
(ir-macro-transformer
(lambda (f i c)
`(begin
,@(map (lambda (x) `(define ,(i x) ',(actionize (- 5 (cadr f)) (cadr f) 1))) (cddr f))))))
(define-with-hits 1
swords
dodge)
(define-with-hits 2
hammers
supported-swords
shield
supported-dodge)
(define-with-hits 3
both
double-supported-swords
supported-hammers
guard
supported-shield
double-supported-dodge)
(define-with-hits 4
double-supported-hammers
supported-both
supported-guard
double-supported-shield)
(define-with-hits 5
double-supported-both
double-supported-guard)
In the game, multiple dice on each side are often rolled. For example, three sword dice versus two dodge dice.
To represent these sets of dice, we implement a combine operator.
The combination of two sword dice look like this:
'(((0 0 2) . 1/36)
((0 1 1) . 1/18)
((0 2 0) . 1/36)
((1 0 1) . 2/9)
((1 1 0) . 2/9)
((2 0 0) . 4/9))
In other words, there’s a 1 out of 36 chance that both dice roll a critical success, and a 4 out of 9 chance that both dice roll a miss.
Our prototype implementation used a list comprehension to compare and combine two die outcomes.
;; Not final
(define (combine A B)
(if B
(list-ec (: ra A) (: rb B)
(cons
(map + (car ra) (car rb))
(* (cdr ra) (cdr rb))))
A))
All nine combinations of the three respective outcomes on die A and die B are combined into one list. For each combination, the results are added and the probability of those results are multiplied.
'(((2 0 0) . 4/9)
((1 1 0) . 1/9)
((1 0 1) . 1/9)
((1 1 0) . 1/9)
((0 2 0) . 1/36)
((0 1 1) . 1/36)
((1 0 1) . 1/9)
((0 1 1) . 1/36)
((0 0 2) . 1/36))
The output is itself represented by the same dice set data structure and can therefore be further combined with other dice sets. With the prototype implementation, this creates very large data structures and very slow comparisons. We implement the optimization of combining duplicate rows. For example, there are two separate rows with the outcome (1 1 0). We can join these and add their probability.
To do this, we leverage the work in Kon Lovett’s lookup-table. The procedure dict-update! has the shortcuts we need: it allows us to use a default when we first insert the key and allows us to combine rather than overwrite entries.
(define (combine A B)
(let ((dict (make-dict equal?)))
(do-ec (: ra A) (: rb B)
(dict-update!
dict
(map + (car ra) (car rb))
(constantly 0)
(cut + <> (* (cdr ra) (cdr rb)))))
(dict->alist dict)))
We use (constantly 0) to generate a zero default probability for undefined results, which defined results will add to. With this, the combination of three swords has ten entries, almost a third of the twenty-seven entries in the dice set generated by the prototype implementation. Three sword dice combined look like this:
'(((3 0 0) . 8/27)
((2 1 0) . 2/9)
((2 0 1) . 2/9)
((0 3 0) . 1/216)
((1 2 0) . 1/18)
((0 2 1) . 1/72)
((1 1 1) . 1/9)
((0 0 3) . 1/216)
((0 1 2) . 1/72)
((1 0 2) . 1/18))
The data structure and the operators for dice sets can handle heterogeneous sets, but in the game, all sets rolled are homogenous.
The second operator is the comparison operator. What is the probability of a particular dice set beating another dice set?
(define crits caddar)
(define hits cadar)
(define prob cdr)
(define percent (compose inexact->exact round (cut * 100 <>)))
(define (beats? A B)
(let ((res (apply + (list-ec (: ra A) (: rb B)
(if (or
(> (crits ra) (crits rb))
(and (> (+ (crits ra) (hits ra))
(+ (crits rb) (hits rb)))
(>= (crits ra) (crits rb)))))
(* (prob ra) (prob rb))))))
(print (percent res) "%, or " res)))
All possible combinations of outcomes are compared, and if A beats B, the probability of A is multiplied with the probability of B, and all winning probabilities are added up and displayed.
Finally, let’s create a function that creates homogenous sets of dice and compares them, to find out some probabilities of actions in the game.
(define (chance-of-wounding na A nb B)
(beats?
(reduce combine #f (make-list na A))
(reduce combine #f (make-list nb B))))
And let’s try it out at the REPL:
#;1> (chance-of-wounding 3 swords 1 shield)
55%, or 707/1296
#;2> (chance-of-wounding 3 hammers 2 dodge)
61%, or 2389/3888
#;3> (chance-of-wounding 2 double-supported-swords 1 shield)
66%, or 143/216
#;4> (chance-of-wounding 9 hammers 5 dodge)
77%, or 60700026331/78364164096
Nice! The Monte Carlo method is great but sometimes you just want to know exactly how dangerous it is.