• Jesse Phillips (17/17) Oct 22 2011 For those who didn't see. AI Challenge, an event sponsored by Google,
• Max Wolter (11/28) Oct 25 2011 And for those who care: I'm working on a bot in D. I'm currently done
• Trass3r (1/3) Oct 25 2011 Dump A*, D* Lite ftw ;)
• Max Wolter (15/18) Oct 29 2011 Hellooo.
• Sean Kelly (12/29) Oct 29 2011 If you want to cheat, there have been books published on ant colony opti...
• Lishaak Bystroushaak (15/35) Oct 29 2011 Hi.
• Max Wolter (11/41) Oct 30 2011 Ola.
• Andrei Alexandrescu (5/9) Oct 30 2011 A* is fairly specific but if the implementation is generic enough (e.g.
• Peter Alexander (2/12) Nov 15 2011 We'd need a graph library first :-)

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.

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

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

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

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

=20
 Dump A*, D* Lite ftw ;)

=20
 Hellooo.
=20
 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.
=20
 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, a=
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=

s? Obviously, if the path needs to be re-planned almost every tick, D* Lite s=
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=

hed here performance-wise.
=20
 /Max

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=

ization. =C2=A0I'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 (le=


t'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 algor=
ithm throughout ticks, for each ant.
 Is the environment in this AI challenge really noisy enough to warrant t=


his? Obviously, if the path needs to be re-planned almost every tick, D* Li=
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=


ighed here performance-wise.
 /Max

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.


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

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

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