Caribou in Covid: Contests are running online as usual. Check out the FAQ for further questions.
300000
English | Français | فارسی | 中文 | Українська | Azerbaijani | ខ្មែរ | Tiếng Việt | Bahasa Melayu736
If you are just interested in which moves to play and not why then advance to the
'Decision Tree' at the bottom.
The 'Index' underneath lists all terms that are introduced in the text and can be used as a
quick introduction.
The Basics
Because we will use some game terms very often we will introduce a few new words.
A box is a small square with 4 neighbouring dots as corners. A box can have 0, 1, .., 4 of its sides drawn and is then called a 0-box, 1-box, ..., 4-box.
A line is the line segment linking two neighbouring dots.
Drawing a line is also called making a move.
If an un-drawn line separates a 2-box and a 3-box then drawing this line does 3 things: it completes the 3-box and thus scores a point, it changes the 2-box to a 3-box, and it gives the player another move which can be used to complete the new 3-box. This situation happens so often that we define new terms.
All connected 2-boxes make up a chain. A chain can have 2 ends and is then called a linear chain whether it is straight or not, like
+ + +---+---+ + +---+
| | , or | |
+ + +---+---+ +---+ +
|
+---+---+
showing chains with 1, 2 and 4 boxes.
A chain can also have no ends and then we call it a loopy chain or simply loop whether it looks like a circle or not, like this one
+---+---+---+
| |
+ +---+ +
| | |
+---+ + +
| |
+---+---+
Making a move inside a chain or on one of its ends is called in the literature opening a chain.
What happens if a chain is opened?
If one player draws one of the un-drawn lines in a chain like move A1 in
+---+---+---+
| |
+ +A1-+ +
| |
+---+---+
then at least one 2-box becomes a 3-box (here the box above and the box below the A1 move) and the other player may complete the(se) box(es) afterwards to a 4-box, earn one or two points and at the same time convert the neighbouring 2-box to a 3-box (here the box left of B1 and right of B2 in
+---+---+---+
| B1 |
+ +A1-+ + .
| B2 |
+---+---+
Each time a box is completed the player must make another move which can be used to complete the next box and all other boxes of the chain. After completing the last box the player must make another move elsewhere unless all boxes of the board are completed.
Initial Play
This is a simple and useful rule although it is not perfect as we will see at the end of this site. At some stage, once about half of all lines are drawn, it is unavoidable to create a 3-box. What happens then? Because chains with 1, 2 or ≥ 3 boxes are treated differently we have to look at them individually.
Let us start by looking at chains having only one box.
Should one always complete a single 3-box, i.e. a chain with one box
+---+ | ? +---+
How can chains with two boxes look like and how should one play in them?
Chains with two boxes look like
+---+---+ +---+---+ +---+---+
or | or | |
+---+---+ +---+ + + + +
or rotated and mirrored versions of them. Drawing the middle line in there leads to
+---+---+ +---+---+ +---+---+
| or | | or | | |
+---+---+ +---+ + + + +
and is called in the literature Hard-Hearted Handout.
Should one always take both boxes in such a position?
Yes, one should take both boxes for the same reasons as one should take always one-box chains. Please convince yourself.
Drawing a line on the border of a chain with two boxes leads to
+---+---+ +---+---+ | or | | +---+---+ +---+ +
and is called Half-Hearted Handout.
A move on the border of a Half-Hearted Handout leads to
+---+---+ | | . +---+---+
Such a move is called in the literature Double Dealing (DD).
A DD move is a sacrifice of two boxes because the player could alternatively first play in the middle and then on the border and earn in this way two boxes. Why would one want to sacrifice 2 boxes? Keep reading.
A move like the Half-Hearted Handout move before DD, which gave the opponent the option to make a sacrifice is called in the literature a loony move. Other examples of loony moves are moves that open chains with 3 or more boxes because the next player then also gets the option to play a DD as we will see below.
Should the next player after DD always take both boxes?
Back to half-hearted handouts, should one always take both boxes
in such a position? If not, when should one play DD on the border?
Try both out in games and see which difference it makes.
Let us consider all differences.
If one takes one box then one should take the second box as well as we found earlier.
If one takes both boxes one gets 2 points but afterwards one has to make a move somewhere else which may be costly because one might have to open a chain with many boxes if no other moves are available.
If one plays on the border one does not complete a square and therefore one does not have to play somewhere else. But playing on the border gives the next player both boxes as just discussed.
Therefore, both plays are possible. We will get back to this question later to determine which move is better in a given situation.
If one has to open a chain with 2 boxes because all other moves
would be even more expensive, should one play a hard-hearted or a
half-hearted handout?
If one plays a in the middle of the chain (a hard-hearted handout) then the other side is forced to take both boxes and afterwards make a possibly expensive move somewhere else.
+---+---+ +---+---+ +---+---+
→ | → | | | plus somewhere else
+---+---+ +---+---+ +---+---+
If one plays on the border of the chain (a half-hearted handout) then one gives the opponent an option of either taking the two boxes like above or playing on the border (a Double Dealing (DD) move):
+---+---+ +---+---+ +---+---+
→ | → | |
+---+---+ +---+---+ +---+---+
This option may be very valuable as we will find out later. Giving the opponent extra options can never be a better move, so aiming at optimal play one should never play a half-hearted handout. In non-optimal fun play one could try half-hearted moves to find out the skill of the opponent. or to confuse the opponent if one is behind but not if one tries to play optimally.
What should one do with opened linear chains of three or more boxes?
If a chain is opened then it has at least one 3-box. One could complete this box and the other boxes as well, but should one?
Are there boxes one should definitely take from a linear opened chain?
On one hand we want to take as many boxes as possible and on the other hand we might not want to pay the price of playing afterwards elsewhere and opening an even bigger chain for the opponent to grab. What we should definitely do is to take all but two boxes as justified before, they are free, there is no negative side effect. After that we can think about taking the remaining 2 boxes as well or playing DD (Double Dealing), more about that later.
Chains with ≥ 3 boxes are call long chains. These include both, linear and loopy chains.
Why is there an extra name for such chains?
If only chains with at least 3 boxes are left then opening one of them then no matter where the move is made, on at least one side of the move there are at least 2 neighbouring boxes, so the other player could play a double dealing which is crucial for the remainder of the game.
How many boxes are needed to make a loop?
The smallest possible loop has 4 boxes:
+---+---+ | | + + + | | +---+---+
If a loop is opened, can one take again all but 2 boxes safely without thinking?
Let us try that out. The smallest possible opened loop is
+---+---+ | | +---+ + | | +---+---+
We surely could take all 4 boxes and then play elsewhere but what if we wanted to avoid playing elsewhere by all cost? If we would take two boxes we reach
+---+---+ | | | +---+---+ | | +---+---+
but we would need to make another move. So we could not stop here because all lines on the border are already drawn so we have to continue to get to
+---+---+ | | | +---+---+ | | | +---+---+
and then move elsewhere and thus possibly have to hand over to the opponent an even a bigger chain.
What else could we do instead?
We want to play a move which does not complete a box in order to not have to play elsewhere. The only possible move is to play in the middle of the opened loop to create
+---+---+ | | +---+---+ . | | +---+---+
This move does not complete a box and thus the other player plays next. We will call this move Double Double Dealing and abbreviate it through DDD. The price is to sacrifice 4 instead of 2 boxes. For the opponent it is best to take the 4 boxes and play afterwards elsewhere.
What if an opened loop has more than 4 boxes?
We can take as many boxes as we like as long as we still have a move left that does not complete a square. This means we can take all but 4 boxes, for example, opening
+---+---+---+---+ +---+---+---+---+ | | | | | + +---+---+ + gives, for example, + +---+---+ + | | | | +---+---+---+---+ +---+---+---+---+
and taking 8 − 4 = 4 boxes yields, for example,
+---+---+---+---+ | | | | | + +---+---+---+ . | | | +---+---+---+---+
Now we would have to decide whether to take the remaining 4 boxes or to sacrifice them to the opponent by playing
+---+---+---+---+ | | | | | + +---+---+---+ . | | | | +---+---+---+---+
More about that later.
In the case of one open chain or the unlikely event of several chains being open, how many
boxes can one safely take without thinking about playing DD
or not playing DD?
So if there is at least one open linear chain that has two neighbouring boxes then complete all other boxes of this chain and complete all boxes of all other open linear and loopy chains. Otherwise, if there is only one or more open loopy chain then complete all but four boxes of one open loopy chain and all boxes of all other open loopy chains.
After these boxes are completed one can start thinking about whether to play DD/DDD or not.
We learned that the game starts with more or less random moves except that both players avoid creating 3-boxes as long as possible, i.e. they avoid opening chains. When this becomes inevitable we take it as the start of the endgame. We start with it because it is the easiest part of all games.
The End Game
As with all other games, the closer one gets to the end, the easier it becomes to predict who will win under optimal play and by how much. We therefore start our analysis from the end of the game.
In the end game all moves either open chains or complete boxes or are DD/DDD moves.
When a player has to open a chain then the first idea would be to open the smallest to give the opponent the fewest number of boxes. Let us try that out in a few examples.
Example 1
Let us assume that all boxes are completed except two chains with 3 and 4 boxes:
+ +---+---+ | | | | + +---+---+ | +---+---+---+ +---+---+---+
Player A who is moving next will open the shorter chain (with move A1) for the other player B to claim that chain and get 3 points and A to get the larger chain with boxes afterwards with a score from these two chains of A:B=(0+4):(3+0)=4:3.
+A9-+---+---+ | | | | +A8-+---+---+ | B5 A6 A7 +---+---+---+ B2 A1 B3 B4 +---+---+---+
By the way, move A1 is what we defined earlier as loony move, a move that gives the opponent the option to make a sacrifice.
But player B is clever and takes only one box with move B2 (in the next diagram), then plays Double Dealing with B3. A then needs to take the 2 boxes with A4, is forced to open the large chain with some move, like A5, and B gets the remaining 4 boxes with a final score of A:B = (2+0):(1+4)=2:5.
+B9-+---+---+ | | | | +B8-+---+---+ | A5 B6 B7 +---+---+---+ B2 A1 A4 B3 +---+---+---+We see that in this situation it is beneficial for B to sacrifice two boxes.
Example 2
Let us assume that all boxes are completed except one chain with 3 boxes and one loop with 4 boxes.
+---+---+---+ | | | + + +---+ | | | +---+---+---+ +---+---+---+Player A moves next.
Case 1: A opens the chain with 3 boxes.
If after A1 player B takes the whole chain, player A gets the loop and the score from these two chains is A:B = (0+4):(3+0) = 4:3.
+---+---+---+ | A7 | | +A6-+A8-+---+ | B5 | | +---+---+---+ B2 A1 B3 B4 +---+---+---+
If after A1 player B plays DD then after
+---+---+---+ | B7 | | +B6-+B8-+---+ | A5 | | +---+---+---+ B2 A1 A4 B3 +---+---+---+the score from these two chains is A:B = (2+0):(1+4) = 2:5 so also here it is beneficial for B to play DD and reach A:B = 2:5.
Case 2: A opens the loop with 4 boxes.
If after A1 player B takes the whole loop, player A gets the shorter chain and the score from these two chains is A:B = (0+3):(4+0) = 3:4.
+---+---+---+ | B3 | | +B2-+B4-+---+ | A1 | | +---+---+---+ B5 A6 A7 A8 +---+---+---+
If after A1 player B plays DDD with B2 we get
+---+---+---+ | B2 | | +A3-+A4-+---+ | A1 | | +---+---+---+ B6 A5 B7 B8 +---+---+---+and a score from these two chains of A:B = (4+0):(0+3) = 4:3. In this case it is better for B NOT to play DDD then then to get A:B = 3:4.
What do we learn from the two cases?
We saw in the second case, that the cost of playing DDD in a loop is high (4 boxes) which can make it preferable not to play it but to take the whole loop.
About the question for player A which chain to open: In this example it is better for A to open the loop which reaches A:B = 3:4 instead of opening the three box chain reaching A:B = 2:5.
We learn that if loops are involved, chains should not be simply sorted by size (number of boxes) to decide which chain to open first. But sorting them by size − 2 if it is a loop would work here: 4−2 = 2 < 4.
Example 3
In this example we want to learn more about the order in which chains should be opened.
Let us assume that all boxes are completed except two linear chains with 3 and 4 boxes and one loop with 4 boxes like here:
+---+---+ +---+
| | |
+ + +---+ +
| | | |
+---+---+---+ +
|
+---+---+ +---+
Player A moves next. It is clear that A will not open the larger linear chain with 4 boxes if there is a linear chain with 3 boxes.
Case 1: A opens the chain with 3 boxes.
Before deciding on the optimal play of B let us check which of the other 2 chains should be opened first:
+---+---+ +---+ | | | + + +---+ + | | | | +---+---+---+ + | | | | +---+---+---+---+
Let players be C and D with C moving next.
Case 1.1: C opens the loop
+---+---+ +---+ | | | + + +---+ + | C1 | | | +---+---+---+ + | | | | +---+---+---+---+
If after C1 player D plays DDD with D2 then after
+---+---+C5-+---+ | D2 | D6 | +C3-+C4-+---+D7-+ | C1 | | | +---+---+---+D8-+ | | | | D9 +---+---+---+---+
the score from these two chains is C:D = (4+0):(0+4) = 4:4. If D does not play DDD but takes the loop then after
+---+---+D5-+---+ | D3 | C6 | +D2-+D4-+---+C7-+ | C1 | | | +---+---+---+C8-+ | | | | C9 +---+---+---+---+
the score from these two chains is also C:D = (0+4):(4+0) = 4:4.
Case 1.2: C opens the 4 box chain
+---+---+C1-+---+ | | | + + +---+ + | | | | +---+---+---+ + | | | | +---+---+---+---+
If after C1 player D takes the whole chain then after
+---+---+C1-+---+ | C8 | D2 | +C7-+C9-+---+D3-+ | D6 | | | +---+---+---+D4-+ | | | | D5 +---+---+---+---+
the score is C:D = (0+4):(4+0) = 4:4. If after C1 player D plays DD with D4 then after
+---+---+C1-+---+ | D8 | D2 | +D7-+D9-+---+D3-+ | C6 | | | +---+---+---+C5-+ | | | | D4 +---+---+---+---+the score is C:D = (2+0):(2+4) = 2:6. The best that D can enforce after C1 is C:D = 2:6 .
What do we learn from the two cases?
It is best for who plays next (C) to open the loop reaching C:D = 4:4 and not the linear chain reaching only C:D = 2:6. If we would sort chains by size − 2 to decide which to open first then (4−2) = 2 < 4 would give the correct result.
We can now decide on the optimal play of B in
+---+---+- +---+
| | |
+ + +---+ +
| | | |
+---+---+---+ +
A1 |
+---+---+ +---+
Should B take the chain or play DD?
If B takes the chain then after
+---+---+A9-+---+ | A7 | A10 | +A6-+A8-+---+A11+ | B5 | | | +---+---+---+A12+ B2 A1 B3 | A13 +---+---+B4-+---+
the score on these 3 chains is A:B = (0+4+0):(3+0+4) = 4:7. If B plays instead DD with B3 then after
+---+---+B9-+---+ | B7 | A10 | +B6-+B8-+---+A11+ | A5 | | | +---+---+---+A12+ B2 A1 A4 | A13 +---+---+B3-+---+
the score on these 3 chains is A:B = (2+0+4):(1+4+0) = 6:5. So the best that B can reach after A1 is A:B = 4:7 obtained by B though not playing DDD.
In both cases we used the earlier finding that the loop should be opened next.
Case 2: A opens the loop with 4 boxes:
+---+---+ +---+
| | |
+ + +---+ +
| A1 | | |
+---+---+---+ +
|
+---+---+ +---+
Case 2.1: B takes the whole loop.
It is clear that the small chain should be played with DD leading to
+---+---+B9-+---+ | B3 | A10 | +B2-+B4-+---+A11+ | A1 | | | +---+---+---+A12+ B5 A6 B8 | A13 +---+---+A7-+---+giving a score on these 3 chains of A:B = (0+1+4):(4+2+0) = 5:6.
Case 2.2: B sacrifices the loop.
Again the small chain should be played with DD leading to
+---+---+A9-+---+ | B2 | B10 | +A3-+A4-+---+B11+ | A1 | | | +---+---+---+B12+ A5 B6 A8 | B13 +---+---+B7-+---+giving a score on these 3 chains of A:B = (4+2+0):(0+1+4) = 6:5.
What do we learn from cases 2.1 and 2.2?
Because of the high price of playing DDD in a loop the best for B here is to take the whole loop reaching a score of A:B = 5:6.
What do we learn from cases 1 and 2?
We have two linear chains with 3 and 4 boxes and a loop with 4 boxes. It is best for A to open the loop and reach a score of A:B = 5:6. If A opens the chain with 3 boxes then it reaches only A:B = 4:7. It is clear that it can not be better for B to open the chain with 4 boxes before the chain with 3 boxes.
Therefore, sorting chains simply by size to determine which to open next does not work. But sorting them by size − 2 if it is a loop seems to work because (4−2) = 2 < 3 indicating that the loop should be opened first.
The order in which chains are opened
With the experience gained from the examples above we are now tackling the problem of determining the order in which chains will be opened and completed. This order of chains will be used below to determine when one of the players will play DD/DDD, who will win the game and by how much.
The good news is that in the endgame this sequence of opening chains does not depend of who's turn it is or who played DD/DDD before.
The reason is that at any point in the game only the lines that have been drawn matter, not by who and not in which order. Even the current score has no effect on future optimal play.
Splitting a difficult problem into easier problems is already a success, in this case the difficult task of who is making which move in the endgame into the problem of ordering the chains that are opened and the problem who is playing DD/DDD and when.
Before we start, we need to think about the general trend in the endgame.
Does the 'value' of opened chains decrease or increase towards the end?
An opened chain is given to the opponent. The chain should therefore have the least possible 'value' where value is on a first look the number of boxes. Therefore over the course of the end game the 'value' of opened chains can only rise or stay constant but not decrease.
In our example above we saw that opening the chain with the fewest boxes for the opponent to take does not work. But we want to sort the chains by some 'value' because every player want to open the least valuable chain for the opponent. For the opponent the value of a chain does not only consist of the number of boxes, and it also matters whether the opened chain is suitable to play DD/DDD in it. A good candidate for that adjustment of suitability for DD is to subtract 2 from the number of boxes if the chain is a loop. So to sort chains by 'value' where we take 'value' = # of boxes if the chain is NOT a loop and take 'value' = # of boxes − 2 if the chain IS a loop.
We start with board positions where each box has at least 2 sides drawn. For that we can formulate two rules that order all chains.
Rule 2: To order chains take for the last chain the largest linear
chain and if there is no linear chain then take the largest loop.
Justification of Rule 2
Justification of Rule 3
For the next player to take or keep control, the value of a chain is the number of its boxes − 2 if it is a linear chain and − 4 if it is a loop. To sort chains one gets the same result if one only subtracts 2 in case of a loop.
What if the opponent does not have control and will not take control in the next turn? Would the opponent not benefit when, based on this ordering, the opponent is to move next in an opened loop with two more boxes than getting a linear chain with same 'value' but less boxes? No! If the opponent completes the whole loop then afterwards when it is this players turn, there will be one loop less and it will be 2 boxes cheaper to take control. ∎
We saw that effect in Example 3 case 2.1 where after player A opens the loop with A1, player B takes the whole loop but as a consequence it became affordable for A afterwards to take control with A7 and obtain the best possible result.
The above rules are clear if all boxes belong to a chain, i.e. if all boxes have at least 2 sides drawn. But what if there are 0- and 1-boxes?
Which chains do these boxes belong to?
Rule 4: To establish a sequence of chains sorted by value perform the following cycle of making moves until the whole board is completed.
- Open one of the chains for which (number of boxes −2 if it is a circle) is minimal with one exception: If there is still at least one loop either connected or disconnected, and if there is only one disconnected linear chain, and if there is no connected tree of only linear chains then do not open the last disconnected linear chain.
- Complete the opened chain without counting boxes. Drawing lines at the end of a linear chain may change a 1-box to a 2-box and thus either merge two linear chains or cut off a loop.
If in the end game there are still 0-boxes and 1-boxes then one can think of such a box as a point and think of the chains as lines which end at such points or end at the edge of the board and then get an artificial additional point.
Points together with lines which connect them are called a graph in mathematics.
The exception in Rule 4 formulated in 'graph language' would say: Do not open a linear chain corresponding to a line disconnected from the remaining graph if the remaining graph has a disconnected part that contains a loop and has no disconnected part that does not contain a loop (and is therefore called a 'tree' in the language of graphs).
Example 4: A graph like a 'T'
The 1-box has a 'T' inscribed:
+---+---+---+ + | T | | + + + + + | | | | + + +---+---+ | | | + +---+---+ +
The graph corresponding to this board would be like a T with 4 points, one where the − and the | in the T meet and 3 points at the 3 ends of the T.
The smallest of the 3 chains attached to the 1-box is on its left. By opening it and completing it
+---+---+---+ + +---+---+---+ + | | | | | | | + + + + + +---+ + + + | | | | | | | | +---+ +---+---+ +---+ +---+---+ | | | | | | + +---+---+ + +---+---+---+ +
one sees that the board has two linear chains, one with 3 and one with 9 boxes.
Example 5: A graph like a 'P'
The 1-box has a 'P' inscribed:
+---+---+---+---+ | | + -+---+---+ + | P | + +---+---+---+ | | +---+---+---+ +
Drawing the side above the 1-box or to the right of this box would create and open one large linear chain with 12 boxes
+---+---+---+---+ | | +---+---+---+ + | | + +---+---+---+ | | +---+---+---+ +
which one would not want to give to the opponent. Drawing the line underneath the 1-box will partition the board into an opened linear chain with 4 boxes and a loop with 8 boxes.
+--+--+--+--+ | | + +--+--+ + | | +--+--+--+--+ | | +--+--+--+ +
In Rule 4 above an exception was formulated. The following example illustrates it.
Example 6: A 'P' graph plus a disconnected linear chain
Two linear chains can be opened, one on the right and one at the bottom.
+---+---+---+---+ + | P | | + + +---+ + + | | | | + +---+---+---+ + | | | +---+---+---+ + +
Case 1. Opening the shortest chain first
21 moves have been made so if player A started, player B moves next.
If after opening the smallest chain with B1 player A takes control right away we get
+---+---+---+---+B1-+ | B5 B12 | | +A6-+ +---+ +A2-+ | | | | +A7-+---+---+---+B4-+ | A8 A9 B11 | | +---+---+---+A10+A3-+
and a score of A:B = (1+4+6):(2+2+0) = 11:4 where (2+2+0) means that player B gets from the 3 opened chains in that order 2, 2, and 0 boxes. Because B can only open the 2nd linear chain with B5, player A can stay in control with A10 with a cost of only 2 and get the loop for free.
Case 2. Opening the longer linear chain first
After B opens the longer chain with B1 below and this chain is completed, whoever gets the last square(s) has to open a chain. According to our Rule 2 player B opens the loop next with B8 to make taking/keeping control expensive. This strategy works because taking/keeping control in the loop does not make sense for player A because it costs 4 and gains only 3 boxes in the last chain.
+---+---+---+---+A14+ | B1 A13 B8 | | +A2-+A12+---+A9-+B15+ | | A11 A10 | | +A3-+---+---+---+B16+ | A4 A5 B7 | | +---+---+---+A6-+B17+
The score is A:B = (4+6+0):(2+0+3) = 10:5
If A would not play DD in the first chain:
+---+---+---+---+B14+ | B1 B13 A8 | | +A2-+B12+---+B9-+A15+ | | B11 B10 | | +A3-+---+---+---+A16+ | A4 A5 A6 | | +---+---+---+A7-+A17+
then the score A:B = (6+0+3):(0+6+0) = 9:6 would be worse for A. The reason is that playing in the loop after it is opened (B9 above) is worth 6-3=3 points and taking control in the first long chain costs only 2 points, so it is worth taking control in the first chain. 10:5 is better than 9:6 for player A.
When comparing cases 1 and 2 and the two scores 11:4 and 10:5 it
is clear that player B should open the longer chain first. The
reason is that if B would open the disconnected linear chain
first then the loop would get completed last which means that
player A would not have to pay 4 points when playing DDD in the
loop to stay in control. We would violate our earlier Rule 2.
One can show in general that if the disconnected chain has
m boxes, the connected linear chain has n boxes
and the loop has p boxes then player B opening the
disconnected chain first gives B 4 points from 2 times DD
whereas when B opens the attached linear chain then B gets
min(p + max(0,m-4),min(6,m+2))
many points. The lowest value this can take is when p has
its lowest value which is 4 (a loop has at least 4 boxes) and
m has its lowest value which is 3 (shortest long linear chain, if
the shortest chain had only 2 boxes that would be played with
hard-hearted handout instantly and the formula would be
different). For p = 4 and m = 3 player B would get
min(4 + max(0,-1),min(6,5)) = min(4+0,5) = 4
and for p > 4 or m > 4 player B would get more than 4 points.
What if there are different equally chains with same lowest value?
If different chains have the same lowest value then our program uses the rule to open a connected chain. The thought behind is that there is a possibility that through this opened chain a loop becomes accessible which can make taking/keeping control only more expensive.
In games one usually takes control by playing DD/DDD at the start of the end game. But if there are many chains with 3 boxes and loops with less than 8 boxes then it may be best not to play DD/DDD and not to take control. We therefore need a general algorithm and not only a rule of thumb.
When should one play DD/DDD and when not?
In the literature on the Dots game the first play of DD/DDD is also called taking control. What this means is that the player takes control of who gets the last long chain, which may not be the same as taking control of the game and winning it by NOT playing DD/DDD as we will see below.
When a player has the option to play DD/DDD then this player has the option to switch roles with the opponent at the price of 2 points (DD) or 4 points (DDD). If one knows the score obtainable from playing optimally the remaining chains then one can decide whether it is worth to switch roles now at the cost of 2 (if the currently played chain is linear) or a cost of 4 (if the currently played chain is a loop). Together with the earning from the current chain one can determine the score before opening the current chain.
This calculation can be performed backwards starting from the end of the game if one knows the sequence of opened chains. Such a sequence can be determined by Rule 4 above.
Rule 5: Decide whether to play DD/DDD or not using the pseudo code below.
In the following pseudo computer code variable A is the number of points obtained in the rest of the game by the player who opens the next chain, and variable B is the number of points obtained by the other player. The number of remaining boxes is A+B.
We calculate backwards and for convenience label chains backwards: the last opened chain in the game is chain 1, the chain before is chain 2 and so on. The current chain is chain k. Any chain j has n_j boxes. The variable playDD records whether DD/DDD is played in chain j.
In the following pseudo code line(s)
- (1) initializes the 3 variables as the result of playing the last chain.
- (2)-(9) update A, B, playDD for chain j where j runs backward from the last but one chain (j=2) to the present chain k.
- (3)-(5) if chain j is linear the cost is 2
- (7)-(9) if chain j is a loop the cost is 4
- (4),(8) if the gain B−A is bigger than the cost (2 or 4) then play DD and reduce B by the cost and add it to A. In any case B get n_j.
(1) A:=0; B:=n_1; playDD:=false;
(2) for j:=2 to k do
(3) if chain j is linear then
(4) if B>(A+2) then begin playDD:=true; B:=B+n_j-2; A:=A+2 end
(5) else begin playDD:=false; B:=A+n_j; A:=B end
(6) else
(7) if chain j is a loop then
(8) if B>(A+4) then begin playDD:=true; B:=B+n_j-4; A:=A+4 end
(9) else begin playDD:=false; B:=A+n_j; A:=B end;
After this calculation
A is the score for the player who opened the current chain
B is the score for the opponent and
playDD says whether the opponent should play DD/DDD now. ∎ (End of Rule 5)
This pseudo code may seem difficult for a non-programmer but it is easy to be executed in one's head because it only means to check whether the benefit of staying in control outweighs the cost of it, i.e. the cost of playing DD/DDD.
Test Question
We know that lowest value chains are opened first. Does it mean that playing DD/DDD becomes more beneficial towards the end of the game?
In other words, does playing DD/DDD now always means
that one needs to play it till the end as otherwise
the opponent will take over control and win?
In nearly all cases, yes. But we saw in Example 6, case 2 that some low value loop may be accessible only after higher value linear chains are completed. As a consequence, although there was not enough incentive to play DDD when the loop was opened (the last chain had only 3 boxes and DDD costs 4 boxes), the incentive was enough to play earlier DD which has a cost of only 2.
Test Question
Let us assume that someone is evaluating correctly whether to play DD/DDD and decides doing it and getting the last chain.
Will that player always win?
No. If we have, for example, 5 linear chains with each 3 boxes. Getting the last one gives an incentive of 3 boxes which is enough to pay for 3 DD each costing 2 and getting 1 box. That means the first chain is completed as a whole and 3 more DD plays gives scores (3+2+2+2+0) : (0+1+1+1+3) = 9:6 for the player who did not get the last chain.
Are our rules to play end games perfect?
No. When one has many chains connected through 0-boxes and 1-boxes then several of them may have the same number of boxes and then a more refined theory or search may be needed to select the optimal one based on which other chains become accessible later through the completion of first chains.
Would it make a difference to the above endgame theory if the opponent
plays non-optimally a Half-Hearted Handout?
The positions
+---+---+ +---+ + | or | | +---+---+ +---+---+
or mirrored/rotated versions of them are treated by our rules like any other linear chains, just having 2 boxes. These chains give the next player the option to take the chain or to play DD so they are treated like opened long chains which have least 3 boxes.
The Long Chain Rule
Rule 6: The first player should try to make # of dots + # of long linear chains even and the second player odd.
Justification of the rule
To begin we introduce some variables where '#' stands for 'number':
nt = # of turns (# of times a player played consequential moves)
nd = # of dots
r = # of rows of dots
c = # of columns of dots
nl = # of lines
nb = # of boxes
nc = # of long chains
nz = # of the turn that opened the first long chain in the endgame
We begin with deriving a relation known as Euler's Identity.
Expressing the number nb of boxes, nl of lines and nd of dots in terms of r rows and c columns of dots we get
nb = (r−1)(c−1) = rc − r − c + 1
nd = rc
nl = # of horizontal lines + # of vertical lines
= r(c−1) + c(r−1)
= 2rc − r − c
and therefore
nl = nb + nd − 1 .
This relation is equivalent to Euler's identity which is valid for arbitrary graphs, i.e. any number nd of dots linked by any number nl of lines, not only vertically and horizontally, surrounding nf faces where in our case nf = nb + 1 because our rectangular grid of dots has an extra surrounding face which is also counted in Euler's identity:
nl − nd + 2 = nf (= nb + 1).
Next we compute the number of turns of the whole game.
A turn is a sequence of consecutive moves of one player.
If after completing a box the other player would move next then we
would simply have # of turns = # of lines, so nt = nl. But in the DOTS game
after completing one or two boxes the player moves again, so we have
nt = nl − ((# of times that drawing a line completed at least 1 box)
− 1
{Completing the very last box does not give another move.})
= nl − (nb − (# of moves which complete 2 boxes) − 1)
= nl − nb + 1 + (# of moves which complete 2 boxes)
= nd {using our earlier relation nl = nb + nd − 1}
+ (# of DD in linear chains) + (# of loops) + (# of DDD in loops)
The last line results from the fact that when completing a loop the last move always completes two boxes and if DDD is played in a loop then another move completes 2 boxes as well. The derived relation
nt = nd + (# of DD in linear chains) + (# of loops) + (# of DDD in loops)
is an exact rule without approximations.
Computing nz which is the turn of opening the first long chain
After the first long chain is opened in the endgame, if no DD and no DDD is played, then the number of remaining turns is equal to the number of long chains as each player completes one chain. Therefore, if (# of DD) = (# of DDD) = 0 then
nz {# of the turn which opens the first long chain in the endgame}
= nd + (# of loops) − (# of long chains)
= nd − (# of long linear chains)
The formula for nz is also valid if DD/DDD are played. Justification:
Any play of DD/DDD could not change what had already happened before, namely the
nz turns that lead to the opening of the first long chain in the
endgame. For each DD and DDD played, the number of turns in the
endgame increases by 1 (please verify) so when subtracting the
number of turns in the endgame from the total number of turns then
(# of DD) and (# of DDD) would each be canceled and we would get
the same value for nz as if no DD/DDD are played.
Long Chain Rule: The first player tries to make (# of dots) + (# of long linear chains) to be even and the second player to be odd. ∎
A wrong derivation of the Long Chain Rule
In some publications on the DOTS game two unnecessary assumptions are made to derive the Long Chain Rule.
1. Assumption:
If both players play the end game optimally then who
plays the last move wins because of the high value of the last
and largest chain and because of not having to move again and
open another chain for the opponent.
So the first player wants nt = (# of turns) to be odd to make the first and last move and win.
2. Assumption:
All long chains except the last chain are played with DD/DDD.
Thus (# of loops) + (# of DDD in loops) is even and can be ignored
and nt = nd + (# of DD in linear chains) becomes
nt = nd + (# of long linear chains) − 1.
Therefore the first player wants this nt to be odd to make the last
move which is when (# of dots) + (# of long linear chains) is even
- the Long Chain Rule. ∎
But we know that these 2 assumptions are not necessary for the Long Chain Rule to be true. The next example will demonstrate this.
Which success is guaranteed by the rule for one player?
The Long Chain Rule gives a necessary and sufficient condition for one player to be the first to play in the opened first long chain in the endgame.
If the first long chain is linear then it has at least 3 boxes and playing DD has a cost of 2 boxes. So in the worst case when the incentive to play DD is 2 then whether playing DD on not playing DD, one will win by at least 1 point from the first chain. If the incentive is >2 then one will earn in addition from playing DD and if the incentive is <2 then one will earn extra from not playing DD.
If the first long chain is a loop then in the worst case the first chain has 4 boxes and the incentive is 4 and then whether one plays DDD or not, both players will get the same number of points in the endgame. But if the incentive is >4, playing DDD will give more points and if the incentive is <4 then not playing DDD will give more points because the loop has at least 4 boxes. And if the first long chain being a loop has more than 4 boxes then this player will get more points even if the incentive is 4.
Example 7: Testing the rule in an unusual situation
On this board an odd number of 5×3 = 15 moves have been made. Move 16 will open the first long chain which satisfies the formula we derived: 16 = (# of dots) - (# of linear long chain) = 20 − 4. Whoever makes this move, in this case player B, will lose if player A plays DD appropriately.
+ + + + + | | | | | + + + + + | | | | | + + + + + | | | | | + + + + +
Player A started and player B has to open a chain now.
What is the score if three DD are played?
If A plays 3 times DD then the final score is A:B = 6:6.
+---+---+---+---+ | A | A | A | A | +---+---+---+---+ | B | B | B | A | +---+---+---+---+ | B | B | B | A | +---+---+---+---+
The score from the last 3 chains is 5:4, so playing DD in the first chain and paying with 2 points for getting one point is not optimal.
What is the score if two DD are played?
It is better for A to take the whole first chain and get a final score of A:B = 7:5.
+---+---+---+---+ | A | B | B | B | +---+---+---+---+ | A | A | A | B | +---+---+---+---+ | A | A | A | B | +---+---+---+---+
Which assumption of the wrong derivation of the Long Chain Rule is violated?
Both assumptions have been violated. A is winning but not getting the last chain. Not in every long linear chain DD is played.
Does the Long Chain Rule still hold for this optimal play?
We get (# of dots) + (# long linear chains) = 20 + 4 = 24 which is even and the first player wins as the rule predicts. So that rule is better than the alternative proof with unnecessary assumptions and wrong interpretation.
Test Question
Does optimal play require EITHER to play DD/DDD OR not to play DD/DDD?
No, both could be equally good. With only two long chains with 3 boxes, A needs to play DD giving a score A:B = 4:2.
+ + + +---+---+ | | | | A | A | + + + +---+---+ | | | → | B | A | + + + +---+---+ | | | | B | A | + + + +---+---+
So the incentive to play DD before these two chains is 4 − 2 = 2 which is equal to the cost of playing DD. Therefore both plays give the same score: 4:(2+3) = 4:5 = (2+2):(4+1)
+---+---+---+ +---+---+---+ | B | A | A | | B | B | B | +---+---+---+ +---+---+---+ | B | B | A | = | A | A | B | +---+---+---+ +---+---+---+ | B | B | A | | A | A | B | +---+---+---+ +---+---+---+
Test Question
Could it happen under optimal play that players repeatedly start and stop playing DD/DDD?
Yes. We saw above how adding a chain with 3 boxes changed the score from 4:2 to 4:(2+3) = 4:5. The incentive to play DD before these 3 chains would be 5−4 = 1 < 2 so less than the cost of playing DD which is 2. Hence, with four chains of 3 boxes, the first would not by played with DD. If there would be another chain with 3 boxes the score would become (4+3):5 = 7:5 = (4+1):(5+2) so the incentive to play second in 5 chains of 3 boxes would be 7−5 = 2 so playing DD would be ok giving in both cases a score of (2+5):(1+7) = 7:8 = 7:(3+5).
+---+---+---+---+---+ +---+---+---+---+---+ | B | B | A | A | A | | B | B | A | B | B | +---+---+---+---+---+ +---+---+---+---+---+ | A | B | B | B | A | = | A | B | A | A | B | = +---+---+---+---+---+ +---+---+---+---+---+ | A | B | B | B | A | | A | B | A | A | B | +---+---+---+---+---+ +---+---+---+---+---+ +---+---+---+---+---+ +---+---+---+---+---+ | B | A | B | B | B | | B | A | B | A | A | +---+---+---+---+---+ +---+---+---+---+---+ | B | A | A | A | B | = | B | A | B | B | A | +---+---+---+---+---+ +---+---+---+---+---+ | B | A | A | A | B | | B | A | B | B | A | +---+---+---+---+---+ +---+---+---+---+---+
By adding more chains with 3 boxes one could have more alterations between play and non-play of DD.
Is the Long Chain Rule satisfied?
The reader is encouraged to check the Long Chain Rule with more examples that involve loops.
Example 8: Applying the Long Chain Rule
On this website of David Wilson the following position is shown which has just one move for the next player to win.
+ + + +
|
+ + +---+
+---+---+---+
|
+ +---+ +
Who would win if both players would follow our endgame rules?
This board has an even number of dots and even number of long chains. The last long chain will not have a DD move played so an odd number of DD moves will normally be played and thus # of points + # of DD is odd so the number of turns is odd so the first player will get the last chain and win. This is in line with the 'Long Chains Rule': "The first player should try to make # of dots + # of long (linear) chains even and the second player odd."
What can the 2nd player do?
The 2nd player can not change the number of dots but the number of DD moves by sacrificing 2 boxes and play the move marked as B which is the only winning move that the 2nd player has in this situation:
+ + + +
|
+ + +---+
+---+---+---+
| B
+ +---+ +
This move reduces the number of long chains from 2 to 1 and thus makes # of dots + # of long (linear) chains odd and thus allows the 2nd player to win by one point instead of losing by one point.
How could the game continue?
The following variations all lead to A:B = 4:5 so to a 1-point win for B.
+ +A10+B6-+
A3 | B9 A11
+ +A5-+---+
B4 A12
+---+---+---+
| | A2 B8
+A1-+---+A7-+
+A3-+A5-+B6-+
A11 | A12
+B9-+ +---+
A10 B4
+---+---+---+
| | A2 B8
+A1-+---+A7-+
+A3-+A10+B6-+
| B9 A11
+ +B4-+---+
A5 A12
+---+---+---+
| | A2 B8
+A1-+---+A7-+
Making this move does violate the very
first Rule 1 of not creating 3-boxes if
not really necessary. How bad is that
break of Rule 1?
This breaking of Rule 1 is not less strange than playing DD. As we found out earlier, it is normal to play DD and pay a price of 2 points in order to switch roles. So this sacrifice is the minimal and fine if it has the same affect as a DD move.
In the above part of this page technical terms were introduced and rules were formulated. The end game is described in detail and for the first part of the game the Long Chain Rule gives guidance. If you like to learn more about the first part of the game then please check [2] and [3] in the References. The following decision tree summarizes this webpage.
A Decision Tree
For the links below to work, one needs to unfold the text above by clicking
- If there is at least one 3-box (a box that can be completed) then
identify all chains that are attached to all these 3-boxes.
- If one of these chains is linear and has at least 2 neighbouring boxes then complete all boxes from all linear and all loopy chains apart from these two neighbouring boxes of this one linear chain. Then analyze whether to play DD and either play DD or complete the last 2 boxes.
- All chains have either length 1 or are loopy. Then complete at first all chains of length 1 and if there is at least one loopy chain then complete all loopy chains except the last 4 boxes of one of the loopy chains. Then analyze whether to play DDD or complete the last 4 boxes.
- There is no box that can be completed.
- If there is a move which does not create a 3-box then
- if it is clear how many linear chains will exist at the end of the game and if the Long Chain Rule predicts loosing the game then consider making a sacrifice move to reduce the number of long chains, else
- it is not clear how many long chains will there be at the end of the game then as first player try to make # of dots + # of long (linear) chains odd and as second player try to make the sum even.
- Each move will create a 3-box.
- If the shortest chain is a 2-chain
+---+---+ +---+---+
where the 2 un-drawn lines can be anywhere but not in the same box, then play in the middle to reach:+---+---+ | +---+---+ - Determine the next chain to open and play anywhere in this chain.
- If the shortest chain is a 2-chain
- If there is a move which does not create a 3-box then
References
[1] Wikipedia: Dots and Boxes, see other references there.
[2] Berlekamp, Elwyn R.; Conway, John H.; Guy, Richard K. (1982), "Chapter 16: Dots-and-Boxes", Winning Ways for your Mathematical Plays, Volume 2: Games in Particular, Academic Press, pp. 507–550.
[3] Berlekamp, Elwyn (2000), The Dots-and-Boxes Game: Sophisticated Child's Play, AK Peters, Ltd, ISBN 1-56881-129-2.
[4] Wilson, David, Dots-and-Boxes Analysis Results, University of Wisconsin
Index
For the links below to work, one needs to unfold the text above by clicking
- # ...
- number of ...
- Box
- a small square with 4 neighbouring dots as corners
- ?-Box
- 0-box, 1-box, ..., 4-box are boxes that have 0, 1, ..., 4 of its sides drawn.
- Chain
- is made up from connected 2-boxes. There are linear and loopy chains.
- DD
- abbreviation of Double Dealing
- DDD
- abbreviation of Double Double Dealing
- Double Dealing
- a move on the border of a Half-Hearted Handout leading to
+---+---+ | | . +---+---+
- Double Double Dealing
- a move in the middle of an opened loop with 4 remaining
boxes, creating, for example,
+---+---+ +---+---+---+---+ | | | | | +---+---+ or +---+---+---+---+ or | | +---+---+ +---+---+ +---+---+---+ | | | | | +---+---+---+ or +---+---+ + | | | | +---+---+ +---+ - Endgame
- is starting when it becomes inevitable to create a 3-box in the next move
- Euler's identity
- a general relation for any graph in the plane,
not only the Dots game, where lines do not cross:
(# of lines) − (# of dots) + 2 = (# of faces)
where faces include the 'outer face' so for us (# of faces) = (# of boxes) + 1. - Graph
- a concept in mathematics where a number of points are connected by a number of lines
- Hard-Hearted Handout
- drawing the middle line in
+---+---+ +---+---+ +---+---+ or | or | | +---+---+ +---+ + + + +or rotated and mirrored versions of them resulting in+---+---+ +---+---+ +---+---+ | or | | or | | | +---+---+ +---+ + + + +or rotated and mirrored versions of them - Half-Hearted Handout
- drawing a line on the border of a chain with two boxes leading to
+---+---+ +---+---+ | or | | +---+---+ +---+ +
- Line
- the line segment linking two neighbouring dots horizontally +---+ or vertically
- Linear chain
- a chain that has 2 ends, it does not have to be straight
- Long Chain Rule
- The first player should try to make # of dots + # of long chains even and the second player odd.
- Long chain
- a chain with ≥ 3 boxes
- Loony move
- a move giving the opponent the option to make a sacrifice
- Loop
- abbreviation for loopy chain
- Loopy chain
- a chain without ends
- Move
- drawing a line
- Opening a chain
- making a move inside a chain or on one of its ends (if it is a linear chain)
- Rule 1
- The most obvious play is to avoid creating a 3-box which the opponent could complete and own.
- Rule 2
- For ordering chains take for the last chain the largest linear chain and if there is no linear chain then take the largest loop.
- Rule 3
- If in the endgame all boxes have at least 2 sides drawn then to order all other chains, sort them by (# of boxes) − 2 (if it is a loop).
- Rule 4
- To establish a sequence of chains sorted by value for the next player, lowest value first, perform a sequence of moves (see text) until the whole board is completed.
- Rule 5
- Use the provided pseudo code (see text) to decide whether to play DD/DDD or not.
- Rule 6
- same as the Long Chain Rule
- Taking control
- same as playing DD/DDD which, as an important side effect, gives the option to repeat playing DD/DDD in the next chains
- Turn
- a sequence of consecutive moves of one player
Follow or subscribe for updates: