## Probability of Dice Rolls in Settlers of Catan

**A few weeks back I played a game of Settler of Catan where an 8 was only rolled once.** This is *a pretty big deal* if you know how the game is played.

In Settlers of Catan, each turn begins with a player rolling two 6-sided dice. The *sum* of this roll determines the game play. The full rules of the game aren’t important for this post, just the fact that players hedge their play based on the probabilities of specific sums occurring. According to these probabilities an 8 should roll, on average, every 7.2 turns. *In our game it took 72 turns to roll an 8!* For the players who had hedged their fortunes on 8s, this was a crushing blow.

After the game we spent some time discussing the rarity of a game such as this. Many felt that only rolling one 8 in 72 turns was incredibly rare. I argued that it wasn’t as rare as we might think. I then took the position that we couldn’t have a logical discussion about these kind of games since randomness was involved. I was wrong, we have probability theory.

Let’s explore probability theory to learn how rare this game really was.

### Single Die Probabilities

When rolling a single 6-sided die, the chance of rolling any side is equal. Since there are six sides to the die, each side has a 1 out of 6 chance of rolling. If, say, we were to roll a single die 600 times, each side would appear on average 100 times.

In probability theory terms this is called a uniform distribution.

### Dice Sum Probabilities

Things get more interesting when pairs of dice are thrown and summed, as in Settlers. In this situation certain sums are more likely to appear than others. This is because there are more possible die-side combinations for certain sums.

The following chart shows this distribution of sums. Notice that the sum of two uniform distributions (each die) makes a triangular distribution.

Shown in this image are the 36 possible outcomes of rolling 2 dice. Six of these combos sum to a 7 while only one of them sums to a 2. It should therefore be apparent that in a game of Settlers, 7s are rolled more often than 2s. *If you don’t believe me, grab a pair of dice and start rolling while keeping track of the sums.*

Looking at this chart we see that 5 of the 36 possible combinations sum to an 8. As such, an 8 should roll on average 5 times every 36 rolls, or as I stated earlier, once every 7.2 rolls (5/36).

### Simulating Dice Rolls

I coded the following visualization to demonstrates these dice-sum probabilities. In this program virtual 6-sided dice-throws are simulated using a pseudorandom number generator. In total over 3000 virtual dice are thrown before the programs resets.

The left-hand graph above shows how often each virtual die lands on a specific side, 1 through 6. Since there is an equal probability of each side appearing, the columns in this graph should all be approximately the same height. This is the uniform distribution I mentioned earlier.

The right-hand graph above shows these same dice-rolls grouped in pairs and summed, just like in a game of Settlers. As the number of rolls increases, this graph of sum-occurrences begins to resemble the triangular distribution shown in picture of the dice sum combos above.

### Randomness is Tricky

Based on these dice-sum probabilities, how often should an 8 roll in 72 turns? Well, if the chance of rolling an 8 is 5 out of 36 (or 13.9%) then in 72 turns an eight should roll *on average* 10 times. Why? Because 13.9% of 72 is 10.

Notice that throughout this post I’ve been using the phrase “on average” when talking about expected dice rolls? That’s the key to our mystery. Yes, based on the probabilities, an 8 should be rolled 13.9% of the time. However, each roll is random and independent from all previous rolls. So with *enough rolls* these probabilities will be true, but for a small sampling of rolls they may not be. Grab two dice and roll them 36 times, a sum of 8 won’t *always* show up exactly 5 times. Such is chaos.

The next visualization demonstrates just this effect. Each refresh of the graphs represents another possible 72-roll game of Settlers. *With a sample size of 72 pairs of dice the graphs are often far from ideal.* In some games dice-sides are far from uniform, and the dice sums do not always follow the expected triangular probability distribution.

### Our Crazy Game

So how rare was our game? I used the AnyDice programming language (which is an amazing tool btw) to find out.

output 72d (2d6 = 8)

This program calculates the odds of rolling any number of 8s in a game of 72 rolls of 2 six-sided dice. Based on the output of this program the odds of rolling only one 8 in a 72 turn game of Settlers is 0.0245020661348%. In other words, a game like this could be expected once every 4,081 games.

