TCO 13: Marathon Finals, part 4

Part 1 Part 2 Part 3 Part 4

This is the last part, and it contains all of the random thoughts that couldn’t be included earlier without breaking my chronological theme. The idea here, is to give you some additional perspective on this 10K-long write-up.

Each section is completely separate and they are listed in no particular order.

Volatility of Finals

After each contest I try to understand what went right and what went wrong. Basing your performance solely on your final placement (being results-oriented) will get you nowhere in terms of improving yourself.

Analyzing on-site contests is particularly difficult, because the variance in them is just huge. One nasty bug, can make you loose 1 hour or more. In fact, they are just a common theme of the finals – in 2012, wleite had a very serious one. But I’m pretty sure that this happened in every championship we had so far, just usually more indirectly. This year, a lot of finalists had many zeros in their final solutions. It seems that if nhzp339 had a 100% working solution, he would have a solid 2nd place.

But this year was brutal for another reason. We had an incredibly close race during the last hour. Top 4 was within 2,5% in the final ranking, while historically it always (visibly) happened only between top 2 competitors. Those 2,5% might seem like a significant spread, but just look at the very simple change that Gassa proposed in the comments section of the second part. After 15 minutes of tweaking, I was able to gain 4% improvement using this trick. If I had it, the contest would have a clear winner, but if any of my opponents had found something similar, we would have a different (and worthy!) winner.

That huge volatility is the main reason why I forfeit some ideas before even understanding why they don’t work – like my “advanced” solution for first phase. And, in the same spirit, why I constantly change the part of my code that I’m focusing on. All of this is the direct succession of me trying to reduce the contest’s variance, as much as I can. The rule of thumb in every kind of competition is that you want to maximize the variance (like doing 1000 pointer first) when you believe you’re the underdog, and minimize it when you believe that odds are in your favor. And lastly, doing a lot of small things is way more fun for me, than betting everything on just one super-duper idea.

What I could do different?

I haven’t put much thought into improving my solution after the contest finished. The main reason was already mentioned – right after the contest I’m left in a very non-comfortable situation (waiting for the final results) and in order to fully enjoy the rest of the on-site event, I try to forget about the contest and especially I don’t want to overanalyze various what-ifs scenarios. The other, rather unusual, is that I somewhat run out of ideas, or at least I run out of ideas quick to implement.

Here is the practice room. The scores there, are using the same set of tests that there were used for provisional ranking during the competition, but the “best scores” for each seed are set to those from the actual contest. And they are fixed, so it’s possible to go over 1M points. My submission there includes a small fix to the last-second update (“unblocking” resources) and some other simple fixes that I forgot to implement during the contest. Adding that 4% change plus some code optimization, would give something slightly over 1M mark. But well, those are the things that I just forgot about or didn’t notice during the contest. Blaming yourself for not being smart enough is not very constructive.

One particular thing that I’m not happy with, is that I completely ignored any kind of code maintainability. My way of working usually consists of rapid prototyping and very frequent refactorization. The golden rule I have is that if I’m not sure if it’s going to end in my final solution, I don’t care how it’s written. This usually means that my core functionality is clear and readable and everything else looks like a total mess. Overall this approach suits me very well, since I rarely work on paper and instead I prefer to quickly create a crude sketch of an idea and see how it performs in reality. If it works I already have it implemented and I can start enhancing it right away. And if it doesn’t then at least I have some new insights about the problem – it’s often priceless to be able to exactly see (in visualizer) why something doesn’t work.

If I had more time I would definitely go back to my approach with splitting everything into 3 different phases. I believe first phase could be solved near-optimally with beam search. State copying is a costly operation, but it can be easily optimized by copying only affected part of the map – using a rectangle or just having a list of harvested resources. After solving first phase we longer have to simulate it – we just start from one of the final states generated by the beam search. It’s actually pretty fast to implement and I actually thought about it during the contest. The main reason why I haven’t tried it, was the already-mentioned mess in my code. I really lacked a “game state” mechanics, I just had a bunch of oddly named global variables. But there’s no lesson to learn here – it’s just the way I create solutions, an unfortunate trade-off that I’m used to doing.

