Dots & Boxes

Dots & Boxes

"Dots and Boxes" is an impartial, combinatorial game.  It involves a piece of paper, a pencil and two players.  I have fond memories of playing "Dots and Boxes" with my younger brother on the Friendly's placemat while we waited for our food.  Back then, my brother and I did not play with much of a strategy in mind.  However, after researching more into championship-level play of "Dots and Boxes" I have found strategies that will make us all "Dots and Boxes" champions.

The Basics: How to Play

For those who are not familiar with how to play "Dots and Boxes", here's the rundown:

1. Players begin with a grid of dots.
2. Players take turns drawing either vertical or horizontal lines between two adjacent dots.
3. If a player completes a 1x1 box, then that player writes his or her initials in the box and then must draw another line.
4. A player who CAN complete a box is not obliged to by the rules of the game.
5. The player who completes the most boxes, once all lines have been drawn, is the winner.

Here an example of what a game could look like:

Source: Winning Ways For Your Mathematical Plays, Vol. 3

In this example we can see that Player B has won (6 boxes to 3).

Another thing to note is that "Dots and Boxes" is unlike the other impartial, combinatorial games we have studied.  For one: "Dots and Boxes" is not played under normal play rules.  Instead of players fighting over the final move, the game is won by the player with the highest score after the last move.

You can play the game by following this link 

Please feel free to comment any strategies you found while playing against the computer.  It will be interesting to see if these strategies coincide with the strategy I will discuss below.

The Basics: Vocabulary

Before we go further into "Dots and Boxes" strategy there some terms that we should know.

A double-crossed move is a move in which two boxes are completed with a single stroke of the pen. 

Source: Winning Ways For Your Mathematical Plays, Vol. 3

A double-dealing move is a move that is followed, usually immediately, by a double-crossed move.

A long chain is a chain that contains three or more potential boxes.

Source: Winning Ways For Your Mathematical Plays, Vol. 3

Whichever player can force their opponent to open a long chain has control of the game.

A hard-hearted handout is when a player draws the middle edge in between a chain of two squares and leaves their opponent with no way of finishing their turn in the same chain.

Source: Winning Ways For Your Mathematical Plays, Vol. 3

Please let me know in the comments if you have any questions on the rules or the vocabulary, and I will be sure to go over them in more depth during my presentation.

General Strategy

The way to win at "Dots and Boxes" ultimately comes down to gaining control.  This means that you should:

1. Make sure that there are long chains and try to force your opponent to be the first to open one.
2. When you have control, you should make sure you keep it by declining the last 2 boxes of every long chain except the last.

By declining the last 2 boxes of every long chain, you force your opponent to take those two boxes with a double-crossed move and then open up a new long chain.  Hence, you must sacrifice some boxes in order to keep control.  If you get too greedy, however, and take those two boxes for yourself, you are then forced to open up the next chain and your opponent can reap the benefits of your mistake.

A more specific strategy can be crafted when we look at odd numbered moves versus even numbered moves.

The Long Chain Rule

Consider two players: Todd and Steven.  When Todd and Steven play "Dots and Boxes", Todd always goes first and thus Todd plays on all of the odd moves and Steven plays the even moves.

The rule that helps Todd and Steven take control is: 

Todd tries to make the number of initial dots + the number of double-crossed moves odd.

Steven tries to make this number even.

Since the number of double-crosses will be one less than the number of long chains this rule becomes the long chain rule.

In general, the long chain rule is:

Try to make the number of initial dots + 

eventual long chains = 

even (if your opponent went 2nd) or

odd (if your opponent went 1st)

Let's look at an example of the long chain rule works. We can use the same visual from our definition of long chains from above:

When we use a visual, the long chain rule becomes rather intuitive.  In this example we have 4 long chains and 36 dots.  Since 36+4=40 we presume the player to play first will win.

If Player 1 opens up the 3 box chain, then his or her opponent will take 3 boxes and open up the 5 box chain.  The odd player will be rewarded with 5 boxes and will open up the 8 box chain.  Player 2 will get 8 boxes, but then be forced to grant Player 1 the final 9 boxes.  This will make the score 14-11 with Player 1 taking the win.

The reason this rule works is because the number of dots at the start + the number of double-crosses = the total number of turns in the game.  This way, if that number is odd, Todd gets the last move.  If it is even, Steven gets the last move.

Formal Proof: The Long Chain Rule

• Suppose a game board for "Dots and Boxes" has m rows with n dots each.
• Then, the number of total dots is mn.
• We know, the number of horizontal moves a player can make is m(n-1) = mn-m.
• And, the number of vertical moves, similarly, is n(m-1) = mn-n.
• Thus, the total number of moves is (mn-n)+(mn-m) = 2mn-m-n.
• The number of boxes = (m-1)(n-1) = mn-m-n+1
• So, (the number of moves) - (the number of boxes) = mn-1
• The number of completed turns = (the number of moves) - (the number of boxes) + (the number of double-crosses) -- since the a double-cross move = two boxes
• Thus, the number of completed turns = (mn-1) + (the number of double crosses) = (the number of dots - 1) + (number of double-crosses)
• Since the last move must complete a box, the final turn is incomplete and we must add this to the total.
• Therefore, the number of turns = (the number of dots) + (the number of double-crosses)

I plan on discussing the Long Chain Rule in greater detail during my presentation so please comment any questions you may have on the proof or general usage of the rule.

Conclusion

"Dots and Boxes" is an interesting game to analyze because it is so different from the other combinatorial games we have studied.  Since the last player to move does not necessarily win, we can not apply Sprague-Grundy theory to find concrete N and P-positions.  However, there is a game called "Nimstrings" that can apply SG theory to "Dots and Boxes" to a certain extent.  Nimstrings is basically just "Dots and Boxes" with the normal play win condition of last to move wins.  I find it fascinating that even though "Dots and Boxes" is not a typical combinatorial game, we can apply combinatorial game theory to it.  It will interesting to see how far SG theory can go in applying to games that have less ties to Nim.

Bibliography

• Berlekamp, Elwyn R., John Horton. Conway, and Richard K. Guy. Winning ways, for your mathematical plays.   Blackwell Science, 1982. Print.
• Nowakowski, Richard J. Games of no chance. Cambridge: Cambridge U Press, 1996. Print.
• "Dots and Boxes." Wolfram MathWorld. Web. 12 Feb. 2017.