Truthfully, since our game went to 79 rolls it was more like a 1 out of 10,594 game. Had no eights rolled in the entire 79 roll game, it would have been a 1 out of 135,000 game. Rare, but still possible. *Such is chaos.*

### UPDATE (18/12/2013): What About The Sequence of No-8 Rolls?

After reading this post, a friend who was at the game suggested that the odds were actually far worse than I calculated, if you take the order of the rolls into account. His argument being that a run of 71 no-8 rolls is a 1 in 40,813 event. See calculation below*.

While this is true, it’s important to note that we are now talking about two different probabilities.

- Probability of
**a sequence**of 71 no-8 rolls: 1 in 40,813 - Probability of rolling only one 8
**anywhere**in 79 rolls: 1 in 10,594

### Resources and Further Reading

Before I started writing this blog post I wrote a Ruby program to simulate the roll of dice in Settlers using the truly random data from Random.org.

**I referenced the following sites while writing this post:**

- Understanding Probability
- Dice Odds for Settlers of Catan
- These dice are driving me crazy!
- Central Limit Theorem
- Two Dice Roll Calculator
- Triangle Distribution - The Sum of Random Variables

***Example Probability Calculation:** The odds of rolling no 8s in a game of 71 turns.

The probability of *not* rolling an 8 is 1 minus the probability *of* rolling an 8.

1 - 5/36 = 31/36

We multiply the probability of *not* rolling an 8 with itself 71 times (31/36 to the power of 71) to find our answer.

The odds are 0.00245020661348% which is

1 out of 40,813.

**Attributions:** The header image for this post was found on enjoyneer.blogspot.ca. The dice-sum probability image was found on rosalind.info. I wrote the two programs in this post using the Processing language and they are hosted on OpenProcessing.org.

I met a robot at a ballet once by Isabela Dos Santos.

Ever felt the urge to play Settlers of Catan, but the game itself was not close at hand? Follow these Instructable on Pen and Paper Catan.

I am eagerly awaiting the arrival of three copies of Robot Turtle.

Lastly, for BIT students who wonder why they take a stats course:

Also:

An MRI scan of a banana flower. More MRI scans of fruit can be found at Inside Insides.

Existential Star Wars by George Lucas and Jean-Paul Sartre.

## Music and Fractal Landscapes

Yesterday @chefquix and I had a fairly involved discussion about consciousness and artificial intelligence. Our conversation centred on my loss of faith in strong AI due to my new-found belief that our consciousness (what ever it is) is not discreet, computational, or algorithmic. In other words, we don’t brute force our awareness of self or our awareness of the world around us. We intuit.

This morning while taking the bus to work, much to the surprise of my fellow passengers, I stood up abruptly, struck by what I was reading. (I then look around and awkwardly sat back down.) I had been reading Douglas Adams’ Dirk Gently’s Holistic Detective Agency, specifically a fictional article written by the story’s main character Richard MacDuff. This article, replicated below, solidified my understanding of yesterday’s conversation with Andrew.

### Music and Fractal Landscapes

by Richard MacDuff (Douglas Adams)

Mathematical analysis and computer modelling are revealing to us that the shapes and processes we encounter in nature - the way that plants grow, the way that mountains erode or rivers flow, the way that snowflakes or islands achieve their shapes, the way that light plays on a surface, the way the milk folds and spins into your coffee as you stir it, the way that laughter sweeps through a crowd of people - all these things in their seemingly magical complexity can be described by the interaction of mathematical processes that are, if anything, even more magical in their simplicity.

Shapes that we think of as random are in fact the products of complex shifting webs of numbers obeying simple rules. The very word “natural” that we have often taken to mean “unstructured” in fact describes shapes and processes that appear so unfathomably complex that we cannot consciously perceive the simple natural laws at work.

They can all be described by numbers.

