Tuesday, September 28, 2010

Google AI Challenge strategy and tips

Basic Strategies for the Google AI Contest.

Here is the first post sharing some strategy and programming ideas for the Google AI Contest, If you don't know what it is, check it out!

In this contest, participants write programs to play a two player, turn based game against other programs. The game, based on Galcon, is a space battle with planets and ships. The ships are either based at a planet, or are part of a fleet flying from one planet to another. When fleets arrive at a planet that is not owned by the player owning the fleet, a battle ensues. Each planet has a growth rate; every turn, the players earn more ships on planets that they occupy.

The great idea with this contest is that the games are turn based, and the input and output are text based. This way, the contest can easily pit programs written in different languages against each other.

I am probably misrepresenting something here, so you may want to browse the official site before going on.

Basic Ideas

Ship economics

There are basically three ways to alter the number of ships you have. First, earn new ships for occupying a planet. Both you and your enemy earn ships based on the planets you each own. Second, attack a neutral planet. That costs you ships, but not your opponent. Third, attack an enemy planet. Then, you each lose the same number of ships. Whoever has the most ships wins, so you want to grow more ships then the enemy, and you want to wisely spend ships to capture neutrals.

One consequence of this is that attacking an enemy planet, without taking it, does not change the "score". Maybe it is worthwhile for other reasons, but it does not change the difference in the ship counts.

Sun Tzu

Maybe other kids were like this... as a teenager I saw a book called "The Art of War", and read it cover to cover in a couple of days... without understanding any of it. I remember one thing out of it though, if only because it seemed weird: attack what cannot be defended, and defend what cannot be attacked. Finally, I have a place where I think I can apply it.

Since you have all of the information of the game state every turn, you can approximate which planets the enemy cannot defend, and try to decide which are the best ones to take. In reverse, you can figure out what is lost, and spend your resources elsewhere instead of trying to save bad planets.

Look into the future

The game state includes a list of fleets that are en route. You can simulate the future of the game, assuming no more fleets are launched, and see what will happen. This way, you can try to occupy a neutral planet the turn after the enemy takes it, and let them absorb the cost of battling the neutral ships. You can also see the effects of the other ships in flight... maybe the enemy is reinforcing a planet you thought you could take, or maybe they gave up on a planet that you were trying to attack.

Cloud the future for the enemy

If you want to see the future for yourself, you would like to keep the enemy from seeing it. One way to do that in PlanetWars is to delay sending a fleet until the last moment. Once a fleet is launched, it is committed, and the enemy will know where it is going and when it will get there. As long as ships are at a planet, they could go any direction on the next turn. Of course, if they are at a planet, they aren't attacking.

There may be some benefit to streaming ships at an enemy planet at times... but I think in most instances, waiting is better.

Coding

Obeleh goes into this in more detail, but here are some lessons I have learned, and relearned, over the years.

Algorithms

There are many chances to go crazy with fancy data structures and algorithms here, but in many cases, simpler code will work fine.

You have to spend time to save time.

This contest has two months to go at this point. Write some tools, spend the time to set up logging when you test locally, write some tests, get things working for debugging your bot. This will pay off in the end.

Keep the code simple

This contest is for fun. The more complex the code is, the more likely it is to be wrong. I have thrown away several days work so far because it was too unwieldy.

Throw away code should be thrown away

This advice is for me. Since this contest is for fun, I used a bunch of single character variable names in an early version of my bot. In a dynamic language. I ended up with a lot of weird errors too. The moral is, if you write it like throw away code... make sure you get rid of it. Write code you are going to keep like code you want to keep.

Version Control

Please use some sort of version control. That way you can more easily track changes, undo mistakes, etc. I use Mercurial which is a good fit for keeping a directory of files under version control. But, since the repository is in the same directory as the working files, make sure it is all backed up somewhere else.

Until next time

OK, that was less organized then I intended, but it was a start. Other things I would like to go into in the future are:

  • more details of strategies I have used
  • algorithm ideas (esp. places where complicated algorithms are likely to get used, but overkill)
  • python specific implementation details.
  • some useful tools for testing, debugging, etc.
  • maybe a simple bot to demonstrate some ideas...

If you have problems, the contest forum and irc channel are a good place to go.

2 comments:

rangzen said...

bitbucket just change account limitation so you can save online in a private mercurial depository.

Dave said...

rangzen, yes I just got that email this morning! That is exciting news, and now I can back up my bot over there.