Lisp developer walks away with Google AI contest | Hacker News Reader

Lisp developer walks away with Google AI contest

zdnet.com

176 pointsjanzer71 comments

Lisp was clearly a fine tool for this kind of challenge, but the programmer was, as usual, the important piece of the solution. Otherwise I'll expect to have some other of the 33 lisp based entries in the top spot (the second lisp entry is ranked at the #280 spot: http://ai-contest.com/language_profile.php?lang=Lisp).

What about the top ten solutions? http://ai-contest.com/rankings.php

  4 Java 
  3 C++
  2 C#
  1 Lisp

So is Java the real king of the AI challenge? ;-)

[edit for formatting]

I find the mix of languages found in the top 100 interesting. Smart is obviously a big factor in determining the winners. Speed was a factor in the contest as well, with a 1 second per move time limit. Based on that, I'd expect to see the faster of what Paul Graham calls "languages for smart people" near the top. Lisp, Haskell, ML and Lua come to mind. That didn't happen. What follows are observations about things I found interesting, with no specific conclusion:

Popularity in industry seemed to be a big factor, with Java, C++, C# and Python making up most of the entries in the top 100.

Speed wasn't that important: Python made up 20% of the top 100.

Some popular languages, such as Javascript, PHP, Ruby and Perl did quite poorly. I'd blame it on speed, but Python did quite well.

New and exciting languages I'd expect the sort of people who enter programming contests for fun to like were underrepresented. Only 6 people used Go, and 4 used Scala.

Unless I'm mistaken, the contest was limited to supported languages. F#, Clojure, Lua and Scheme don't appear because they weren't supported, not because nobody wanted to use them.

I think a lot of participants might be in the same situation I'm in: I like new and exciting languages and play with them now and then in my free time, but I work in one of the "boring" languages. Having way more experience with the boring language, it's the one I turn to when I have a deadline or the problem is hard enough that I can't afford to spend brain cycles on the language itself.

I feel like Clojure has crossed that threshold for me.

I program in Java at work because it's what my team understands and it's what the rest of the application is written in. But if I need to do some exploratory programming or build tools to increase my personal productivity, I turn to Clojure first. It's much more productive because I can test each little piece at the REPL and it takes so much less code than it does to do the same things in Java (even when it is just invoking methods on Java objects).

If I need to, it is then a straight forward step to expand the code out into its verbose Java form.

'Speed wasn't that important: Python made up 20% of the top 100.'

In the article, speedy execution can be taken to mean the speed/ease with which you translate you idea into code and not the speed at which the resulting code runs

I don't know about this challenge, but during the Tron AI challenge, execution speed was very important. There was a time limit for how long your AI could take to make a move so the faster your execution the deeper your min-max tree.

Unless I'm mistaken, the contest was limited to supported languages. F#, ... don't appear because they weren't supported

I'm not familiar with how the contest was implemented, but I would assume that if C# was supported, then any .Net language would work. It should be trivial to build a C# wrapper for your F# code, if the interface you must support can be implemented in all those other languages.

You could have written a program in any language. It just needed to accept certain command line options and send results to stdout in the proper format. They only provided "starter kits" for a few languages, but if you were willing to write a little extra code, you could have used anything.

Any language you could get working on the official server and you wrote a starter pack for would be supported. That's one of the nice things I like about this challenge as opposed to other competitions which are generally restricted to Java, C# and / or Python.

That said there were quite some initial problems getting some languages working since they were running on a very old Ubuntu.

Speed wasn't that important: Python made up 20% of the top 100.

I wonder if the Python programmers recoded their bottlenecks in C or C++. Would the rules of the contest allow that?

Uh...No.

Yes, the programmer was the important piece of the solution. Note the careful wording the winner used in his advocacy: "Lisp doesn’t get in my way as much as other languages."

From the article's description of how far ahead Melis was (2nd paragraph), you could say Java was king of "a race for second place".

