The MATLAB Ants Contest has come to an end. Thanks to all the participants and spectators who have helped make the contest a success, and congratulations to all our winners!
Hannes and Cobus, we haven't heard from you, so please contact us regarding your prize. Read on to see photos of our winners and read about their contest stories.
MATLAB Contest Grand Prize Winner, the cyclist, has finally revealed his identity. Tim Vaughan, who lives near the MathWorks headquarters in Natick, MA is the Ants Contest winner.
Tim has been programming in MATLAB for almost 13 years now. During the course of his career, he has used it in a variety of areas ranging from theoretical particle physics and biophysics to financial risk modeling. This contest, however, provides Tim with his first glimpse into the world of pismire neurology.
Ants was the fifth Programming Contest that I have entered, and it was simultaneously the most interesting and the most infuriating for me. Unlike past contests, in which I primarily tuned in to search for simple tweaks, this time around I tried to keep up with the algorithmic improvements too. Having a better conceptual idea of the solutions was more satisfying; but the early, random plummet into a deep local minimum caused many frustrations, as my "brilliant" ideas that glutted the test-suite anthills came up empty in the contest.
I'm indebted to JohanH and the prolific Mr. Alderson, and I'm glad to see that they both won prizes. The key to my "soo sneaky" was noticing that JohanH's nut-cracking breakthrough had been based on TLL280, a relatively ancient entry. I was able to meld them and rattle off several clones to protect against the vagaries of CPU timing.
Kudos to The MathWorks and the Contest Team for another fun contest.
Jack Snoeyink is a professor in the department of computer science at the University of North Carolina at Chapel Hill, and his main research is in computational geometry -- algorithms and data structure for geometric problems that arise in computer graphics, GIS, and molecular biology.
In addition to using MATLAB for prototyping in his work, he created a one-semester introduction to computer programming for science majors that uses MATLAB as the programming language. In his e-mail to us, Jack tells us his inspiration for trying to solve the ant puzzle.
I first participated in the Mastermind Contest (Sept 2001), because I was teaching a MATLAB-based programming course at UNC Chapel Hill. I learned a lot about the just-in-time compiler from later contests, so when I learned I'd be teaching that course again in the fall, I looked into the latest contest and got hooked into spending time that I didn't have.
I liked the ant problem for several reasons, the main one being that David Kirk, nVIDEA's chief scientist, had just complained in a talk here that students are taught sequential programming, when multicore, multithreaded, and vector processors will soon be dominant. I agreed and commented that I would try to teach MATLAB's vector operations before introducing if-then and loops, but couldn't find a book with that order. Let me know if you have any suggestions (other than David's of writing my own).
So identical, parallel ants with no memory but the scents they put down sounded good. Since each ant runs the identical code, there was less chance for the long, case-based, patchwork code that was successful in other contests. It was fun seeing the ideas at the end of Twilight. It was unfortunate that Jan hit the magic random number so early, so that we didn't have as many moments when new algorithm ideas trumped code-tuning efforts.
-- Jack Snoeyink
Hannes and Cobus are from Pretoria, in South Africa. They are currently electronic engineers at Denel Aerospace Systems. Occasionally they have the opportunity to play around with some algorithms in MATLAB, but mainly use lower-level languages such as C.
When the contest first started, they tried developing their own algorithms individually, but found it very helpful to be able to explain the algorithm out loud to someone else. The other perspective, as well as the need to organise one's train of thought before being able to explain the concept to another person turned out to be tremendously helpful. They continued to code more or less separately, but implemented similar sets of algorithms. It was amazing to see how differently the same algorithm could behave due to subtle differences in implementation.
Originally we intended to only participate in the darkness and twilight phases, since we didn't really have the time that would be needed to keep up with the algorithms during daylight. The fact that the size of the code didn't grow exponentially as in previous contests allowed us to keep up to date without stealing too many work hours, even in the daylight phase.
Our focus remained on improving our own algorithms (but this didn't prevent us from using Jan's beautiful code as a base from which to work!), and although we seemed to make some good improvements, we couldn't beat the magic 18563!
We enjoyed the contest immensely and are eagerly awaiting the next one.
-- Hannes and Cobus
Jan Langer is a student of Information Technology at Chemnitz University of Technology in Germany, where he's currently finishing his master's thesis. He hasn't had the opportunity to use MATLAB much outside of his course projects, though I'm sure we all agree that he's very good at it.
This is Jan's third contest and favorite MATLAB contest so far. When he saw the rules for the recent contest, he noticed that it was similar to another programming contest (ICFP'04), in which he had no chance to participate. He was excited to be given a second chance.
At the beginning of daylight, I noticed that the leading entry more or less only used the inner 3x3 matrix for scent navigation. In earlier attempts during twilight I already tried to write an entry using the full 5x5 matrix for navigation, but I had problems with ants getting stuck at corners and the like.
The butz benser entry (named after the famous actor Bud Spencer) winning the Big Sunday Push was actually a rewrite of the ideas in the current leader with the addition of 5x5 navigation. This time it worked because I marked areas behind walls or around corners as walls. After some work with the MATLAB profiler (which is great to work with) and several random numbers (5 to be exact ;-)), I was lucky to hit the top spot.
After unsuccessfully having tried to win the Big Sunday Push twice, I kept nervously watching the queue all night and saw Timothy Alderson coming closer by many little steps, but in the end the initial jump was big enough.
The problem seems perfect for a programming contest. The huge impact of random numbers and the rather large runtime causing the queue to be very packed most of the time, were a little unfortunate.
-- Jan Langer
You might recognize Niilo Sirola from the previous Furniture Moving Contest where he won the Big Sunday Push prize. Congratulations Niilo on being a second-time winner!
Since the last contest, he has been in the UK for the spring semester as a visiting researcher at the University of Manchester. He will be back in Finland this summer to complete his Ph.D. in applied mathematics at the Tampere University of Technology.
Again in this contest, I spent most of my time developing my original algorithm that in the end didn't come even near the leading entries. When everything else failed, I even collected all the ad hoc parameters in one vector and ran a direct search optimization over those parameters overnight, but even that didn't get me in top 200.
So, by Monday I was all set for starting the blind speed-up tweaking of other entries. Actually, my largest improvement was some kind of typo which fortunately improved the results (is this evolutionary programming or what!). Finally, when the midnight was getting near, I noticed that the leading entries still lacked some of the tweaks I'd been doing the whole day so I made my own versions of the most promising entries in the queue and it paid off. Too bad I wasn't around when the contest finished as the winning entry still seems to have bit of slack in it...
-- Niilo Sirola
Timothy Alderson is another second-time contest prize winner. Like Niilo, he also won a prize in the last Furniture Moving Contest. Congratulations, Timothy!Timothy is married with two children, ages six and four. He currently works for Lockheed Martin in Orlando Florida as an electro-optical engineer. He uses MATLAB daily for image processing on the Apache night vision sensor upgrade.
I found this to be very enjoyable even though I think it fizzled in the last few days due to a magic number local minimum that occurred. I was in the lead with a time tweak of an algorithm from 24 hours earlier when I saw the next phase of the contest and submitted an entry with no tweaks to be first in line (18 seconds after start). After that when no new higher scores were seen over the next 20 hours (even though many better algorithms were tried) I won this.
I have participated in the last 4 contests and I think this one I ended up concentrating more on time tweaks than the others. It was an enjoyable experience overall and I look forward to the next contest. Thanks MathWorks for continuing to host these events.
-- Timothy Alderson