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

31–39 of 39 posts

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

#31

Post by eru »

dutchflyboy wrote: post #24
jerf wrote: post #17

Earlier quoted context omitted.

"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 networ…

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

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

#32

Post by dutchflyboy »

eru wrote: post #31
dutchflyboy wrote: post #24

Earlier quoted context omitted.

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

Hmm, you're right, I misread his comment. Sorry for the confusion.

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

#33

Post by by »

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…

"... the language makes almost no difference in actual productivity, it's just personal preference."

If that were true how can we explain the results in this paper

http://www.macs.hw.ac.uk/~trinder/papers/ICFP2007.pdf

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

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

#34

Post by jcl »

jerf wrote: post #17
corruption wrote: post #14

Earlier quoted context omitted.

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

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.

See, for example, the comments on this page: http://www.spoj.pl/problems/ABCDEF/

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

#35

Post by a1k0n »

Blasa wrote: post #30

Did you do any sort of memoization of the minmax evaluation? 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 would cut down the search space some. Of course it adds memory overheads. You could also memoize the voronoi heuristic if that takes a long time to compute.

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

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

#36

Post by a1k0n »

amatos wrote: post #25
dutchflyboy wrote: post #6

Earlier quoted context omitted.

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.

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

#37

Post by scott_s »

megaman821 wrote: post #13
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…

A literate Haskell entry: http://news.ycombinator.com/item?id=1168991

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

#38

Post by Blasa »

a1k0n wrote: post #35
Blasa wrote: post #30

Did you do any sort of memoization of the minmax evaluation? 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 would cut down the search space some. Of course it adds memory overheads. You could also memoize the voronoi heuristic if that takes a long time to compute.

> 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? Tha…

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

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

#39

Post by corruption »

by wrote: post #33
corruption wrote: post #14

Earlier quoted context omitted.

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…

"... the language makes almost no difference in actual productivity, it's just personal preference." If that were true how can we explain the results in this paper http://www.macs.hw.ac.uk/~trinder/papers/ICFP2007.pdf 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 redu…

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