Don't most Lispers argue that just knowing Lisp makes you a better programmer whether you use it or not? Perhaps a better measure of how great Lisp is would be to examine the proportion of programmers who know Lisp and submitted a top ranking entry.

The language used was only a small factor. I was the next Lisp entry ranked at #280. Programmer quality and experience are far more important.

A better title: "3 Time Winner of Computer Games Olympiad Wins Yet Another Contest".

Can't believe this Reddit quality comment is getting any upvotes. Google AI Challenge is "Yet Another Contest"? Though you may not be surprised, he is, http://quotenil.com/Planet-Wars-Post-Mortem.html/.

The point is that he won because he's a great programmer, not because he used Lisp.

It's far from clear which way the causality runs.

Well, the 33 lisp entrants don't appear to hold the top 33 spots:

http://ai-contest.com/language_profile.php?lang=Lisp

So more than a fifth of the lisp entries are in the bottom twentyfifth of the competition. So you could also use the contest results to argue that lisp is five times worse for AI than the average language.

(Or, rather, that language alone doesn't guarantee success, but that would be too rational and boring for an online forum).

You'd have to be an idiot to argue that language alone guarantees success. A more common bad argument is say that because this is idiotic it follows that language is irrelevant. That's actually a popular position nowadays.

Just because computers obey the law of excluded middle does not mean we should.

Your math doesn't seem to work.

For that to be true, more than a quarter would have to be in the bottom 25th percentile. (In fact, it still points to lisp being better than average).

Anyway, The bottom 25th percentile of the competition is relegated to submissions that didn't run.

There was a bug (still is, I believe) in the lisp 'starter pack,' which caused the client to crash (It sent garbage to the server or something). So even the default Java starter submission would beat it.

Given the number of people who submitted once and walked away, I wouldn't read too much into it anyway.

The point the guy himself makes is that lisp allows him to be a great programmer.

Of course the program could be rewritten into qbasic. It is getting your ideas and thoughts into a form that is not a compromise to the language which matters.

Yes. Any program can be written in any Turing-complete language, but is far from equally likely to be written in it.

The point is that he won because he's a great programmer, not because he used Lisp.

Given that people have argued that the absence of Lisp winners from such competitions is evidence against Lisp's greatness (I'm going by memory here and don't have time to dredge up the record), it seems relevant to point out when it does happen.

So, essentially:

a) given that people has made bad arguments before b) it "seems relevant" to make bad arguments in the opposite direction now

Huh?

It's relevant because it's a counterexample. Now people can't say, "If Lisp is so good why don't people win these things with it?" They have to say things like this instead:

http://news.ycombinator.com/item?id=1961546

Obviously the OP is relevant for other, better reasons than this, but that's what my comment meant.

It would only be a "counterexample" if it was a valid example. This only keeps the "counter" part, but as an example it is flawed.

I think it's worth pointing out that not only is the argument logically incorrect, it's based on incorrect facts. For example:

A: "Lisp sucks. If it didn't, we'd see it winning contests or something"

B: "But it has been used to win a contest. Besides, you're really bad at making an argument"

Wait, what? My original comment got at least one upvote, and then my edit ("For example:..."), that was meant to clarify what I was saying, is getting downvotes. Can someone explain?

I'm not trying to disagree with the OP in general (you can't fight bad logic with more bad logic) but just pointing out that correcting someone's facts can be easier (and with this datum point, possible).

Edit: I like the upvote, but an explanation would be better.

It's the pianist, not the piano. It's the photographer, not the camera. Nonetheless, highly skilled people do care about their tools.

From the article: "Lisp doesn’t get in my way as much as other languages."

His expression of surprise is a reference to the winners post-mortem last round. http://www.a1k0n.net/blah/

I prefer pithy comments, but I can give you a verbose one too. I've used Lisp professionally for 20 years and I'm a huge fan of the language. But if there are lots of brilliant programmers who use other languages to build brilliant systems, how can I claim my favorite language is superior? The language is less important than the programmer. In this case, the winner has proven he's a very good programmer by winning other contests. The fact that he used Lisp merely shows that it is capable of doing the job.

