7 ms·

Winner of 2011 Google AI Challenge Describes Released Code

190 points by tvorryn 15y ago

tszming 15y ago
No content inside (but ads)
- brettnak 15y ago
  Either the link has been changed or this is just incorrect.
- bhrgunatha 15y ago
  > bplaced.net Zugriff verweigert, Fehler 403. Sorry, access forbidden, error 403. Contact service provider I think the hosting provider may have pulled the plug after a traffic surge. Google cache http://webcache.googleusercontent.com/search?hl=en&q=cache%3Ahttp%3A%2F%2Fxathis.com%2Fposts%2Fai-challenge-2011-ants.html&btnG=Search&pbx=1&oq=&aq=&aqi=&aql=&gs_sm=&gs_upl= http://webcache.googleusercontent.com/search?hl=en&q=cac...
peregrine 15y ago
Now this is what I go to HN for! The most interesting part for me was that he did not focus on some huge strategy. Just individuals and small groups with clear goals and constant revaluation. Keeping in mind that the only thing kept between rounds were missions and those were constantly reevaluated as well. I think this is a vivid, albeit simplified, example of how successful organizations of anything should operate. EDIT: grammar
- Jyaif 15y ago
  What's that? You aren't more interested in the SOPA drama?
  - peregrine 15y ago
    Well I was when it was 1 day from being jammed down our throats. Then it was postponed to the new year, at least the lobbyists in our courts(EFF, Google, etc) have sometime to throw some cash around. And people can do something. I do think the SOPA Drama was a bit delayed and overblown here on HN.
icefox 15y ago
I had fun playing around with the challenge and spent most of the time poking around with map exploration as implementing min-max once again isn't too much fun. I ended up having the most fun playing around with the idea of an anti-object . The simplicity of anti-objects combined with the low memory and low cpu overhead was very nice. Wrote it up in a little blog for others: http://benjamin-meyer.blogspot.com/2011/11/using-collaborative-diffusion-rather.html http://benjamin-meyer.blogspot.com/2011/11/using-collaborati... Any ideas for a type of challenge that wouldn't be reduced to mostly min-max for the ranking, but could explore other concepts?
- tvorryn 15y ago
  I actually used this idea from the forums and your post to get 683rd place even though I started on it with 36 hours to go before the deadline. http://aichallenge.org/profile.php?user=972 http://aichallenge.org/profile.php?user=972 So thanks. How'd you do?
memnips 15y ago
Unfortunately the link appears to be temporarily dead. Luckily before you read about his bot you should watch it play anyways! Here are two replays of the same map. The first is played by average players and the second is played by xathis (and other top bots). Avg: http://aichallenge.org/visualizer.php?game=335973&user=8180 http://aichallenge.org/visualizer.php?game=335973&user=8... Top: http://aichallenge.org/visualizer.php?game=329760&user=4513 http://aichallenge.org/visualizer.php?game=329760&user=4...
- WildUtah 15y ago
  Note that every one of those "average" players finished in the top 10%. It's a hard problem to write any kind of generally adequate player for. All the good bots depend heavily on subtle properties of emergent behavior. Don't let the simple explanations fool you.
LearnYouALisp 15y ago
The first lines seemed familiar: http://quotenil.com/Planet-Wars-Post-Mortem.html http://quotenil.com/Planet-Wars-Post-Mortem.html
- tvorryn 15y ago
  Haha. It didn't say that before, because he hadn't officially won yet. It's actually been propagated from Tron: http://a1k0n.net/2010/03/04/google-ai-postmortem.html http://a1k0n.net/2010/03/04/google-ai-postmortem.html
  - LearnYouALisp 15y ago
    It seemed like a tradition, but strangely Google only showed his page at the top.
  - a1k0n 15y ago
    I definitely had no intention of starting a tradition there. Haha.
    - tvorryn 15y ago
      You didn't do too badly this time yourself. 11th place. Looking at what he did, do you see what you could do to improve your bot further?
      - a1k0n 15y ago
        Sure, but as he concludes at the end, I didn't want to spend too much time on it. My bot was fairly unique in that it used Monte Carlo methods rather than deterministic minimax, and it got the job done without too much effort. I wrote a forum post describing the basic approach here: http://forums.aichallenge.org/viewtopic.php?f=24&t=2044 http://forums.aichallenge.org/viewtopic.php?f=24&t=2044
