Quote :

"The AI Challenge is all about creating artificial intelligence, whether you are a beginning programmer or an expert. Using one of the easy-to-use starter kits, you will create a computer program (in any language) that controls a colony of ants which fight against other colonies for domination. It only takes 5 minutes to submit one of the starter kits..."

http://aichallenge.org/

All you cats taking AI this semester should be all up ins. Our ranking:
http://aichallenge.org/organization_profile.php?org=405

Oh, and I thought my previous thread was fairly amusing, but I guess no one got the joke:
message_topic.aspx?topic=620139

11/8/2011 4:16:26 PM

Come on you lazy bastards.

11/10/2011 2:59:35 PM

I actually started tinkering with this over the past couple of days. Thanks for posting

Don't think I'll have enough time to put together a worthwhile bot, but I have one pseudocoded on paper that should do considerably better than most of the ones I've seen on the top positions of the leaderboards.

Since they allow bots to have state memory (aka you can construct your own internal map) to be able to use pathing algorithms (A* and BFS), you can actually use well proven combat and scouting strategies.

11/10/2011 5:27:26 PM

Yes, I have been surprised at how far you can get with BFS and A*.

11/10/2011 5:29:41 PM

Fair warning. One thing that does suck about this challenge is that every time you submit a new version you start at the bottom of the rankings And it takes a surprisingly long time for your rank to settle, since it takes several hours to play one game. I submitted my last version a week ago and that shit is still moving up significantly.

I compare this to Rock Paper Azure:http://www.rockpaperazure.com/
Sure, that game was a lot simpler. But you knew within 5 minutes exactly where you stood.

Now, don't let that stop you from playing. There are plenty of sample bots and the tools are pretty nice such that you can run your own games locally.

Quote :

"Don't think I'll have enough time to put together a worthwhile bot, but I have one pseudocoded on paper that should do considerably better than most of the ones I've seen on the top positions of the leaderboards."

Haha. I bet. "Everybody's got plans... until they get hit." -Mike Tyson

[Edited on November 11, 2011 at 7:40 AM. Reason : asdfasdfafd]

11/11/2011 7:38:31 AM

the Charlotte ALT.Net group did a battleship competition last year, it was pretty fun.

11/11/2011 9:27:38 AM

sorta reminds me of http://discovermagazine.com/2008/jan/robots-evolve-and-learn-how-to-lie

11/11/2011 10:53:31 AM

BOOM

we on the front page of rankings, haters



http://aichallenge.org/rankings.php

11/14/2011 10:15:11 AM

Nice. So is a class project working on the that algorithm, or is this you personally?

11/16/2011 10:39:13 AM

gg

[Edited on November 16, 2011 at 11:14 AM. Reason : you wanna post your code? i'd be interested to look at it]

11/16/2011 11:14:02 AM

^^Nope. I happen to be taking AI at the moment and there was some brief chatter on our message board, but that's it. I'm myopia and I have no idea who owns the rest.

Quote :

"you wanna post your code? i'd be interested to look at it"

ha. it's the ugliest spaghetti code you'll ever fucking see. last time I posted code on tww, I got mad butthurt about it being called inelegant

I don't mind writing out some psuedocode if you're interested in that

[Edited on November 16, 2011 at 11:51 AM. Reason : asdfasdf]

11/16/2011 11:44:36 AM

hahah i don't care i've written my fair share of slapped together code. maybe put it on github or bitbucket or something?

[Edited on November 16, 2011 at 11:55 AM. Reason : or pseudocode. whatever you please]

11/16/2011 11:54:46 AM

11/16/2011 1:02:18 PM

I'm in, but I've got a lot to learn.

11/18/2011 5:39:57 PM

I am in also, and just doing a lot of reading on known strategies, etc...

11/18/2011 7:05:54 PM

Just downloaded the starter package. CSC 326 project is due on Tuesday, I'll have time to work on it after that.

11/18/2011 9:44:40 PM

http://aichallenge.org/profile.php?user=11878

I just whipped up a very simple food-seeking bot. I did it in python for now, but I might switch to java, because the ultimate strategy i want to implement might be too hard (for me) to do in python.

The player in #1 seems to be using a very straight-forward strategy, i think he's beatable.

edit:

wow, i dominated my first match... nice

[Edited on November 19, 2011 at 2:05 AM. Reason : ]

11/19/2011 2:03:25 AM

I'm posting psuecode (I feel a bit uncomfortable about posting code both because it's shit and ethically speaking). Notes:

