Knights of the Cardboard Castle

This post is a detailed walkthrough of my bot’s internal logic, the source code of which is attached. It’s written in Java using Notepad++. I probably should have used a real IDE as it would have helped save time finding compile errors. It’ll also contain some improvements that I’d have added if I had the time and some notes on some of the cool bots other competitors have submitted and their strategies.

Source code in zipped file

My Bot’s Logic

Rather than retype everything, I’m copying from my post on the official forums here:

Strategy-wise, my bots borrows ideas from quite a few people, both from here and from QT3. Mistmanov’s very detailed overview of his bot was key. lesslucid (QT3 member!) prompted me to think about more complex strategies beyond what the starter bots did. And shangas (QT3 member!) provided some very useful ideas and advice, in particular about how to define a “front”. I also browsed through most of the threads in the Strategy section of this forum, and all that helped in countless small ways. Ok, finally, let’s talk what my bot does now.

1. If it’s the first turn, my bot checks how far away the enemy starting planet is and reserves just enough ships to ensure that it will be able to survive a first turn Ragebot-style all out attack. As per Mistmanov, it also calculates the maximum distance between planets and stores it to use for a variety of purposes, including how far ahead to calculate future turns. All other ships are simply sent out according to a simple rate of return calculation (the standard distance + defenders / growth rate). I do check that the minimum expected return I can get in ships exceeds my initial investment, which ensures that my first turn expansion targets aren’t vulnerable to sniping. I’ve tried to experiment with more elaborate first turn moves, but none of them worked better than this.
2. On normal turns, the first thing my bot does is defend. It simply looks at incoming enemy fleets and sees if each planet has enough ships to defend. If not, send ships from other planets to help out. My bot can send ships from multiple sources to a single friendly planet to help at the same time. But there’s no prioritization system at all. Reinforcement ships are basically sent out on a first-come, first-served basis. I don’t assign scores to defensive moves and pick the best ones. I just defend whatever can be defended. Ships that are not needed to defend get put in an arraylist of ships available for other tasks. If I find that a planet is going to be lost next turn, I also add all of the ships on it to the available reserves.
3. Next, I do Mistmanov’s future state calculation thing but only for planets not currently owned by me (Yeah, I even kept the name. I’m so shameless.) I’m not going to explain this in detail as you can just look at his original post. I store all these results in a hashmap and then move on.
4. Then, for each of planets with available reserves on it, I evaluate a score for each of these future planet states and have it do the best one that it can do. My bot does not stream ships. It only deliberately sends ships to neutral or enemy planets if it is certain that it will be able to take it. It is also incapable of sending ships from more than one planet to carry out a single invasion mission. I added this ability later but the original still worked better so I left it out. But here is a key part that I think helped improve my bot a lot. When the time comes to carry out a move, my bot does a final sanity check. If the best possible move that the reserves on a planet is capable of doing is still a rather poor move (arbitrarily defined), then the mission gets cancelled and those ships do nothing. This simple change was ridiculously effective in my private testing.
5. Each time my bot issues an order, I recalculate my planet state thing for the planet to which I just sent ships and store the new result in the same hashmap, so that the changes to the predicted future would be taken advantage of by my other planets.
6. Finally, ships that are still available are sent to the front. I look for the closest enemy planet and send ships to the closest friendly planet that is closer to that enemy planet than I am. I believe that shangas’ implementation send fleets directly to the friendly planet closest to the closest enemy, but that didn’t work very well for me, so I went for a mixed approach, sending them directly when the alternate route is too long and moving to the closest friendly first if it’s not too long.

Improvements

There are a number of ways in which my bot could be improved. Some were features that I’d struggled with before the final round and had to give up because I couldn’t get them to work correctly. A few ideas came to me only after I’d watched some matches from the final round.

1. Invasions should draw ships from multiple friendly planets. I made a couple of different implementations but they didn’t work very well. I think that given enough time to debug and test, I could have gotten it to work well, provided that I also added this next feature.
2. Friendly planets should not expose themselves to invasions. This means that I should reserve ships on my planets in case the enemy sends ships to them. I experimented with this but it simply made my bot too conservative, expanding too slowly. I believe that combining these two features would balance out the weaknesses and result in a much stronger bot. I lost many matches in the final round due to my bot lacking this feature. It would calculate that it had sufficient ships to take over an enemy planet and did so, but didn’t count on the enemy vacating the planet and choosing to swap planets instead.
3. Friendly planets should stream ships at enemy planets when the bot doesn’t have sufficient ships to take over the targets but does have superiority in both ship count and production. If one side has more ships than the other, it is in that side’s interests to reduce the ship count of both sides equally so to improve the ratio by which it has more ships.

Naturally, there are many more ways that my bot could be improved but these are ralatively easy changes that would fit within the existing framework. More extensive improvements would require a completly different approach. It’d still be far from top 10 material, but I suspect my ranking could be significantly raised with these changes. I also note that I didn’t use any tools other than those in the starter package and that I didn’t do any additional testing on non-official servers. It would probably have helped a lot if I had invested the time and effort to look into the more specialized tools other competitors have made and done more testing against other players’ bots.

Other Bots

Many other competitors have posted details about their bots and released their source code. The most highly anticipated of these was of course the blog post by the winner, Gábor Melis. However, I found his explanation to be a bit too complex for me and I confess to only the most superficial understanding of how his bot works. I found the explanation of the second-place contestant, Iouri Khramtsov of Canada, to be much more digestible. I found it fascinating how the early version of his bot greatly resembles mine, but he pushed it much further with his concept of potentials for both offense and defense, allowing his ships to be redistributed among his planets in an intelligent to maximize both. It’s certainly a much more refined approach than my crude defense and sending ships to the front systems.

Finally, one bot worthy of special mention is Space Invaders of Austria. This is a bot built entirely using genetic programming methods, with the team responsible submitting the best version of each successive generation once a day. They haven’t released their source code as they hope it will have commercial applications but their detailed overview of how they made it work makes for a fascinating read. The bot only reached 277th place in the final round, but the team claimed that they were severely constrained by the lack of computing power and thus a rate of evolution. It would have been interesting to see what it could turn into given more resources.