The interesting subtext of this competition is that to an extremely good approximation, everyone who was interested enough to write a competitive entry used C/C++, even though the organizers went to great lengths to support as many languages as possible (e.g. Haskell, Scheme, etc.) This is with a small self-contained problem where performance wasn't a main difference between entries, and fast prototyping and experimentation could be extremely valuable.
What I take from it is being more convinced that the claims of dramatically increased productivity from other languages, in practical terms, are at best extremely overblown. If this isn't a practical problem where a Haskell or Scheme programmer could be competitive using advantages of those languages, it really makes me question what is.
It's really difficult to know because all the programming contest culture is C++, from what I can see. Someone who is experienced with programming contests is much more likely to do well than someone just trying something out for the first time for fun, and all those people use C++ because the programming contests mostly accept only a small handful of languages, of which C++ is the clear winner for performance.
I would expect this effect to utterly dominate any actual differences in languages right now. Comparing programming-contest-experts-in-C++ to newbies-with-$FAVORITE_LANGUAGE is not going to be a fair fight in something like this, where algorithms and insights dominate.
If TopCoder et al took the same suite of languages, and had for long enough that skills had equalized after the first mover network effects to whatever was really best for this sort of thing, we'd be able to make a better guess about what languages are good for what. (I would then conclude that I still don't really care because I'm not usually doing programming contests. But it would at least mean something, unlike the current results.)
Surely if language X is blub and language Y isn't then Y beats X if all else is even.
Surely everyone experienced at these competitions would quickly figure out that lisp et al are huge competitive advantages, and everyone would quickly switch.
From what I've seen working with some living legends in computer science the language makes almost no difference in actual productivity, it's just personal preference.
It's just trading one performance characteristic for another. Every language has it's sweet spot, and if you know them you are just as productive in that as another.
If you aren't productive in a specific language, you are doing it wrong.
"Surely everyone experienced at these competitions would quickly figure out that lisp et al are huge competitive advantages, and everyone would quickly switch."
You missed the part where I pointed out that current major competitions don't accept arbitrary languages. That's the key point of my post. All else is not even. If they did accept arbitrary languages I would accept your logic, given sufficient time for network effects to wear off.
Otherwise, if you're going to argue that it's the people and their experience that really matter, you reduce back down to my point, which is that all the experienced people have their experience in C++ as cost-of-entry to the major contest sites and thus tended to use C++ as the language they have by orders of magnitude the most experience in by virtue of it being the only sane choice of the ones actually offered, rather than any intrinsic advantage C++ has over the non-offered languages.
Also, there are programming contests that accept other languages, but because these contests tend to focus on finding an algorithm of a given efficiency, it becomes hard to tune the time limits for multiple languages. So they tune to the most efficient/popular languages, which puts everyone not using C++ at a disadvantage.
"You missed the part where I pointed out that current major competitions don't accept arbitrary languages."
In this competition, if you wanted to use another language, you just needed to make a starter package (a stupid bot) and some instructions to get the compiler working on their end. So in this competition, arbitrary languages where accepted.
Oh, he talked about learning effects from other competitions. The fact that you could use other languages here doesn't interfere with the argument. (Though you are right, of course.)
which compared writing the same large application in Erlang, Haskell and C++ and showed the C++ program needed 40 times more code than Haskell and concluded:
"The high-level constructs dramatically reduce application size, thereby reducing development time and aiding maintenance."
Well that's simple. Right tool for the job. Erlang was built specifically for telecommunication systems. It's like comparing soap and rest and saying "soap is bloated".
You know, I didn't even once mention the language I used. Realtime constraints and searching speed were the driving factor here; you have to return a move in under one second. I didn't want to risk GC pauses, and I'm not good enough with Haskell to guarantee I'm writing fast code. Otherwise I probably would have used something else, but I don't consider it all that important. Really, there wasn't anything too complicated data-structure-wise to do. In fact it does next to no dynamic allocation. I wanted to use destructive updates for speed when doing a backtracking search on a map. The hard part was just implementing various recursive algorithms, and C++ didn't really get in the way of doing it except that it would have been nice to have multiple return values.
I did have some problems throughout the contest with my choice of C++ -- in fact without Valgrind, my entry may never have run correctly. (Turns out one of my algorithms was "escaping" off the border of the map and scribbling in RAM) But hey, I've been dealing with problems like that for more years than I care to count right now.
> I did have some problems throughout the contest with my choice of C++ -- in fact without Valgrind, my entry may never have run correctly. (Turns out one of my algorithms was "escaping" off the border of the map and scribbling in RAM) But hey, I've been dealing with problems like that for more years than I care to count right now.
The first few days of the contest were dominated by higher level languages (iirc Python help the top spot for a little). The forums were filled with people talking about their approaches, and there was a ton of rapid prototyping.
Once the algorithms were solidified, the people that knew C++ implemented them as optimized as possible. The bots had a limit of 1 second for processing per move. As soon as the ideal algorithms were understood, it was a no brainer to make it as fast as possible.
It really just came down to raw speed in the end, which is hardly representative of most real world problems.
I'm curious, did anyone start out prototyping in Python or other high level languages, then translated to C++ for speed? Or did the Python people mostly stick to Python all the way through?
Well, you should understand that at the end the bot had to be pretty complex to be competitive. Fast prototyping wasn't so important, as most of the theory was already there. But only a few managed to get them working together. In this case a prototyping language didn't have an advantage (like with most project with >4k lines, it's hard to oversee).
And secondly, most bots relied on minimax, which is a brute force algorithm. Performance was a big difference. For example, a friend of mine ported my code from C# to C++ (from compiled language to other compiled language) and got in the top 50 (I finished 81st), this without any changes to the algorithm.
Fast prototyping lost its edge early on in the competition. Once people figured out the winning formula is something like Flood Fill + Minimax + Voronoi it all came down to tweaks and optimizations to search deeper, and making sure your evaluation function was accurate, not trying out completely new paradigms or anything like that.
There are a couple of reasons that isn't a valid conclusion.
First the value of prototyping was reduced by the length of the contest (as opposed to the contest being 48 hours) and by the fact the forum members provided some good strategies to the winner so he did not have to uncover them himself.
Second it turned out one of the most effective algorithms involved brute-force, an area which C/C++ excels at.
Actually it is surprising Haskell, Scheme, and Python ended up in the top 10% at all, I would like to see how they did it.
That is interesting indeed. If you go on to page 2 of the rankings* you can see that there were indeed a large number of Haskell, Python, Lisp and Ruby entries, but the top 100 (and especially the top 25) are totally dominated by C++.
The other thing I find interesting is the lack of Java entries. Java is as widely-known as C++, but there's only one Java entry in the top 100, and even in the top 200 Java is only about as common as Haskell or Ruby, and far less common than Python.
The problem with Java was that it was impossible to get it running fast enough. You had 1 second of thinking time, but with Java you could barely access 0.05s, while compiled languages like C/C++ or even C# could easily use 0.95s without having any timeouts (which leads to disqualification).
My impression is that as long as you can ignore startup time, Java in general is pretty close to C++ and definitely much faster that Python. I am surprised this would be a problem with Java and not with Python. Did anyone had the same problem with Python?
The contest site had a problem with their JVM which interacted badly with their sandboxing environment. The 1-second time limit would disqualify any Java entry that took something like 50ms or more for some unknown reason.
It might have something to do with the blatant warning on the entry page telling you not to use Java due to some mysterious problem with it and their sandbox.
The real reason why C/C++ worked out so much better among the top bots is because it is faster, allowing the C/C++ bots to explore more of the game tree.
Not to be an apologist, but you still have to account for programmer skill and number of programmers. I'd be interested in seeing the average and median for different programming languages, not just the top results.
Now I understand why my bot did so badly (190 out of 800). My iterative deepening algorithm never worked quite right because I didn't have the Voronoi heuristic implemented properly.
This was a great walkthrough, and the contest, even though I was nowhere near winning, was a nice learning experience for me.
> Did you do any sort of memoization of the minmax evaluation?
None. Considered it, but didn't really think it was worthwhile. I was mostly focused on having a good evaluation. I know a lot of my competitors did that, though, but without changing the evaluator it is, as I said, self-deluded.
> For example the expected value of moving up and left should be the same as the the expected value of moving left then up?
That isn't true; that ends up with the wall from the middle move in a different spot.
At any rate, there was a lot I could have done to improve the search speed/depth but I didn't have time, so instead I worked on a better evaluator.
It was pretty interesting -- I would frequently see stronger moves (as best I could tell, after analyzing a losing game) found at shallower levels of search depth discarded in favor of weaker moves at deeper levels. Presumably it assumed the opponent would maximize its Voronoi territory at a time when it was actually a bad thing to do.
> That isn't true; that ends up with the wall from the middle move in a different spot.
Oops yes you are right. They would only be of the same value if the map was symmetrical on the diagonal line going between the first position and the last one.
I wonder it they should be similar (at least in situations where you don't touch walls).
What I take from it is being more convinced that the claims of dramatically increased productivity from other languages, in practical terms, are at best extremely overblown. If this isn't a practical problem where a Haskell or Scheme programmer could be competitive using advantages of those languages, it really makes me question what is.