The Fall 2011 MATLAB® Programming Contest has come to an end. Thanks to all the participants and spectators who have helped make the Vines Contest a success.
Congratulations to all of our prize winners!
Alfonso Nieto-Castañón is a returning player to the MATLAB Programming Contest. He was the Grand Prize Winner of the Color Bridge Contest .
This has been a very interesting contest. The problem was complex and very well designed to take advantage to the ‘intelligence of the crowd’, where many different approaches were possible, and each contributed to improving the score on a subset of board types. There was a big collaborative feeling throughout the contest, and while I was only able to participate in the beginning and end stages of the contest I was very lucky to have an impact on the incremental development of the winning entry both with an early stage general algorithm that solved reasonably well many boards, as well as some last day tweaks and new ideas complementing the existing solvers.
Darkness-prize algorithm: First I considered an algorithm that did not use any tile movements. If there are no adjacent same-valued tiles on the board, the optimal vine can be computed using a standard Bellman-Ford algorithm. When adjacent same-valued tiles are present on the board this introduces closed loops on the previous approach and computing the optimal solution becomes considerably harder. For these cases, I divided the problem into two somewhat separate problems. First I computed all clusters of connected same-valued tiles, and computed an optimal between-clusters trajectory using the same Bellman-Ford algorithm as before. Once the optimal between-clusters path was defined, then, within-clusters, I used Dijkstra algorithm to compute the (shortest-path) trajectory between the entry tile and all possible exit tiles within each cluster (and chose the furthest exit tile possible). This was followed by a Peano-style recursion to grow the previous path into a longer path trying to flood each entire cluster. After all of this I added some additional post-processing steps to further grow the resulting vine now aided by tile movements. The approach was very simple: first I used the same Peano-style recursion as before to grow the vine using tile movements to bring compatible tiles adjacent to the current vine. This was followed by a method that extended the two end-points of the vine using a greedy approach that moved the next lowest/highest-valued tile on the board to a position adjacent to the end/begin- endpoint of the current vine. The combined algorithm performed reasonably well on most boards, and it allowed me to win the Darkness phase, followed closely by Robert Macrae and Nicholas Howe’s entries. Nevertheless my algorithm produced clearly suboptimal solutions for those cases where there were a lot of available tile movements where more structured tile-movement strategies clearly dominated (as Nicholas Howe showed with his effective Twilight entry).
Grand-prize algorithm: After some real-world interruptions I was again able to come back to the problem for the last days of the contest and I was happy to see that the original algorithm had survived with relatively few changes within the currently leading entries of the competition. This algorithm was mixed with a plethora of other algorithms (from Nicholas Howe, Robert Macrae, Kurt Janssens, and Michael C., among many others) many focusing on solving individual sub-types of high-scoring boards. In addition Sebastian Ullmann and Wesley had introduced the SimpleLongestPath function which offered an order of magnitude speed improvement over my original Bellman-Ford algorithm as well as other similar implementations solving the no-tile-movement problem. I adapted this function to work as well on the between-clusters problem and that gave me a very nice speed improvement, so I decided to see if I could squeeze a few more points from my previous algorithm simply by increasing the complexity of the tile-movement post-processing strategy (which on many boards seemed to be ‘wasting’movements on low-gain vine-growing strategies while other higher-gain growth strategies were visually apparent). The new version used a single method that precomputed a list of all individual vine-growth choices (among Peano-style and end-point growth methods), and then chose sequentially the next individual vine-growth step using a greedy maximization of the expected score-gain by number-of-tile-movements ratio (updating the list after each step). In addition to this improved ‘baseline’ method, and motivated by Robert and Nick discussion about a potential new method based on spiral patterns, I also created a new ‘spiral’ solver, which would simply try to move sequentially the next highest-valued tile into a vine forming a predetermined spiral pattern starting from the center and fitted to the shape of the board (and limiting the choice of next tiles candidate to those within a given radius of the vine end-tile at each step). Last I added both of these methods to a very competitive mix of solvers created by Amit Rajora (rsk-red vs tm). On the testsuite, the ‘baseline’ method was the best method on 80% of the boards, and the ‘spiral’ method was the best method on 10% of the boards (the remaining 10% of the boards were solved best by some of the other solvers present in Amit’s entry). I was happy to see that on the contest suite the combination of Amit’s solver with my ‘baseline’ solver (lasttry01 entry) improved the score by 6197 points, and adding the ‘spiral’ solver to the mix (lasttry03 entry) got to further improve the results by an additional 5659 points, which sufficed to place my entry on the top position, followed by Nicholas Howe (implementing a very competitive and somewhat similarly-spirited set of algorithmic improvements), and Magnus S (the best-among-tweakers entry with a smart selective board-rotation tweak).
As always this contest has been a very stimulating experience, and I would like to thank the Matlab team for making it happen. I learned a lot from the multiple approaches brought to the table, and I remain hooked waiting to see the next problem that the Matlab team comes up with!
I am currently working at Marine Biological Lab in Woods Hole, MA after completing my M.S. in Biomedical Engineering at Drexel University in 2009. At MBL, I work as a Software Developer in support of developing state-of-the-art imaging systems, microscopy applications and techniques. MATLAB has been an integral part throughout my graduate studies and at my current work place. I primarily use MATLAB for algorithm development, image processing, instrumentation and signal processing. I also enjoy using MATLAB for its versatility and interacting with Java and C# to develop quick customizable solutions.
For The Saturday Leap prize, I followed my previous contest experience and that was to add a new solver to the code. However, Alfonso's and Nick's solver worked well on most of the boards which left less room for improvement. To gain a significant leap I decided to focus on high value boards which would yield significant improvement and to further reduce the net, targeted boards that showed some sort of trending. The result was implementing Robert's solver to the mix focusing on boards that had a continuous back and forth gradient with scattered speckles. The filter tried to eliminate the upward turns in a trial vine by overwriting the speckle with unused values and thus extending the vines significantly. The submission also yielded a significant improvement in score and held its lead through Saturday.
The Best Result prize was an interesting one since one of the key to attain the best result would be to utilize the maximum time being just shy of the timeout limit. At the time of my submission Sergey's entry had been leading strong and I wasn't sure adding any more solvers would do much good to get a healthy lead. My best bet I believed was to utilize more time and try board variation on the primary solver by Alfonso which worked best on majority of the boards. Using that basic idea I went along with my submission and in the words of Ned Gulley "cruised limbo-style beneath the timeout limit" and maintained the best result lead till the deadline.
Many thanks to the MATLAB team, and all the participants, for another enjoyable contest and looking forward to the next one!
Sergey Yurgenson has a Ph.D. in physics from Leningrad State University (Russia). His previous wins in the MATLAB Central Contest include the Tuesday Leap and the 10000 Character Challenge Winner in Peg Solitaire (May 2007). Currently Sergey works at Harvard Medical School. He uses MATLAB for data analysis and control of data acquisition in Neurobiology research.
I am participating in MATLAB competition from 2006. Usually, one or two days after the end of Twilight phase competing algorithms are converged together, combining all best ideas of first days of the competition. It is good time to spend several hours studying code line by line to better understand it and find areas of possible improvement. During Vine contest I had relatively free weekend and was able to dedicate some time to code "proofreading". One of my "finds" was in postprocess function. That function was trying to improve result by moving board elements to extend existing vine. It was looking for best element to move using only value of that element. I realized that that optimization is correct only if we have significant number of available moves. If we have small number of moves available then optimization needs to take into account how many moves is necessary it position element into place punishing elements that require a lot of moves to position. I created new optimization function and tried to determine parameter space where that function is better than original. I made my submissions during "slow time" to have more time to optimize my submission without interference of other submissions. At the end that idea generated more than 200 points score gain. Together with some other code modifications it gives me enough lead to finish first in Sunday Push.
Nick Howe teaches computer science at Smith College in western Massachusetts. He uses MATLAB extensively to conduct research on problems in computer vision. The Gerrymandering contest (April 2004) was his first MATLAB Central Contest. He has been participating on and off ever since.
Like many people, I began with a vine builder that searched for the best sequence possible without moving any tiles. This scored pretty well in Darkness, but since it didn't move any tiles around it couldn't beat Alfonso's entry which did. For Twilight I decided to go in the opposite direction and create a solver that would build a solution from scratch by moving tiles as much as necessary to form a snake at the edge of the board. A few other people had this idea, but I was able to amplify its effectiveness by applying it to transposed and flipped versions of the original board in an attempt to find an orientation that required fewer moves to build the snake. I also added collision-avoidance so that high-value tiles would move out of the way of other tiles being moved.
By now it was clear that the contest suite included a number of different board categories, and that one way to improve the result was to write a specialized solver just for one category of board. Although I was tempted to work on the plateau levels for aesthetic reasons, their weights were such that they contributed only a negligible amount to the final score. So I instead looked at the levels that had almost-complete snakes in them, interrupted by occasional noise tiles. I wrote a specialized solver that identified the noise tiles and shifted the remaining ones to cover them up. The process made me think of separating wheat from chaff, and so I titled my Twilight winner the "Revenge of Antichaff".
For the Early Bird, I set out to build another specialized solver that dealt with levels where every other column of numbers needed to be reversed. After several hours of work, I realized that the general snake-building method I had already written did a better job than the new approach I was trying, but that given the typical orientation of boards in the testsuite it could do even better when I flipped the board vertically first. So that observation formed the basis for my "Cheap Reverse" entry.
During the rest of the contest I worked on more ways to solve the high-value boards, mostly by limiting the number of moves required to construct a vine. Like Alfonso, I developed a spiral vine builder. I wanted to work on something that would build better vines on boards where only a few moves were allowed, by joining partial viable vine sections, but in the end I didn't have time to finish it. Alfonso's winning code made some nice improvements in this area and he justly deserves the grand prize for his efforts.
My name is Alexander Pesch, I live in Jena, a small town in Thuringia, Germany, but with big history in optics. Also my live is characterized by the work in the field of micro-structured optics.
In the darkness of the contest I developed my own algorithms to solve the problem, first looking for the best chain of numbers, later also using the possibility to move squares, which brings really a big progress in score.
Sunday I studied the algorithms, created some charts about the behavior of the parameters and optimized the algorithm for the given board at start. But the parameters and best algorithm choice are usually optimal for only one set of boards and a specific machine, caused by the time dependence. I decided to participate in the sub contest of the Square One Challenge, where the chain has to begin in the upper left corner. First I changed my algorithms and some of the others to got a solution, but saw another one some minutes before the end. A short check showed it uses not the best parameters and this was the chance to do a little hopeful tweak.
Unfortunately missed the final spurt due to professional activity. But I was really impressed which progress it does in the last hours of the contest.