Monte Carlo Analysis of Chutes & Ladders with Python

If you spend time around young children, sooner or later you’ll end up playing the game Chutes and Ladders. This game actually has quite an interesting history, dating back to ancient India. The Milton-Bradley version dates from the 1940s.

The game’s history is probably the most interesting thing about the game, beause it is utterly devoid of strategy or technique. The players’ only interaction with the game is to spin a spinner that provides a random number from 1 through 6; there is no skill aspect, there are no decisions to be made. And certainly, while perfectly enjoyable as a family pastime that brings people together, in and of itself the game offers little intellectual distraction.

This intellectual idle-time led me to think about the nature of the board. I wondered if the game, being entirely stochastic, had any hidden patterns within. After all, it’s reasonable to assume that Milton-Bradley didn’t have access to any sort of automated analysis of their game back in 1943. I wondered things like:

  • What’s the average number of spins to win?
  • How many chutes and ladders will a user typically hit?
  • Are the chutes and ladders balanced?
  • Are some squares hit more often than others?

What’s neat is the nature of the game lends itself well to numerical analysis. There’s no human component that requires estimation or approximation. Literally the only action a player takes is to spin a spinner. Why not use Monte Carlo analysis to play bulk trials of the game and look for answers?

Coding this in Python was fairly straightforward. Although not the most performant language, Python’s excellent visualization tools make it the language of choice for this project. Using joblib to parallelize the task meant that I could simulate 500,000 single-player games in 7 seconds. (Why single-player? The game doesn’t change at all by the number of players. There are no exclusions or conflicts or indeed any alterations at all, from a numerical analysis perspective.)

The results are kind of interesting if you’re the sort of person who wonders about these sorts of things.

For half a million games, I saw this:

7.633320899999944 seconds elapsed time
Minimum number of spins to win: 7
Maximum number of spins to win: 446
Arithmetic mean number of ladders hit by player: 3
Arithmetic mean number of chutes hit by player: 4
Arithmetic mean of spins to win: 40.092362
Median of spins to win: 33.0
Standard deviation = 25.522641855046196

There’s more information to be found in the visualizations:

Noting the average number of spins to win the game is 40, the cumulative number of spins to win a game rises in a smooth curve. You can see, for example, that the probability of concluding a game between 50 and 60 spins is about 81-82%, and that most games are won under 40 spins (the median number-of-spins-to-win being 33).

The heatmaps of board positions are particularly interesting to me. There are two heatmaps of note:

  1. a heatmap of where the user lands initially after spinning (i.e. before following any chute/ladder)
  2. a heatmap of where the user ends up at the conclusion of their turn (i.e. after following any chute/ladder)

The former shows two notable darker/cooler bands across the board: along the bottom, and in the upper third. These cooler bands are areas of infrequent landing. Once chutes/ladders are taken into account, however, the picture becomes much noisier. The squares with ‘0’ values may seem counter-intuitive until you realize those are the heads of chutes or bottoms of ladders — no turn ever ‘ends’ on these squares. This heatmap shows some particular hotspots such as the top of the “big ladder” and the bottom of Square 48’s yellow chute. Also note how it’s very, very common to get stuck at square 99, waiting for an exact spin of ‘1’ to finally win the game.

If you care to try this out locally, the source code is on Github.

On the ground at CppCon 2014

I’ve just returned from the week-long CppCon 2014 in Bellevue, Washington. Here’s what I experienced.

I’ve absorbed a great deal from a variety of C++ developer conferences – CppNow, Going Native, C++ And Beyond – but always virtually, via video and webcast. This was an opportunity to jump into the thick of things and participate in person. With community heavyweights like Herb Sutter and Scott Meyers in attendance I knew the content would be stimulating and informative. (Honestly, the speaker list featured nearly every name in the “C++ royalty” that you could imagine. I smiled to myself seeing Bjarne Stroustrup standing in the registration line like he was just another attendee.) So when the conference’s early-bird admission opened in March, I eagerly sent in my hard-earned dollars and blocked off the week of September eighth on my calendar.

Continue reading

Steering Behaviors for Ruby game dev now on Github, Rubygems

I just released my Steering Behaviors package to Github, and an accompanying Gem to Rubygems.

If you’re building a game, you’ll want your game agents and characters to exhibit realistic motion. A standard way of doing this is with ‘steering behaviors’.

The seminal paper by Craig Reynolds established a core set of steering behaviors that could be utilized for a variety of common movement tasks. These include such behaviors as predictive pursuit, fleeing, arrival, and wandering. This Ruby library can accomplish many/most of those tasks for your Ruby / JRuby game.

The basic behaviors can be layered for more complicated and advanced behaviors, such as flocking and crowd movement.

Embellishments and expansions are planned, but this is working software you can use to drive your own game’s characters. (I’m using it in my own game programming.) The Github repo includes working graphical examples, and you can install the Gem for easier and more direct use in your own game.

Pull requests are enthusiastically encouraged.


