Open Tutorial
PW_BaptismByFire.medium

PlanetWars AI Challenge and Advanced Strategy Guide, AiGameDev.com Prizes!

Alex J. Champandard on October 6, 2010

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:

  1. Worst Case — Predicting the state of a planet if only the enemy sends his ships there.

  2. Best Case — Predicting what will happen if only you send your ships to this planet.

  3. 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.

Opponent Modeling

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.)

Useful Tricks

  • 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.

  • Read these other strategy guides: first, second, third.

Conclusion

You should join the PlanetWars AI Challenge. It's fun. There are AiGameDev.com prizes!

It's that simple :-)

Discussion 6 Comments

jpeck on October 11th, 2010

Hi Alex, Thanks for driving interest in the Google AI challenge. You say: "We'll also provide any single person team that ranks higher than our official bot three months of AiGameDev.com PLUS ..." So how and when is that determination made? Currently, "the__graid" is ranked 233 while aigamedev is 293, so technically it "ranks higher than our official bot"! Do I qualify for the prize? the__graid: [url]http://ai-contest.com/profile.php?user_id=11011[/url] aigamedev: [url]http://ai-contest.com/profile.php?user_id=10752[/url]

alexjc on October 12th, 2010

jpeck, If you can hold the ranking at the end of the contest -- yes! I have another version of the bot that's roughly 2x better and it should be ready for submitting in a few days hopefully ;-) Alex

quayo on October 31st, 2010

I love the enthusiasm and I will be looking forward to the next version of aigamedev bot. Do you have any plans for writing more articles on the advanced topics of developing a bot for Planet Wars?

alexjc on November 1st, 2010

Quayo, Thanks for your kind words! I plan to update this post with more recent discoveries from the community once I've submitted the new bot... I hope to work on that today. Alex

meatkat on December 6th, 2010

How do we go about claiming our prize and getting upgraded to plus?

alexjc on December 8th, 2010

meatkat, I'm trying to figure out a way to do this logistically. Unfortunately, the sponsorship fell through as the organizer never kept up their end of the agreement, and we got no exposure what so ever (worst sponsorship ever). I doubt they'll help me give out the prizes either for that matter, not even address the issue... The best way so far seems to start a thread in the PlanetWars forums and have you post your AiGameDev.com username and bot name/ID. Then if you claim someone else's they'll notice ;-) Alex

If you'd like to add a comment or question on this page, simply log-in to the site. You can create an account from the sign-up page if necessary... It takes less than a minute!