Dots and Boxes has a rich mathematical theory which can be divided into three separate parts. The first is the mathematical proof of the chain rule, the second is the application of combinatorial game theory to resolve Dots and Boxes endgames, and the third is computer analysis.
The chain rule was discovered by Elwyn Berlekamp while he was in Junior High School and an outline of the proof is given in the chapter on Dots and Boxes in volume 2 of Winning Ways.
The application of combinatorial game theory to Dots and Boxes is also due to Berlekamp, and is fully discussed both in Winning Ways and in Berlekamp's book on Dots and Boxes.
Computer analysis consists of an exhaustive analysis of all positions to provide a rigorous evaluation of a game. It has been provided for 5x5 dots as well as other special positions by David Wilson. This type of analysis was first used with great success by Ken Thompson for analyzing chess endgames.
A normal game is one in which both players take turns without moving into any chains or cycles until all that is left is chains and cycles. At this point, a player will have to move into a chain or cycle. A normal game will continue with the other player responding by taking control and keeping it. A normal game ends when the player having control takes all the boxes in the last chain.
More precisely, the chain rule states that if a player wants to force his opponent to be the first to move into a chain or cycle in a normal game, then
To understand the proof of this result, one works backwards, by understanding how a normal game ends.
In a normal game, the last player is the one who took all the boxes in the last chain on his last turn. But this is the player who kept control in order to take all the boxes of the last chain, so this is also the player who got control when the first chain was given away. One can conclude from this that
Lemma 1: In a normal game the player who took the last turn is the one who forced his opponent to first move into a chain or cycle.
Since the first player always takes the odd turns and the second player always takes the even turns (recall the definition of turn) one can restate this as follows.
Lemma 2: A normal game in which the first player forces his opponent to first move into a chain will have an odd total number of turns. A normal game in which the second player forces his opponent to first move into a chain will have an even total number of turns.
The chain rule now follows from the following result, due to Berlekamp.
Theorem: No matter what the shape of the initial Dots board, one always has the formula
where DOTS is the total number of dots, DOUBLECROSSES is the total number of doublecrosses, and TURNS is the total number of turns.
This theorem immediately implies the chain rule, so I will do this part before turning to the proof of the theorem itself.
First, let's assume that the total number of dots is odd. The formula of the Theorem shows that
This is due to the simple results
Since the parity of TURNS determines the chain rule, it remains to understand DOUBLECROSSES, the total number of doublecrosses.
In the final phase of a normal game, the player in control always leaves one doublecross for each chain, except the last, and two doublecrosses for each cycle. Since there have been no doublecrosses before the final phase (by definition), one gets the formula
where CHAINS is the total number of chains and CYCLES is the total number of cycles. One therefore gets
Combining this with the previous formula, one concludes
The reader will note that, due to the opening remarks, this is exactly the first part of the chain rule. The second part of the chain rule is proved in exactly the same way. This completes the proof of the chain rule, assuming that the Theorem is true.
If there are no doublecrosses, placing an edge has either just created a single box or has given the turn to the other player (but not both). This gives
where the -1 is needed because the first turn was not included in this count: It is not preceded by placing an edge. But, there is a known formula from graph theory that states that
is always true for any shape of Dots board. I will discuss this important and deep result in the next section. Combining these two equations gives the result
that is, the number of turns equals the number of total dots, when there are no doublecrosses, and the Theorem is true in this case.
For the general case, let C be the total number of doublecrosses. Now, consider the same counting argument as above, but without taking into the count any edge which fills in a doublecross. There are C such edges, and note that such edge captures two boxes but does not change the turn. Therefore, one gets
which simplifies to
Elementary algebra gives
which is the required result.
where E is the total number of edges, B is the total number of boxes, and D is the total number of dots, which I said was true for any dots board.
In fact, this is a special case of a general formula in graph theory due to the famous mathematician Leonhard Euler (1707-1783). This formula states that for any planar graph (one that you can draw without edges crossing each other) one has
where V is the total number of vertices, E is the total number of edges, and F is the total number of faces. I won't prove this here because there are many proofs available online. I should just say that the formula is usually written with a "2" on the right, because it is really about graphs on a sphere, so that the outside of the graph counts as an extra face.
To understand what I just wrote, you should think of Euler's formula three dimensionally. For example, consider the cube. It has 8 vertices (V = 8), 12 edges (E = 12), and 6 faces (F = 6), and so V-E+ F = 8 - 12 + 6 = 2. You can check that the same holds true for a pyramid with square base (like the great pyramid of egypt), where the base is counted as a face, or any other polyhedron.
The formula for polyhedra was first noted by mathematician and philosopher Rene Descartes, but Euler was the first to state it explicitly for all graphs.
This formula is a first step in algebraic topology, the area of mathematics which tries to find numerical characteristics of geometrical objects which don't change if you deform the object smoothly. It is the simplest example of the Euler-Poincare characteristic.
DIAGRAM
The chain rule will still be valid, except that it will have to be modifed because Euler's formula says that
In fact, there is no longer any boundary to the dots board, so making chains is much harder since they have to be rooted to cycles. So, the chain rule for toroidal Dots should probably be called the cycle rule since the game will be dominated by cycles.