300000
Загальна кількість перемог : : 26573
Dots
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
Terminology: Let's introduce some new terms that we will use to talk about the game.
A box is a small square with 4 neighbouring dots as corners. A box can have 0, 1, 2, 3, 4 of its sides drawn and is then called a 0-box, 1-box, 2-box, 3-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 type of "chain reaction" happens very often.
All connected 2-boxes make up a chain. A chain can have 2 ends and is then called a linear chain, whether it is a straight line 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 a 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 opening a chain in the mathematical literature about this game.
What happens if a chain is opened?
If a 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 on the board are completed.
Initial Play
Rule 1: The most obvious play is to avoid creating a 3-box which the opponent could take by completing it. 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, creating a 3-box becomes unavoidable. 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?
+---+
| ?
+---+
Yes, one should always do that. Whether one takes the box and afterwards makes a move A or not taking the box and playing on A has no impact on what the opponent does except that either you or the opponent gets the box, so it is better that you get the box.
How can chains with two boxes look 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 always take 1-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).
Drawing the line in the middle which completes both boxes is called a Double-Crossed Move. A loop is always completed by such a move but in a linear chain it can only happen when the opponent plays a DD move in order to take control as explained below. In such a situation the player making a double-crossed move is tricked, i.e. 'double crossed', therefore this name for that move.
Should the next player after DD always take both boxes?
A DD move is a sacrifice of two boxes because the player could alternatively first play in the middle of the Hard-Hearted Handout and then on the border and earn in this way two boxes. Why would one want to sacrifice 2 boxes? Keep reading to find out!
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.
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 what 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. This may be costly because one might have to open a chain with many boxes allowing the opponent to take more squares. 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 costly, should one play a Hard-Hearted or a Half-Hearted Handout?
If one plays in the middle of the chain (a Hard-Hearted Handout) then the other side is forced to take both boxes and afterwards make a potentially costly 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 do so?
Are there boxes one should definitely take from a linear opened chain?
On one hand, we want to take as many boxes as possible. On the other hand, we might not want to pay the price of playing elsewhere afterwards and thereby opening an even bigger chain for the opponent to take. What we should definitely do is 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). We will talk more about that later.
Chains with ≥ 3 boxes are called long chains.. These include both, linear and loopy chains.
Why is there an special name for such chains?
If only long chains with at least 3 boxes are left, then opening one of them, in no matter what way, would mean that on at least one side of the move there are at least 2 neighbouring boxes. So, the other player could play Double Dealing which is crucial in determining 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 all but 2 boxes safely without thinking?
Let us try that out. The smallest possible opened loop is
+---+---+ | | +---+ + | | +---+---+
Of course we could take all 4 boxes and then play elsewhere, but what if we wanted to avoid playing elsewhere at all costs? 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 we are obliged to make a move elsewhere, which could possibly hand over an even a bigger chain to the opponent.
What else could we do instead?
We want to play a move which does not complete a box in order to avoid having 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 (DDD). The price is to sacrifice 4 instead of 2 boxes. For the opponent it is best to take the 4 boxes and play elsewhere afterwards.
What if an opened loop has more than 4 boxes?
We can take as many boxes as we like as long as we can still play a move afterwards 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?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 chains, 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 Endgame
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 endgame 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 for a strategy might be to open the smallest of the available chains 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. So which chain should player A 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've learned 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 for player 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 the player who plays next (C) to open the loop reaching C:D = 4:4 rather than 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 for 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 through 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 cannot 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 on whose 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 determining who is making which move in the endgame has been divided into two problems: the problem of the order in which to open chains, and the problem of 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, at a glance, the number of boxes. Therefore over the course of the endgame 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 wants 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; 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
A player in control does not open chains and therefore does not sort chains. So any player sorting chains wants to make taking or keeping control (i.e. playing DD/DDD moves) for the opponent as costly as possible. A DD move costs 2 boxes and a DDD move costs 4 boxes. This price has to be paid for all chains except the last one. Therefore to maximize the total cost for the opponent, in the sorting of chains the last chain should be linear if possible and not a loop. ∎
Rule 3: If in the endgame all boxes have at least 2 sides drawn, then to order all other chains, sort them by (number of boxes − 2 if it is a loop).
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 player's 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 the value (number of boxes, or if it is a loop the number of boxes −2) is minimal with one exception: If there is still at least one loop, whether 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 endgame 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 connected with lines 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. Example 6 illustrates this exception.
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 costly. This strategy works because taking/keeping control in the loop does not make sense for player A since it costs 4 boxes but only wins 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 hasits lowest value which is 4 (a loop has at least 4 boxes) andm has its lowest value which is 3 (shortest long linear chain, ifthe shortest chain had only 2 boxes that would be played with Hard-Hearted Handout instantly and the formula would bedifferent). 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 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 endgame. 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 in the remaining chains, then one can decide whether it is worthwhile 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 by 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 that 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)-(3) initializes the 3 variables as the result of playing the last chain.
- (4)-(22) update A, B, playDD for chain j where j runs backwards from the last but one chain (j=2) to the present chain k.
- (5)-(13) if chain j is linear the cost is 2
- (14)-(22) if chain j is a loop the cost is 4
- (6)-(9), (15)-(18) 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
(2) B = n_1
(3) playDD = false
(4) For each chain j from 2 to k:
(5) If chain j is linear:
(6) If B > (A + 2):
(7) playDD = true:
(8) B = B + n_j - 2
(9) A = A + 2
(10) Otherwise:
(11) playDD = false:
(12) B = A + n_j
(13) A = B
(14) Otherwise → If chain j is a loop:
(15) If B > (A + 4):
(16) playDD = true
(17) B = B + n_j - 4
(18) A = A + 4
(19) Otherwise
(20) playDD = false
(21) B = A + n_j
(22) A = B
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 execute 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 mean that one needs to play it until 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 while 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. They decide on playing it and getting the last chain.
Will that player always win?
No. For example, let's suppose we have 5 linear chains with 3 boxes each. 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 give 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 endgames 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 a Half-Hearted Handout non-optimally?
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 the number of dots + the number of long linear chains even and the second player should try to make this value 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.
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.
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. We call the derived relation
Number of Turns Formula:
nt = nd + (# of DD in linear chains) + (# of loops) + (# of DDD in loops)
It is an exact formula that is not based on any assumptions.
Computing nz which is the turn which opens the first long chain
After the first long chain is opened in the endgame, in case 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 has 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.
So no player wants to make that move, i.e. the first player does not want nz to be odd and therefore wants nz to be even. 2×(# of long linear chains) is an even number so adding it to nz does not change whether nz is odd or even which finally results in the
Long Chain Rule: The first player tries to make (# of dots) + (# of long linear chains) even while the second player tries to make it 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 endgame optimally, then whoever 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 be able 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 be able 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 to decide which player is the first to play in the first opened long chain in the endgame. This player P can choose whether to play DD/DDD or not to play DD/DDD. We have 2 cases.
If the first long chain is linear then it has at least 3 boxes, and playing DD has a cost of 2 boxes.
• If the incentive for playing DD is <2 then player P will not play DD and take the whole first chain and the opponent will get at most 1 more box from the remaining chains, so P gets in the endgame at least 3−1 = 2 more boxes than the opponent.
• If the incentive is 2 then it does not matter whether P does play DD or does not play DD in the first long chain and therefore gains ≥3 boxes more in the endgame.
• If the incentive is >2 then P plays DD and gets >3 boxes more in the endgame.
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, then 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 is a loop with more than 4 boxes, then P will get these extra points as an advantage in the end game, even if the incentive is 4.
What are possible score differences at the start of the endgame?
• If the number of 1-chains is even and the number of linear 2-chains is even then the score difference at the start of the endgame is zero.
• If the number of 1-chains is even and the number of linear 2-chains is odd then the score at the start of endgame is 2.
• If the number of 1-chains is odd then after completing all 1-chains, the score difference is 1. Then each completed 2-chain will only flip between both players of who is leading by 1 box.
So how important is the Long Chain Rule?
When does the Long Chain Rule not determine the outcome?
Which rule should be followed then?
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 DD 3 times 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. DD is not being played in every long linear chain.
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 misinterpretations.
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 by 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 Chain Rule': 'The first player should try to make # of dots + # of long (linear) chains even and the second player should try to make it odd.'
What can the 2nd player do?
The 2nd player cannot change the number of dots but rather the number of DD moves by sacrificing 2 boxes and playing 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 minimal and fine if it has the same effect as a DD move.
In the above part of this page technical terms were introduced and rules were formulated. The endgame 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
- Before starting the game think of whether to play first or second. See point 3.A.a below.
- 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 opened 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.
- If all chains have either length 1 or are loopy, then first complete 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.
- If there is no box that can be completed, then
- If each move will create a 3-box, then
- 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 (in this case):+---+---+ | +---+---+ - Else, 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
- if in the game there will be at most 1 long chain (linear or loopy), for example, because the rectangle of dots is small or thin, then no DD/DDD moves will be played and then the player taking the last turn wins and because of the Number of Turns Formula, the first player should try to make the sum # of dots + # of loops odd and the second player even. Because the # of dots is fixed, one can only try to get 0 respectively 1 loop. If that is impossible then change who is playing first.
- if it is clear that there will be at least two long chains in the game but it is not clear how many, then follow the Long Chain Rule and as first player try to make # of dots + # of long linear chains even and as second player try to make the sum odd, else
- if it is clear how many long linear chains will come up in the game and if the Long Chain Rule predicts losing the game then consider making a sacrifice move to reduce the number of long linear chains.
- If each move will 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
- # ...
- the number of ...
- Box
- a small square with 4 neighbouring dots as corners
- ?-Box
- 0-box, 1-box, 2-box, 3-box, 4-box are boxes that have 0, 1, 2, 3, 4 of their sides drawn.
- Chain
- a sequence made up of connected 2-boxes. There are linear chains and loopy chains.
- Double-Crossed Move
- a move that completes two neighbouring boxes at once. It is played immediately after a Double Dealing move in a linear chain or when a loop is completed.
- 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
- the final stage of the game which starts when it becomes unavoidable 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, not necessarily straight
- Long Chain Rule
- The first player should try to make # of dots + # of long chains even and the second player should try to make this value 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
- Number of Turns Formula
- an exact formula giving the number of turns in a game which is the basis for the Long Chain Rule and which is useful for a low number of dots to decide whether to be the first player or not
- 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 take by completing it.
- 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
- Refers to 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
Слідкуйте за оновленнями або підписуйтесь на них: