When I was in high school, one of my favorite ways to waste time in class (not recommended) was to play a game called dots and boxes (although at the time we just called it dots). I was very surprised to find later that this game belongs to a class of games called “Impartial Combinatorial Games”. These are games where the moves available to the player depend only on the position of the game, and not the player.

In a game of Dots and Boxes, we start with an initial grid with dots at each row and column intersection. At each player’s turn, they have the option of drawing either a horizontal or vertical line between two neighboring dots (depending on if the dots are in the same row or column). If a player fills in the last line on a box (the 4th side), we say that player “owns” the box. The game ends when there are no neighboring dots without a line between them. At the conclusion of the game, the player who owns the most dots is declared the winner.

The game is impartial because there is no restriction on which move a player can make other than the fact that a player cannot re-do a move that has already been made (a partial version of this game would be if player one could only move horizontally and player two could only move vertically).

I have implemented a javascript version of this game. Check it out and let me know what you think.

I also spoke earlier about the discovery that this game in particular was an active area of research. I wanted to provide a link to a paper entitled “Solving Dots and Boxes” by Joseph K. Barker and Richard E Korf that speaks about winning strategies for each player in a game of dots and boxes.

- Nim Games (0.643)
- Hidden Markov Models: The Baum-Welch Algorithm (0.507)
- Polynomial Arithmetic (0.507)
- The Euclidean Algorithm (0.178)
- Gaussian Elimination (0.178)

I used to love the dots and line game. Once you get in the dominant position you take a long row of boxes and leave just two for the other person and then get the next long line of boxes. Fun stuff.

As fun as this game is, it was very exciting to see that there were journal papers analyzing this game. Its still a research question of what the best strategy is when playing this game. You mention one, but there’s also the possibility of not taking all the boxes in a chain, instead breaking it at an unfavorable position for your opponent. But this gets into another question of exactly what an “unfavorable position” is.

But I hope you enjoy the game.

“The game is impartial because there is no restriction on which move a player can make other than the fact that a player cannot re-do a move that has already been made (an impartial version of this game would be if player one could only move horizontally and player two could only move vertically).”

??? Do you mean a partial version would have the restricted moves?

Having fond flashbacks myself…

Thanks for noting that. Yes, I did mean a partial version of this game. I’ll make the correction.