Google AI Challenge

First iteration: this is a schoolbook-example of discreet state spaces; the moves of each player can be represented by a tree, in which we're searching for a node with the following properties:

-is it OTHERplayer's move

-without him having further valid steps

Using a breadth-first search, calculating the number of moves forward has a (both time, and space) complexity of N^3 (you can not move backwards). Calculating all of the possible steps forward, then selecting consistently moves, where all possible end-state is a winning state would yield a mathematically guaranteed always-win robot (to the extent the table's configuration allows for).

This is feasible for several of the built-in test maps (the ones without nasty combinatorial explosions), as well as in endgames.

Working from this one backwards, see how much space you can fill for each player at a given step! If fill(a) != fill(b) then one of the players has been cut off; and the one with larger space wins.

This should give you a good head start; of course, you still need to figure out a good heuristics, that puts you into a position for a killer state-space :)

About the problem itself, it seems solvable in a way that a good algorithm will never lose. Or am I off in my intuition?

Once they make scheme available, I might give it a shot.

It was a fun way to learn programming.