www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.announce - AI Challenge - Ants

reply Jesse Phillips <jessekphillips+d gmail.com> writes:
For those who didn't see. AI Challenge, an event sponsored by Google, 
supports the use of D 2.054 and provides a starter pack.

http://ai-contest.com/

http://www.reddit.com/r/programming/comments/ljk4v/
ai_challenge_fall_2011_ants_now_open/

From the D.learn post:

So here is the deal: You write a program that controls a population of
ants. You get a number of ant hills and explore the map with your ant
horde looking for food to produce more ants and enemy ant hills that you
can raze for points.
There is fog-of-war and obstacles. Moving ants in groups gives them better
chances to survive by outnumbering enemies. The map is on a grid and ants
wrap around if they move over the edges. A match usually has between 2-8
players and is turn based. The players make their moves simultaneously
within a time window of 500ms. Oh yeah and it is free to sign up and
requires no previous knowledge in AI programming.

Feel free to ask questions on the IRC channel #aichallenge on Freenode.
Oct 22 2011
parent reply Max Wolter <awishformore gmail.com> writes:
On 10/22/2011 6:49 PM, Jesse Phillips wrote:
 For those who didn't see. AI Challenge, an event sponsored by Google,
 supports the use of D 2.054 and provides a starter pack.

 http://ai-contest.com/

 http://www.reddit.com/r/programming/comments/ljk4v/
 ai_challenge_fall_2011_ants_now_open/

  From the D.learn post:

 So here is the deal: You write a program that controls a population of
 ants. You get a number of ant hills and explore the map with your ant
 horde looking for food to produce more ants and enemy ant hills that you
 can raze for points.
 There is fog-of-war and obstacles. Moving ants in groups gives them better
 chances to survive by outnumbering enemies. The map is on a grid and ants
 wrap around if they move over the edges. A match usually has between 2-8
 players and is turn based. The players make their moves simultaneously
 within a time window of 500ms. Oh yeah and it is free to sign up and
 requires no previous knowledge in AI programming.

 Feel free to ask questions on the IRC channel #aichallenge on Freenode.

And for those who care: I'm working on a bot in D. I'm currently done implementing the A* algorithm for path finding and it won't be long until I have finished the exploring / gathering of food roles. The combat strategy however is going to be huge, so that'll take a bit longer. If anyone wants to exchange ideas, feel free to get in touch - I'm hanging out in the freenode channel of the challenge regularly. I will have a busy few weeks ahead, so expect the first D bot (if it will be the first) to pop up on the upper part of the scoreboard in in about 2-3 weeks. /Max aka awishformore
Oct 25 2011
next sibling parent reply Trass3r <un known.com> writes:
 I'm working on a bot in D. I'm currently done implementing the A*  
 algorithm for path finding

Dump A*, D* Lite ftw ;)
Oct 25 2011
parent reply Max Wolter <awishformore gmail.com> writes:
On 10/25/2011 1:44 PM, Trass3r wrote:
 I'm working on a bot in D. I'm currently done implementing the A*
 algorithm for path finding

Dump A*, D* Lite ftw ;)

Hellooo. Correct me if I'm wrong, but in A*, I can just find a path, store it (let's say as a string) and find a new one if it's blocked for some reason. As far as I could see from what I've read about Lifelong A*, D*, Focused D* and D* Lite, I would have to store all nodes used in the algorithm - so, as opposed to A*, I have to conserve the state of the entire search algorithm throughout ticks, for each ant. Is the environment in this AI challenge really noisy enough to warrant this? Obviously, if the path needs to be re-planned almost every tick, D* Lite seems like a better choice to me. But if you have 100+ ants, that would be a lot of allocated heap memory, wouldn't it? I really don't have a clue how the processing vs allocating should be weighed here performance-wise. /Max
Oct 29 2011
parent reply Max Wolter <awishformore gmail.com> writes:
Ola.

Well, my A* algorithm is already working very nicely - and imo there 
isn't any problem-specific optimization left to implement other than the 
data structures holding the nodes themselves. So the question is only 
whether it would pay off to switch to D* instead.

Second, I'm aiming for the #1 spot :D. I have a lot of strategy in mind 
that I haven't seen implemented by anyone else yet and I think a TOP 10 
spot should definitely be possible. Minimizing the impact of the 
path-finding on computing requirements is thus certainly a priority.

/Max

On 10/29/2011 9:26 PM, Lishaak Bystroushaak wrote:
 Hi.

 I don't think, that you have to use some advanced strategies and path
 finding. I'm currently 261 with this simple code:
 http://pastebin.com/1Nsb81rj With hill defense and ant grouping, you
 could be imho easilly in first 100 without A* :)

 2011/10/29 Sean Kelly<sean invisibleduck.org>:
 If you want to cheat, there have been books published on ant colony
