Dots
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.
We see that in this situation it is beneficial for B to sacrifice two boxes.
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.
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.
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.
Let us assume that all boxes are completed except two chains with 3 and 4 boxes:
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.
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.
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.
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.
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.
Let us assume that all boxes are completed except one chain with 3 boxes and one loop with 4 boxes.
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.
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.
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.
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
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:
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
Before deciding on the optimal play for player B let us check which of the other 2 chains should be opened first:
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.
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:
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.
In this way all boxes will finally belong to some chain. The reason for not opening the last disconnected chain will become clear in the following examples.
In this way all boxes will finally belong to some chain. The reason for not opening the last disconnected chain will become clear in the following examples.
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.