On Github: my Fuzzy Associative Memory (FAM) package

I’ve just released to Github my working fuzzy logic module, Fuzzy Associative Memory.

A Fuzzy Associative Memory (FAM for short) is a Fuzzy Logic tool for decision making. It uses Fuzzy Sets to establish a set of rules that are linguistic in nature; examples might include:

  • “If the room is a bit warm, turn the fan up a little bit”
  • “If the orc’s hit points are a little low, retreat from the enemy”
  • “If the ship is off course by a little bit, correct just a little to the right”
  • “If the bird is much slower than the flock, speed it up a lot”

As you can see, the rules are deliberately vague and use qualifiers like “a little” and “a lot”. This is the nature of fuzzy sets; they capture such human fuzziness in a way that extracts highly natural behavior from the fuzzy rules.

It has a wide range of applications:

  • Industrial control, such as governing a fan to keep a room at the “just right” temperature
  • Game AI, such as giving human-like behavior capabilities to NPCs
  • Prediction systems


This is working, functional software. It currently supports:

  • Triangular fuzzy sets for input/output
  • Larsen Implication (scaling)
  • Atomic antecedent propositions (if A then Z)

To do:

  • Trapezoidal (and other shapes) for fuzzy sets
  • Hedges (‘very’ and ‘fairly’)
  • Mamdani Implication (clipping)
  • Composite antecedent propositions (if A or B, then Z)
  • Additional examples


The bin directory contains the following examples:

  • hvac_system_example illustrates how a FAM could govern an HVAC fan unit to maintain a constant, comfortable temperature

Get it here!

Force maximum performance for the NVIDIA driver in Ubuntu Oneiric

The NVIDIA X Server Settings app for Linux lets us tune the performance of our NVIDIA display adapter. On a laptop this is especially important as it lets you enable the power-saving features of the adapter to extend battery life. The adapter (and the settings app) default to “Adaptive” mode, which is a balanced mode that can scale up for performance but scale down for battery-savings.

The problem with Adaptive mode is that it doesn’t kick in as quickly as you might like. You’ll notice choppy behavior when scaling windows in Unity, etc. So if you customarily employ your laptop “like a desktop” or just want to force full-time maximum performance mode, the settings app will let you do so.

But wait, there’s a catch: the performance settings don’t seem to persist across reboots or even across logout/logins. The adapter will revert to Adaptive mode every time. This necessitates the annoyance of remembering to run the X Server Settings app each time you log in in order to re-set the power mode.

I have good news. There’s a straightforward hack to force maximum performance while on A/C power and fall back to the adaptive strategy while on battery. And the beauty of the hack is, you don’t need to touch the NVIDIA X Server Settings app at all for this. All you have to do is add a few configuration items to your Xorg configuration.

In Ubuntu Oneiric 11.10, you no longer edit the xorg.conf file like you did in previous distributions. You simply place configuration files in /usr/share/X11/xorg.conf.d/ and they will be loaded at X startup. For this hack, make a file /usr/share/X11/xorg.conf.d/05-nvidia.conf and put in it:

Section "Device"
Identifier "MyNvidiaDevice"
Driver "nvidia"
VendorName "NVIDIA Corporation"
BoardName "NVS 140M"
Option "RegistryDwords" "PowerMizerEnable=0x1; PerfLevelSrc=0x3322; PowerMizerDefaultAC=0x1"

Note that Identifier, BoardName etc. are indicative of my Lenovo Thinkpad T61 and may not match your own hardware. However, these lines are largely irrelevant to the way X runs. The key is the Option line. These configuration items direct the NVIDIA adapter how to handle performance scaling.

You can see exactly what these hex values mean and learn some other possibilities for the values by consulting this reference.

Hey, is that kitchen timer TSO’d?

I saw this picture of the space shuttle Atlantis this morning, and it made me smile.

Chris Ferguson, STS-135 commander, is pictured on the flight deck, surrounded by sophisticated, highly techn… hey wait! That’s a kitchen timer!  Not just any kitchen timer, but the very one that we have in our own kitchen:

My personal jury’s still out on whether this is one small step for Atlantis, or one giant leap for CDN Kitchen Timer.

Easy Doxygen code snippets for Xcode 4

Fred McCann has two great blog posts describing how to document  your Objective-C code with Doxygen, a popular and standardized documentation system for C, Java and other languages. His posts are extremely well-written and definitely worth a read; he takes you all the way from a basic introduction to Doxygen to generating the Doxyfile output.

But in Xcode 4 you don’t need to use a complicated scripting system to produce commonly-used Doxygen-compatible documentation. Xcode has a “snippets” facility that comes pre-populated with a variety of Objective-C snippets; let me show you how to leverage them.

Simple Doxygen documentation for a method might look something like this:

Compute the distance to another waypoint in nm.
@param other the other Waypoint
@returns the distance in nm

