Tuesday, September 5, 2017

Your Random May Vary: Addendum

My coworker and good friend Tim has provided a bunch of good information in response to my last post. I'm posting it here (mostly) unedited, because it sheds light on the underlying principles.

"sir, you have posted something false to the internet and it is my duty to berate you for it!

combining multiple random numbers is not the same thing as choosing a random number between bigger values.

it flys in the face of one of the most beautiful underlying principles of statistics (possibly the only beautiful thing about statistics):

If you add together many random numbers, you get a NORMAL DISTRIBUTION!
Isn't that interesting... I wonder why the normal distribution pops up so often? Oh that's right because this sort of thing happens all the time. Think about it for a bit; if you flip a coin 6 times, what is the probability of getting all heads? Is it the same as rolling a 6? Nope... you have a might higher probability of getting 3 heads than getting 6 heads. You might not notice it much for six goes, but if you flip a coint 18 times, you are very unlikely to get 18 in a row. It's because the distribution of outcomes is very different, not because one is more or less random than the other.

d&d is built on this principle; creating pseudo normalized random distributions by combining dice rolls.

If you want a better explination of this (and the 3 principles of statistics) I highly recommend reading the short chapter on statistic from "The Art of Game Design: A Book of Lenses" -- Jesse Schell. You can get it from the local library for free and the chapter is really concise and illuminating. The whole book is excellent actually."

Many thanks to Tim for the info!

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..."

Friday, September 1, 2017

Cabin In The Woods, Pt 4

I woke up early the next day in order to call the kayaking company. You see, the quality of the kayaking is heavily dependent on the river authority and how much water they release from the nearby reservoir. Strangely, the recent rains hadn't raised the river level very much, and I was worried that the river wouldn't be high enough to boat on. Luckily for us, they had released a little water, and the river was good enough (according to the proprietor).

As such, we were off for our kayaking adventure!

Day 5: Kayaking

There are *lots* of kayaking companies in the Broken Bow area. After researching, we decided to go with Yippie Kayo Kayaks. We had a good experience with them. If you're ever in the area and want to get out on the river a bit, you should definitely look them up.

There was another family in our launch, so the van was quite full on the way to the river. You might say we were crammed in there like sardines, but I'm pretty sure sardines are saltwater fish. Is there a tiny, tight-schooled freshwater fish?

Sorry, back to the actual story. We had high hopes of high adventure as we entered the river.

...except Gabriel, full of trepidation.
What a great day to kayak that was. The temperature remained in the 80s or below and the sun was occasionally obscured by clouds. The river itself wasn't very high, which was good and bad. In the area we kayaked, if the river gets too high, the rapids become... more challenging. As it was, we only had a single waterfall to go over.

Tanya was our official photographer, by the way. The following picture was taken after we all successfully made through the rapids (most of which I had to walk through, since my boat dragged the bottom) and then over the falls.

Those are the falls, under the arrow.
I had water cooler duty.

Water cooler duty
You see the cooler? It's full of bottled water. It also happens to have a small bottle of bug spray in it. It's lashed to my kayak by a single, small bungee cord. Given how I've described the river, you'd think that would be good enough to keep the cooler securely fastened. Not so much, as it turns out. There were a couple of spots where the kayak went up on its side or completely turned over (hey, it happens even on simple little turns or rocks -- for the record, I had to get out and right the kayak or move it past rocks several times).

The reason I bring this up is that even though the cooler's lid was super-tight, the cooler still got river water in it. In addition, the bug spray bottle must've leaked a little, because at the end of the trip there was a very delicious lemony smell expelled from the cooler as we opened the lid. Needless to say, no bugs wound up drinking from those water bottles...

At one point, a bald eagle put on a display for us... a display of confusion. We were paddling along when this majestic creature swooped out of a tree, diving straight towards the far bank of the river. It grabbed what looked like a rock, started ascending back towards its tree, but dropped the rock about halfway over the stream. The rock landed with a less than thrilling splash as the eagle resumed its perch.

I have no idea what I'm doing.
Our best guess is that the eagle had grabbed one of the turtles from the water near the far bank, and then either instinctively dropped it in order to crack its shell or was getting snapped severely enough by the turtle itself that the eagle decided it wasn't worth the effort. In either case, we couldn't figure out why the silly bird didn't make a grab at the fish that we could clearly see splashing around all over the river. Maybe it's a turtle-tarian?

I was surprised to learn that everyone actually enjoyed the kayaking. I had doubts about whether or not the boys would think it was fun. Photographic proof follows.

Gabriel approves of not getting sunburnt

Garrett and I try a tandem experiment. It failed.
Tanya makes me take a picture without goofy sunglasses. I smiled despite myself.
Victory! Raise your paddles for a job well done!
I've got to let you guys in on a secret. I've saved the best part of the experience for last. Are you ready?

.

.

.

SPACE PANTS!

Space Pants!
And if you're wondering, these are *not* mine, they're Tanya's, but yes, I absolutely want a pair.

This was the last of our adventures on the surprise summer vacacay. It was unexpectedly enjoyable. If you ever have a hankering to rent a Cabin In The Woods, indulge that hankering. And get out on some zip lines, and onto the river in some kayaks. If you can avoid or embrace the thunderstorms, you're bound to have a grand ol' time!