Find a stronger AI for a game, or even a winning strategy

Question

It is a two player game. First we have a eight by eight matrix with a white stone on the (1,1) entry and a black stone on the (8,8) entry. Then alternatively Player 1 and Player 2 move the white stone and the black stone respectively in eight directions: east, northeast, north, etc. For example, at the start of the game, P1 can move the white stone southeast from (1,1) to (7,7), and then P2 can move the black stone west from (8,8) to (8,2). But there is one rule to follow: if you move the stone from entry A, say (2,2), to entry B, say (5,5), then the entries on the straight line from A(2,2) to B(5,5), in this case (2,2), (3,3), (4,4), (5,5), must not be any entry that has been a position for the stones before. At last, to win the game is to force your opponent into a position where he cannot move his stone any more.

Zermelo's theorem tells us that for a game of this kind, i.e. a finite two-player game of perfect information, one of the players has a winning strategy. But it can be very hard to find such a strategy even with the help of a computer. Can you find it?

Even if we can't find the winning strategy, one can at least try to program a strong AI. One try would be as follows. If it is the AI's turn to move, it calculates, for each possible choice of move, the number of moves its opponent can make afterwards; it then pick a move with the smallest such number. So this strategy bases itself upon the idea that, the situation is worse if you have less choices of moves.

But there should be many other things to consider to make the AI stronger. So can you give me some suggestions?

Answer 1

Unless I'm missing something, player $1$ (white) has a simple winning strategy. First he moves southeast from $(1,1)$ to $(7,7)$. Player $2$ (black) must then move north (along the eastern border) or west (along the southern border), since the diagonal is blocked. White then moves in the same direction as black did, all the way to the edge of the board, thereby sealing black into a one-square-wide corridor. Black now has at most six moves left, and white has plenty of room to putter around until black runs out of room and loses.

The game is likely to be more interesting from a more generic starting position.

Answer 2

This isn't really an answer, but it's a start anyways.

I think the game is most interesting when considering a general map (not necessarily 8x8, and possibly with certain tiles already filled in and un-passable) with arbitrary starting positions.

This is very similar to the 2010 Google AI Challenge -- Tron. Here's a video showing the game. Each player controls a Tron LightCycle (motorcycle) starting on a particular square. As you move over the grid, you leave a trail behind you that acts as a wall. Neither player can cross your light trail. When you run into a wall (whether one that was on the map originally, or a light trail), you die. The last player standing wins.

The differences here are that (a) this is turn-based rather than simultaneous-move, (b) in Tron you can only move one square at a time, and must move to an adjacent square; here, you can move a farther distance on each turn, (c) here, squares that you pass over on a long move can be re-used later (like on the move from (1,1) to (7,7), the square (2,2) can later be used for a stone).

To think up good heuristics, the crucial observation for Tron, and I believe for your game as well, is that the winning player who stays alive the longest; and this is the player with the longest (guaranteed) path.

A first rough approximation to this is to compute the number of squares that you can reach before your opponent can. However, this is not good enough: You might have 10 squares "available", but you need to make a choice to turn either right or left, and whichever way you choose, only 5 will be available and you will be cut off from the other 5, so you really only have a path of length up to 5 available. Similarly, think of a map that looks like a comb: It has lots of space available, but ultimately you can only go down one of the "teeth", so the longest path available is not that long.

So one good strategy is to do a minimax sort of thing where you evaluate the position by attempting to approximately compute the longest path available to both players, and picking the move that seems to guarantee you an advantage. There could be lots of heuristics for this. But it seems hard here because moves can be very "non-local" (like a jump from one side of the map to the other).

You can see a post-mortem from the winner of that AI challenge; maybe it will be interesting or useful. Maybe there is some easy winning strategy for white, but I can't see it.