The MathWorks News & Notes - January 2006

MATLAB Central
Competitive Collaboration:

The MATLAB Programming Contest

By Ned Gulley

Suppose you were in a car race and after every lap you could ask to drive the current leader’s car instead of your own. Now suppose that everyone else in the race could do this.

The MathWorks sponsors a programming contest that works like this imaginary car race. Twice a year, for about a week, participants submit short MATLAB programs that solve a specific problem as quickly as possible, and all entries are freely available to everyone. Thus, if your clever code is in first place, I can copy it, modify it, and enter it under my name. The result is a chaotic, unfair, yet wildly successful collaborative competition. What is the secret of its success?

How the Contest Works

The MATLAB programming contest typically involves tricky optimization problems like the Traveling Salesman: “What is the shortest possible trip through a set of cities?” Contestants must write a MATLAB program that, given the city locations, returns an ordered list that provides the shortest route through all the cities. Submissions are immediately scored, ranked, and displayed for all to see. Scoring is based on each algorithm’s results (distance traveled and calculation time, both of which are to be minimized). Time limits force contestants to explore the trade-offs between performance and execution speed.

The contest is divided into three phases: “darkness,” when you submit your own code but cannot see other people’s code; “twilight,” when you can see everybody’s score but not their code; and “daylight,” a free-for-all that encourages code-stealing and open discussion of solutions and strategies. A typical contest gets several thousand entries. Some contestants submit a single entry, while others submit dozens (Figure 1).

Figure 1. Click on image to see enlarged view.

Visualizing the Results

Figure 2 shows the entries from our May 2005 contest. We plot each entry’s score against the submission time, so the horizontal axis spans one week. The entry with the lowest score when the contest closes wins. The red line, which traces the current best (lowest) score at any point, declines steadily until it stops with the winning entry.

Figure 2. Click on image to see enlarged view.

A nearly flat red line reflects small code changes. Big vertical drops or leaps in performance are rarer and indicate more fundamental improvements. A leading strategy tends to get repeated minor modifications, or tweaks, before a significantly different approach displaces it. The interplay between these two approaches—alternating leaps and tweaks—leads to the stair-step pattern you see in the graph. Contestants constantly probe the leader for weak spots. Stretches of tweaking can be interrupted by sudden, dramatic shifts that present fresh tweaking opportunities as competitors tighten up the new leader. Though some contestants complain about tweaking, it keeps them coming back!

Collaborative contests are unusual. Despite, or perhaps because of how easily contestants can “drive the leader’s car,” they regularly tell us how much fun they’re having. “It’s one of the most addictive things I have tried,” says one. The result is a winning entry that, rather than being the work of a lone coder, is a tapestry spontaneously assembled by dozens of people.