Contest Analysis
Gerrymandering Contest Winners
We've come to the end of another exciting MATLAB Contest. Congratulations to Paulo
and all our winners! This contest included slight changes in format with the addition of Darkness and Twilight
phases. In these phases, competitors could submit code without their entries being visible to others.
If you want find out who the Kristine entry was dedicated to and why Ken Crounce named his
winning entry Mg3Si2O5(OH)4, read on to hear it from our winners.
Paulo Uribe
Grand Prize Winner
You might find Paolo's name familiar.
After all, he is the first person to win the coveted grand prize in three MATLAB Contests.
This is certainly no small achievement. Congratulations Paulo!
You can find out more about Paulo from his profile in the Molecule
Contest winner's page. Paulo also won the Grand Prize in the Mars Surveyor Contest.
Read on to find out how Paulo went from never having placed first in the course of the contest to winning the grand prize.
Other than for several minutes during the middle of the contest my submissions
were never ranked first until my final and winning entry was submitted at exactly 5:00 PM. I would like to thank
all hackers and spammers for not clogging the network at that time; otherwise my last submission would
have missed the deadline. I am also very proud that my algorithm entered during Darkness Phase was ranked
in the top five.
It was a rudimentary combination of a "snake" and "growing" algorithms but as with most entries ranked
below one, it never made it into the mix. However I noticed some of my contributions in the top entries
even though it had not claimed the top spot and was quite intrigued. Perhaps somebody picked them up from
the queue or searched second place entries for inspiration. Whoever it was, thanks for making me
part of the genetic code.
The modification that produced the winning entry was inspired by the mid-contest
analysis by Lucio. He provided some examples of convex and non-convex homogeneous maps where the
current leaders were failing. I created a snake algorithm that could spawn several “heads” and could
completely solve those types of maps. It became a 200+ line monster but would crash with certain maps.
I then realized that with a small modification to the sub function crystallise6, I could achieve the same
result. After testing it “undercover” in the official test suite I knew I had something valuable. It was
just a matter of tuning it for speed and holding it until the end. That was the hardest part as I was
really tempted to use it during the "60 Second Showdown". I am glad I did not succumb to temptation as
that was the difference between winning a shirt and a jacket!
--Paolo Uribe
Ken Crounse
End of Darkness Prize Winner
Ken is our very first End of Darkness
prize winner. His was able to develop the best scoring entry without feedback
from the official test suite or viewing any other submissions. Congratulations Ken!
Ken lives in Somerville, MA and works for Agfa Monotype Corp.
He is an imaging scientist working primarily on algorithms for halftoning and color reproduction.
Off the clock he uses MATLAB to solve mathematical puzzles, such as those found at
IBM Research "Ponder This".
Ken recalls first using MATLAB more than ten years ago in grad school at UC Berkeley,
where he was studying the computation capabilities and pattern-formation properties of certain retina-like processing chips
called cellular neural networks. His other technical interests include cellular automata,
image compression, and trying to understand the amazing human visual system.
I've been following the
MATLAB contest since Gene
Sequencing and have made a few submissions, but mostly
amused myself by watching how people
were attempting to reverse engineer it, and trying a
few such ideas myself. Although I would usually spend
some time thinking about a good approach to solving
the contest problem, I felt there was no way I could
keep up with the relentless group evolution of the
mainstream approach. Instead, I tended to go for
simple, uniform approaches that cover all the cases,
but may not be all that efficient. That allowed me to
get the first passing entry in the Infection round of
the Golf Contest. Also, I don't feel like I have
much to offer in solving discrete, combinatorial
problems, which the contest problems tend to be.
The darkness phase of the Gerrymandering Contest also
allowed me an opportunity to try a simple approach
without having it evolved. I drew heavily on
approaches I had seen previous contests, most notably converting two-dimension problems into one-dimension by using a snake. From the program names I could tell during the darkness phase that some others were using a similar approach. I think the only novelty of mine is that it would step-back-one along the snake if it
were locally beneficial to do so. By the way, the
name Mg3Si2O5(OH)4 was supposed to be a kind of
hint, since it is the chemical formula of a type of
Serpentine rock (common in the San Francisco Bay
Area).
Also, a note about The Great Rumpuscat:
although he is usually known from the musical Cats,
the best source of information on him can be found in
Old Possum's Book of Practical Cats by T.S. Eliot.
"You never saw anything Fiercer or Hairier!"
-- Ken Crounse
Klaas Hartmann
End of Twilight Prize Winner
Our first contest winner from down under, Klaas is a new name to the MATLAB Contest Hall of Fame.
Klaas recently completed his Bachelors with Honors in Mathematics at James Cook University
in North Queensland, Australia. His academic interest is in mathematical ecology and he hopes to pursue a
PhD in the near future. Klaas currently works at CSIRO Marine Research in Hobart, Tasmania. He uses MATLAB
on a daily basis in various applications ranging from analyzing species diversity throughout the Indo-Pacific region
to calculating orbital elements of binary star systems.
Klaas also enjoys the great outdoors. When not at work, you can find him out in the wilderness,
hiking or hanging off a cliff. A little known fact about Klaas is that he's spent five years of his
life aboard a sailing yacht, cruising the oceans with his parents and sister, instilling
in him a love of nature.
In the Darkness phase of the contest I mistakenly put excessive
emphasis on optimizing the speed of my simple algorithm. My algorithm broke down the problem
into a single one dimensional problem for which it was quite easy to find a good solution.
Once the entries were scored I realized that it was much more important to increase the quality of
the solution than the algorithm efficiency -- at least at this stage of the contest.
The one dimensional problem that I was solving is only one of many that
the full problem can be broken into, each of which generally has a different maximum score.
A few hours before the end of Twilight deadline I submitted an entry that solved a few different
1D versions of the 2D problem, and returned the best solution. This algorithm produced an unexpectedly
large increase in my score and over the next 2 hours I hurriedly (and messily!) incorporated a whole
swag of new methods for generating 1D problems, thus stealing the lead from François Glineur. My entry was
named after my wife, Kristine, who was very understanding about not getting any attention from me during
these first stages of the contest!
-- Klaas Hartmann
MR Keenan
Early Bird and Sixty Second Showdown Prize Winner
Another of our contest veterans, Mike
(a.k.a. MR Keenan) finished with not one but two prizes in the Gerrymandering Contest. His previous wins
include the Grand Prize in the MATLAB Protein Contest. You can find out more about Mike Keenan
on the winners page.
In his contest anecdote, Mike tells us more
about the minutes leading up to his two winning submissions.
I implemented the mysolver method during Twilight or Darkness, but
I found that it wasn't very effective without a good starting condition.
During Daylight, I grafted it onto Klaas Hartmann's Kristine and was lucky
enough to win the Early Bird prize. I had thought to save it to the end of
the contest but you never know if that will work!
One the last day of the contest, it was time for the 60 second showdown.
I noticed that my function (mysolver) was virtually unchanged since the
previous Friday and that it was still an integral part of the leading entry.
I noticed an entry from Paulo that scored a 0.209 and knew that I could tweak
mysolver to beat that. I got it down to 0.201 and then with some help from an
entry by Cleve Moler (of all people!), I got it down to 0.197 and won.
I have been using MATLAB for 19 years now, but I am still learning a lot from
these contests. Thanks to the Mathwork's team (and Klaas, Cleve and
Paulo) for a great contest. Although my specialty is the optimization of continuous
function, these discrete problems are a lot of fun.
-- MR Keenan
Christian Ylämäki
Big Sunday Push Prize Winner
We last heard from Christian during the Trucking Contest
in May last year, when he won the Midnight Madness Prize. Since then, he's started working on his
Master's thesis where he evaluates the performance of a paper machine control system, a task which
not surprisingly, MATLAB comes in handy.
Read on to learn about how Christian created his Ozzy solver, named for the Prince of Darkness.
My Sunday push involved many small tweaks and one slightly larger
modification where I included my own solver Ozzy. I had seen that Ozzy could
improve the result on the public testsuite and was planning on saving it for
the final showdown. However, I didn't have the patience to wait and
submitted it on Sunday already. It made quite a good improvement on the
result but was far to slow to run on all testcases, this led to the biggest
and most questionable tweaking effort in my contest history. In the end Ozzy
was only used when he could make an improvement on the score, this enabled
the program to run fast enough to take the lead.
The basic algorithm in Ozzy chooses the n biggest squares as starting districts
then continuously expands the smallest district by adding its biggest adjacent square.
The name Ozzy came from my first submission "Prince of darkness" aka Ozzy
Osborne. Inside Ozzy the word liberties is used, this is because I reused parts from
a simple Go playing program I wrote during a MATLAB course.
I would like to thank the MATLAB contest team and all the other contestants
for making this contest one of the best so far. Hopefully I will see you all
next time.
-- Christian Ylämäki
Vincent Wu
First Past Five Prize Winner
Vincent Zhili Wu is our First Past Five winner.
He attended Tsinghua University in Beijing, China
and is currently pursuing his Masters degree in the areas of machine learning and data mining at Hong Kong Baptist University.
Having used
MATLAB for more than three years, he always tries to convince his friends to convert to MATLAB. Recently,
he also achieved good results in the research-oriented NIPS 2003
Feature Selection Competition by using MATLAB as the development environment.
Vincent's other interests include chess, Chinese calligraphy,
and reading.
When the snake approach dominated in the daylight stage, people were fighting
with unreadable tweaks. Each time we improved the code a little, a slightly
faster hastily put together version appeared. What we should have done was to work harder
on readable versions - I think this was in fact the real darkness time! Later I noticed
that each snake path was independent of the set of mirror-symmetrical transforms of an input map,
and was even insensitive to the central-symmetrical transforms of a square map. I then submitted
the reUsePattern1 by rewriting the function structures to separate the process of specifying snake
patterns, such that for each map the snake patterns can be reduced to 5 or 10, not the originally 40.
People could then easily devise snake patterns, instead of doing extreme tweaking. Later
Christian contributed most for pattern construction and deserved to win the Big Sunday Push prize.
Also we should thank a neatly written version of code, which forced hastily written code out.
Soon the snake methods suffered a bottleneck. People started to combine
other methods, but the plateau come again with many specific parameters shown in submissions. At
first I didn't understand why so many magic numbers appeared, later I figured out these
numbers were from tuning through multiple submissions, I then simply added constants
into the whySpecificConstant, which won me the First Pass Five prize just after two guesses.
-- Vincent Zhili Wu
Roger Stuckey
Midnight Madness Prize Winner
In this contest, we have two winners from Australia! Roger works
at the Defence Science and Technology Organisation, Australia,
and is currently living in Melbourne. He's been using MATLAB since the early 1990's back when it was called
PC-MATLAB and ran from a text-prompt within MS-DOS. More recently, he's used it extensively for his PhD in
Aeronautical Engineering at the University of Sydney, during
which he developed a set of routines for the estimation of nonlinear aircraft stability and control
parameters from flight data. A MATLAB champion, Roger also started a MATLAB User Group for
sharing ideas and code at DTSO, where he works.
Well another contest draws to an end and after participating in a few, I have finally
managed to score a place amongst the winners! The latest contest was, again, quite different
to the previous ones with periods of "Darkness" and "Twilight". Like many others, I found
these stages the most fun and challenging, since everyone was using their own unique algorithms
to solve the problem. Unfortunately, the program I was developing was way off the lead
(as estimated with the test-suite) at the time, so I spent most of my time refining and testing offline.
When "Daylight" broke, many of the entries got left behind or merged with the leading one, and the
tweaking began. It would have been interesting to see a snapshot of the entries, including their
performance, prior to Daylight. And as Lucio pointed out in his
Mid-Contest Analysis, a fundamentally different growing algorithm may have found the exact
solution to a map with non-convex districts, whereas the snake approach, such as the one the
leading entries were based on, never would.
During the "Midnight Madness" stage (actually more like "Afternoon Madness" down here),
I focused on one of the test cases in which the top entry performed the worst - an evenly
distributed scatter of squares with equal population. By generating a greater number of
vertical divisions for the snake-algorithm to work on, I was able to achieve a more even
distribution of the districts and a better result.
For me, the rest of the contest involved mostly offline work, as I endeavoured to
improve my algorithm to an acceptable level. Finally, on the last day, I realised that
it could, in fact, get better results, but only for certain maps, and it took longer to execute too :)
So I decided to amalgamate my code with the leading entry and employ the algorithm only for a
limited range of cases. My final submission:
All Your Rectangles Are Belong To Us V2.6 managed 0.001% better score, but took roughly 0.2 sec
longer than the leader at the time and consequently didn't get a top placing. But then, as we all know,
at 0.005% under the mark, and about about 0.005 seconds before the deadline, Paulo's entry came
in and blitzed the field anyway!
-- Roger Stuckey
Yi Cao
Tuesday Leap Prize Winner
Yi Cao adds another contest to his belt by winning his
fourth prize in a MATLAB Contest! In this contest, he was awarded the Tuesday Leap
Prize for making the largest single improvement to the top score of the day.
A university lecturer in the UK, Yi Cao has previously won prizes in the Trucking,
Protein, and Molecule contests.
This seems to be my style of participation in MATLAB contests: a lazy brain does
not know how to solve the problem at first, then starts to looking around trying to understand what
others do and to identify room for improvement, finally the brain cannot stop itself from analyzing
the problem even after the contest ends. Obviously, this lazy brain could not cope with a contest like Golf.
I am glad that the contest is back to its usual form. I still could not produce any useful
algorithms during Darkness and Twilight phases, but it didn't stop me from spending more and more time on it.
The repeated
submatrices idea was inherited from original code to identify repeated rows. Initially, it only
considered a factor of 2 but I extended it for columns (Repeated Square). However, no improvement
was observed from the official testsuit although it did improve on the sample testsuite. During the Big
Tuesday Leap sub-contest, I suddenly found the code had been upgrated for multiple factors. Therefore, I
thought it was worth a try to do the column search again. However, when I submitted it, I never expected
it would produce such a big leap in score. That was why I just edited it online and didn't bother to test it
on the testsuit. Luckily, I did it and got the prize.
-- Yi Cao
|
