Dots Tutorial: Masters and Non-Mathematicians

Chapter 1, Section 4 of my Dots page

by

Ilan Vardi

(ilanpi on Yahoo Dots)




Masters and Non-Mathematicians

The last part of this tutorial is for players who aspire to complete Dots mastery. I will describe my conception of optimal Dots from observation of the 5x5 Dots oracle. I will end by explaining Nimstring strategy in terms most accessible to Dots practitioners.

6x6 Dots

So you've finally reached the stage where you hardly ever lose on Yahoo Dots (2400+). You may even be starting to get bored with all those easy wins. Well, the next logical step is to play 6x6 Dots, which will present new and interesting challenges. In particular, it will avoid all the known openings, ties, and computer analysis of 5x5 Dots, but without the interminable and intractable games of 10x10 Dots. In fact, no one knows who the theoretical winner is in 6x6 Dots.

It appears that the biggest difference in 6x6 Dots is the much more important role of preemptive sacrifices. This must be due, in part, to the fact that in 6x6 Dots, you can use it to win a game with only a two box advantage, whereas a three box advantage is required in 5x5 Dots, see my proof of this result. The greater possibility of creating chains, due to the larger playing area increases the chance of sacrifices preventing a chain from forming, thereby giving a player a material lead which allows him to use the preemptive sacrifice effectively.

To play 6x6 Dots on Yahoo Games, just choose a 10x10 board and limit your moves to the bottom left-hand 6x6 corner.

In order to make this restriction clear, the players have cooperated to make an enclosure around the 6x6 board. Note that this does not change the sides: Yellow, who start the enclosure, will also play Yellow (first player) in the 6x6 Dots game.

When the 6x6 game is over, the loser must agree to resign the game, as in this diagram, since the Yahoo game is not actually over.

Therefore, playing 6x6 on Yahoo Dots requires a great deal of cooperation and trust between the players. It is therefore limited to expert players who are highly motivated to test their skill on this more challenging venue.

Handicap Dots

One way of challenging yourself against less able competition is to play Handicap Dots.

The only direct handicap possible on Yahoo Dots is to always play Green. This roughly corresponds to a 100 point rating difference. As you improve, you will note that playing Green is the only way to attract competition. Always playing Green is difficult, due to the fact than any error against a good opponent is fatal, while an error with Yellow can often be rescued to obtain a tie. Continually playing second is made more stressful due to the fact that Yellow dictates the opening, so can vary his game as he wishes, whereas Green must closely defend against the first player's choices and has little flexibility in his responses.

Strong players must come to terms with this handicap, especially since the Yahoo system doesn't automatically change colors. This Yahoo peculiarity renders Dots similar to Go in which the recognized stronger usually plays second. One can even follow Go tradition by having intermediate handicaps, for example, to let the weaker player go first in two out of three games.

In any case, many players refuse to go second, so it is important for both sides in such matches to be aware that refusal to play Green is acknowledgement of a sizeable handicap and recognition that the other player is stronger.

More severe handicaps are possible, such as giving your opponent some free boxes at the end. For example, giving a one box handicap simply means that the weaker player wins tied games, that is, "draw odds."

I recommend giving one box for every 200 Yahoo rating point differential, and always play Green when there is an extra 100 points difference.

This type of handicap is not directly feasible on Yahoo Dots, however, keeping box handicaps n mind will help you stay honest by always trying to play the optimal move, that is, the one which gives you the biggest possible winning margin.

These considerations stress the fact, at least superfically, Dots is more similar to Go than to Chess, the latter being consistently cut-throat with players trying to give themselves every advantage short of cheating, e.g., setting up the White pieces for themselves at the beginning of a match. On the contrary, Go practice has included letting the weaker player move first, declaring a tie favorable to the second player, and having the first player give a number of stones (these days 6 and 1/2) to his opponent at the end of the game. However, the Go handicap system consisting of letting the weaker player start with more than one stone has no direct counterpart in Dots-and-Boxes, since Dots players do not place different types of edges, in the sense that a player can make boxes using edges placed by his opponent.



Studying Games

To achieve the highest level of play, you will need to start studying games very carefully. In particular, you will need to play over games in order to identify mistakes or find improvements. You can also record your opponents' games in order to find weaknesses in their strategy.

Using Dabble

The easiest way to record and play over games is to use Dabble. To record a game (that you are not playing with Dabble) you first, you turn off "Autoplay" in the "Game" menu. You then click on the sequence of moves. When you're done with that, you save to a Dabble file (*.dbl) using the "File" menu.

