Two players take turns coloring edges on an $n$-by-$n$ grid. Both players use the same color. Every time a player surrounds a square of the grid, they mark that square with their name and go again. A player cannot pass; they must move if it is their turn. The goal is to make as many squares as possible. What is the score with optimal play as a function of $n$? Note that ties are only possible if $n$ is odd so that the total number of squares is even.
To state it more formally: there is a graph with vertices labelled by pairs $(i,j)$ for $i,j \in \{1,\ldots,n\}$. There is an edge between a pair of vertices $(i,j)$ and $(k,l)\ $ iff $\ |i-k|+|j-l|=1.\ $ The state of the game is described by specifying the player whose move it is and specifying a bit for each edge, saying whether that edge is "colored" or "uncolored". One player moves first. Initially all edges are uncolored. On a turn, a player picks an uncolored edge and colors it. If the edge that a player colors makes at least one elementary square colored (i.e. that edge is in a cycle of length $4$ of colored edges), then the player scores one point for each such elementary square, and it is that player's turn again. Otherwise, it is the other players turn. Game terminates when there are no uncolored edges. Each player tries to maximize their own score.