Programming languages are like basketball shoes. You need a minimum feature set to play safely (ankle support, good traction, comfortable arches, etc). But buying a Nike Zoom Kobe will not make you the next Kobe Bryant. So what's the minimum feature set for a good programming language? I don't know. C appears to be good enough, while assembly is not.

To further abuse that analogy, it's more that programming languages are like shoes in general. You can play basketball in cowboy boots, but it's a less than ideal setup.

That said, Kobe Bryant could probably beat me at basketball wearing a pair of cowboy boots. Likewise for programmer skill vs. task vs. language appropriateness.

Reminds me of a classic comic strip:

http://www.whattheduck.net/strip/95

Is there a summary of the algorithms he used anywhere? I don't see how it was the language that won the competition, rather than the code he wrote in it.

Looks like alpha beta with a good evaluation function, move ordering, and a changing depth parameter (not sure about this one, though).

Isn't alpha-beta pruning a type of optimization you can do to a search algorithm, but not the base algorithm itself? I only bring this up since I helped make an Othello bot that used Mini-max _with_ alpha-beta pruning to help reduce the number of branches it needed to follow down a tree.

Alpha-Beta pruning is, to my knowledge, only really defined in a mini-max setup. By definition, it leverages the mini-max framework to prune areas of the search space.

You can apply the core concept -- refusing to expend computation effort when the result of that effort is guaranteed to not be used -- to any number of other methods and approaches in Machine Learning and AI.

As far as the first line in the wikipedia page goes..."Alpha-beta pruning is a search algorithm which seeks to reduce the number of nodes that are evaluated by the minimax algorithm in its search tree."[1] it seems like you're correct. Thanks.

[1] http://en.wikipedia.org/wiki/Alpha-beta_pruning

Ah, thanks. Nothing that couldn't be implemented in a number of languages, then...

Hmm .. maybe I should consider settling in Hungary.

food's better and cheaper... thats for sure.

After seeing Gábor’s performance, many participants commented that they would be taking a new look at the 1000 year old country. "Bocsimako is the proof that Hungary is best for AI algorithms", quipped one player.

Being born and educated in Hungary is even better. Compare John von Neumann, Edward Teller, Leo Szilard, and Eugene Wigner.

They changed the education system, and no longer used the one they had around 1900. Unfortunately.

Don't forget Paul Erdos!

I don't know about that. The first wave of 20th century combinatorialists were pretty much all Hungarians (Bollobas, Erdos, Polya, Szekeres). Hungary hasn't stopped churning them out either.

I'd argue that their education system's just fine.

There is a quote that I don't know who to attribute to or even the exact quote but it's roughly "Only in Budapest can a man walk into a revolving door behind you and come out in front of you"

Actually I intended my comment to be taken in two ways -

a. really in appreciation of Hungary for all of its contributions to mathematics and the mathematical sciences.

b. I wished to hint that if the author wanted, the same article could've been about Hungary instead of lisp. Instead of asking "what makes lisp so great at this kind of stuff?" the question could've been "what makes Hungary so great at this kind of stuff?", with a badge saying "Made in Hungary". We always focus on the things we want to focus on as causes don't we?

There are many comments here that he won because of his programming/thinking skills versus using the Lisp language, and I think this true in comparison to the other contestants. However, one thing he mentions that is an interesting piece of the puzzle -- and a common theme in language competitions that include Lisp -- is:

Lisp doesn’t get in my way as much as other languages. After getting hooked I learned to value the interactive development environment, the object system, etc.. What’s good about Lisp is rapid development and speedy execution.

This might be a small effect, and you can have good programmers in every language, but if he was just as familiar with Java as he was with Lisp, could he have accomplished the same results in the same time with Java? How would the code look?

I know at least a few people who had bots written in/were prepared to write bots in Clojure. They didn't end up adding support for it, however. I still can't wait for the next contest—wouldn't Pentarow be cool? Or Pente?