If you’re interested on how each of my submissions scored, here you can download a file with my local scores. Please mind that those scores were obtained on my home computer after the contest was finished. Submissions that crashed are not included. At the far right you’ll see the best score obtained among each of the submissions and the last row describes my estimated provisional score for each of the submissions (but it doesn’t take any potential time-outs into account).

Why did I write this?

Originally, I wanted to make a more detailed “Post Your Approach”-like write-up including the psychological aspect (and I’m sure that by now, you must have noticed that I put more much weight on psychology than on the knowledge). Explaining not only my ideas, but also why I did end up using them, and most importantly how I came up with them. Later I noticed, that actually I need to add a lot of background info, because lots of decisions are based on the leaderboard, my current mood or some meta-ish strategy. And since I’m already doing it, I might as well try to capture how does it feel to compete in the finals.

I’ve been often asked about how do I solve problems, what’s my standard plan, etc. And I was really tired of answering them that I never have a plan that lasts longer than 1 hour :) I sometimes had a feeling that those who tried marathons or other optimization-like type of problems, expects from us (me and other top-rated competitors) to perform some kind of magic, or at least do rigorous analysis and have an incredible comprehension of what we’re doing. But the truth is, that most of the things we do are really dumb. That’s it – just doing dumb things, over and over again. We just do them fast, and we’re able to learn on their results. And I believe I might have a small edge over others, because there is just no dumb enough idea that I would completely discard ;)

I’m oversimplifying a bit – there’s of course a ton of intuition behind the whole process. But it’s not used as often as one might expect. If you read closely the whole write-up, you would see that the common theme was that I have no idea how to efficiently solve particular subproblem, so I’m settling with absolutely anything that will move me forward. Bah, even moving sideways (creating something that doesn’t yield better score) is way more productive than doing nothing. And well, almost all of my “advanced strategies” didn’t work out at all. To be perfectly honest, it’s something that doesn’t happen too often, but I believe this is what made this contest very interesting in my eyes – I had a lot of (albeit none of them significant) failures and thanks to that, I could show how I am handling those situations.

Lessons to Learn

The original idea was to show this detailed write-up, so everyone can find something interesting in it. But since this ended up us something that is much longer than the attention span of an average reader, I think that it might be a good idea to recall some of the more important thoughts. Just take into account, that this is a very subjective list – some of them can be completely against your style, and it’s absolutely fine to just ignore them.

  • Stay in shape – it’s often neglected by people who perform work that is intellectually demanding. But physical exercises boost concentration by a lot. Also, physical stamina and mental stamina are very closely related.
  • If you struggle with the lack of motivation, it’s a good idea to follow a strategy of small improvements. For some strange reason, human mind gets motivated when it sees improvement, but it doesn’t care about the size of it. In practice this means that it’s better to start with trivial solution and gradually improve it, instead of trying to come up with a brilliant idea and refuse to implement anything worse.
  • Remember that if you implement something that doesn’t improve your score, you can analyze what exactly happened and you can get few more insights in that way. This means, that anything you do is a win-win scenario.
  • It’s very important to not get stuck on a single concept.
  • Don’t be discouraged by bugs. They happen to everyone. Literally everyone. As far as I know, I’m someone who spends very little time on debugging and during this TCO I spent probably around 30-40% of my time on it. It’s not the most fun experience, but still a learning one. Testing often is the easiest way of reducing that time.
  • Always remember to enjoy what you’re doing.

Thanks for reading, …

I hope that this bloated write-up turned out to have some educational and entertaining value, and most of all, you enjoyed it as much as I wanted it to be done :)

If you have any feedback or suggestions for future posts, I’ll be more than happy to hear it. And if you want to keep up with my posts, it’s really easy to drop your email address in the appropriate field *winks*.

And you have to wait for part 5 now, just kidding :)

3 thoughts on “TCO 13: Marathon Finals, part 4

Leave a Reply

Your email address will not be published.