Google AI Challenge: Winner post-mortem and source code

Alternatively, it's possible that those using other languages just wanted an exercise to learn more about those languages.

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.

* http://csclub.uwaterloo.ca/contest/rankings.php?page=2

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.

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.

overblown for algorithms experts, maybe. selection bias.

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.

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.)

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.

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.

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.

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.

> 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.

So would I, but I'm afraid to find out.

Most of the development was done after putting my son to bed and before collapsing of exhaustion at 3am.