Due to other engagements, I've decided to pass on in participating this, but not before my imagination went wild :)
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 :)
These kind of collective challenges seem to me the best way to learn programming. If I had the time/money, I'd love to find a way to monetize a website dedicated to competitive challenges like this. I'm surprised TopCoder doesn't sponsor them.
About the problem itself, it seems solvable in a way that a good algorithm will never lose. Or am I off in my intuition?
Deleted, my assumption about an m-by-n board with opponents starting in opposite squares was wrong [0]. Apparently, there will be arbitrary maps with what looks like mirrored (not random) starting positions. My intuition would then be to generate dynamic strategies which attempt to box the opponent. But that seems easier said than done :)
Any idea what size grids the contest is actually using or at least within what order of magnitude? The graphic used seems to show a square grid with a size of around 15-20 on a side.
As a kid I wrote AI for snake in Atari Basic. I was very proud of it since it played aggressively and when you moved your snake close to its, it turned to get in you way when it was sensible.
Working on this. The way the Ruby starter pack is written makes it mostly useless, so I ended up rewriting all the map class. I suppose that's what happens when they translate Java to Ruby.
I'm also trying Ruby on Mac OS X and I can't run any java simulations. Always throws a Bad Version number in .class file exception. I think I have the JDK, but anyway the most recent version on the Sun's website is not available for Mac OS X...
Yeah, I'm going to use this to improve my python skills. The last time I used python for anything remotely serious was 5 years ago... seems like it might be a bit dated.
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 :)