Case Analysis
In the game of Dots and Boxes you are trying to achieve as many 1 × 1 squares
in the graph whose vertices are lattice points and the edges join any two
consecutive horizontal or vertical vertices. Note that the 1 × 1 squares in this
graph are actually the circuits of length 4. In other words, players take turns at
choosing one edge from the graph determined by the grid and the goal of the
game is to have as many cycles of length 4 as possible. Strategies for this game
have been studied. Can you explain some of these strategies in terms of graph
theory concepts/theorems?
Ans:
In the game of Dots and Boxes, the winner is generally the player who makes the last move.
The reason for this is that at the end of the game, there are usually a few long corridors or
chains of boxes left to be taken. If your opponent is forced to play in one of these chains, then
you can take all but two of the boxes and, by sacrificing the last two boxes, make certain that
it is his turn to play into the next long chain. You will thus win all but two boxes in each long
chain, and of course you will win all boxes in the last chain. We say a chain is long if it
contains at least three boxes.
The above program for playing Dots and Boxes uses an algorithm that is not very good, but it
will play well once there are only long chains left. You may use it to improve your play at the
next level of understanding. This next level requires determining which player will move last.
This is most usefully done using the following rule.
The Long Chain Rule: Suppose the playing field is a rectangle of m rows and n columns and
so has mn boxes. If both m and n are even, then the first player should play to make the
number of long chains odd. If either m or n is odd, then the first player should play to make
the number of long chains even.
Of course then the second player wants an even number of long chains if both m and n are
even, and an odd number of long chains otherwise.
It must be pointed out that in this rule, loops do not count as long chains.
Here is the reason this rule works. There are (m+1)n horizontal edge moves and m(n+1)
vertical edge moves for a total of 2mn+m+n moves. Without the rule that the player who
completes a box moves again, we could say that the player who moves first also moves last if
and only if 2mn+m+n is odd.
With the rule that the player who completes a box moves again, we must subtract one for
each time at least one box is filled, except for the last box. Some moves complete two boxes
simultaneously. Let us call these moves double-box moves. If there are no double-box moves,
then since there are mn boxes and since completing the last box doesn't change things, we
must subtract mn-1 from the total number of moves to get the number of move changes. This
gives 2mn+m+n-(mn-1)=mn+m+n+1=(m+1)(n+1). Thus if there are no double-box moves,
In the game of Dots and Boxes you are trying to achieve as many 1 × 1 squares
in the graph whose vertices are lattice points and the edges join any two
consecutive horizontal or vertical vertices. Note that the 1 × 1 squares in this
graph are actually the circuits of length 4. In other words, players take turns at
choosing one edge from the graph determined by the grid and the goal of the
game is to have as many cycles of length 4 as possible. Strategies for this game
have been studied. Can you explain some of these strategies in terms of graph
theory concepts/theorems?
Ans:
In the game of Dots and Boxes, the winner is generally the player who makes the last move.
The reason for this is that at the end of the game, there are usually a few long corridors or
chains of boxes left to be taken. If your opponent is forced to play in one of these chains, then
you can take all but two of the boxes and, by sacrificing the last two boxes, make certain that
it is his turn to play into the next long chain. You will thus win all but two boxes in each long
chain, and of course you will win all boxes in the last chain. We say a chain is long if it
contains at least three boxes.
The above program for playing Dots and Boxes uses an algorithm that is not very good, but it
will play well once there are only long chains left. You may use it to improve your play at the
next level of understanding. This next level requires determining which player will move last.
This is most usefully done using the following rule.
The Long Chain Rule: Suppose the playing field is a rectangle of m rows and n columns and
so has mn boxes. If both m and n are even, then the first player should play to make the
number of long chains odd. If either m or n is odd, then the first player should play to make
the number of long chains even.
Of course then the second player wants an even number of long chains if both m and n are
even, and an odd number of long chains otherwise.
It must be pointed out that in this rule, loops do not count as long chains.
Here is the reason this rule works. There are (m+1)n horizontal edge moves and m(n+1)
vertical edge moves for a total of 2mn+m+n moves. Without the rule that the player who
completes a box moves again, we could say that the player who moves first also moves last if
and only if 2mn+m+n is odd.
With the rule that the player who completes a box moves again, we must subtract one for
each time at least one box is filled, except for the last box. Some moves complete two boxes
simultaneously. Let us call these moves double-box moves. If there are no double-box moves,
then since there are mn boxes and since completing the last box doesn't change things, we
must subtract mn-1 from the total number of moves to get the number of move changes. This
gives 2mn+m+n-(mn-1)=mn+m+n+1=(m+1)(n+1). Thus if there are no double-box moves,