hunterp 15y ago
There are 20 buttons on the page. Nuff said? -1 pls.
DanBC 15y ago
I see a few people saying that they didn't have much time (or that they didn't want to spend too much time) for this. Is that really actually true, or is it some kind of 'modesty'[1]? When people talk about IQ there's usually a list of people saying something like "IQ is meaningless, it's a flawed concept (but my IQ is 138)". Are there any people saying "I worked really hard at this, I spent a lot of time and effort. I ranked 984th."? Because I'd love to see the results if those smart people got together and spent some serious time and effort on it. Lots of popular science projects suffer from a heavy churn rate, which leads to people being introduced to the subject, producing an introductory program, doing a bit of reading, but then moving onto something else. A few people stay, and work on intermediate and advanced level projects, but they suffer from lack of interest and expertise. See, for example, all the millions of artificial life / evolution softwares derived from Martin Gardners Bugs. (See also the death of Fractint, which was excellent software but did not transition to Linux or Windows or modern display programming.) [1] Not the right word but I'm not sure what fits.
- cpeterso 15y ago
  Netlix's movie rating prediction contest is a great example of smart teams collaborating. As the contest progressed some teams would join forces forming new hybrid algorithms.
  - tvorryn 15y ago
    Yeah. In this competition collaboration was discouraged. That does keep politics/alliance building skills out of the equation at the cost of worse overall final products.
- ajays 15y ago
  I didn't participate, but there's also the concept of "sour grapes". If one wins, then one describes how hard fought and thought out the victory was; if one loses, then one says one didn't spend much time on it at all ("if only I had more time..."). It's a way to placate the ego. :)
scotty79 15y ago
> Otherwise if the ant was just spawned sitting on my hill, the target border tile is determined using some complex calculation considering the ratio of own/enemy ants near that border position, the possible distance to enemy hills, how many ants are already on a mission to a near border tile and how long they do need to reach their desitnation... Oh, I'm kidding, it was random. Completely random. Like in target = area.border.get(turnRandom.nextInt(area.border.size())); Nice pun targeted at over-thinking of things. If you try to take many things into account without any concrete knowledge of how they influence outcome you'll get random result. So you may just start with random and see if it's good enough.

190 points by tvorryn 15y ago

tszming 15y ago

No content inside (but ads)

brettnak 15y ago
Either the link has been changed or this is just incorrect.
bhrgunatha 15y ago
> bplaced.net Zugriff verweigert, Fehler 403. Sorry, access forbidden, error 403. Contact service provider I think the hosting provider may have pulled the plug after a traffic surge. Google cache http://webcache.googleusercontent.com/search?hl=en&q=cache%3Ahttp%3A%2F%2Fxathis.com%2Fposts%2Fai-challenge-2011-ants.html&btnG=Search&pbx=1&oq=&aq=&aqi=&aql=&gs_sm=&gs_upl= http://webcache.googleusercontent.com/search?hl=en&q=cac...

peregrine 15y ago

Now this is what I go to HN for! The most interesting part for me was that he did not focus on some huge strategy. Just individuals and small groups with clear goals and constant revaluation. Keeping in mind that the only thing kept between rounds were missions and those were constantly reevaluated as well. I think this is a vivid, albeit simplified, example of how successful organizations of anything should operate. EDIT: grammar

Jyaif 15y ago
What's that? You aren't more interested in the SOPA drama?
- peregrine 15y ago
  Well I was when it was 1 day from being jammed down our throats. Then it was postponed to the new year, at least the lobbyists in our courts(EFF, Google, etc) have sometime to throw some cash around. And people can do something. I do think the SOPA Drama was a bit delayed and overblown here on HN.

icefox 15y ago

I had fun playing around with the challenge and spent most of the time poking around with map exploration as implementing min-max once again isn't too much fun. I ended up having the most fun playing around with the idea of an anti-object . The simplicity of anti-objects combined with the low memory and low cpu overhead was very nice. Wrote it up in a little blog for others: http://benjamin-meyer.blogspot.com/2011/11/using-collaborative-diffusion-rather.html http://benjamin-meyer.blogspot.com/2011/11/using-collaborati... Any ideas for a type of challenge that wouldn't be reduced to mostly min-max for the ranking, but could explore other concepts?