To play over the stored game, you first retrieve the Dabble file you previously saved using "Load" in the "File" menu of Dabble. You then click on the right arrow in the Dabble window to see each successive move.

The first method (Dabble with Autoplay off) is also the easiest way to review a game you recorded using a scoresheet.

Scoresheet for 5x5 Dots

Click on this picture and print it to make scoresheets for 5x5 Dots (4x4 boxes). Using this scoresheet, you can record the games you play on Yahoo Dots. You can also bind these scoresheets together to make a book of your best games.

Scoresheet for 6x6 Dots

David Wilson has written a scoresheet for 6x6 Dots (5x5 boxes). It is best suited for recording face to face games with two playes facing each other at a table, for example, in a real (non-internet) Dots tournament.



Consulting the Oracle

If you aspire to perfection, then I recommend you consult the 5x5 Dots Oracle. This is a program written by David Wilson which gives all the optimal theoretical outcomes for the opening moves. That is, for about the first 10 turns of the game, it gives, at each step, the final outcome of the game, if both sides play perfectly.

You can use this site to analyze your openings, and see whether you or your opponent made a mistake in the opening. You can also test openings, and search for variations which limit the number of good options for your future opponents.

The oracle also provides a challenge to players who have reached the top of the Yahoo hierarchy. Indeed, lack of Yahoo competition becomes an issue fairly quickly, so it appears that one way to improve to the next level is to try to understand the often obscure winning moves decreed by the oracle.



The Nimstring Method

The game of Nimstring, which was invented by Elwin Berlekamp, is a variant of Dots which has a very nice mathematical theory, but which is also useful for playing some Dots positions. The name "Nimstring" comes from an equivalent form of Dots called String and Coins by Berlekamp. In fact, I will talk about the more directly relevant game of Nimdots here.

Beyond Life and Death

The Nimstring method will help you out if you tend to get nervous when positions like this come up.

DIAGRAM

That is, you don't feel comfortable with all those unresolved life and death issues going on simultaneously and you always hurry up and resolve the problem. Well, if you are consistently losing those games, then it is time for you to get with the Nimstring Program.

The Mirror Strategy

Most good Dots players are men, and like any self-respecting male, a good Dots player is afraid of commitment. Consider the following position.

Whoever wins the battle on the top part of the board will be able to take all 8 boxes on the bottom and win the game. Note that chain issue has not been decided in the two regions at top, and that the first person to resolve the chain issue in one of the regions will lose, since the other player responds by resolving the chain issue in his favor in the other region.

The simple way to achieve this is to simply use a mirror strategy, copying the exact move made in one region into the other until the chain issue is resolved in one region.

Interestingly, the chain rule doesn't come into consideration, because the player using the mirror strategy will be always be able to resolve the chain parity in his favor.

When are Two Regions Equivalent?

Interestingly, the mirror strategy method works even for two regions which are not exactly identical. For example, in this positon

This is again a win for Yellow, but what is interesting about it is that there is again a mirror strategy. That is, for each move in one region there is a corresponding response in the other region (possibily preceded by capturing a box) which turns the chain parity question in the players favor.

In this sense, the two regions at the top are equivalent to each other. In general, two regions will be equivalent if for each delaying move (or move resolving the chain issue) in one region there is a corresponding move in the other region which gives the same delaying options (or move deciding the chain issue either way).

Beyond Parity

Before talking about Nimstring strategy in detail, it is useful to understand how the delay strategy works in a position where the chain issue has already been resolved.

