›
This forum is in permanent archive mode. Our new active community can be found here.

Google AI Ants Challenge

AprecheApreche
edited October 2011 in Technology
http://aichallenge.org/

I have decided that after I eat dinner, I am doing this full on. It will be way more worthwhile an activity than playing video games, which is probably what I was going to do tonight otherwise. Anyone else out there want to have a go at it?

Comments

  • AndrewAndrew
    Depends on my availability, but yes I'm interested. When is the deadline?
  • AprecheApreche
    edited October 2011
    Just finished eating. Tried to sign up. Account creation is closed? WTF.
    Apparently all accounts will be purged tomorrow. It's beta right now.
    Post edited by Apreche on
  • RymRym
    I just looked at the Python starter kit. This is not so bad for even a beginner programmer to play with.
  • AprecheApreche
    Nothing in the rules says I can't be open source. There's no prize, so no reason not to share. So far I've got just the tutorial bot and that's it.

    https://github.com/Apreche/Ants
  • Anthony HemanAnthony Heman
    I havn't had time to look at this too heavily yet, but the first strategy I would implement is to try to figure out the optimal growth strategy as if it was a solo game. Basically, if your growth strategy beats the enemies growth strategy, you should at least have a good baseline from which to start planning an offensive or defensive strategy.
  • AprecheApreche
    edited October 2011
    Finally figured out how to get pygraph to do an A*. Thing is, I can only get it to work using the euclidean heuristic, and not the chow heuristic. It's just so poorly documented. The euclidean one is fine, but I think it might be a problem when it comes to the Pac-Man wrapping scenario. I have to test it more to see if that is really an issue or not. If it's not an issue, then I think the euclidean heuristic will actually be better for this situation.

    Simply applying the A* results to the tutorial bot will make a tremendous improvement, and should be a very formidable bot. The tutorial often has ants that go back and forth forever in a loop, and A* will solve that. Once I add 5-10 more simple obvious improvements on top of that, it will be an easy ride up near the top of the charts. Then it will be an insanely hard ride to get even higher.

    My general plan to have dynamically changing priorities. I'll program behaviors for exploration, growth, attack, and defense. Then each turn the four priorities will be reordered and ants will be allocated to the four different behaviors accordingly with most ants performing the highest priority task and the fewest doing the low priority task.
    Post edited by Apreche on
  • Anthony HemanAnthony Heman
    I'm looking at each of the base implementations first to see which one I would rather work with as a start. I've looked at python, perl, PHP, Java, and Javascript. I almost want to use the Javascript one just because someone did it. I think I like the java more than the others I've looked at so-far.

    I actually want to try an AI based solution. Maybe something as simple as randomly select an action from the available action types, record the ants surroundings at the time, the action chosen, and the net value of the "turn" based on the change in score. Save that off to a seperate file, and repeat till you have an approximation of which actions are "good" in a given scenerio. Let that cook for a while, then use the data to seed your next set of actions (but keep calculating and improving). I have no idea how poor that would end up being, but it sounds like fun to test.
  • Anthony HemanAnthony Heman
    Now I"m thinking about class-based ants. Defender ants. Attacker ants. Scout ants. Forager ants. Court Jester ants. Sleepy ants. Ants that play snake.
  • AprecheApreche
    I actually want to try an AI based solution. Maybe something as simple as randomly select an action from the available action types, record the ants surroundings at the time, the action chosen, and the net value of the "turn" based on the change in score. Save that off to a seperate file, and repeat till you have an approximation of which actions are "good" in a given scenerio. Let that cook for a while, then use the data to seed your next set of actions (but keep calculating and improving). I have no idea how poor that would end up being, but it sounds like fun to test.
    I was also thinking of a genetic algorithm, however there is a rule against writing to files. You can read from a file, but you can't write. That means you would have to generate all your data on your own computers, and couldn't learn anything while on the system.

    Maybe you could get around this rule by storing your data in a web service and connecting to it via an API. Even if they allow this, I see a high chance of your bot dying if there is a network hiccup. Remember, if you miss one time limit then you are done and all your ants sit still forever.
  • Anthony HemanAnthony Heman
    I was also thinking of a genetic algorithm, however there is a rule against writing to files. You can read from a file, but you can't write. That means you would have to generate all your data on your own computers, and couldn't learn anything while on the system.
    Which still sounds fun.
  • AprecheApreche
    Which still sounds fun.
    Yes, but it would probably suck since the only bot your bot could learn from would be other bots you have written, or bots other people gave you willingly. You would never be able to learn from actual competitive bots, and you would probably end up sucking.
  • Anthony HemanAnthony Heman
    Which still sounds fun.
    Yes, but it would probably suck since the only bot your bot could learn from would be other bots you have written, or bots other people gave you willingly. You would never be able to learn from actual competitive bots, and you would probably end up sucking.
    Your undwarf-like attitude seems oddly unfitting.

    Oh, also, my ants are dwarves with randomly generated names.
  • Anthony HemanAnthony Heman
    There also appears to be a replay feature... perhaps that can be manipulated if you wanted to be able to gather data from the live server?
  • RymRym
    My ants should just form up into the shape of a penis and march around the map.
  • AprecheApreche
    There also appears to be a replay feature... perhaps that can be manipulated if you wanted to be able to gather data from the live server?
    That's not a bad idea. Put a bot out there. It won't learn as it plays, but you can download all the replays, update the data file, and upload it again with the new data file.
  • AprecheApreche
    My ants should just form up into the shape of a penis and march around the map.
    You win.
  • SchnevetsSchnevets
    Totally down, but not until after midterms.
  • AprecheApreche
    Registration is now open. I created a Front Row Crew team
  • AndrewAndrew
    Registered, but not for the FRC team :(
  • Anthony HemanAnthony Heman
    Joined. I havn't put any real time into this yet, maybe sometime this weekend. It's a side project near the bottom end of my side-projects... but it sounds like fun.
  • AprecheApreche
    So python-graph is working great, but there's a problem. The euclidean heuristic is slow as balls. It uses all the CPU and all the RAM if the graph has any resonable number of nodes and edges.
  • AprecheApreche
    I figured out the problem. The euclidean heuristic builds a gigantic data table when you call optimize(). I replaced it with a heuristic that computes simple as-the-crow-flies distances on the fly. Not great, but it works well on a non-weighted graph such as this game.

    I'm still having timeout situations on larger maps. I have to figure out what's causing that.

    Also, because my guys are so good at finding the shortest path, they often make a bee-line for an enemy hill. But they don't clump up, so they die marching single file on the shortest path to their doom. I need to have some sort of formation strategy.

    I haven't submitted this bot yet because it times out. I have submitted the tutorial bot, and it does surprisingly well. I'm amazed at how many people have submitted bots that are worst than the tutorial!
  • ClockianClockian
    Scott, thank you for your super-techie talk (to an amateur). You've given me the inspiration to spend the entire weekend figuring out what you are talking about.
  • Anthony HemanAnthony Heman
    edited October 2011
    A* and the other big algorithm are both, generally speaking, very slow algorithms to try to use for all ants individually. You can use them, but I think to do so well you might end up having to spend a lot of time on optimization. The ants also have a bit of a traveling salesman problem going on.

    One idea I've had as a starter is to designate ant classes. The "worker" ants might use a* exclusively for food, while the "warrior" ants (maybe 50/50 split?) group up and only use a* once for the entire pack to hunt down nests. They would need to know how long to wait grouping up too. One warrior is designated general after the cluster is formed... you check path for him only (unless he dies), and all the other ants in the pack just try to move the same way. If the general moves up, they all try to move up. It's clumsy, but perhaps practical to get you one step closer to a base-line?
    Post edited by Anthony Heman on
  • AprecheApreche
    Well, naturally my first attempt is to treat it like a board game and brute force the perfect solution. Due to the time restraints, now I have to scale back and take into the technological limitations.

    One thing I am definitely going to do is something I saw when I looked at the top bots. Remember, even if ants can shoot further than they can see, they would need a spotting ant to actually do the seeing for their "artillery". That means almost all of the time you can stay perfectly out of range of enemy ants. The behavior I saw on a really good bot was that when an enemy was encountered to stay just out of range. Then put out a rallying cry for other ants. And when the tide was turned, attack. Basically, an ant never has to step in an unsafe square. I'm going to implement something along those lines. Even if my ants are attacked from both sides, they will be squished together into a formidable force that will have a good chance for survival or doing as much retaliation damage as possible.
  • lackofcheeselackofcheese
    I intend to put my full effort into this once I have time (a few weeks from now). You're all going to lose.
  • AprecheApreche
    I intend to put my full effort into this once I have time (a few weeks from now). You're all going to lose.
    Yes, because I have moved on to other things.
  • Anthony HemanAnthony Heman
    I intend to put my full effort into this once I have time (a few weeks from now). You're all going to lose.
    Depends on what game we're playing. If Rym's game is trolling ants, you can both win.
  • open_sketchbookopen_sketchbook
    I cannot code whatsoever, being an art guy, so I'm going to take the example code, change the values at random, and see what happens.
  • StarfoxStarfox
    Some guys made a contest in the same mold as the ants AI challenge called halite. Looks pretty cool, I'll give it a shot.
Sign In or Register to comment.