The MATLAB Peg Solitaire Contest has come to an end. We hope you enjoyed it as much as we did.
Thanks to all the participants and spectators who have helped make this contest such a great success. Congratulations to all our winners! We also want to give a special "high-five" to those winners who are already in our MATLAB Contest Hall of Fame, yet made the effort to participate again in this contest.
Yi Cao, our Twilight and Grand winner is no stranger in MATLAB Contests having previously won prizes in the Gerrymander, Trucking, Protein, and Molecule contests.When not participating in our contests, Yi is also a university lecturer in the UK.
Peg Solitaire is an interesting contest. The problem is simple and easy to be understood. Anyone with reasonable MATLAB knowledge should be able to develop a valid solver. However, the problem is also so hard that after 7 days of hard work, many contestants believe we are still far away from the optimal solution. This motivated a long post-contest discussion in the newsgroup.
After 7 days evolution, the winning code Buy a ticket, like many other mature code submissions, had become very complex, with length over 30,000 characters. To explain such a code within a limited space is a difficult task. Thanks to Alan Chalker, who did a great job buy putting very detailed comments twice into winning entries during the contest. Most of these comments are still available in the final wining code. Because of his great work, in this Final Analysis, instead of to explain the winning code, I decided to tell stories about code development and contest evolution. From these stories we may better understand the code origins.
Read more from Yi's Final Analysis
Stefan Rach, know in the contest as srach, lives in Oldenburg, a city in northern Germany. He is a psychologist and works as a research associate at the department of Psychology at the University of Oldenburg, Germany. He is also a PhD-student at the Jacobs University Bremen. His research areas are psychophysics, multisensory integration and Fechnerian Scaling.
He originally learned MATLAB during his second undergrad year in 2001. Since 2004, he has continued to use MATLAB everyday for data analysis and stochastic modeling and for preparation of experimental visual and auditory stimuli.
Peg Solitaire was the third contest I took part in. Unfortunately, my time was very limited during darkness and twilight, thus, my own algorithms were very underdeveloped as daytime arrived.
During daytime I tried to understand the leading entries -thanks to Alan Chalker for contributing "Guided tour to dreamland I & II". Both were of great help to me. I focused on decreasing processing time. First by searching the board for non-moveable pegs and resizing the board accordingly ("pslct"-entries). Then I tried finding criteria to limit the number of calls to subsol after a certain score is reached ("leave early"-entries and "leave even earlier"-entries).
When I noticed the "Best result by 4 pm" contest it was already 2 pm. I noticed that the leading entry used only 165 seconds of processing time. Thus, I concentrated on how to spend additional 15 seconds of runtime. In the end, the winning entry "any candies left? 5" just made use of one additional call to the randomized version of subsol.
This contest was really fun and I would like to thank the MATLAB contest team for organizing it.
-- Stefan Rach
Sergey Yurgenson has a Ph.D. in physics from Leningrad State University (Russia). Currently Sergey works at Harvard Medical School. He uses MATLAB for data analysis and control of data acquisition in neurobiology research.
I did not start very well during Darkness and Twilight. I spent time trying to find significant algorithm improvement rather than introducing small tweaks. However, at some moment, I looked at the best 1000 Character Challenge submission and recognized my Twilight code stripped to 1000 characters! Naturally I decided to play with it a little bit more! In several hours, it was overpowered by very good recursive algorithm by Steve Hoelzer, but I was hooked to the 1000 character challenge already.
My new algorithm was soon optimized time-vise, but I could not improve my overall result for many more hours. It was difficult to make significant algorithm modifications within the code size limit. I came to the conclusion that the only option was to introduce a weighting coefficient. The first version I tried produced a good result improvement, so my plan became not to look further. Instead, I tried to find the best weighting parameter for the test board set and to submit the code at the last moment. This strategy worked and my submission Cat45 took first place with a reasonable lead. (There was a fascinating discussion about move metrics and weighting coefficients after the competition in newsgroup)
Next morning, while studying current best code (“testing again 2+” by Jin), I realized that there was a simple improvement to it. Worrying that somebody else would soon discover it, I submitted the code and continued working on some other ideas. However, shortly after that, 3 min contest was announced and it completely stalled the queue. I finished second in the 3 min competition - the main benefit for me was that it slowed the queue, making practically impossible to test any new tweaks and ideas ! That allowed my morning entry CatIsWakingUp to stay on top until finish of Tuesday leap competition.
-- Sergey Yurgenson
Markus is from Germany. He is already a member of the the MATLAB Contest Hall of Fame, having won Twilight in the Blockbuster contest. He is currently a scientific associate and Ph.D. student at the University of Stuttgart. His research area is automotive radar. Markus completed his undergraduate degree at the University of Bochum. He also spent four months in Princeton, New Jersey as an intern at Siemens.
Markus has been using MATLAB since 1999. Today, he works mainly in MATLAB and uses it for larger projects implementing classes and objects.
During darkness and twilight I have been working on my own solution to the Peg Solitaire Contest. I implemented a recursive depth-first search, but there were too many for-loops in it and the conditions to stop searching were not very well. So I ended only in positions 7 and 12.
The degree of vectorization in the twilight winning code of Yi Cao was impressive, so I immediately started working on it (still without the comments that Alan Chalker introduced later). I found large space for optimization, first by padding the board to avoid boundary checking, then by avoiding to compute intermediate results that were not used. Short before the deadline of the Saturday Early Morning Special, I discovered the commented version of Alan Chalker. As I considered it a brilliant idea in the spirit of the contest, I started introducing the comments into my optimized version. However, in merging the two versions, I introduced an algorithmic error and my submission markus8 did not get on top.
Well, as markus8 finished somewhere in no man's land, of course no one took notice of the code improvement. So I had the chance to use it in another attempt. My submission markus9 - now with the error corrected - made an improvement about 8 points. However, looking into the statistics later that day, I was disappointed that Jan Langer had already reached a cumulative improvement of more than 10 points by numerous tweaking contributions.
But, to my great surprise, my optimization disappeared from the leading code again over the day! Nathan Quinlan introduced a fast update to the vector of possible moves, an even larger boost in computation speed. He took the lead with his submission about an hour after mine, but without merging his optimization with that of my version. As the other contestants now started working on the code of the new leader, it happened that I had a third chance to use the same modification again. This time the impact was even larger (about 18 points), lifting me up to win the Big Sunday Push. I guess in the next contest, I may not hope that Nathan gives me such assistance again in winning a midcontest prize. :-)
A great thank you goes to the contest team, who again managed to keep a whole lot of MATLAB programmers busy and entertained!
-- Markus Buehren
Nick Howe teaches computer science at Smith College in western Massachusetts. He uses MATLAB extensively to conduct research on problems in computer vision. His first entry was in the Gerrymandering contest, and he has been participating on and off ever since.
On the Darkness winner:
I prefer the Darkness and Twilight phases because of their limited time spans. In several previous contests, I had come close to winning one of these phases, but always fell a bit short. I actually didn't expect to come out on top with this one — unlike previous contests, I didn't feel like I had any special tricks up my sleeve. The entry that won was one of a series of implementations of a simple beam search algorithm, basically just the textbook solution to a problem of this kind. My first attempt used a fixed beam size and was fairly slow. In developing the winning entry, I adjusted the beam size according to the size of the puzzle and the steepness of the fitness curve at each step, and I had improved the speed of the code to allow searching many more possible moves. Because the beam size directly controlled the running time of the code, it was easy to select any time/performance tradeoff that I desired. I tried to limit the number of different variants to a reasonable number, so it was partially luck that one of the entries turned out to be fairly well tuned for the test set.
On the Early Bird winner:
Lots of development was going on with Yi Cao's twilight winner, but I was still hoping I could improve my own Darkness code to make it competitive. I noticed that the leading solver didn't do so well on small board sizes, so I thought I could combine the two by choosing the my own solver for the small boards. Well, as I was working this out, the leading solver's score was steadily dropping, and by the Early Bird deadline the added benefit offered by my solver was too small to make up for the time penalty it incurred. However, I had noticed another piece of Twilight code by Jim Mikola that also seemed to do well on small problems, and so I made up a similar combination entry using that code.
I only finished it a few minutes before the deadline, and luckily for me it worked without any bugs and won the prize.
-- Nick Howe