Monday, September 4, 2017

Your Random May Vary


At the beginning of the summer, we started hosting a semi-monthly Dungeons and Dragons game at our house. It's typically a lot of fun, involving much role-playing and dice rolling. We share Dungeon-Mastering duties; I think I've run most of the sessions, but at least two or three have been run by someone else. When I'm running the game, my character is typically an NPC. It's a bit of a shame, because my stats are pretty awesome.

I got to thinking this morning... I rolled my current character (as all my characters), using real dice and a "roll-4-keep-3" approach. I roll four 6-sided dice, discarding the lowest, and summing the other three. I do that six times in a row, and I've got the stats block for a new character.

I never use anything but real dice unless I happen not to have a set (and fyi: I carry a couple of sets around in my backpack just in case a spontaneous or random one-shot happens). Garrett used to roll great stats very often using his IPhone dice, and tended to roll challenges really highly as well. I started thinking about the difference in our results and decided to mess around with a rolling app this morning.

It's been a while since I posted anything technical. Bear with me.

I started by creating a little app that would roll a six-sided dice for me.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
(ns stats-generator.main
  (:gen-class))

(def d6 [1 2 3 4 5 6])

(defn roll-d6 []
  (rand-nth d6))

(defn -main
  "I don't do a whole lot ... yet."
  [& args]
  (println "Hello, World!"))

I quickly realized that I didn't quite know where to go. TDD to the rescue!

1
2
3
4
5
6
(ns stats-generator.main-test
  (:require [clojure.test :refer :all]
            [stats-generator.main :as main]))

(deftest test-roll-4-keep-3
  (testing "Given a roll of 4 6-sided dice, sums the highest 3"))

I started with a description of one of the end goals: a function that would roll four dice and keep the highest three. That... is probably too broad. Let's decompose for a moment. We know we'll need to roll four 6-sided dice and drop the lowest roll. Maybe that dropping function is easier to test and implement.

1
2
3
4
5
(deftest test-drop-lowest
  (testing "Given all different values, drops the lowest"
    (let [v [1 2 3 4]
          expected [2 3 4]]
      (is (= expected (main/drop-lowest v))))))

There's the test; we should stub a red (failing) function.

1
2
3
4
(defn drop-lowest
  "Given a vector, returns a vector sans its lowest value."
  [v]
  v)

Done! Run the tests!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
(run-tests)

Testing stats-generator.main-test

FAIL in (test-drop-lowest) (main_test.clj:9)
Given all different values, drops the lowest
expected: [2 3 4]
  actual: [1 2 3 4]
    diff: - [2 3 4]
          + [1 2 3 4]

Ran 2 tests containing 1 assertions.
1 failures, 0 errors.
=> {:test 2, :pass 0, :fail 1, :error 0, :type :summary}

Failed as expected. What's a simple solution that will work?

1
2
3
4
(defn drop-lowest
  "Given a vector, returns a vector sans its lowest value."
  [v]
  (rest (sort v)))

Seems reasonable. Tests tell us...?

1
2
3
4
5
6
7
(run-tests)

Testing stats-generator.main-test

Ran 2 tests containing 1 assertions.
0 failures, 0 errors.
=> {:test 2, :pass 1, :fail 0, :error 0, :type :summary}

Yay! Green tests! Let's fill in some other assertions to make sure we're not fooling ourselves.

1
2
3
4
5
6
7
8
9
(deftest test-drop-lowest
  (testing "Given all different values in random order, drops the lowest"
    (is (= [2 3 4] (main/drop-lowest [1 2 3 4])))
    (is (= [2 3 4] (main/drop-lowest [4 2 3 1]))))
  (testing "Given identical values, drops one of them"
    (is (= [1 1 1] (main/drop-lowest [1 1 1 1]))))
  (testing "Given some duplicated values, drops whatever's lowest"
    (is (= [2 2 3] (main/drop-lowest [2 3 2 2])))
    (is (= [5 6 6] (main/drop-lowest [5 6 4 6])))))

That's good enough. A question I'm often asked is "how much automated test coverage should I implement?" The pedantic answer is "100%," but the pragmatic answer is "as much as you can that covers stuff you would do by hand anyway." That's my rule-of-thumb, in any case. Sometimes I do more, sometimes less. But if I find bugs, I try to reproduce them with tests and then they're covered into perpetuity. As such the test coverage grows organically.

Alright, let's fill in some more of the decomposed functions and see where we wind up.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
(ns stats-generator.main
  (:gen-class))

(def d6 [1 2 3 4 5 6])

(defn roll-d6 [_]
  (rand-nth d6))

(defn roll-4
  "Rolls a d6 4 times"
  []
  (map roll-d6 (range 4)))

(defn drop-lowest
  "Given a vector, returns a vector sans its lowest value."
  [v]
  (rest (sort v)))

(defn sum [v]
  (apply + v))