We know, however, that the mind is capable of understanding these matters in all their complexity and in all their simplicity. A ball flying through the air is responding to the force and direction with which it was thrown, the action of gravity, the friction of the air which it must expend its energy on overcoming, the turbulence of the air around its surface, and the rate and direction of the ball’s spin.

And yet, someone who might have difficulty consciously trying to work out what 3 x 4 x 5 comes to would have no trouble in doing differential calculus and a whole host of related calculations so astoundingly fast that they can *actually catch a flying ball*.

People who call this “instinct” are merely giving the phenomenon a name, not explaining anything.

I think that the closest that human beings come to expressing our understanding of these natural complexities is in music. It is the most abstract of the arts - it has no meaning or purpose other than to be itself.

Every single aspect of a piece of music can be represented by numbers. From the organisation of movements in a whole symphony, down through the patterns of pitch and rhythm that make up the melodies and harmonies, the dynamics that shape the performance, all the way down to the timbres of the notes themselves, their harmonics, the way they change over time, in short, all the elements of a noise that distinguish between the sound of one person piping on a piccolo and another one thumping a drum - all of these things can be expressed by patterns and hierarchies of numbers.

And in my experience the more internal relationships there are between the patterns of numbers at different levels of the hierarchy, however complex and subtle those relationships may be, the more satisfying and, well, whole, the music will seem to be.

In fact the more subtle and complex those relationships, and the further they are beyond the grasp of the conscious mind, the more the instinctive part of your mind - by which I mean that part of your mind that can do differential calculus so astoundingly fast that it will put your hand in the right place to catch a flying ball - the more that part of your brain revels in it.

Music of any complexity (and even “Three Blind Mice” is complex in its way by the time someone has actually performed it on an instrument with its own individual timbre and articulation) passes beyond your conscious mind into the arms of your own private mathematical genius who dwells in your unconscious responding to all the inner complexities and relationships and proportions that we think we know nothing about.

Some people object to such a view of music, saying that if you reduce music to mathematics, where does the emotion come into it? I would say that it’s never been out of it.

The things by which our emotions can be moved - the shape of a flower or a Grecian urn, the way a baby grows, the way the wind brushes across your face, the way clouds move, their shapes, the way light dances on the water, or daffodils flutter in the breeze, the way in which the person you love moves their head, the way their hair follows that movement, the curve described by the dying fall of the last chord of a piece of music - all these things can be described by the complex flow of numbers.

That’s not a reduction of it, that’s the beauty of it.

Ask Newton. Ask Einstein.

Ask the poet (Keats) who said that what the imagination seizes as beauty must be truth.

He might also have said that what the hand seizes as a ball must be truth, but he didn’t, because he was a poet and preferred loafing about under trees with a bottle of laudanum and a notebook to playing cricket, but it would have been equally true.

Because that is at the heart of the relationship between on the one hand our “instinctive” understanding of shape, form, movement, light, and on the other hand our emotional responses to them.

And that is why I believe that there must be a form of music inherent in nature, in natural objects, in the patterns of natural processes. A music that would be as deeply satisfying as any naturally occurring beauty - and our own deepest emotions are, after all, a form of naturally occurring beauty…

A short 3D animation based on and inspired by the article ‘Music and Fractal Landscapes’ by Douglas Adams in his Book ‘Dirk Gently’s Holistic Detective Agency’.

Beautiful projection-mapping on moving objects. The graphics you see were not added in post-processing but were projected onto the two moving screens in real-time. What you see in this video is exactly what you would have seen had you been present in the room during the filming.

The video ends with my favourite Arthur C. Clark quote:

"Any sufficiently advanced technology is indistinguishable from magic."

**Related:** Winnipeg company PO-MO wants your help funding an interactive projection toy for children.

Verb: That’s What’s Happening (1974). via

I put my heart in action. Verb! To run, to go, to get, to give. Verb!

You’rewhat’s happening. — Lyrics

I’m happpy to have been selected to present at the BSides Winnipeg security conference this November. Tickets are on sale now for $20. Buy now, there are only 150 tickets available!

**From the organizers:**

