digitalmars.D.announce - AI Challenge - Ants
- Jesse Phillips <jessekphillips+d gmail.com> Oct 22 2011
- Max Wolter <awishformore gmail.com> Oct 25 2011
- Trass3r <un known.com> Oct 25 2011
- Max Wolter <awishformore gmail.com> Oct 29 2011
- Max Wolter <awishformore gmail.com> Oct 30 2011
- Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> Oct 30 2011
- Peter Alexander <peter.alexander.au gmail.com> Nov 15 2011
- Sean Kelly <sean invisibleduck.org> Oct 29 2011
- Lishaak Bystroushaak <bystrousak kitakitsune.org> Oct 29 2011
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
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
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
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
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
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
Peter Alexander <peter.alexander.au gmail.com> 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
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
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