Why type all that over and over again? (And this is only a small subset of what Doxygen can do. In truth, the Doxygen system is very rich and, frankly, as complicated as you want to make it. Note that in this post I’m not covering Doxygen itself, just creating the code snippets.)

In Xcode 4 I use “dox <TAB>” to insert my custom method-documentation snippet. Here’s how you can do the same:

 Read the rest of this story...

  1. Activate the right-hand Utilities drawer and in the bottom of it, click on the curly braces {} to activate the Code Snippet Library.
  2. In the code editor, type or paste the code that you want to turn into a snippet; highlight it all.
  3. Drag the highlighted code to the Snippet library. (It can be stubborn and not want to drag. Holding the mouse button down for a moment before dragging seems to help.)
  4. Your snippet has been added to the Library; click once on the snippet and a callout window will show you the snippet and permit you to edit it.
  5. Add your own descripton, completion shortcut, etc. Any text you surround with <# #> marks will be highlighted with a blue bubble for quick tabbing and substitution.

Here’s the full snippet that I employ. It’s fast and it encourages proper code documentation.

 @param <#parameter#>
 @returns <#retval#>
 @exception <#throws#>

CNN covers HealthWeaver, my team’s software for cancer patients

At the University of Washington I am a Software Architect in the Department of Medical Education and Biomedical Informatics (say that three times fast!) where I am embedded with a cancer research team.  We are working on ways to use software and the Internet to improve the lives and well-being of breast cancer patients.

On April 16 CNN profiled our HealthWeaver software and interviewed my professor and team leader, Dr. Wanda Pratt.  From the UW Information School News:

Dr. Pratt’s work with cancer patients profiled by CNN features a story about the work of UW iSchool Associate Professor Wanda Pratt and her team. The team has developed an online system called HealthWeaver. HealthWeaver includes a social networking tool, and aims to help cancer patients manage information about their care, get their questions answered and interact with others who can aid them in their treatment.

CNN reporter Elizabeth Landau interviewed Dr. Pratt and Biomedical and Health Informatics Ph. D. student Meredith Skeels after their research presentations at the ACM Conference on Human Factors in Computing Systems in Atlanta this week. Other members of Pratt’s team include Kent Unruh, who was instrumental in formulating the idea; Chris Powell, who programmed the system; and many breast cancer patients and survivors who contributed to the design. The HealthWeaver core research team includes Andrea Civan Hartzler, Pedja Klasnja, and Marlee Mukai.

The full CNN article: Social networking makes it easier for patients to ask for help

Perceptual blindness and the TSA

As any traveler knows, flying on commercial airlines involves a large number of inconveniences in the name of anti-terrorism security. Any critically-minded traveler recognizes that these mainly comprise a variety of theatrical measures that bear little resemblance to effective security. As a result, the TSA is criticized fairly and often for ineptitude.

Let’s just take as granted that the TSA’s personnel act in 100% good faith, for the moment. Stepping back from the plethora of highly relevant and appropriate criticisms above, I have a more philosophical question: is the TSA engaging in perceptual blindness?

Also known as inattentional blindness, this is the phenomenon of not perceiving things that are in plain sight. It most easily manifests when a person engages in extreme mental focus — the mere act of focusing on task or stimulus A causes the person to completely miss stimulus B.

Need an example? In this short video, you’ll see two groups of people passing basketballs around in a circle. Your task is to count the number of times the WHITE t-shirts pass the ball while ignoring the BLACK t-shirts.  (I’ve linked directly to the researchers’ video instead of embedding it.)

Don’t read further until you’ve watched the video!

Were you able to keep the balls mentally separated? How many passes did you count? 14? 17?

And by the way, did you see the person in the gorilla suit stroll through the scene? If you didn’t you’d better watch it again.

This video comes from a well known study conducted by researchers at the University of Illinois and Harvard University. The researchers found that half of test subjects failed to see the gorilla. This and other studies have confirmed that when people concentrate too heavily on one specific target or task, they often miss obvious — yet unexpected — stimuli.

If the TSA’s security theater has them over-focused on “shoe bombs” and “three ounces or less,” will they be ready to spot the obvious, yet unexpected, REAL threat?

Election Theory

In the USA we customarily use “plurality voting” to choose elected officials. This methodology’s chief advantage is its simplicity: each voter casts a single vote for a single candidate, and after the numbers are totaled the candidate with the most votes wins. It’s a system that is easy to administer and for the voters to grasp: “designed by geniuses to be run by idiots” as the saying goes.

But the 2000 presidential election exposed a rather severe problem with this simple system. Mr. Nader’s “stolen” votes are commonly believed to have been behind Mr. Gore’s loss, in that those voters would likely have preferred Mr. Gore over Mr. Bush. This splitting of the vote is known as the “spoiler effect” and is often cited as plurality’s chief flaw.

A common fallacy is to think that plurality voting is the only — or even best — election methodology. Voting theory emerged as a legitimate field of academics before the French Revolution, so after over two hundred years of study the science can be regarded as mature.
Continue reading