(defn roll-4-keep-3
  "Rolls a 6-sided die 4 times, summing the highest 3 values"
  []
  (-> (roll-4)
      (drop-lowest)
      (sum)))

(defn -main
  "I don't do a whole lot ... yet."
  [& args]
  (println "Hello, World!"))

That seems reasonable. Test coverage is minimal, but enough for me to know that I'm not doing something overtly silly.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
(ns stats-generator.main-test
  (:require [clojure.test :refer :all]
            [stats-generator.main :as main]))

(deftest test-roll-4
  (let [roll (main/roll-4)]
    (is (= 4 (count roll)))
    (is (every? #(<= 1 % 6) roll))))

(deftest test-drop-lowest
  (testing "Given all different values in random order, drops the lowest"
    (is (= [2 3 4] (main/drop-lowest [1 2 3 4])))
    (is (= [2 3 4] (main/drop-lowest [4 2 3 1]))))
  (testing "Given identical values, drops one of them"
    (is (= [1 1 1] (main/drop-lowest [1 1 1 1]))))
  (testing "Given some duplicated values, drops whatever's lowest"
    (is (= [2 2 3] (main/drop-lowest [2 3 2 2])))
    (is (= [5 6 6] (main/drop-lowest [5 6 4 6])))))

(deftest test-sum
  (is (= 18 (main/sum [6 6 6])))
  (is (= 3 (main/sum [1 1 1])))
  (is (= 12 (main/sum [3 4 5]))))

(deftest test-roll-4-keep-3
  (testing "Given a roll of 4 6-sided dice, sums the highest 3"
    (is (<= 3 (main/roll-4-keep-3) 18))))

At this point, I'm ready to do the REAL implementation. We'll set up a little recursion to see if we can generate a set of six 18s. I'm not good at math, but the likelihood seems pretty low that I'll actually do it. Let's compromise and try 100 MILLION times. We'll also squawk if we get close.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
(defn roll-all-18s []
 (let [counter (atom 0)]
   (println "STARTED AT:" (now))
    (loop [current-roll []]
      (swap! counter inc)
      (cond
        (= 100000000 @counter)
        (do
          (println "Gave up after ONE HUNDRED MILLION sets...")
          (println "ENDED AT:" (now)))

        (= [18 18 18 18 18 18] current-roll)
        (do
          (println "All 18s took" @counter "attempt(s).")
          (println "ENDED AT:" (now)))

        :default
        (do
          (when (<= 5 (count (filter #(= 18 %) current-roll)))
            (println "close call!" current-roll))
          (recur (roll-stats)))))))

Alrighty! We can run this in the REPL. The first try's results follow.

1
2
3
4
5
(roll-all-18s)
STARTED AT: #inst "2017-09-04T17:26:34.981-00:00"
close call! (5 18 18 18 18 18)
Gave up after ONE HUNDRED MILLION sets...
ENDED AT: #inst "2017-09-04T17:44:07.983-00:00"

It took us 22 minutes to try 100 MILLION times, and in all those tries, we only got close once. The frequency lines up with my (admittedly bad-at-math-and-fuzzy) expectations.

So how in the world did Garrett's IPhone roll so well for him so often? I suspect they weren't using the same approach as I was (roll-4-keep-3). After a little more research, I found that another approach that simply took a random integer between 3 and 18. This seemed like a pretty simple and probably more efficient implementation, but I suspected that the level of randomness in that picking was LOWER than that of the roll-4-take-3 approach. Again, I don't have the math or computer science to tell you why -- it was just my instinct.

So, I implemented a couple more rolling functions...

1
2
3
4
(def range-3-18 (range 3 19))

(defn roll-d3-18 [_]
  (rand-nth range-3-18))

...and refactored the roll-stats function into a multi-method that dispatches on the roll style you wanted to use.

1
2
3
4
5
6
7
8
9
(defmulti roll-stats identity)

(defmethod roll-stats :roll-4-keep-3
  [_]
  (map roll-4-keep-3 (range 6)))

(defmethod roll-stats :range-3-to-18
  [_]
  (map roll-d3-18 (range 6)))

No tests were added. I wanted to get to the bottom of this silly thing. Let's do some more REPLing!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
(roll-all-18s :range-3-to-18)
STARTED AT: #inst "2017-09-04T21:56:32.650-00:00"
close call! (18 12 18 18 18 18)
close call! (18 18 17 18 18 18)
close call! (18 18 18 18 18 10)
close call! (18 18 18 18 17 18)
close call! (18 18 18 18 12 18)
close call! (18 18 18 18 18 7)
close call! (18 18 18 9 18 18)
close call! (18 18 18 17 18 18)
close call! (18 18 18 18 8 18)
close call! (18 13 18 18 18 18)
close call! (18 9 18 18 18 18)
close call! (18 18 14 18 18 18)
close call! (18 18 18 4 18 18)
close call! (18 18 18 18 12 18)
close call! (18 18 18 18 10 18)
close call! (18 18 18 18 18 3)
close call! (18 3 18 18 18 18)
close call! (18 18 18 18 10 18)
close call! (18 18 10 18 18 18)
close call! (18 18 18 18 18 3)
close call! (18 18 18 18 15 18)
close call! (18 18 15 18 18 18)
close call! (18 18 18 18 12 18)
close call! (18 18 18 11 18 18)
close call! (3 18 18 18 18 18)
close call! (18 18 15 18 18 18)
close call! (18 18 18 9 18 18)
close call! (18 18 18 18 18 7)
close call! (17 18 18 18 18 18)
close call! (18 18 18 18 15 18)
close call! (18 18 18 18 11 18)
close call! (18 17 18 18 18 18)
close call! (18 4 18 18 18 18)
close call! (18 18 16 18 18 18)
close call! (18 18 18 8 18 18)
close call! (18 18 18 18 9 18)
close call! (18 18 15 18 18 18)
close call! (9 18 18 18 18 18)
close call! (18 18 18 18 7 18)
close call! (18 11 18 18 18 18)
close call! (18 18 18 6 18 18)
close call! (18 18 18 18 8 18)
close call! (18 18 18 15 18 18)
close call! (18 18 18 18 18 9)
close call! (18 18 9 18 18 18)
close call! (18 18 18 18 4 18)
close call! (18 18 18 18 11 18)
close call! (7 18 18 18 18 18)
close call! (18 18 18 18 18 3)
close call! (18 11 18 18 18 18)
close call! (18 18 12 18 18 18)
close call! (18 18 18 5 18 18)
close call! (18 18 18 18 18 6)
close call! (18 17 18 18 18 18)
close call! (18 6 18 18 18 18)
close call! (18 18 18 9 18 18)
close call! (18 18 18 11 18 18)
close call! (18 11 18 18 18 18)
close call! (18 16 18 18 18 18)
close call! (14 18 18 18 18 18)
close call! (18 18 10 18 18 18)
close call! (18 18 18 18 18 12)
close call! (18 18 18 18 18 16)
close call! (18 18 18 4 18 18)
close call! (18 18 18 18 12 18)
close call! (18 11 18 18 18 18)
close call! (18 18 18 18 16 18)
close call! (18 18 5 18 18 18)
close call! (18 18 18 18 18 16)
close call! (18 18 18 17 18 18)
close call! (5 18 18 18 18 18)
close call! (18 18 18 11 18 18)
close call! (18 18 18 18 18 12)
close call! (18 18 18 18 18 7)
close call! (18 18 18 3 18 18)
close call! (18 18 18 18 8 18)
close call! (18 18 18 5 18 18)
close call! (15 18 18 18 18 18)
close call! (18 5 18 18 18 18)
close call! (18 18 18 16 18 18)
close call! (18 18 18 18 4 18)
close call! (18 18 17 18 18 18)
close call! (18 14 18 18 18 18)
close call! (18 18 18 18 18 7)
close call! (18 18 18 4 18 18)
close call! (18 18 18 18 4 18)
All 18s took 13880334 attempt(s).
ENDED AT: #inst "2017-09-04T21:57:12.554-00:00"

WHOA! There were a TON more close calls, and an actual hit about 14 milllion rolls in.

I decided to re-run the roll-4-take-3 strategy to verify its performance.

1
2
3
4
5
6
7
(roll-all-18s :roll-4-keep-3)
STARTED AT: #inst "2017-09-04T22:51:37.468-00:00"
close call! (18 18 18 18 14 18)
close call! (13 18 18 18 18 18)
close call! (18 18 18 18 18 9)
Gave up after ONE HUNDRED MILLION sets...
ENDED AT: #inst "2017-09-04T23:09:02.571-00:00"

A few more close calls were had, but roughly the same result. I re-ran the range-3-to-18 strategy:

1
2
3
4
5
6
(roll-all-18s :range-3-to-18)
STARTED AT: #inst "2017-09-04T23:24:08.765-00:00"
close call! (18 18 8 18 18 18)
close call! (18 18 18 5 18 18)
All 18s took 321349 attempt(s).
ENDED AT: #inst "2017-09-04T23:24:09.925-00:00"

Wowzers. SO MUCH MORE LIKELY to roll 18s using that approach. The second run only took a second and slightly more than 321,000 tries.

So, what's the moral of the story? I think it's that the amount of randomness you get from computers may vary, based on what the underlying strategy is. Random numbers aren't truly random in the machine. Always keep that in mind when they rise up and become our overlords.

Also: rolling 321,000 times by hand, at one set of rolls per second, would still take you almost 4 straight days of rolling to get that all 18s set. So for you DMs out there... if a player comes to you with a character they said they rolled, and it's got six 18s, you give them a knowing wink while handing them your dice and telling them "roll again..."

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.