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.

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

> I'm working on a bot in D. I'm currently done implementing the A* algorithm for path finding

Dump A*, D* Lite ftw ;)

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

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

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
>

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

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

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