Anyway, cheers to Waterloo for putting this on again!

You should beware not to be too enthusiastic, because this year's organizers were pretty aggressive when I politely asked (over PM) if there was any specific problem with adding Clojure. I still don't know what the problem was.

Bocsimako is the proof that Lisp is best for AI algorithms

Cargo cultism at its finest

Ugh. Cargo cultism? The full quote is:

After seeing Gábor’s performance, many participants commented that they would be taking a new look at the 50 year old language. “Bocsimako is the proof that Lisp is best for AI algorithms,” quipped one player.

one player.

And as any reader of the Hardy Boys can tell you, "quipped" implies that it was said in jest.

Cargo cultism is applicable to one person

It seems that any positive inclination towards lisp is cargo cultism.

Gabor Melis is a seriously smart guy, and probably would have kicked ass in any language.

That said, I'm going to pull out that phrase next time someone says 'Java/C# is good for Enterprise', or 'C++ is good for video games', or 'C is good for systems programming'.

Cargo cultism indeed.

Two things:

1) "X is good for Y" is very much not the same thing as "X is best for Y"

2) One person having great success at something is not a pattern, and doesn't usually prove a general rule (I'm hedging with 'usually' - I can't think of a counter example but I expect someone else will :-). Common usage, while not a guarantee, is at least a good indicator of fitness - if Java were better for systems programming than C, it's likely (though of course not certain) that we would be saying 'Java is best for systems programming', and have some basis for that claim beyond the success of one person who has already demonstrated competence in the same general area (i.e. the contests previous competition wins).

The headline might better have been "Experienced programmer uses Lisp to win Google AI contest". Correlation vs causation - he didn't win because he knew Lisp, but he did use Lisp in his winning solution, and you can understand that without taking a position on Lisp itself; there are shades of fanboism in some of the comments on this thread.

1.) People (who use them) will happily tell you that each of those are the 'best' choices in their respective fields. People say 'C is best for systems programming', that I worded it more weakly is irrelevant.

2.) Lisp has been in use in AI, since before the birth of AI. It is still used in AI, and there has been plenty of success with it. There is plenty of 'constant conjunction' (to borrow the causative definition from Hume), associated with Lisp and AI.

Acting as if his use of Lisp couldn't have given him an advantage in an AI contest is pretty much the ultimate lisp denial-ism.

part of being seriously smart is to use the best tool.

I don't think you understand the term "cargo cultism"

That the language is Lisp isn't important. The important consideration is that he ascribed the success of the entry to the language without any evidence linking the two.

"You can win 6, 12 or 24 months of membership to AiGameDev.com PREMIUM if you place third, second and first in the contest respectively. We'll also provide any single person team that ranks higher than our official bot three months of AiGameDev.com PLUS — our brand-new part of the site that launched last week."

he must be excited. until google puts out non-trivial problem sets and offers non-trivial prizes i'll save my upvotes and cycles.

Meh, it's worth quite a bit to have that on your resume.

Very interesting stuff. Is the source for the various bots posted anywhere? Is it even a requirement that you disclose your source or that it will be made public after the results are published?

I looked around but couldn't find any obvious place to find the source for the bots used.

The winner: http://quotenil.com/git/planet-wars.git/

There's a thread on the competition's forums: http://ai-contest.com/forum/viewtopic.php?f=18&t=1168

The matrix will be programmed in Lisp...if it's not already...

It is already: see http://matrix.itasoftware.com/.

Not a bad article, but did you have to make the title a Lisp promotion fest?

This very short article mentions the winner's views, as he sees it, on the suitability of Lisp (used by 0.7% of the contestants, surely interesting) for the job. Half the article never even mentions Lisp. And this amounts to a 'promotion fest'?

The point is that he won because he's a great programmer, not because he used Lisp. I was referring to the title and not the article. Do you understand that or have you got more asinine comments?

Reply on news.ycombinator.com