It is currently Sun Apr 23, 2017 7:38 pm Advanced search

The story of agent_smith

Share and discuss ideas for your entries here.

The story of agent_smith

Postby agent_smith » Thu Dec 22, 2011 6:51 pm

As people give the descriptions and code of their bots, I will do something similar. Maybe more of a story than description, because clearly there's a lot of better bots to look at. Mine is ranked around 180 at the moment.

I learned about the competition quite late - registered on November 23rd. I decided to go with Python, because it's an elegant, simple language and I had known it a bit from before. I entertained a thought of learning Clojure, but decided it would be too difficult to learn a new language and code a bot at the same time.

Early on, it became clear that there might be some performance problems with Python. Most top ranking bots were written in C or Java, and dynamically typed languages (Python, PHP, Ruby) seem to run about thirty times slower.

First I did the tutorial and improved on tutorial bot. This version just moved randomly or in straight lines, and when it had food in sight, it went for it. It worked surprisingly well, althought wasn't that great in mazes.

Overall, there were two main breakthroughs in the development of my bot. First had to do with navigating the map and gathering food, second with combat.

Then first one was when I read about a collaborative diffusion. I liked it right away, because it offered a unified way of dealing with all kinds of movement.

Implementing diffusion was easy and it worked right away. My diffusing bot ranked around 650 at one time - and it was ignoring enemy ants completely, that is, just went where the scent was coming from. And the scent was coming from food, invisible areas, unexplored areas, enemy hills and later from enemy ants.

The main thing left was combat. I wasn't sure how to approach this. Fortunately, first a1k0n and then Memetix wrote about their methods. At first, I had trouble understanding them. Then I tried a1k0n's version, but it didn't work for me and I suspected Python would be too slow to do this. I decided I better go implement Memetix' approach, which was very common sense. It was quite easy once I understood the idea.

The method is simplified in that it only sees own and enemy ants, without paying attention if there's more than one enemy. I suppose it gives worse results when multiple parties are involved, but one may say it works well enough. I run out of time to write a full version.

Finally, my ants were behaving! They were forming lines, and regrouping, something that looked at least vaguely like what top bots were doing. This version managed to reach about 180th place before the finals.

One other important moment was when I learned about PyPy, which is basically a Python with JIT compiler - runs muuuuuch faster. Suddenly, the same code was running several times quicker, and performance stopped being a major bottleneck.



So here's the agent_smith, in case you want to take a look or match your bot against it.

The thing is based on starter pack and rather short: basically less than 1200 lines of code, including whitespace and scarce commments. There's also some AI visualization stuff that I enclose for completeness.

The bot runs on two simple ideas:

1. Each ant decides which direction to go, based on the strength of scent coming from each direction - towards the strongest scent. Of course, scent map must be prepared earlier. This is diffusion part.

2. If there's an enemy around, each ant checks own and enemy strenght (influence), as described by Memetix. If it's safe to go, it goes, if not, it doesn't (with some exceptions).

Main problem with combat is "lazy friends", that is, ants are unsynchronized, so it may happen that one goes one way and the other one some other way when they both need to go in the same direction to defeat an enemy ant.

To overcome this, in a week before the final I tried writing a combat simulator which took all ants close to enemy and aimed to find optimal combination of movements. It was quite frustrating, because I pushed myself hard to do this, but the effect was underwhelming. I got it to work in my third attempt, but it was inferior to my best bot and there was no time left to work on it further, so I went with the previous, simple version.

Just before the deadline I slapped a few quick hacks to improve areas that needed improvement, namely defending own hills and attacking enemy hills. Maybe it helped a little.

So here you go, a version which is currently in competition.
Attachments
MyBot.zip
(10.21 KiB) Downloaded 211 times
agent_smith
Colonel
 
Posts: 54
Joined: Mon Nov 28, 2011 2:28 pm

Re: The story of agent_smith

Postby Nefbrethilion » Thu Dec 22, 2011 9:03 pm

Hello agent_smith,
thanks for your story, I enjoyed reading it and like to hear about other Python only bots. I myself use pypy too although it doesn't seem to improve my bot a lot.

I considered a scent system even before the collaborative diffusion post but didn't want to go too far in these kind of things, since I would need a very good visualiser (which was not available at the time) and since I wanted more fine-grained control. So I implemented the first thing that came to my mind: astar :-) Since I didn't have a lot of time I just kept with this and improved my bot, adding exploration and combat later on. Here is a small overview of my technique:

* Divide map in a uniform grid, use this to speed up searching close ants
* Astar to objectives (food, grid cells, hills), cache the path for next turn
* Explore neighboring grid cells when there are less ants (this ensures "territory ownership" and thus quick food gathering in my territory)
* BFS to enemy hills
* Memetix method for combat

I tried to overcome the "lazy ant" problem too but didn't succeed. It would be nice to recalculate the combat for each ant you move but this took waaay too long in silly Python :-) I also tried to detect "intruders" and chase them but it didn't yield better results.

I'd love to hear about highest ranked Python (only! - no c extensions) bots.
Nefbrethilion
Cadet
 
Posts: 7
Joined: Sun Oct 30, 2011 10:16 pm

Re: The story of agent_smith

Postby zaphod » Fri Dec 23, 2011 3:35 am

I also have a Python bot, though a crappy one! Not worth to be there even in the top 500, but is surprisingly placed around 350 at the moment. I have tried to solve the lazy ant problem to some extent though. What I do is whenever checking for the best directions for my ant, if I find that the movement of an ally ant can cause the death of an enemy ant, I just add the ally ant and the direction which could cause the enemy death to a dictionary. Its more like a request for the ally to move in that direction. When movements are evaluated for the ally ant concerned, it will first check the movement requested. If this movement does not cause a "free" death (surrounded by more than one enemy), it will move in the requested direction. If however, that movement causes a 1 v many scenario, then it will ignore the request and move to a safer place. This could have been changed, but I preferred not to. So in the best case, the ants both move as expected, while in the worst case the 1st ant dies in a 1 v 1 fight, which is still not bad, since there is hardly any processing needed!
zaphod
Captain
 
Posts: 21
Joined: Tue Nov 01, 2011 6:07 pm


Return to Strategy

Who is online

Users browsing this forum: No registered users and 1 guest

cron