Can we use math to win this 'Dots and Boxes' variant?
‘Dots and Boxes’ is a common game played by children globally. Many variants of this game exist, so I will clarify the ruleset we are using here.
I understand that others have done a lot of work on other variants of the game, namely Elwyn Berlekamp, but this variant includes a speciric ‘chain reaction' rule which changes endgame strategies.
I grew up in rural Ireland, where we used to play this exact variant between classes and out in the playground.
The mechanics of the game are quite simple: players take turns adding edges to a grid of dots (arranged in a rectangular manner). Every time a player makes a “box” (4 lines connected in a square), they score a point. When a player makes a box, they draw on the next edge.
In this variant, completing a box triggers a mandatory chain reaction. If your move leaves any adjacent boxes with three sides filled, you must immediately complete them. This "forced capture" continues automatically until no further boxes can be closed, at which point you must draw an edge elsewhere and your turn is over.
While in most other variants, the player can choose to stop after having claimed the first box, in the Irish variant of game claiming the first box forces the player to claim the other 3 boxes (or however many there are).
To start, I will clarify some of the terminology I will be using:
Final State: the final state of the game is the position where the next player to move will be forced to concede at least one box, before any boxes have been claimed
This game is in final state, as the next edge drawn will enable the next player to make 2 boxes
Edge: an edge is any horizontal or vertical line connecting two vertices (dots)
Closed Room: a closed room is an area not connected to another room, which can be claimed in one move
This game consists of two closed rooms, as each will be claimed in one turn
If at any point you don't fully understand something I say, or just want to see it work out yourself, I recommend you use this game board tool (the one I used for all the diagrams here! Or, alternatively, you can use the old-fashioned pen and paper!
When I started trying to analyse this game, I started drawing out many games in their final state. My first instinct was to create tables with edges and lines for the n=3 game (meaning the board is a square with length of 3 dots, 9 in total). Here was the data I found:
The maximum amount of edges I could draw on a n = 3 grid was 8, and the minimum was 4. What I noticed, was that usually the sum of edges and rooms was equal to 8 (E + R = 8).
8 edges and 1 room, and 4 edges and 4 rooms configurations
I decided to draw out a similar table with n=4 to see if the pattern continued:
From this table, I saw a similar patter emerge. With 1 room, the amount of edges was one more than predicted. I will discuss the 5 rooms case in more detail soon.
I tried to generalise what I had found, and I noticed that my results mostly followed this pattern:
Rooms + Edges = n² - 1
R + E = n² - 1
However, this model failed to explain two things:
What was happening in the 5 room case in n=4 ?
And what was happening with only 1 room?
Here is a diagram of the 5 room case:
This final state seems to have 5 rooms, and 8 edges (5+8=13). However, since n=4, 4²-1 = 15, so either something is wrong with our formula, or this diagram contains something we don't understand yet.
To understand where the difference here is coming from, let me introduce you to a new concept:
Open Room: an open room is an area, similar to a closed room, which cannot be claimed in one turn
This diagram contains one open room, but it would take 3 separate turns to claim this area
I soon realised that this was the case with our 5 room problem. Yes, the game had 5 rooms, but one of them was an open room, meaning it would take 7 turns to claim the entire area.
This diagram shows how to seperate the fifth ‘open' room into three ‘closed’ rooms. It is important to note these dotted edges do not count towards our edge count
So now that we had clarified the number of rooms in the 5-room (now 7-room) case, does our equation balance?
R + E = n² - 1
7 + 8 = 4² - 1
15 = 15
Yes! Our equation now balances for the ‘5-room' case, but what about the other problem we had? Where the 1-room cases were always one greater on the ‘R + E' side of the equation? Let me show you both cases again:
1 room + 8 edges = 9
3² - 1 = 8
1 room + 15 edges = 16
4² - 1 = 15
At this stage, I was starting to think my formula was wrong. I spent countless hours staring at different configurations of 1 room designs, and always found the same problem. 1 room problems always were 1 greater on the ‘R + E’ side of the equation.
Eventually, I realised it had to do with forming loops on the graph. If you look at the two examples closely, you can see that each one contains a ‘loop.’
Loop: a series of edges which connect back onto themselves
To force the equations to balance, I updated my model to it's final version:
R + E - L = n² - 1
This formula only applies to games that are in ‘final state'
Here's an example of the formula in use:
We can count 22 edges, 4 rooms, and 2 loops in this diagram, and n = 5
R + E - L = n² - 1
4 + 22 - 2 = 5² - 1
24 = 24
While our experimental results are promising, they do not proove the formula for all cases. To do this, we can use ‘Euler's Polyhedral Formula for a disconnected graph.’
Euler's formula states:
V - E + F = 1 + C
Vertices - Edges + Faces = 1 + Components
Faces: any window of space enclosed by edges (including the area outisde the graph)
Components: the amount of separate parts the graph is divide into (including stand-alone nodes (dots))
An example with Euler's formula:
We can count 16 vertices, 14 edges, 2 faces, and 3 components
V - E + F = 1 + C
16 - 14 + 2 = 1 + 3
4 = 4
We can see that the ‘n²’ term in my formula is the same as Euler's ‘V,’ since squaring the length of a square gives the area. Therefore, my formula can be written as:
R + E - L = V - 1
R - L = V - E - 1
Rearranging Euler's formula:
V - E + F = 1 + C
V - E - 1 = C - F
Both our equations contain ‘V - E - 1' on one side, so we can merge out formulae to say:
R - L = C - F
To show this, I will split the equation into two parts:
R = C - 1
The final state is a special case where the graph is fully split into rooms. To create a single room, two contributions must be used (if there were only 1 contribution, the graph would not be in final state as it could be claimed in the very next turn. If there were 3 contributions, the graph would be an open room).
So, what makes it impossible to draw a room with 1 contribution? Well, there are two types of rooms with 1 contribution that could be possible: with a full ‘wall' of edges around, and with a single gap somewhere in the wall. Now, the problem here is, for an area to be big enough to contain a room with one contribution, it will have to be at least n=3, meaning there is a free node (dot) in the middle*. Which is a problem, because that free node counts as a second contribution.
* This is because each side of the room must be 2 wide, otherwise the opposite walls would be too close, and the graph would no longer be in final state.
So it can't be the version with a full wall around, but what about the version with a gap in the wall around and an edge connecting the node in the middle to the wall?
This is the graph described above, the dotted line shows that this is not possible, since the graph would not be in final state
You might now think of extending the size of the graph to add more area in the middle to avoid this problem. The problem is, whenever you add an edge to the middle, you are connecting two parallel walls 1 edge apart. This forces there to be at least one box with 3 of the edges surrounding it drawn in, meaning the graph is not in final state.
Here is an example of a graph with 2 rooms and 3 contributions. The dotted line shows that this room with 3 contributions is not possible, and it must be split into two closed rooms.
So now we know that for any graph with 1 room, there are 2 contributions (in final state). Adding any next room adds one more contribution, because the other contribution of that room is a shared contribution with a previous room. Think of it as walls to a house: to build your first room, you need 4 walls, but any next rooms can be build by adding 3 walls to an existing wall.
The shared contribution between these two rooms is dotted.
So, great! We have shown that there is always one more contribution than a room, and hence R = C - 1.
L = F - 1
A loop was earlier defined as ‘a series of edges which connect back onto themselves.’ This means, any loop must close back in on itself, creating an extra face on the graph. Since the outside of the graph is also considered a face in Euler's formula but not considered a loop in ours, there is always one more face than loop. Hence, L = F - 1
Returning to the original formula I am trying to proove:
R + E - L = n² - 1
Substitute R = C - 1, and L = F - 1
C - 1 + E - (F - 1) = n² - 1
C - 1 + E - F + 1 = n² - 1
C + E - F = n² - 1
Since we showed earlier that n² = V
C + E - F = V - 1
C + 1 = V - E + F
Since this derived Euler's formula from earlier from our own, we have shown that our formula should hold true for all cases in final state.
So now we have a formula which shows us explains the mechanics of the final state. But how can we use this information to predict which player will go on to win? To understand this, we need to familiarise ourselves with how the endgame works. Here's an example, where player A took the first turn of the game, and player B the second:
This game board is in final state. Since there are an odd number of edges already placed, player B must place the next edge.
Player B is now forced to concede either the 6 boxes on the left or the 3 boxes on the right. Player B should choose to concedes the three on the right.
Player B draws in an edge, and then Player A claims three boxes
Now Player A must go again (after claiming a box, it is your turn again), and is forced to concede the remaining 6 boxes. What we can notice here, is that the player who concedes the first room should always win when there are an even number of rooms. However, when there are an odd number of rooms, the player who concedes the first room will lose, because rooms should be conceded in order of least valuable first, and the player who gets the first room will always claim a room with either equal or greater value than each room their oppoents claims.
This can be summarised as follows:
Even Rooms →Player who claims first lose
Odd Rooms →Player who claims first wins
What we must now figure out, is which player claims first with each set up (assuming a final state is achieved).
We know that the player who places an edge directly after the final state is the first player to concede, meaning the player who doesn't place an edge after final state is the first to claim. When there are an odd number of edges, first to claim is player A. When there are an even number of edges, Player B claims first.
First of all, we will assume a case with no loops. Meaning, we can return to our simplified formula:
R + E = n² + 1
Whenever n is odd, n² + 1 must be even (n² must be odd since odd × odd = odd, and odd + odd = even). Alternatively, whenever n is even, n² + 1 must be odd.
When n² + 1 is even, rooms and edges must both be either odd or even. If we break this down:
Both odd:
Odd number of edges means A claims first. Odd number of rooms means first to claim wins, so player A wins.
Both even:
Even number of edges means B claims first. Even number of rooms means second to claim wins, so A wins again.
This means, for any odd n, player A should win.
Using the same logic, we can easily show that when n is even, player B should always win.
But, we're missing something massive here. We were using a simplified version of the formula, assuming there were no loops.
What is important to realise, is that adding a loop doesn't actually change the parity of the equation. What it does do, is replace one edge (or room, both yield the same result) with a loop. We know that when an edge (or room) is removed, this completely changes the state of the game because the other player now gets to claim first. In short, every loop flips the advantage to the other player.
I would like to add that while I used ‘n' throughout this article, this can be replaced with ‘nm' (dots vertically × dots horizontally) and you will find the same results.
To summarise my findings, in any game with odd values for n, player A has the advantage. In games with even values for n, player B has the advantage. However, every loop created flips the advantage to the other player.
So, now we know how to win any game which reaches a final state, but in real game scenarios, sometimes a player makes a mistake early on and the game never reaches a final state! In that case, how can we tell which player is going to win?
To analyse this, I am going to introduce a new term:
Safe: an edge which can be drawn without leaving the opponent a chance to form a box
This diagram shows solid lines for edges (already placed), and dotted lines for safes (not already placed)
What we must do is analyse what happens when a mistake is made: to do this, let me show an example:
This game is one move away from final state (there is one safe left in the bottom left corner). We can count 11 edges have been placed
This graph is for n=4, so player B should have the advantage, since there are no loops. 11 edges have been placed, so player B is next to place:
Player B made a mistake! Player A can now claim the single box, and draw in the safe
Player A takes the box, and it is now player B's turn.
Note that in this position player B will still win. Player B should concede the top 3 boxes, and force player A to concede the row of 5 through the middle.
What actually happened when player B made that mistake? Well, when player A claimed the room, there was one less room up for offer in the endgame (1 less room flips the parity of the rooms, flipping the advantage). In that case, should the advantage not have flipped!?
Well, not quite. Because of the specific rule that forces a player to play again after having scored a box, players effectively swap positions after that box was claimed (this does happen in the endgame, we just think of it differently by advantages for odd and evem rooms).
Since a mistake flips the advantage two times in total (once for rooms, once for turns), a mistake does not have any net effect on the advantage.
This means, the player with the advantage will still win the rest of the board.
Here's a fully worked example for a game in an n=4 grid:
n = 4 means player B has the advantage initially.
Player A takes the first turn
After 10 edges have been placed, player A has managed to create a loop. Player A now has the advantage
It is now player A's turn next. The dotted line represents the only remaining safe.
I am now going to split into two different possibilities; the first where player A plays optimally, and the second where player A makes a mistake.
Player A plays optimally:
Player A takes the last remaining safe. Player B must now concede the lowest value room
Player B concedes the top right corner, and Player A draws in a line to concede the long chain down the left. 1-0 to player A
Player B claims 4 boxes and concedes the bottom right corner. 1-4 to player B
Player A claims the 4 boxes. 5-4 to player A
As predicted, player A wins the game after having flipped the advantage by forming a loop!
Player A makes a mistake
Here is the state of the game where we resume. It is player A's turn, and the dotted line respresents the remaining safe which player A should draw in
Player A made a mistake, and conceded the top right corner
Player B claims the top right corner, and plays the remaining safe. Player A is now forced to concede a room. 0-1 to player B
Player A concedes the row on the left
Player B claims the row on the left, and concedes the bottom right corner. 0-5 to player B
Player A claims the remaining boxes. 4-5 to player B
So wait, if player A had the advantage, how did player B win? Well, this is a special case, since both rooms remaining were both of value 4. This means, after player A made the mistake, player A drew the remainder of the board with player B.
So the game ended in a draw, except for the one box that player A conceded earlier on that player B won.
Note that this is a very particular case, and normally the player who makes a mistake will still win (particularly on bigger boards).
I'd like to thank you for reading, and hope you enjoyed uncovering the secrets of a childhood game of mine with me!
Feel free to contribute to the conversation by leaving a comment below! Maybe somebody wants to look at non-rectangular boards or some other variants of the game. Either way, thanks for reading, and have a great day!