The Mathematical Theory of Dots


Chapter 2 of my Dots page

by

Ilan Vardi

(ilanpi on Yahoo Dots)



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.




The Chain Rule

Proof of the chain rule

The chain rule gives exact conditions for which player will be the first to play into a chain or cycle , in a normal game.

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

DOTS + DOUBLECROSSES = TURNS,

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

TURNS is odd if and only if DOUBLECROSSES is even.

This is due to the simple results

ODD + EVEN = ODD and ODD + ODD = EVEN.

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

DOUBLECROSSES = CHAINS -1 + 2 * CYCLES,

where CHAINS is the total number of chains and CYCLES is the total number of cycles. One therefore gets

DOUBLECROSSES is even if and only if CHAINS is odd.

Combining this with the previous formula, one concludes

If DOTS is odd, then TURNS is odd if and only if CHAINS is odd.

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.

Proof of the Theorem

This follows the proof given in Winning Ways, Volume 2, page 537. In a Dots and Boxes game, let D be the total number of dots, T the total number of turns, E the total number of edges, and B the total number of boxes.

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

E = B + T - 1,

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

E = B + D - 1

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

T = D,

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

E - C = B - 2 C + T - 1,

which simplifies to

E = B - C + T - 1.

Elementary algebra gives

D + C = T,

which is the required result.

Euler's formula

In the proof the chain rule, I used the formula

E = B + D - 1,

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

V - E + F = 1

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.

Toroidal Dots and Other Games

Nothing prevents you from playing Dots and Boxes on other types of surfaces. For example, you can play on a torus by simply identifying the opposing sides of an ordinary Dots and Boxes board

DIAGRAM

The chain rule will still be valid, except that it will have to be modifed because Euler's formula says that

V-E+F = G + 2
where G is the genus of the surface, that is, the number of holes it has. For the sphere, the genus is zero, but for the torus, the genus is one. One therefore has the formula

D - E + B = 3
for toroidal dots, where the number 3 comes from G = 1 and the fact that there is no longer and "outside" box.

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.




Combinatorial Game Theory




Other Games

1