The Grid Disconnection Game

Alice and Bob are playing a game on an $8\times8$ grid. Two cells in the grid are adjacent if they share a side; the shared side is called a passage between them. On their turn, a player removes any remaining passage from the grid. A route from cell $X$ to cell $Y$ is defined as a sequence of cells $X=c_1,\dots,c_k=Y$ where, for each consecutive pair $c_i$ and $c_{i+1}$, $c_i$ is adjacent to $c_{i+1}$ and the passage between them has not yet been removed. We say that the grid becomes disconnected the first time there exist two cells which do not have a route between them. The game ends when the grid becomes disconnected, and the player who made the last move loses. Define the length of the game as the number of removed passages. Alice starts.

1. (a)What's the minimum length of the game? What's the maximum?
2. (b)Assume that both players are rational, i.e., the winner wants to win as fast as possible and the loser wants to lose as slowly as possible. What's the length of the game? Who will win? What is the winning player's strategy?
3. (c)Suppose instead on Bob's turn, he reinforces one existing passage, i.e., makes it permanently indestructible. Alice wins if she can disconnect the grid; Bob wins otherwise. Assume that both players are rational. Who will win? What is the winning player's strategy?
4. (d)$^*$Assume that both players remove passages uniformly at random. Approximate the expected length of the game.
5. (e)$^*$Suppose instead Alice and Bob are playing on an $n\times n$ grid ($n\ge2$), and they remove passages uniformly at random. Find an asymptotically tight bound on the expected length of the game.

For the following parts, flip the game: the player who made the last move wins. Assume that both players are rational and $m,n\ge2$.

1. (f)Suppose instead Alice and Bob are playing on a $2\times n$ grid. Does the same player win for all $n$? If so, who wins, and what is their winning strategy? If not, characterize the values of $n$ in which Alice wins.
2. (g)$^{**}$Suppose instead Alice and Bob are playing on an $n\times n$ grid. Does the same player win for all $n$? If so, who wins, and what is their winning strategy? If not, characterize the values of $n$ in which Alice wins.
3. (h)$^{***}$Suppose instead Alice and Bob are playing on an $m\times n$ grid. Does the same player win for all $m,n$? If so, who wins, and what is their winning strategy? If not, characterize the values of $m,n$ in which Alice wins.

$^*$ These are quite instructive and probably my favorites among the problems.

$^{**}$ Beware; this one is surprisingly difficult, but there is a very clever solution.

$^{***}$ I haven't been able to solve this one; please reach out to ndawit611@gmail.com if you find a solution!