strategy - Rook game on chessboard

A rook stands in the lower left corner of an $m\times n$ chessboard. Alice and Bob alternately move the rook (horizontally or vertically, through any number of squares). As the rook moves, it leaves a trail of painted squares: every square through which the rook passes or at which the rook stops is painted red. The rook is not allowed to pass through a red square nor can it stop on a red square. The first player who cannot move loses the game.

Determine the winner of the game for every combination $(m,n)$ of positive integers $m$ and $n$. (As usual, we assume that Alice and Bob use optimal strategies.)

Answer

I will assume that the square in the lower left is painted red as well.

Note that an $m\times n$ board is the same as an $n \times m$ board. So WLOG we will assume that $n \le m$.

When $n=m=1$, then the first player automatically loses because there is no valid move.

So lets assume $m>1$.

When $n=1$, then the first player will win simply by moving the rook all the way down the row. Player two will have no valid move.

When $n=2$, the first player can force a win again by moving the rook all the way down the row. Player two is forced to move up one into the next row, and the game degenerates into $n=1$ case.

The same is true for $n=3$. Player two must move up one or two rows, and by taking the complete row, player two is again forced into the remaining row.

In fact, this same strategy can be used for all $n$. The general strategy used by player one is to take the complete row. Player two is forced to move to a different row, and player two can again complete it.

One way for player two to beat this strategy would be to force the game into a spiral condition where the act of moving into a new row exhausts all entries in that row. But since the first move was made eliminating $m$ squares, and $m \ge n$, the remaining rectangle is $n-1 \times m$, and player two must move to a different row. The only way that a spiral could form is if player one failed to take the complete row, resulting in a rectangle with more rows than columns. But since player one is not using that strategy, this can never happen.