So, how many move can you delay in a region where the chain issue is resolved? The answer is that you can delay you can delay zero moves if you must move into a chain or take the last box (that is you can't delay at all!) in that region, and you can delay exactly one move in the region if there is one move left on the board which doesn't move into a chain or force you to move again outside the region (capturing the last box), and

When there are more moves available, the answer is given by the Non-Chain Rule: Once the number of chains is determined, no choice of move will change which player will first have to move into a chain or cycle.

This means that no matter what the choice of move, the player who will first have to move into a chain in the region will always be determined by the parity of the number of turns left until someone has to move into a chain (or take the last box) in the region.

It therefore makes sense to say that a region is equivalent to 0 if the player to move will be the first have to move into a chain, and equivalent to 1 if the player can move into a position where his opponent will first have to move into a chain, that is, he can move into a 0 position.

To repeat myself once more, the non-chain rule says that every region in which the chain number is resolved is equivalent to 0 or 1.

Note that moving into a chain always loses the delaying battle. This is because the opponent can then decide which side he wants to continue the game as (strategy stealing). This is a special case of the more general

Zero game: A Nimdots position is a win for the second player if and only if its value is 0.

Nimdots: The Theory of Delaying Moves

To make the theory of delaying moves clearer, one invents a new game called Nimdots in which the goal is to force the other player to take the last box (or move into a chain). In other words, Nimdots is played exactly like Dots: You place edges on a rectangular array of Dots and whenever you take a box, you have to move again, except that the total number of boxes captured is not taken into account, the loser is the last person to take a box.

In mathematical works on Dots, this game is always called Nimstring, but the two games are completely equivalent.

It is fairly clear that in the two examples of delaying strategy, the winner of the game is the player who wins the Nimdots positions at the top half of the board.


Nimdots Values

The game of Nimdots has a much simpler mathematical theory than ordinary Dots because every Nimdots position can be characterized by a single number, its value.

As already mentioned, as far as delaying moves are concerned, every Dots position in which the chain count is determined has value 0 or value 1, that is:

Every Nimdots position in which the number of chains is determined has value 0 or 1.

Recall that this simply says that deciding which player will first have to move into a chain only depends on the parity of the number of turns left to play in that region.

For positions in which chain parity was not determined yet, there was the concept of equivalent positions, that is, in which the same delaying options exist in each region. Positions which are equivalent in this sense will be said to be equivalent Nimdots positions and will have the same Nimdots value.

Two Nimdots regions are equivalent if you can move into the same equivalent Nimdots positions. So, one can see that the Nimdots value can be computed from knowledge of the Nimdots values of all the positions you can play into. This method of computing Nimdots values should work, since final positions are simpler, since they have fewer options. It may seem hard to believe that this always works, but this way of building up values for positions is guaranteed to work for all combinatorial games.

For example, one can try to computer the value of the region

From this position, all moves resolve the chain question, so all moves will result in a value of 0 or 1. If you make a chain, then the result is 0, as decided above. If you decide to prevent a chain by sacrificing two boxes, then you leave your opponent the last delaying move (another two box sacrifice). This means that the second choice moves into a position with value 1.

Therefore, the options from the diagram are to move into 0 or into 1. By definition, this position will be said to have value 2.

More generally, if you have a position in which the options are to move into any of 0,1,2, then the Nimdots value will be 3.

However, the rule is slightly more interesting if there is a missing value:

MEX Rule: The Nimdots value of a position in which you can move into the values A, B, C,... is the minimal excluded value among A, B, C,....

For example, if, in a Nimdots position X, you can move exactly into positions with values 0,1,2,4,5, then the position X has value 3.

The reason for this rule can be understood from the mirror strategy. Consider the Nimdots position X from which you can only move into any of the values 0, 1, 2, 4, 5. If you play that position against any other position Y which has value smaller than 3, then the first player can win on his first move: If the Y value is 2, for example, then you move into a position of value 2 from X and continue with the mirror strategy. The same if the Y position has value 0 or 1.

However, if the Y position has value 3, then you will always lose if it is your move. The reason is that if you move into 0, 1, or 2 from X, then your opponent will also move into 0, 1, or 2 from Y, then use the mirror strategy. If you move into 4 or 5 in X, then he will move into 3 from those positions leaving you with a 3 and 3 and a loss due to the mirror strategy.

Finally, you can see that if the Y position has a value bigger than 3, then you can win by moving into 3 from that position, leaving a 3 and 3.

So, this argument shows that position X will win against every value not equal to 3 but lose to the value 3, so X must have value 3. This same argument always works in general.

The Value of the 4-Corner

As an example of the Nimdots computation, I will indicate how one computes the Nimdots value of the 4-Corner.

To compute this value, one must build up a catalogue of Nimdots values, starting with the simplest ending positions, which all have value 0 (the player must move into a chain, or have to move on the board). The final answer is that the value of the 4-corner is equal 2. Since there many positions to cover, I will only follow one branch in the large tree of possible continuations.

The justification for the value 2 is that the possible positions one can move into have values 0, 1, 3. The value 2 follows from the MEX rule, since 2 is the smallest number not appearing.

DIAGRAMS

The first position has value 3, because the possible positions one can move into have values 0, 1, 2.

DIAGRAMS

The first position has Nimdots value 2, because the possible positions one can move into have values 0, 1.

DIAGRAM

The first position has Nimdots value 0, because it is a loss for the player to move, he has to move into a chain.

Using Nimdots Values

The basic difficulty with the Nimstring Strategy is that Nimdots values are difficult to compute. To make things harder, the knowledge of the Nimdots value of a region is not very helpful if you don't know the Nimdots values of all the positions you can move into. Therefore, to use the Nimstring Strategy, it seems that (human) players should stick to memorizing the values of certain positions, as well as all the values of all the positions that can be reached from that basic position. A good start is to figure this out for the 4-Corner.

The problems involved in computing Nimdots values can be worth the trouble, because there are some general rules which make them easy to use.

Zero game: A Nimdots position is a win for the second player if and only if its value is 0.

This says that in a Nimdots position, you have a theoretical win if and only if its value is not 0. In that case, you win by moving into a position which has value 0.

In terms of Nimdots values, the mirror strategy simply says.

Mirror rule: Combining two Nimdots positions with equal values gives a value of 0.

This is the simplest case of a completely general rule for combining Nimdots values.

Nimdots addition: To compute the value of the Nimdots position X composed of the independent Nimdots positions A, B, C,..., having values a, b, c,... you write a, b, c, in base 2 and add without taking carries.

DIAGRAM

For example, in this position, the board is split into three separate regions. One first computes the Nimdots value of each region. The analysis of the 4-corner shows that the Nimdots value of the top left region is 2 and the value of the top right region is 3. In the bottom region, the first player can force a unique chain, so the non-chain rule states that the Nimdots value is either 0 or 1. Since there are an odd number of total Dots in the bottom, the chain rule implies that this game is a win for the first player. Since there are an even number of edges placed in the bottom region, it is the first player's move, so the Nimdots value must be 1.

The three regions have values 1, 2, 3, and to compute the Nimdots value of the whole board, one uses Nimdots addition. Converting into base 2, one has 1 = 01, 2 = 10, 3 = 11. Adding without carries gives the result 00 = 0. One concludes that the position is a Nimdots loss for the player to move.


Nimdots and 5x5 Dots

In this position, Yellow has managed to attain all the basic objectives of the Nimstring strategy: He has set up a zero value Nimdots position at the top, a long chain at the bottom as well as winning the Nimdots position there as well. Therefore, Green will be the first to resolve the chain issue in one of the top regions, allowing Yellow to win the chain fight. In this continuation, Yellow uses the mirror strategy to his advantage and easily wins the game. However, Green did not make full use of the resources available to him, and has a number of tying moves. Perhaps the simplest one is the following. This moves threatens to make a quad, leading to a standard tie. It is seen that Yellow cannot prevent Green from making that quad. Indeed, Green's clever move has the advantage that Yellow can prevent the quad only by resolving the chain issue in that region, in which case Green wins by making the corresponding move in the other region.

This seems to indicate that the quad is the key to Green's defence when Nimstring considerations are not his favor. Since Nimstring will always favor Yellow when the board is split into three in this way, it makes sense that Yellow should try to prevent a quad as early as possible. In particular, Yellow can try to do this in the opening. I therefore adopted the following "anti-quad" opening to mathter unsuspecting opponents.

This forces Green to adopt different equalizing strategies, since this opening effectively prevents the standard quad ties.


Nimstring Strategy in Action

In the game ilanpi (Yellow) versus x0x_iceman2_x0x (Green) of February 10, 2003, the play from the above diagram continued.

Yellow's Turn 9 also threatens to connect the two left regions making a single chain and winning the game since Yellow will be able to prevent a chain on the right. It should be noted that Yellow a slightly stronger pivot move on his ninth turn, that is, placing the edge perpendicular and to the top left of the actual ninth move. This carries the same threats, but leaves yellow a stronger position on the bottom after Green has made the same response as in the game. As it is, Green has very few saving moves.


David Wilson's 5x5 Dots oracle shows that there are exactly five Green moves preserving a tie, that is, all other Green moves will lose the game, with best play by both sides.

It is not an understatement that understanding why these moves, and only these moves tie, remains somewhat obscure to the human mind.


The Game continued with Yellow's Turn 11 which split the board into three separate regions.

The Nimdots value of this position is 0, as was previously computed. This means that the position is a Nimdots loss for the player whose turn it is to move. This player will have to declare himself first in the top half of the board.

Green's 18th move must lose because it is a preemptive sacrifice which always loses if the number of boxes is equal, as I have proved. A similar proof shows that entering a chain always loses the corresponding Nimdots game, no matter what the number of boxes. One can therefore say that Green's 18th move was the culmination of Yellow's Nimstring strategy.

Indeed, if Yellow obstinately continued to try to force Green to commit himself first in the top two regions, then the game would have been a tie. For example, the game could have continued as follows:






Next Chapter

1