We’re proud to be hosting the first ever BSides Winnipeg security conference this November in Winnipeg! BSides is a different kind of conference - it’s highly technical, providing the latest up-to-date information “from the trenches”, so to speak. The combination of low cost with high quality talks makes this perfect for anyone from students to industry professionals!

The conference will take place over two days (November 16 and 17, 2013) on the second floor of the King’s Head Pub. It runs from noon - 7pm both days, after which the bar is open to the public (attendees are welcome to stick around, if they want!)

**My presentation:**

This talk is about building bots. Specifically, it will focus on @abotlafia, a Twitter bot inspired by the “bot” in Umberto Eco’s 1988 novel

Foucault’s Pendulum. The talk will demonstrate how little code is required to create automated accounts on Twitter. This will be followed by a discussion of the security/ethical implications of algorithmic social media accounts, and the possibility of a future where we are unable to determine who is real and who is a bot on the Internet.

Yesterday I bought the iOS programming app Codea and a BlueTooth iPad keyboard. This video shows my first Codea/Lua program, coded and executed on an iPad. I’ve used Lua in the past to code for my PSP, but the experience was nowhere near as slick as using Codea.

What the video doesn’t show is my use of UI sliders to control the movement, size, and colour of the bouncing ball. With a few tweaks (like touch control over the circle) this will already make an interesting game for my 21 month old daughter.

## Music for the Eyes

Three distinct takes on the visualization of MIDI-based music.

I imagine videos of this sort would be a helpful addition to music lessons, helping students explore the structure and melody of the songs they are learning to play.

**Music Visualization #1**

Rimsky-Korsakov’s Flight of the Bumblebee visualized by Andy Fillebrown using AudioCarver.

This one has a Guitar Hero feel to it. It’s also the closest in feel (imo) to plain old sheet music.

**Music Visualization #2**

Resonant Chamber by Animusic a company that specializes in the 3D visualization of MIDI-based music.

My 19 month old daughter loves this one the most.

**Music Visualization #3**

Bach Little Fugue in G Minor visualized by A. P. Anderson using the MAM MIDI Player.

This is the most abstract of the three visualizations, but I feel it conveys the most information about the structure of the song.

**Related:** Music Visualization: Beautiful Tools to ‘See’ Sound

An infographic-based survey.

Also from information is beautiful: Rhetological Fallacies

## A Scientific Approach to Debugging

This list, taken from John Regehr’s How to Debug (via), aligns nicely with my process for debugging software.

- Verify the Bug and Determine Correct Behaviour.
- Stabilize, Isolate, and [Reproduce].
- Estimate [Likelihood of Probable Causes].
- Devise and Run an Experiment.
- Iterate Until the Bug is Found.
- Fix the Bug and Verify the Fix.
- Undo [Unwanted] Changes.
- Create a Regression Test.
- Find the Bug’s Friends and Relatives.

My changes/clarifications are shown within square braces. Trust me, read the full post. Each step is explained in detail.

I’ve just finished re-reading Robert Pirsig’s Zen and the Art of Motorcycle Maintenance, where a similar debugging approach (the scientific method) is explained.

“For this you keep a lab notebook. Everything gets written down, formally, so that you know at all times where you are, where you’ve been, where you’re going and where you want to get. […] Sometimes just the act of writing down the problems straightens out your head as to what they really are.

The logical statements entered into the notebook are broken down into six categories:

- Statement of the problem.
- Hypotheses as to the cause of the problem.
- Experiments designed to test each hypothesis.
- Predicted results of the experiments.
- Observed results of the experiments
- Conclusions from the results of the experiments.
“The real purpose of scientific method is to make sure Nature hasn’t misled you into thinking you know something you don’t actually know. […] One logical slip and an entire scientific edifice comes tumbling down. One false deduction […] and you can get hung up indefinitely.

As a programming instructor I help students when things go wrong with the applications they’re writing. Because of my experience with the types of apps they are coding, I’m usually quick at spotting the source of the bug. Pointing out these bugs may fix their immediate problem, *but it does little to correct the error in logic that led to the bug*. Perhaps before coming to me, students with buggy source code should work through steps 1 through 4 from either of these lists.

