 An open exchange for the MATLAB and Simulink user community |
Hosted by The MathWorks |
|
| Related Topics |
| New Products | Support | Documentation | Training | Webinars | Jobs | Newsletters |
| Problems? Suggestions? Contact us at files@mathworks.com | © 1994-2008 The MathWorks, Inc. Trademarks Privacy Policy |
While I haven’t had much time to compete in this contest, I’ve done some analysis and unfortunately believe that the 13000 mark is going to be virtually impossible to beat. Here are some key points:
As of midnight Tuesday, the leading entry has the following stats:
Result: 134617
Time: 40.0336
Cyc: 21
Nodes: 7289
Score: 13508.84
Because of the way the scoring formula works, the ONLY way to beat 13000 is to lower the result. Even if the time, cyc and nodes were reduced to 1 each, the score would only improve by 45 points to 13464. In order to reach 13000, the result needs to improve to ~129500, or by approximately 5117 (which is a 3.8% improvement).
That might not seem like much, but it actually is. Based upon the null move solvers submitted at the start of the contest, we know that there are a total of 359141 points in the original test suite. The current result is only 37% of the max value of the test boards.
However, keep in mind that there is a non-zero lower limit to the score for a ‘perfect solver’. While it’s impossible for us to know what that is without examining the test suite, we can make some good guesses based upon the best results statistics. The best result so far is 133225, almost 1400 points better than the current leader (although it took 148 seconds to run), but still 3700 points away from 13000, assuming it could run in less than 1/3 the time it currently does.
Another way of looking at it is the % improvement column on the stats webpage. The score has only improved by ~4% since Sunday morning until right now. Thus in order to break the goal, in the next 12 hours entries need to outperform ~72 hours worth of steady improvements.
Examining the current leading solver against random individual boards in the sample test suite, I found that there might be room for slight improvement, however overall it’s doing a really good job, as one might expect.
Thus, while I’m sorry if this bursts anyone’s bubbles, hopefully this will allow some competitors to refocus on just getting a top entry instead of trying to beat an arbitrary score. Good luck everyone for the remainder of the contest!
Nice analysis, Alan. It was my original judgement as well when the challenge was announced.
Yeah, but in 4 hours David Jones wakes up (if he does sleep at all) and pulls a rabbit out of his hat which pushes the score to 13001. Then The Cyclist comes around, picks this entry, shuffles around some colons and semicolons, and gets the price. :D
(Sometimes I think that this procedure is part of the contest rules.)
It seems that new entries don’t show up anymore because the queue is clogged.
Thanks for sharing your analysis Alan. As you have argued persuasively, it looks like 13,000 is unattainable. The leading entries (at the moment) are nibbling away at 13,465, … even speeding up the deep solver would give a score around 13,320. Assuming we get an algorithmic breakthrough, the winning entry might achieve a score just below 13,300.