Tag Archives: java

Ants AI Challenge Introduction

So we are going to start with my most recent project – my entry for the latest AI Challenge (sponsored by Google) Ants.

You have a colony of ants to control, and the aim is to destroy as many enemy ant hills as possible. You grow your army by eating food, and try not to get your own hill destroyed. There are rules to resolve fights, and food gathering, as well as ant vision.

Screenshot of Ants

Not quite winning

Sure this sounds simple enough, but trust me when I say it isn’t.

The current suggestion is to use a BFS (Breadth first search) algorithm for each ant to each point of interest. The advantage of this would be that each ant finds the optimal path to food etc. There are some interesting behaviours that are being programmed by the current leaders – such as not approaching an enemy ant until your local forces outnumber theirs (something I’ll admit I haven’t implemented quite yet).

As of today, I am ranked 783rd in the world (or 34th in the UK) out of a possible 5788 and growing. I have some improvements to make, and I am planning on making them in the near future.

Currently I am using a derivative of the flood fill that I call the 4-way limited incremental flood fill (catchy, isnt it) to move my ants. The idea is that I place “seeds” in positions on the map, and every ant will attempt to move down the flood towards the seed point. This algorithm is fairly simple to implement, and does not slow down as the number of ants increase. I can control the size of these fills and so determine how many ants (if any) will traverse them, and I can overlap them to give priority to different features. The only disadvantage is that my ants will tend to clump together, reducing my overall map coverage, in turn collecting less food, resulting in a smaller army.

Improvements include

  • Adequate dispersion across the map.
  • Protect own hill from attack.
  • Do not engage if the result is my ant dies.

Again, there are exceptions to these rules based on the amount of points I currently have against the amount of points my enemies might have, or the amount of ants I have at my disposal – I am more than willing to sacrifice some of my ants to clear an enemy hill of its protection.

Unfortunately, the ants dont make any decisions for themselves – I have told them to head for food within a set distance, attack an enemy hill based on a set army size, and explore unexplored points. It is up to me which criteria gets priority, and if they lose a match it is because my decisions were not good enough. I don’t know what the optimum search distance for food is, or how many ants to keep at my base relative to how many ants I had. But to be honest, I don’t know if I am ready to leave the ants to their own devices, or even how to leave them to their own devices. A successful game is one where I get more points than the opposition – this is easy to quantify and qualify. So how do you define a successful ant; is it one that stays alive the longest, or gathers the most food? Is an ant that gathers 100 food more successful that one that destroys 1 enemy base? The second ant could win me the game, but he wouldn’t be alive if the first ant hadn’t collected the food. Is an ant that sacrifices itself to clear the enemy hill such that it can be destroyed more or less successful that the one that destroys it?

These questions are important as they define how the ant would see itself, and shapes the decisions that the ant would have to make in order to win the game. Unfortunately, it doesn’t even sound simple anymore.