If I were to mandate this for my classes, I’d have to add a step zero:

**Be Prepared to Learn From Your Mistake.**

New programmers are often quick to blame the language or framework they are using when their code doesn’t work. I still catch myself thinking “*IT* isn’t working” when I encounter troublesome bugs in my code. However, experience has shown me two things:

- My tools are rarely the source of my problem.
- If I’m not prepared to accept responsibility for my bugs, I’m doomed to repeat them.

ʕ•ᴥ•ʔ

Recommended reading:

Bike! - A short film about biking in Winnipeg.

We’re all part of the club

Whether you see life in pedals and spokes

Or, you’re just out for a Sunday ride

It’s about freedom

It’s not revolutionary

It’s human powered

You’ve always been a cyclist Keep moving

Brett Geisel argues that “Winnipeg’s downtown is not only safe, and the suburban idea that it is dangerous is driven not by facts, but by racism.”

Plus a thoughtful response by Kate Sjoberg:

“Brett’s assertion that Winnipeg’s downtown is safe is only partly true, and raises issues that need more attention. Winnipeg’s downtown is safe depending on a number of social markers. It is most safe for white able bodied, heterosexual men between the ages of 20 and 60 who have a job and a place to live, whether they live there, commute in to work, or attend a hockey game.”

From the Spectator Tribune, news and opinion pieces from the Canadian prairies.

## Self-Assessment While Learning to Code

I teach computer programming in the Business Information Technology program at Red River College. Following the lead of Jody Gillis, another BIT instructor, I have added self-assessments to my student assignments.

### What is self-assessment?

I ask my students to grade their own assignments using the same process I use, a weighted grading rubric. My rubrics are a collection of project requirements and instructor expectations. For each assignment a self-assessment is completed and submitted along with the project source code.

More often than not, the students assign themselves full marks with little reflection on their work. I need them to buy into the process, to see the value in it.

### Why I want my students to value self-assessment.

Each week I introduce my students to new coding techniques. They must practice these new skills to learn them. Since each new set of techniques builds on skills acquired in the weeks before, a student’s ability to assess what they know and what they don’t know is essential. Insert “house of cards” analogy here. ;)

### Practice Makes Better

To integrate more practice time into my courses, I’ve split assignments into two types:

- Take Home Assignments. Five or six a term. Individual work. Assessed by me and self-assessed.
- In Class Coding Challenges. One a week. Students can work together. Self-assessed only, but no formalized rubric.

The coding challenges provide an opportunity to experiment, to make mistakes, and to learn from direct experience. My gut feeling is that the better my students are able to self-assess these challenges and assignments, the better they will be able to direct their own learning.

My gut also tells me that my students are self-assessing once they believe no further work is needed on their assignments. I have to do a better job of explaining that self-assessment should be used throughout the development of their assignments, allowing them to reflect on and improve their code as they go.

More reading: Self-Assessment Does Not Necessarily Mean Self-Grading

## Philosophy, Physics, and Teaching

The audio lectures I’ve been enjoying this month.

**Physics and Philosophy: Arguments, Experiments and a Few Things in Between**

University of Oxford

Exploring links between our scientific and philosophical understanding of the world. Six 10-25 minute discussions on “the nature of space and time, the unpredictable results of quantum mechanics and their surprising consequences and perhaps most fundamentally, the nature of the mind and how far science can go towards explaining and understanding it.”

**General Philosophy**

University of Oxford

An eight-week chronological view of the history of western philosophy delivered by Peter Millican to first-year philosophy students. Thirty-three 10-20 minute lectures.

**Teaching and Learning**

- What I wish I had known about teaching when I started - Frédéric Mégret - McGill - iTunes (track 1)
- Teaching for Learning - Jennifer Summit - Stanford - iTunes (track 37)

Other audio lectures I have enjoyed:

Ashes and Snow by Gregory Colbert.

Also: Feature to Fire