Over the past few weeks I’ve been spending my free time taking part in the Google AI competition (organised by the university of waterloo).
While I didn’t end up doing so well (I was disqualified for taking just over the 1 second per move permitted in one of my games), I thought I’d post how I went about the problem. Many of the other contestants used similar algorithms, but for those who haven’t been following here’s the full thinking behind it:
The Game:
The game was Tron – two light-cycles, controlled by player’s AIs, battle it out to be the last one standing (example game).
How I played it:
My code (largely done in a blur very late at night) ended up having a couple of noticeable bugs – but here’s the algorithm I was going for.
Note – If the two players cannot reach each other, then it suffices to consider your own player alone – and in this situation you simply have to keep moving for as long as possible – creating the longest path you can.
That’s the strongest strategy when players are separated – I implemented the search for the strategy by emulating every step I could make, as many moves forward as I could go in the second (since you can make up to 3 different moves each step, the first step has 3 possible states, the second 9, the third 21, etc.).
At each possible state, I used a block-counting algorithm (described later) to see how many blocks I could reach from that point – and using all that information I could decide on which move would leave me with the best possible moves in the future.
Originally I wrote my code in Python, and could reach about 4 steps deep – but after porting to C (using a mixture of hand-written code and Cython) I found I was getting up to 15 steps deep – well enough for this algoritm to almost always find the perfect strategy.
When they opponent is within Reach:
When the two players are not separated, I (and most others) used a minimax algorithm. The idea behind it being that you generate all the possible moves of each player, and you assume that at each move you make the best move you can – and the opponent makes the best move they can. You calculate how good a game state is by calculating some heuristic function of that game state (described later)
The strategies generated by minimax are Nash equilibria in games where the two players take alternate moves – however in games such as tron, where the two players take simultanious moves, this cannot be stated – and if you take a single pure minimax solution then it can be shown to be sub-optimal.
This fact caused a lot of discussion in IRC and on the game forums about wether there may be other algorithms that could achieve a better strategy – although it seems it didn’t effect the competition much, which was largely dominated by the choice of the heuristic function and the depth at which people could search.
Note that this time both players can move three directions, so after the first move you have 9 positions, the second you have 81, the third 729 etc. Even once I’d ported to C I could normally average only 4 steps deep.
Block Counting
When considering a map like the following (“1″ is your player):
####### # # #### 1 # # #######
The most basic algorithm for counting the number of possible blocks would be to perform a flood fill – but that clearly gives false results on the map above as the player cannot actually fill both the top and the bottom chambers (a flood fill gives the result as 12 blocks – the correct result is 8 blocks).
Half way through the competition, one player (dmj) pointed out that this problem is analagous to the “checkerboard problem” – i.e. since we can only move N,S,E,W the board forms a bipartite graph, and we can colour the entire board (here with “X” and “Y”).
The maximum number of fillable squares is then given an upper bound of MIN(number of X’s, number of Y’s) (we can sometimes lower the bound by 1, but I’m ignoring that here)
####### #XYXYX# ####XY1 #XYXYX# #######
Now, as we can only move from an X to a Y (or v.v.) – we can count the number of “X”s (here 7), and the number of “Y”s (here 5) – and we return 10 blocks (closer to the correct 8, but still wrong). This has the advantage of being very efficient, but is still incorrect.
A better technique still is to separate the map into chambers: for example (using “A”, “B”, etc. for chambers):
####### #CCCAA# ####AA1 #BBBAA# #######
Next, these chambers need to be mapped into a chamber graph showing which chambers are reachable from each other. e.g.
A--B | +--C
We can now calculate the space in each chamber (using the block counting algorithm). In the above example, adding these up gives the correct result (8) – but not in the general case.
This was as far as I had time to get – but several contestants managed to look at the maximum length of paths within this chamber graph – giving even better results.
The Final Heuristic
My final heuristic (for measuring how good a game’s state was for my player) ended up being something like this:
- If I have won -> return 100
- If I have lost -> return -100
- If the players draw -> return 0
- If the players are separated at this point -> return (block_counting(my space) – block_counting(their space))
- If the players are not separated at this point -> split the remaining space into space they can reach first, and space I can reach first, then return the difference as above
Well, that’s just about it (give or take a few minor tricks) – unfortunately all my unit tests were on 5*5 maps – so in my tiredness I never spotted a few serious bugs in time to fix them (or how much time it took to free memory as I rolled down the stack – hence my timeout) – but it was a huge amount of fun taking part.
Thanks go out to the organisers, and congratulations to the winner, Andy Sloane (“a1k0n_”) from Yahoo! .
