PlanetWars is an AI programming game where you write a bot to conquer the galaxy, planet by planet. The rules are simple; each planet produces ships per turn, and ships can be used to take over other planets from the enemy or neutral forces. It's inspired by Galcon for those of you that are familiar with the game. Once you have written your bot in one of many supported languages, you submit it to the official site and it competes online against others from around the world!
The contest is run by the University of Waterloo Computer Science Club and supported by Google. Until today there were no prizes either, but here's some good news for you; AiGameDev.com is providing some prizes for the winners! You can win 6, 12 or 24 months of membership to AiGameDev.com PREMIUM if you place third, second and first in the contest respectively. We'll also provide any single person team that ranks higher than our official bot three months of AiGameDev.com PLUS — our brand-new part of the site that launched last week. Note that space for PLUS is limited, so if our bot doesn't rank very highly we'll give out the prizes for PLUS incrementally over the months after the contest :-)
In the rest of this article, I want to focus on advanced tactics. I'll talk about what I did with the official AiGameDev.com bot to get into the Top 10%, and what you'll need to do better! If you follow this tutorial and implement the ideas here, you should be able to beat our bot and win yourself the PLUS prize we're offering. Simple!
Screenshot 1: The official AiGameDev.com bot's first game (red), ending in a solid victory. Subsequent games didn't go quite so well! (Click to watch.)
Kinetic and Potential Energy
PlanetWars is a game about balancing two forces: ship production (or kinetic energy) and ship count (or potential energy). If that sounds obvious to you, let me ask you the following question:
“Does your code spend as much time reasoning about ships that will or could exist, compared to the ships that actually do already exist?”
In practice, that means you should be writing a lot of your code, and spending a lot of your runtime doing things like:
Which future ships you will have available and how you can include them into your plans.
Thinking how future ships of friendly planets nearby could help with defense of incoming enemy fleets.
Considering how future ships that result from an enemy attack underway will impact your attack.
Evaluating whether you have enough margin to attack an expensive neutral planet even if you get attacked.
What does this mean in practice? You need prediction via simulation... Lots of it!
Planet State Prediction
Probably the most useful thing you'll need is predicting the state of the planet in the future. To visualize it, a nice way to do this is using a histogram. Each bar is a number of fleets, the ones above zero are yours (in blue) and the ones below zero your enemies (in red). This makes it very obvious at a glance to see the state of a planet, and figure out if you're under attack, if ownership will change, and what your bot should be doing about it!
Screenshot 2: Predicting planets into the future. Time flows from left to right, and each line represents a planet. A) The first planet is neutral and remains neutral. B) The second planet is yours, and the number of ships in blue grows over time. C) The third planet is enemy, and the ships in red are also increasing their numbers. D) The fourth planet belongs to you now, but an incoming enemy fleet takes over in six turns. E) A neutral planet is captured by your blue ships, and then remains in your control. F) The last planet is in your control, is attacked by the enemy, but remains in your control.
The prediction happens from the next turn, until a horizon / limit that you pick. The bigger the maps, the longer the prediction may have to run to take into account all fleets, but it's not clear whether that's entirely useful yet! Another trick you can use is to avoid simulating each step (credit to Hamstah), but instead only process incoming events and use interpolation of the fleets numbers in between.
Using Custom Predictions
Prediction of what's going to happen is very useful, and you can build pretty good bots based on that. However, taking this a step further is even more useful: doing custom simulations to predict what could or should happen depending on what you want to know. Here are some examples:
Worst Case — Predicting the state of a planet if only the enemy sends his ships there.
Best Case — Predicting what will happen if only you send your ships to this planet.
Extreme Case — Predicting the state of a planet if everyone sends their entire fleet there.
The official AiGameDev.com bot uses all of these. The worst case helps figure out the risk-level of a planet; the best case helps figure out if there's even an attack opportunity at all; and the most extreme case is useful for figuring out which fleets would be safely available.
Of course, when you start customizing the predictions, rather than having these "stock" predictions calculated once upfront, you'll find yourself re-calculating these predictions as you make decisions and evaluate where to send your ships. It's a great way to assess the impact of an attack that relies a bit less on magic numbers and hand-crafted heuristics.
One last thing that's missing for any advanced strategy is opponent modeling. Many bots are currently doing this implicitly by calculating heuristics for taking over planets that include various aspects of the enemy planets. However, by modeling the opponent more explicitly — for example including a minimal sensible defense in your predictions — you will get much better results.
Opponent models help you figure out if it's a waste of time for you to attack, and better prioritize your planets for attacking and reinforcement. More so than just the "extreme case" prediction I mentioned above, having a basic model of your opponent should your bot avoid things like "sniping" and get the edge on the endless battles for the middle ground. Adding a basic opponent model to the predictions in our official bot has made it twice as good as the current iteration, so it will hopefully hit the Top 5% on the next submission!
Screenshot 3: The first time-step of map50.txt. This is a prediction of the extreme case, where both sides go "all in." Home planets are the solid histograms of entirely either red or blue bars. Easy planets to take start of neutral and then end up entirely blue or red. Expensive planets that are tough to hold (without taking intermediate planets to reinforce) switch from red to blue, or blue to red — depending who gets there first. The graph is drawn with matplotlib directly from the bot itself, and it takes the library 1s just to generate the PNG! (Click to enlarge.)
- Setup some difficult maps with specific bots (e.g. RageBot) that can be solved only if playing perfectly.
Unit test your basic planet prediction; you'll thank me later!
Get yourself some nice histograms and setup a HTML5 visualizer.
You should join the PlanetWars AI Challenge. It's fun. There are AiGameDev.com prizes!
It's that simple :-)