Ora bem, servirá este post para descrever um pouco como me correu a minha participação no AI Challenge, por questões de poder interessar a outros participantes o post será em inglês.
For a start here is my bot http://aichallenge.org/profile.php?user=7746
It ranked 230, with first place in my country.
About the strategy, well I will try to explain my development through the contest and hopefully it will give some insight on it, but mostly there is nothing great about it, and probably you will give up reading this because it will be more a report of the development than of the strategy itself, but I’m no good writer.
NOTE: After writing it, yes it is more like a report, if you want a basic idea of what I did scroll to the bottom and skip the great wall of text.
Language choice:
This one was not exactly a linear thing, since my latest development projects were done with Java and some PHP, I was leaning towards them, but I started with python because I wanted to learn a little more about it. After getting annoyed with the indentation (it’s something I can’t get used to, especially since I move my code around a lot), I proceeded to PHP just to see how it would go (I was a little sick of the amount of work I had done in Java) but then I found myself thinking this will be rather slow, and I need a lot of stuff that Java already has, I even considered C++, but then some years have passed since I wrote some serious C++ code, so I ended up with Java.
With a language decided and set, I proceeded to go for the tutorial so I could get some better comprehension on the problem, and from there went with my own changes.
Since some of the class names were too confusing for me, I went and renamed them for something more understandable by my brain these are the ones I remember:
Ants -> AntManager
Aim -> Direction
Ilk -> TileType
I created a simple logger class so I could output everything I wanted as debug, but not wanting to go around enabling and disabling it, I made sure it was only turned on when 2 command line parameters were set, so I would set them while testing but on the server they were not used.
First thing I wanted to do was improve path finding for my ants, being somewhat forgotten of my AI classes, remembering that A* was a good solution I proceeded to implement it, but I ended up not doing an exact A* and it may even be something else but I’m happy calling it A*. The biggest difference was that I only used the distance returned by getDistance for the value of a tile, not counting how much it costs to reach it, yes it had some drawbacks on some cases but other than that it was great.
Something I thought from the start was something to keep the path for my ants and to make them move around without having to re-evaluate the path unless it became obsolete, so I created Missions, these were thought to be of several types, but I ended up using only one of them missions with target, so each mission would have an ant, a target tile and a list of directions (N,E,S,W), and some callback functions that would depend on the target etc. And used it for food.
Next I went into the exploration, I changed a lot in the starter code so I would have a new TileType, UNKNOWN the idea was to get an random unknown tile and send an ant with a mission there, on the update for tiles I would unset them as unknown into the proper type and when setting the vision too it got a little confusing but it worked. And then used the missions again for attacking enemy hills, yes my ants were blind and would go in a single line and could be easily killed by 2 smart enemy ants.
Having time usage issues, I proceeded to add cache to my path finding, if I knew the problems it would bring, I would have never done it. Anyway some versions later and lots of bugs found and fixed.
Now only one thing was worrying me, combat and hill defense. For defense I added a few static ants around my hill since other players were using it and in cases of lone attackers it would be enough.
Combat, not knowing much where to start, started by counting enemies around my ants and if they were less they would run, not great but better than nothing. With no more ideas I went into the forums in a search for inspiration and I ended up finding some interesting, collaborative diffusion.
After reading about it I decided to give it a try, and proceeded to code it, threw everything I had done for food gathering, exploration and hill razing and went with diffusion, after some hours with the diffusion parameters and some debug output into a file that I would plot in octave so I could see the diffusions, I ended up with some nice values, while trying to make everything easy do adjust in the future.
Now with better movements around my ants were lacking combat again, having diffusion tried to use it for combat but there was not much success, so I proceeded to brute force the combat solutions but that was too heavy and gave up on it. No more ideas means forums again.
In the forums I found two ideas, a1k0n and memetix ideas, memetix code being simpler was implemented first but I didn’t have much success with it and proceeded for a1k0n idea, after a lot of frustration by not being able to make it work (probably because of a bad evaluation) I ended up with something that worked here is how it was, first I would move my ants towards the enemies, then I would reset each ant position at a time and evaluate every move it could do (using full combat resolution, yes it was heavy, but it was the only thing working for me) and the rest was based on a1k0n idea, increment the dirichlet distribution etc.
A nice improvement I added was enemy stillness detection. If an enemy does not move after some number of turns I consider it static and do not move it when evaluating combat.
Now my bot was better and was nearly taking first place in Portugal, so I was pretty much happy with it, also the time was running out, but I had a small problem, two or more ants would go for the same piece of food because of diffusion, so my last improvement was to move my ants when going for food with my old A* code, but still use diffusion for exploration and enemy hill attack because it was faster.
Cleaned up my code and uploaded it I was at version 22 at the moment, it reached first in Portugal and was able to climb up to rank 150 with around 71 skill if I recall correctly.
In the last day I did some cleanup to the code, but knowing it is a terrible idea to change something and not test it properly, even though it was a small change and useless code removed I decided not to take a risk, in the TCP servers it was fine but not being able to test in the official servers those changes never made it and version 23 never existed.
So in the end what my bot was doing was:
- Food gathering via a sort of A* algorithm.
- Exploring (just into unknown tiles) and hill capture via diffusion.
- Defense, static incremental number of ants around the hill according to the number of ants I had.
- Combat based on a1k0n idea (thank you for that) with some help from diffusion to move the ants into the enemy at the start of the evaluation, I had some convergence problems but moving them into the enemies helped a little. Note that even the static defense stopped being static when in combat.
This pretty much sums it up.
Thoughts about the contest:
I learned a lot and being the first competition of this kind that I participate and I’m pretty happy with the results.
Thanks to all the contest organizers for making such a great competition.
To everyone who shared their ideas specially a1k0n, Memetix, and icefox (names at the forums) and all others who shared their ideas with others who didn’t had any ideas (like me).
