The MATLAB Blackbox 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 the Blackbox 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.
This is the first time Alan has won a prize in the MATLAB Programming Contest. He has completed three previous contests, and was mentioned in the Blockbuster contest blog.
He has been using MATLAB for about 10 years, originally learning at Ohio State University where he was working on his degree in electrical engineering. He also has a Ph.D. in biomedical engineering from the University of North Carolina at Chapel Hill.
Alan works as a Senior Systems Designer for the Ohio Supercomputer Center in Columbus, Ohio. His team works with MATLAB as part of several Department of Defense (DOD) contracts, providing high-level support and training to DoD High Performance Computing (HPC) users all over the country. Most of their efforts focus on parallel MATLAB (e.g. DCE/DCT, MPI, etc). They offer training classes on MATLAB throughout each year at various DoD facilities.
He describes his winning contest strategy:
The first entries I tried during darkness were simple raster scans, with high beams in some to try to 'clear the board'. I ended up with the 8th best entry, but it was nowhere near as sophisticated as the better scoring entries.
On Friday Steve Hoelzer submitted entries ("worst score ever") that tried to max out the results (one was 20 digits long), and it occurred to me that the results could pass information about the contents of the test suite. Specific details of all the probing I did are included in the final analysis writeup.
In addition to the probing, at times I tried improving the leading algorithm's running time via Profile command output analysis. There were several tweaks that briefly gave me the lead, such switching from global variables to nested functions ("this is the end").
Monday was the 1000 character challenge and I ended up in 10th place, behind nine entries from Alfonso Nieto-Castanon. That challenge was the first use of a probed lookup table, which David Jones introduced ("Almost Concise Enough"). My entry was a speed-up tweak of his entry.
Since there was discussion in the newsgroups about the probing, and I knew other people were scrutinizing my entries, I reluctantly decided to introduce obscufated code. I used a short script that copied random lines into end of line comments. This made it tedious enough to decipher to deter casual inspection but not impossible for others to read via dedicated effort.
Tuesday was the Leap and I introduced some more lookup tables in an attempt to win. My winning entry ("Persistence pays off") included the n=40, 60, 34, 53 and 55 cases and utilized the then leading algorithm for the rest. Those 4 new lookup tables improved the results by almost 400 points, or over a 3x improvement.
On Wednesday, I continued probing and ended up with ~800 total entries for the contest, the third most of any competitor. I ended up with tables for the n=55, 40, 35, 60, 34, 53, and 16 tests. In the final minutes of the contest, during the traditional entry submission rush, I submitted a series of entries (e.g. "This must be the end!", "The end of the ends"), most of which were deliberately bad, and were immediately copied by several other people. The winning entry ("End of it all") was submitted with less than 3 minutes to go and improved upon the previous leader by ~300 points.
On a final note, when the generality contest was announced, I went through the statistics page and essentially resubmitted entries that had held a significant lead at some point. One entry ("generality try 11"), which was the runner-up, was based upon Per Rutquist's twilight winning entry ("Aargh :-)"), which is a very interesting result.
-- Alan Chalker
See also Alan's Blackbox Final Analysis of contest highlights and strategies.
Alfonso is a telecommunication engineer from Spain. He has a Ph.D. on computational neuroscience at Boston University working on neural models of speech and fMRI analyses. Recently, he has moved to Argentina where he consults on data mining and data analysis for neuroscience, as well as other fields.
In this contest for the 1000 character challenge the algorithm was simply a variation on the common rastering strategy. It had the ability to do a raster following any direction in the board, and it decided what direction best to do this from attempting to avoid when possible rather than solve the problems starting the rastering. This algorithm still did a complete raster of the board, not sparing any particle. The version that got the generality award was a continuation of this version that had the added ability to spare one or two lines at the end of the raster, when it was possible to spare two lines the algorithm would try to find the lines with the heaviest particles to spare. This version also had some added intelligence into the cases where there were unavoidable problems starting the rastering (it used a scan of the problematic line of particles together with the information of the rest of the puzzle once it was solved to estimate using learned a-prioris the likelihood of the unknown particle positions; I found myself without enough time to truly optimize this portion of the algorithm but it produced good guesses nevertheless).
-- Alfonso Nieto-Castanon
Jan is from the Saxon city of Chemnitz in Germany. He is a research assistant at the System and Circuit Design Group at the Chemnitz University of Technology.
He says he uses "MATLAB only occassionally", which is quite remarkable as he has definitely shown his skills in previous contests, including winning the Big Sunday Push Prize in the Ant contest.
Again, I tried to participate in Darkness and Twilight, but didn't read the rules too well. So, I didn't recognize that detecting and destroying the blocks actually saves points. My Darkness entry just tried to detect some blocks at the edges and was not even near the winning entries.
As every contest I tried to spend the Saturday to read and understand the top entry and think of possible improvements. The only thing which actually improved the score was some minor correction of corner block detection (entry "der schwabke is noch off"). Then I saw Per Rutquist's great improvement "R" and looked at it. He stopped the destruction not at the last line but the one before, and detected the last line from the bottom. I had played with something similar (e.g. 33663) but it didn't work and I was too tired to do much debugging.
While reading "R" I had this idea of not stopping at the last two lines but at another place in the middle, more densely packed with blocks. Fortunately, this worked very well and gave me the lead. Afterwards I followed the queue (until it crashed) closely, but had no real ideas left.
However, when entry "OneMoreCat" got the lead on Tuesday, it took advantage of a bug in my code, and I noticed that there was still some (probably quite small) room for improvement (in estimating which two lines save the most points if they are not destroyed). But with Alan Chalker's Testsuite Recovery Project in progress, there was not much use in implementing this idea.
In the end, the problem has been really good and I had a lot of fun. I especially liked that there was not too much influence of random numbers. However, the next time I think about also trying to go for testsuite recovery right from the start, if that is feasible. Because some people probably will do, and then the contest is boring for the others.
-- Jan Langer
David is a professor in the department of Electrical and Computer Engineering at McMaster University. His main research is computational vision. David uses MATLAB in his research lab for running visual psychophysics and brain imaging experiments as well as data analysis and computational modeling, and simulations.
Per works for Volvo Technology Corporation in Gothenburg, Sweden. He is also a Ph.D. student in the Control and Automation Laboratory at Chalmers University of Technology. Per is a veteran 7-year MATLAB user. Currently he is using MATLAB in building fuel cell models as well as for implementing dynamic programming algorithms. I like the "darkness" and "twilight" phases of the Matlab contests best, so that is usually where I put my energy. This year I put a typo in the would-be-winning code for darkness (which I of course didn't realize until the results were published). Before daylight I think most people either focused on hardly using the "high" beam (which was the strategy hinted at in the rules) or blowing up everything (which worked much better). My strategy was to blow up *almost* everything, which proved quite successful in twilight. -- Per Rutquist Cobus Potgieter is from Pretoria, in South Africa. He is currently an electronic engineer at Denel Aerospace Systems. His name may sound familiar as he has been a prize winner in both the Blockbuster and Ants contests. In those contests he worked with team mate Hannes Nuadé. Most of his development is done in lower-level languages such as C, but his enjoys finding opportunities to play around with some algorithms in MATLAB.
Per works for Volvo Technology Corporation in Gothenburg, Sweden. He is also a Ph.D. student in the Control and Automation Laboratory at Chalmers University of Technology.
Per is a veteran 7-year MATLAB user. Currently he is using MATLAB in building fuel cell models as well as for implementing dynamic programming algorithms.
I like the "darkness" and "twilight" phases of the Matlab contests best, so that is usually where I put my energy. This year I put a typo in the would-be-winning code for darkness (which I of course didn't realize until the results were published). Before daylight I think most people either focused on hardly using the "high" beam (which was the strategy hinted at in the rules) or blowing up everything (which worked much better). My strategy was to blow up *almost* everything, which proved quite successful in twilight.
-- Per Rutquist
Cobus Potgieter is from Pretoria, in South Africa. He is currently an electronic engineer at Denel Aerospace Systems. His name may sound familiar as he has been a prize winner in both the Blockbuster and Ants contests. In those contests he worked with team mate Hannes Nuadé.
Most of his development is done in lower-level languages such as C, but his enjoys finding opportunities to play around with some algorithms in MATLAB.