tvorryn 15y ago
I actually used this idea from the forums and your post to get 683rd place even though I started on it with 36 hours to go before the deadline. http://aichallenge.org/profile.php?user=972 http://aichallenge.org/profile.php?user=972 So thanks. How'd you do?

memnips 15y ago

Unfortunately the link appears to be temporarily dead. Luckily before you read about his bot you should watch it play anyways! Here are two replays of the same map. The first is played by average players and the second is played by xathis (and other top bots). Avg: http://aichallenge.org/visualizer.php?game=335973&user=8180 http://aichallenge.org/visualizer.php?game=335973&user=8... Top: http://aichallenge.org/visualizer.php?game=329760&user=4513 http://aichallenge.org/visualizer.php?game=329760&user=4...

WildUtah 15y ago
Note that every one of those "average" players finished in the top 10%. It's a hard problem to write any kind of generally adequate player for. All the good bots depend heavily on subtle properties of emergent behavior. Don't let the simple explanations fool you.

LearnYouALisp 15y ago

The first lines seemed familiar: http://quotenil.com/Planet-Wars-Post-Mortem.html http://quotenil.com/Planet-Wars-Post-Mortem.html

tvorryn 15y ago
Haha. It didn't say that before, because he hadn't officially won yet. It's actually been propagated from Tron: http://a1k0n.net/2010/03/04/google-ai-postmortem.html http://a1k0n.net/2010/03/04/google-ai-postmortem.html
- LearnYouALisp 15y ago
  It seemed like a tradition, but strangely Google only showed his page at the top.
- a1k0n 15y ago
  I definitely had no intention of starting a tradition there. Haha.
  - tvorryn 15y ago
    You didn't do too badly this time yourself. 11th place. Looking at what he did, do you see what you could do to improve your bot further?
    - a1k0n 15y ago
      Sure, but as he concludes at the end, I didn't want to spend too much time on it. My bot was fairly unique in that it used Monte Carlo methods rather than deterministic minimax, and it got the job done without too much effort. I wrote a forum post describing the basic approach here: http://forums.aichallenge.org/viewtopic.php?f=24&t=2044 http://forums.aichallenge.org/viewtopic.php?f=24&t=2044

hunterp 15y ago

There are 20 buttons on the page. Nuff said? -1 pls.

DanBC 15y ago

I see a few people saying that they didn't have much time (or that they didn't want to spend too much time) for this. Is that really actually true, or is it some kind of 'modesty'[1]? When people talk about IQ there's usually a list of people saying something like "IQ is meaningless, it's a flawed concept (but my IQ is 138)". Are there any people saying "I worked really hard at this, I spent a lot of time and effort. I ranked 984th."? Because I'd love to see the results if those smart people got together and spent some serious time and effort on it. Lots of popular science projects suffer from a heavy churn rate, which leads to people being introduced to the subject, producing an introductory program, doing a bit of reading, but then moving onto something else. A few people stay, and work on intermediate and advanced level projects, but they suffer from lack of interest and expertise. See, for example, all the millions of artificial life / evolution softwares derived from Martin Gardners Bugs. (See also the death of Fractint, which was excellent software but did not transition to Linux or Windows or modern display programming.) [1] Not the right word but I'm not sure what fits.

cpeterso 15y ago
Netlix's movie rating prediction contest is a great example of smart teams collaborating. As the contest progressed some teams would join forces forming new hybrid algorithms.
- tvorryn 15y ago
  Yeah. In this competition collaboration was discouraged. That does keep politics/alliance building skills out of the equation at the cost of worse overall final products.
ajays 15y ago
I didn't participate, but there's also the concept of "sour grapes". If one wins, then one describes how hard fought and thought out the victory was; if one loses, then one says one didn't spend much time on it at all ("if only I had more time..."). It's a way to placate the ego. :)

scotty79 15y ago

> Otherwise if the ant was just spawned sitting on my hill, the target border tile is determined using some complex calculation considering the ratio of own/enemy ants near that border position, the possible distance to enemy hills, how many ants are already on a mission to a near border tile and how long they do need to reach their desitnation... Oh, I'm kidding, it was random. Completely random. Like in target = area.border.get(turnRandom.nextInt(area.border.size())); Nice pun targeted at over-thinking of things. If you try to take many things into account without any concrete knowledge of how they influence outcome you'll get random result. So you may just start with random and see if it's good enough.