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.

• Quick Start
• Tutorials and Strategy Guides
• Game specification — important!! especially about battle resolution
• Obeleh's Strategy Guide in the forums — pretty good. if you can read only one of his or mine, you might want to choose his

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.

Well, I have been doing ok in the Google AI Contest so far as dmj111. As time goes on, I hope to share some of what I learned in the contest.

Google AI Challenge

Well, there goes all of my free time. The Google AI Challenge is back, and I have a hard time ignoring it. My entry is doing well so far, but that will change when the match scheduling gets better. Several people have much better entries, but from the luck of the draw, they have lower ratings.

Last time, I did ok, but spent too much time on it, mostly chasing lack-of-sleep induced bugs. Let's see if I can learn my lesson this time around.

One to nine puzzle

The problem

Find a number using the digits 1 through 9 once each, such that

• the number is divisible by 9
• if the right most digit is removed, the number is divisible by 8
• if the next right most digit is removed, the number is divisible by 7
• ... until there is only one digit left, which is divisible by 1

Brute force

The first thing to do, is see if brute force will work. Often it will, and even if it doesn't solve the problem, thinking this approach through can help find a better solution.

We could loop throuch each possible nine digit number, and see if it meets all the rules. We might do it like this:

for i in 123456789 to 987654321 do
    # check if i contains each digit once
    # check if i is divisible by 9
    # check if floor (i/10) is divisible by 8
    # ...

That might not be too bad, but it will check 864,197,532 numbers, and the logic in the loop isn't that clean. Instead of checking if each digit is used once, we could generate all permutations of 123456789 instead. That way, every number meets the criteria of using each digit once. Also, we would only check 9!, or 362,880 values, checking far fewer numbers than the first idea.

Not so brute force

If we look closer at the problem we can see that we have a number of the form abcdefghi. "a" must be divisible by 1. "ab" must be divisible by 2. "abc" must be divisible by 3, and so on. Using that information, we could first check "ab", before appending any more digits to it, and wipe out a lot of possible numbers. For example, we know that "21" can never be the start of our answer, since 21 is not divisible by 2. Of the 72 possible two digit starting values, about half will fail this test. That will take us down to 180,000 values or so! Then, we can eliminate about 2/3's of the rest by checking all of the first three digits, and go down again to about 60,000 possible values.

We can get this solution to work with a recursive function. The inputs will be a list of digits left to use, and the current number we are considering (the first n digits). We will write the function so that the current number is always valid, so it contains no duplicate digits, and it follows the divisibility rules. Also, the digits to use list contains exactly the digits we need to make a valid solution, and no more.

def fast(nums=range(1,10),acc=0,d=1):

    if not nums:
        # we have reached the end... print the answer!
        print "result: ", acc
    else:
        for n in nums:
            # update the number with a new digit at the end.
            newnum = n + 10*acc
            if newnum % d == 0:
                # this is a valid partial solution.
                # Call recusively with a new list of nums.
                tmp = [x for x in nums if x is not n]
                fast(tmp,n+10*acc,d+1)

I abused the default arguments of the function so it can be called without any arguments. The new function runs in less than two milliseconds, which is about 1/300,000th of the brute force timing.

If you only want the answer, the brute force solution is good enough. But, you can work at it to find a cleaner answer, and then learn a technique that can help in other problems.