First, the website recommends BFS and A* search. These are pretty simple and I found them to meet all my searching needs so far. But for performance reasons, I used a limited search (not in any systematic way... they just cut off after a certain number of nodes have been expanded). Different limits are passed in based on the task. If there is food in sight for instance, you know it's very close by.
http://en.wikipedia.org/wiki/A*_search_algorithm
http://en.wikipedia.org/wiki/Breadth-first_search



********************************************

maintain a permanent list of enemyHills

maintain a permanent list of food

maintain a permanent list of integers for each explored tile

initialize a list of tiles that needExploring

maintain a permanent list of frontier tiles (tiles adjacent to any unexplored tiles)


loop explored
    increment explored[i] (elsewhere, set explored[i]= 0 each time tile is seen; tiles that haven't been explored recently have high values)
   if explored[i] is high
       add tile to needsExploring

//food gathering (this section is detailed... skip it if you understand optimal food strategies)
initialize list of lists of distances between tiles
loop food
    loop myAnts
        A* for piece of food (use extremely low limit... low hanging fruit)
        if path found
            add distance to list of distance
    if no paths have been found
        repeat the above but with higher limit
    sort food distances
    add that list to list of lists
sort list of lists (based on lowest distance in each list)

iterate through list of lists to gather food (each piece of food should get assigned the closest available ant)


loop myHills
    BFS from hill to enemies using a low limit
    //limit actually needs to be even lower on a multi-hill map because shit is crowded
    loop myAnts
        A* ant to hill
        //this should make nearby ants converge on hill to defend it


//this is how you actually win
loop enemyHills
    loop myAnts
        A* ant to enemy hill


loop myAnts
    BFS ant to frontier


loop myAnts
    BFS ant to needsExploring


loop myAnts
    if ant is on a hill
        move ant away (to prevent clogging)


//if all else fails
loop myAnts
    move ant in direction that is away from closest hill

11/21/2011 6:57:16 PM

Do you keep track of each ant individually or do you just "reset" what an ant is supposed to do after it reaches a goal?

And do you have it programmed so that one goal can "interrupt" another goal? Like if you have a path plotted to food, but an enemy ant or a new food appears closer, do you flush the previous commands and reroute?

11/21/2011 7:09:26 PM

Nope. Keeping track of ants individually (as a permanent object) is something I need to add, especially once I get to battle formations.

As of now, it seems to work OK just keeping a list of orders, iterating through the ants, and assigning ants to the current (and closest) highest priority goals. It's not even necessarily maintaining all the steps to a goal until it gets there. It's really just looking at things one turn at a time. That's why it's called myopia!

So I guess the answer to your second question would be yes, a closer piece of food would override a further one.

And just for clarity, the way I have A* implemented.... it can "reroute" in the course of a single search if a shorter path arises.

[Edited on November 21, 2011 at 7:55 PM. Reason : asdfasdf]

11/21/2011 7:31:37 PM

So you re just recalculating the A* each turn I assume?

Seems inefficient (just kidding but I get OCD about stuff like that sometimes)

11/22/2011 2:09:40 PM

Yes and you're right. It is inefficient. Ants with persistent goals would be much better.

But then you'd still have to deal with the question of interrupts. What if closer food arises? Are you going to ignore it to save a few executions of A*? You also have to deal with the case in which a tile on the path becomes blocked by other ants.

11/22/2011 3:25:35 PM

Hey Euro,

I'll post you my pseudocode when I get home tonight. It handles the interrupts, battle formations, defense and exploration. Since I'm not likely to get to build my own bot, at least someone should take advantage of the work I did do

It should be a pretty big efficiency gain over the turn to turn recalculating of every ant.

11/22/2011 3:45:56 PM

Cool

By the way, the contest submission ends December 18 (the Sunday before Christmas). That's the first time I've seen the deadline posted. Pretty awesome timing for me.... It's several days after I finish my AI final.

11/25/2011 10:00:31 AM

^^ psudo code?

12/6/2011 5:40:50 PM

^^^suede-code?

I've been pretty busy with class. I'm hoping that I'll be able to crank out some new features on the very last weekend, but it'll be tight.

12/8/2011 11:18:03 AM

Damn. I've dropped from ~100 - ~250

The competition must be really heating up. That or someone open sourced a highly ranked bot.

12/13/2011 6:47:29 AM

here's a post by the winner

http://xathis.com/posts/ai-challenge-2011-ants.html

12/23/2011 10:48:04 PM