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 :)

0. http://csclub.uwaterloo.ca/contest/forums/viewtopic.php?f=10...