optimization.  I'm sure the related papers could be dug up.

 Sent from my iPhone

 On Oct 29, 2011, at 3:12 AM, Max Wolter<awishformore gmail.com>  wrote:

 On 10/25/2011 1:44 PM, Trass3r wrote:
 I'm working on a bot in D. I'm currently done implementing the A*
 algorithm for path finding

Dump A*, D* Lite ftw ;)

Hellooo. Correct me if I'm wrong, but in A*, I can just find a path, store it (let's say as a string) and find a new one if it's blocked for some reason. As far as I could see from what I've read about Lifelong A*, D*, Focused D* and D* Lite, I would have to store all nodes used in the algorithm - so, as opposed to A*, I have to conserve the state of the entire search algorithm throughout ticks, for each ant. Is the environment in this AI challenge really noisy enough to warrant this? Obviously, if the path needs to be re-planned almost every tick, D* Lite seems like a better choice to me. But if you have 100+ ants, that would be a lot of allocated heap memory, wouldn't it? I really don't have a clue how the processing vs allocating should be weighed here performance-wise. /Max



Oct 30 2011
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 10/30/11 3:43 AM, Max Wolter wrote:
 Ola.

 Well, my A* algorithm is already working very nicely - and imo there
 isn't any problem-specific optimization left to implement other than the
 data structures holding the nodes themselves.

A* is fairly specific but if the implementation is generic enough (e.g. parameterized on the node type and the heuristic use) I think it would have a place in Phobos. Andrei
Oct 30 2011
parent Peter Alexander <peter.alexander.au gmail.com> writes:
On 30/10/11 4:30 PM, Andrei Alexandrescu wrote:
 On 10/30/11 3:43 AM, Max Wolter wrote:
 Ola.

 Well, my A* algorithm is already working very nicely - and imo there
 isn't any problem-specific optimization left to implement other than the
 data structures holding the nodes themselves.

A* is fairly specific but if the implementation is generic enough (e.g. parameterized on the node type and the heuristic use) I think it would have a place in Phobos. Andrei

We'd need a graph library first :-)
Nov 15 2011
prev sibling next sibling parent Sean Kelly <sean invisibleduck.org> writes:
If you want to cheat, there have been books published on ant colony optimiza=
tion.  I'm sure the related papers could be dug up.=20

Sent from my iPhone

On Oct 29, 2011, at 3:12 AM, Max Wolter <awishformore gmail.com> wrote:

 On 10/25/2011 1:44 PM, Trass3r wrote:
 I'm working on a bot in D. I'm currently done implementing the A*
 algorithm for path finding

Dump A*, D* Lite ftw ;)

Hellooo. =20 Correct me if I'm wrong, but in A*, I can just find a path, store it (let'=

=20
 As far as I could see from what I've read about Lifelong A*, D*, Focused D=

s opposed to A*, I have to conserve the state of the entire search algorithm= throughout ticks, for each ant.
=20
 Is the environment in this AI challenge really noisy enough to warrant thi=

eems like a better choice to me. But if you have 100+ ants, that would be a l= ot of allocated heap memory, wouldn't it?
=20
 I really don't have a clue how the processing vs allocating should be weig=

=20
 /Max

Oct 29 2011
prev sibling parent Lishaak Bystroushaak <bystrousak kitakitsune.org> writes:
Hi.

I don't think, that you have to use some advanced strategies and path
finding. I'm currently 261 with this simple code:
http://pastebin.com/1Nsb81rj With hill defense and ant grouping, you
could be imho easilly in first 100 without A* :)

2011/10/29 Sean Kelly <sean invisibleduck.org>:
 If you want to cheat, there have been books published on ant colony optim=

 Sent from my iPhone

 On Oct 29, 2011, at 3:12 AM, Max Wolter <awishformore gmail.com> wrote:

 On 10/25/2011 1:44 PM, Trass3r wrote:
 I'm working on a bot in D. I'm currently done implementing the A*
 algorithm for path finding

Dump A*, D* Lite ftw ;)

Hellooo. Correct me if I'm wrong, but in A*, I can just find a path, store it (le=


 As far as I could see from what I've read about Lifelong A*, D*, Focused=


, as opposed to A*, I have to conserve the state of the entire search algor= ithm throughout ticks, for each ant.
 Is the environment in this AI challenge really noisy enough to warrant t=


te seems like a better choice to me. But if you have 100+ ants, that would = be a lot of allocated heap memory, wouldn't it?
 I really don't have a clue how the processing vs allocating should be we=


 /Max


Oct 29 2011