Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Google AI Challenge: Winner post-mortem and source code

a1k0n.net

Post reply on HN
Print view View original

11–20 of 39 posts

Re: Google AI Challenge: Winner post-mortem and source code

#11

Post by jerf »

WilliamLP wrote: post #3

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 experime…

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

Re: Google AI Challenge: Winner post-mortem and source code

#13

Post by megaman821 »

WilliamLP wrote: post #3

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 experime…

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.

Re: Google AI Challenge: Winner post-mortem and source code

#14

Post by corruption »

jerf wrote: post #11
WilliamLP wrote: post #3

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 experime…

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 wou…

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.

Re: Google AI Challenge: Winner post-mortem and source code

#15

Post by NathanKP »

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.

Re: Google AI Challenge: Winner post-mortem and source code

#16

Post by NathanKP »

WilliamLP wrote: post #3

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 experime…

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.

Re: Google AI Challenge: Winner post-mortem and source code

#17

Post by jerf »

corruption wrote: post #14
jerf wrote: post #11

Earlier quoted context omitted.

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 wou…

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 ju…

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

Re: Google AI Challenge: Winner post-mortem and source code

#19

Post by sgk284 »

WilliamLP wrote: post #3

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 experime…

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.

Re: Google AI Challenge: Winner post-mortem and source code

#20

Post by jimbokun »

sgk284 wrote: post #19
WilliamLP wrote: post #3

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 experime…

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 algori…

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?
Post reply on HN