4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ what do you mean by "the score"? also, do you want exact answer or asymptotics? $\endgroup$ Oct 5, 2021 at 0:28
  • $\begingroup$ It's a two player zero sum game of perfect information. So, the game has some value, e.g., perhaps for some n with perfect play the first player has 2 more squares than the second so the score is +2. Exact answer would be great. Asymptotics would still be great. Even knowing who wins would be great! When you play this game it is hard to know if you are winning or losing until suddenly someone gets a lot of squares. $\endgroup$ Oct 5, 2021 at 0:43

1 Answer 1

13
$\begingroup$

This just the game of Dots and Boxes. There is a huge literature on this game. In particular, Berlekamp's book referenced in the above link shows how difficult this game is.

$\endgroup$
1
  • $\begingroup$ Thanks! Ok, great to get a pointer to the literature. I am not surprised it is complicated. $\endgroup$ Oct 5, 2021 at 1:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.