Article
galcon1

Solve This: An AI Bot to Colonize the Galaxy in 5 Minutes

Alex J. Champandard on November 19, 2007

Over the last few months on AiGameDev.com, I’ve written numerous in depth reviews of the artificial intelligence in AAA game. There’s certainly a lot to learn from such titles, but looking at things from the opposite side of the games industry is equally helpful.

This article focuses on an independent game called GalCon, a galactic colonization game that takes a few minutes to play. The game is pretty addictive; try the demo! This review starts with a short introduction to the gameplay and how the AI framework is implemented, then describes what the main challenges are.

Galactic Colonization Single Player

Screenshot 1: Single player GalCon against the default AI bot.

GalCon Gameplay

The game can be picked up in a few minutes, but as the saying goes, takes a lifetime to master. The rules are as follows:

  1. The planets in your control produce ships depending on how big they are. You start with one big planet..

  2. You can send your ships to attack neutral planets, guarded by a constant number of ships.

  3. In battle, ships are lost one-to-one; you can take over a planet once the number of opposing ships reach zero.

  4. Your enemy also controls ships, takes over neutral planets, and can attack you even.

The goal of the game, obviously, is to destroy the enemy force within the galaxy. It’s not necessary to control all the neutral planets, however.

The Framework

You can see the framework in action in the demo, but you’ll need to register the full version to be able to run your own mods.

The AI is implemented as a Bot class which uses a simple and elegant scripting API written in Python. A new bot can be implemented in one file only, using the following boilerplate code:

import galcon

class MyBot(galcon.Bot):
  def init(self):
    """Setup the bot AI."""

  def loop(self):
    """Called every frame."""

Within the main update function, you can use a fleet command to order your ships from one planet to another. Planets and all the information you need is available from the base Bot class also.

This approach is rather typical of current games. It gives the implementor the important information from the game, and exposes the necessary actions, exposed in a dynamic programming language that can be reloaded at runtime. The scripting languages imposes very few constraints on the way you structure the AI, so there’s a lot of freedom to experiment with new approaches.

Galactic Colonization Three Bots

Screenshot 2: Three way symmetrical game (plugin) among three AI bots.

The Challenges

The gameplay is deceptively simple, but the little details that make the game fun also make it extremely hard to build AI. Specifically:

  • The ships have a speed limit, so it takes time for any attack or defense to arrive.

  • Individual ships in the same fleet arrive at different times, and get caught behind planets.

  • You don’t know how many ships the enemy has stationed in each planet. (Update: Theoretically, the AI can cheat obviously.)

What’s particularly challenging is to find a balance between conquering neutral planets (which take a known & constant number of ships) and taking over enemy planets (with an unknown number of ships, but constantly producing). It’s also necessary to take into account the current ship inventory with future production.

How Would You Solve This?

This kind of game is ideal for practicing the design and implementation of game AI. So how would you approach the problem of developing AI for this game?

  1. What kind of information would you gather about the current galaxy, and how would you implement this?

  2. How would you use this information, and how would you make trade-offs between the different options?

Be sure to share your designs and ideas in the comments below! And be sure to check out the game.

Discussion 6 Comments

Andrew on November 20th, 2007

Neat find, I'll have to try it out. No doubt unless there is a heavy bias towards one kind of strategy, that the AI might have to take best guesses due to the lack of knowledge - not a bad thing, just hard to model. Can you also pit AI vs. AI? I loved tracking (for a while) Age of Empires 2 AI contests which was very easy to setup AI vs. AI on randomly generated maps (with contests being "best out of...X" ones to remove the element of chance you'd start up in a poor position). I'd need to get into Python to work with it though, but I should check this out, soounds cool (Although I need to get to bed right this second).

Jare on November 20th, 2007

Hehe, I think I remember this game was presented in the "Swarm" contest. Very impressive! Given the small amount of planets, it should be feasible to approach it as a board game. Take a few fuzzy logic techniques, use brackets for estimations of unknown values (# of ships in enemy planets) and search possible moves using best / worst / average values. Once the basics are done, add in some tactics for scouting, harassing and baiting, and some personality factors to weigh the value / confidence of best, average and worst case scenarios. Easier said than done, but good AI is never easy, is it?

alexjc on November 20th, 2007

[B]Serge[/B], I think you're side-stepping a lot of important details by just using linear optimization. Could you give us more details of how you'd approach this? [B]Jare,[/B] Sounds like a very sensible approach to add scripted behaviors on top of fuzzy estimations. How would you take into account ships in flight, and potential arrival times? [B]Andrew[/B], The game seems quite balanced, and there are lots of options that open up in real-time... so not that many biases. :-) But after playing it for a while, I'm inclined to believe the default bot implementation cheats to produce ships faster than you. You can watch bots play together on random maps with a nice plugin called Symmetry. And, yes, it's a great way to start programming! (Read through and make minor changes to existing bots first.) Alex

Andrew on November 20th, 2007

The default bot cheats? The swine! First thing to remove when editing it is the code after "CheatWithSuperShipProduction()" :) Since it seems quite balanced I'll take a gander when I have a chance, it's bookmarked now. In the future an AI site (well, this one, since I can't find really any other *active* Game AI sites!) should have a small contest for some game like this to pit AI vs. AI, especially if the game itself is any good and can be programmed easily (I'm not sure this game is any good yet ;) ).

alexjc on November 20th, 2007

[B]Andrew,[/B] A contest is a good idea. I've run them before but don't have the time right now in the build up to GDC :-) Phil, Galcon's creator, is interested in having one for his game, but it'd be nice to have one that's generally open for anyone to join in. If anyone is interested in helping set this up, [URL=http://aigamedev.com/author#contact]email me[/URL]! [B]Zeroth,[/B] Great ideas. The only thing I'm not sure about is how well minimax would perform in such a real-time problem... It's traditionally turn-based, but it could work I guess. Alex

Jare on November 21st, 2007

"How would you take into account ships in flight, and potential arrival times?" When evaluating a move, also estimate how long it would take to be complete, and extrapolate the movements of ships in flight, but only generate moves of the AIs when my move is complete. After that, I would subdivide that period based on the smallest time that AIs would take to complete their current moves. Once that is in place, I'd consider more frequent subdivisions, and probably take ships in flight into account when evaluating the board score. In essence, try to treat it as a turn-based game where the time of each turn is variable.

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!