A New Medium

Shortly after discovering, sometime in the late eighties, that magically, mysteriously, I could use a joystick and button to control a spaceship or a keyboard to command a boy to explore a castle, I found myself wishing that I could make that magic happen myself. In grade school I made some plans. In high school I read some books. In college I took some classes. In grad school I studied algorithms and I even interviewed with video game companies, maintained a stats site for an existing game, built AI that learns to play a board game, and so on, but never quite turned the corner.

Scoping Problem

A number of friends had expressed interest at some time in my life in helping me make a game. None of us ever did. I made attempts—built a rudimentary physics engine, contacted my favorite band to ask if I could use their music, and wasted a great deal of effort on other equally fruitless tasks. I should have recognized this problem for what it was, a disease commonly afflicting software, called scope creep. In short, it happens when we try to do everything at once, and it prevents us from doing anything ever. Somewhere deep inside, I felt like making a game meant making a blockbuster.

Extending My Reach

I decided that I needed to reach outside of my base of friends and family. Fortunately, I wasn’t the first in my town to have this thought. Again, however, I spent a fair amount of time learning new tools, toying with mechanics, thinking, discussing, and now, networking. All of these things were useful, but I still hadn’t quite reached the milestone of having made my own. Then, my scope tightened.

Competitive Building

There is a game development competition. It’s called Ludum Dare. The premise is to build a game in two to three days. That’s it. The prevention of scope creep is baked right in to the rules. I participated in Ludum Dare 33, and did in seventy-two hours what I had previously failed to do in twenty-five plus years. Was it great? Absolutely not. Was it good? No! Was it terrible? Almost certainly. Take a look for yourself. I asked my wife to draw some artwork on a white sheet of paper, scan it, and send it to me. I borrowed some generic assets for a background. I neglected to add music or sound.

Then I asked my five-year-old son to show it off to a small crowd of people collected to celebrate what had been built that weekend. And the amateurish mechanics, unpolished images, and childish puzzles are still magic. I built an unambiguously complete game and learned a breadth of things that would have otherwise taken months.

A Moral?

Given the technology available today, and the growing base of people like me, who grew up with gaming as infrastructure, not as new technology, I’m excited to see what happens as it, like books and television before it, becomes more integrated into our daily lives. I think it will do much greater things than either of those predecessors and I have a feeling I’ll have more to say about that in a future post. In the meantime, I’ll certainly be making more games myself, maybe even some good ones.

# Jocks vs. Nerds

Each Contestant Meets All Other Contestants In Turn

A few years ago, a co-worker participated in a local cricket league. Each team played all of the others in the league twice, and the top few qualified for a playoff. He wanted to know how many games his team needed to win in order to guarantee an appearance in the playoffs. This type of scheduling goes by the name “round-robin”.

I was interested in the following questions:

1. In the worst case, how many wins would a team need in order to advance? This is the case my colleague asked about.
2. In the best case, how few wins could a team achieve and still make the playoffs?
3. What is the average case? How many wins would be necessary to make the playoffs 50% of the time?

I don’t remember the specifics of my colleague’s tournament, so let’s just solve the problem in general. Continue reading Jocks vs. Nerds

# Entropy: The Opposite of Chaos

What Disorder Looks Like

Which image below looks more disorderly? Which seems more chaotic?

Perhaps these seem like trick questions—they’re not. They may seem like leading questions—they most certainly are. Feel free to answer with your gut on this. (Hint: That image on the right looks fairly orderly to me.)

Entropy

Entropy is commonly referred to with the terms disorder, randomness, and chaos. In fact, many textbooks use the term disorder explicitly to introduce the concept; however, this description tends to lead to misunderstanding of the concept. Continue reading Entropy: The Opposite of Chaos

# When Will This Game End?

## Geez, This Is Taking Forever!

A short time ago, I watched my hometown college football team come back to tie a game in the fourth quarter, triggering overtime. Because overtime is so much fun to watch, I immediately wondered how long it would last. That particular game ended in two overtimes, but I decided I’d like to know how many overtimes one can usually expect.

As it turns out, the NCAA publishes every overtime game including the number of overtimes. We’ll come back to this later, but I decided to ask a more interesting question instead. I wondered whether regulation time performance matches overtime performance well enough to predict the average number of overtimes. Continue reading When Will This Game End?

# Derangement Can Solve Your Problems

## Men Without Hats

Here is a very fun and surprising result which is not really new, but if you haven’t seen it, you really should. The problem looks like this:

One-hundred men throw their hats into a closet. Each one randomly selects one of the hats until all of them have a hat again. At the end of the process, how many men do we expect to have their own hat?

I had a professor who gave us the answer to this question, and put it on every test he gave, but never actually proved it, so today I’m going to do it. I’m actually going to solve this problem (and the more general one, with $N$ men and $N$ hats) in two different ways, but let’s start with a brute force approach. Continue reading Derangement Can Solve Your Problems

# Rage Faces and Math

A co-worker of mine recently emailed me a link to a rage face comic with the following:

“Is this always true??? I mean the math part… Stephen???”

Knowing that I have an irrational love of rage faces as well as math, he knew I couldn’t resist trying to prove or disprove the algorithm presented in the comic, which I’ve displayed below (without permission) in case you didn’t follow the link.

So, here goes: Continue reading Rage Faces and Math

# The Story of Squaring a Triangle

Back in 1998, I overheard my high school math teacher musing to another teacher about the following problem:

Given a line segment of unit length, select any two points to cut the line into three parts. What is the probability that the resulting three line segments will form a “good” triangle.
By a “good” triangle, he meant one which completely encloses a non-zero area. That is, if the longest side is longer than the sum of the other two sides, it’s impossible to use those three segments to enclose an area. The trivial case exists where the longest side is equal to the sum of the shorter sides, but this triangle encloses no area.

A Delayed Response

Several years later, after I had learned to program myself, I wrote a Monte Carlo algorithm to simulate this situation, but much to my dismay, after 1000 trials, I got a probability of a little more than $.19$. To me, this certainly meant that the answer should really be $\frac{1}{5}$ – I just needed a few more trials. Unfortunately, as I increased my trial size, the number started converging to $.1931-ish$. This really disturbed me, but at the time, I was weak, so I gave up. Continue reading The Story of Squaring a Triangle

# Learning to play Mancala

Because I love genetic algorithms and video games, I always wanted to create some artificial intelligence that learns to play a game. My first attempt is the subject of this entry.

A college friend and roommate of mine once showed me how he used a GA to solve the two bishops chess endgame scenario from any position. I decided that it would be fun, and within my capabilities to focus on a simpler game, Mancala.

What’s a Genetic Algorithm?
A GA is just a search. Continue reading Learning to play Mancala

# Excel Dice Rolling Simulator

Probability distributions have a way of yielding unexpected and counter-intuitive results, so I thought it might be fun and instructive to build a “practical” example to illustrate some of the most often protested facts about them. Since speed and visual feedback are important, I decided to try to build a dice-rolling simulation in Excel. Continue reading Excel Dice Rolling Simulator

# How long will it take to get to Free Parking?

According to the official rules of Monopoly, landing on the Free Parking space results in no action, however, many house rules include some sort of financial reward for landing on this space. For instance, I have always collected everything paid to “The Bank” through Chance/Community Chest cards, the Luxury Tax space, and Income Tax space to give to the lucky one who hits Free Parking.

In any event, let’s find out how many rolls it takes to get there. Continue reading How long will it take to get to Free Parking?