3. Can you Mathter Mathematical Games?

Chapter 3 of my Dots page

by

Ilan Vardi

(ilanpi on Yahoo Dots)


The Unreasonable Ineffectiveness of Combinatorial Game Theory

For some time, I had been wondering whether detailed mathematical analysis was relevant to game playing, and my main interest in Dots and Boxes was to try to understand whether this theory was required to become a very good player. It was my opinion that Dots is similar to other board games like chess and go, in the sense that mathematical theory, has little or no relevance.

Of course, one has to mention that combinatorial game theory has shown that many mathematical games are "hard" in a theoretical sense, that is, NP-complete, see the survey article of Aviezri Frankel. Indeed, NP-completeness is also true for Dots-and-Boxes, as is proved in Winning Ways. However, this result only show that Dots-and-Boxes becomes hard as the board size grows to infinity, so does not impact the most popular versions of Dots-and-Boxes played on 5x5 and 6x6 boards. Similarly, the NP-completeness of a class of chess positions played on very large boards is not relevant to regular chess

It is my belief that standard board games like Chess, Go, and Dots, are mostly about handling technical details, once a few general abstract concept are assimilated. I consider them to be the equivalent of doing long mental multiplications, a difficult task for most people, even though most people understand the underlying principles of multiplication exteremely well.

Acquiring technical ability in board games is mostly a question of experience, as is indicated by psychological studies of chess players (de Groot), that is, playing thousands of games. These studies also show that one phenomenon separating very good players from less able counterparts is that in many crucial positions the weaker player will not even examine the correct move. This is very important in understanding how to improve: lessons, abstract knowledge, and other passive activities have very limited success: they won't help you to find the right move.

The mathematical theory described by Berlekamp is a technique for figuring out subtle Dots endgames and uses a reduction to Nim, a famous mathematical game, first analyzed completely a hundred years ago by Bouton, who showed that Nim positions can be completely understood using a simple mathematical formula.

In fact, my interested in Dots started when I realized that I had been playing Nim for a long time with good success, but I had never used the mathematical formula. Like many people, I had learned Nim (actually a slight variant called "Misere Nim") by watching the classic movie "Last Year at Marienbad" in which the game plays a prominent role. A mysterious stranger appears and beats all comers, obviously a metaphor for the inevitability of certain stuff, leading some of the protagonists to state that he is using mathematical formulas ("logarithms"). In fact, viewing the relevant scenes in slow motion reveals that his opponents are playing poorly, and he is able to take advantage of his mistakes.

Being a self-respecting nerdly 14 year old, and not being too challenged by my classes, I spent the next 3 days doing a complete analysis of the basic Nim position of the movie. I memorized a number of key positions and could reduce all other positions to these. In this way, I learned to play perfect Nim years before hearing about the mathematical theory. In my limited experience, I can do well against someone who has learned the mathematical theory. I will further conjecture that even a player starting out with the mathematical theory will start using the reduction and memorization method after a while.

The potential for uselessness of the mathematical theory was truly highlighted in the Spring of 2002, when I taught a seminar on Combinatorial Game Theory at the in Paris. I ended the seminar by organizing a Domineering tournament for the participants of the seminar. Domineering has a much richer mathematical theory than Dots and Boxes since all kinds of surreal numbers and much more, appear.

Well, the tournament was won by one of the seminar participants, but tied for second place was the sister of one of the participants. She was a high school student who had not come to any of the lectures, and had simply learned the game by practicing with her brother. Also tied for second was a very strong mathematician having years of complete familiarity with combinatorial game theory.

I had limited my choices for the tournament were essentially limited to Domineering and Dots and Boxes, since I knew that there had already been successful tournaments played with them at an MSRI workshop on combinatorial game theory, see the account by Julian West in the book Games of no Chance by Richard J. Nowakowski. I finally chose Domineering because it was a better illustration of what I taught in my Numbers and Games seminar.

Six months later, I discussed this issue on the Usenet group fr.sci.maths with mathematician Denis Feldmann who stated that he was very good at mathematical games. But it occured to me that it is not at all easy to verify that you are good at a mathematical game. This was confirmed by the results of my Domineering tournament. I wanted to find a mathematical game in which ability could be judged by some objective criteria.

I finally decided to try to learn to play Dots for real, when I saw that it was on Yahoo Games web site. Not only were the games rated, thus giving a criterion for comparison, but I would also be able to ask the best players whether they knew anything about the mathematical theory.

So, on November 24, 2002, I played my first game on Yahoo Dots.

A Brief History of Dots

Before describing recent Dots advances, I will briefly outline what I know about Dots past.

There is Dots prehistory, consisting of countless unrecorded games played without the basic strategy.

Dots History is almost entirely due to one person, master mathematician and Dots-and-Boxes player Elwyn Berlekamp. A professor at the University of California, Berkeley, Berlekamp has a distinguished list of mathematical achievements in numerous areas which include algebraic coding theory (his textbook is a classic) algorithmic number theory (his polynomial factoring algorithm is at the heart of every computer algebra system), etc., and of course, mathematical games. He has written a number of books on the subject, including his book on Dots, and similar book on Go, and is a co-author of Winning Ways. A number of Berlekamp's students, have had an impact on game theory. Notably computer analysis in chess, David Wolfe co-author of the Go work, and Katherine Scott who has worked about Dots-and-Boxes. Berlekamp was also instrumental in organizing conferences on combinatorial games at MSRI.

In the Preface of his Dots and Boxes book, Berlekamp describes his life-long interest in Dots and Boxes. He discovered the basic strategy while in Junior High School, and he examined the game in more depth, eventually writing the chapter on Dots and Boxes in the second volume of Winning Ways.

I first met Berlekamp in 1986 when I invited him to give a lecture at a seminar on Numbers and Games that I was running. Though he spoke about Domineering, we started off the talk by playing a few Dots and Boxes games in front of the class. Since these were actually my first games ever, I don't think he had too much trouble beating me.

In fact, one must wonder what competition he faced during these years. As far as I know, there weren't any Dots and Boxes tournaments organized before 1994, and, without any Dots servers, it was not really possible for people to play except face to face and with pencil and paper. It appears that Berlekamp had to pick his competition from random members of the mathematical community, none of whom were skilled players, as in our 1986 match.

One example was related to me by Peter Sarnak. In the mid-1970's, Sarnak came to Stanford University to pursue graduate studies in mathematics. Already a master level chess player, he had composed a chess position which had an infinitesimal value, according to Conway's theory of Numbers and Games. He therefore went to Berkeley to visit Berlekamp, Conway's co-author, and show him the result. When Sarnak entered Berlekamp's office, the latter exclaimed: ``I am the World Dots-and-Boxes Champion. By entering this office, you have challenged my title. You must now play!'' So, they played a game, which was won by Berlekamp, poor Peter never having never played Dots before. After that game, Berlekamp had to rush off to a meeting, since he was department chairman at the time, and Sarnak never got the chance to show him his chess position. Unfortunately, he did not pursue this interest further and about 10 years later, Harvard mathematician Noam Elkies, also a master level chess player, developed an interest in the same question, but he published his result in a paper called "On Numbers and Games", which appeared in Nowakowski's book on the 1994 MSRI conference on Combinatorial Game Theory. Sarnak did go on to a brilliant career in Number Theory and Analysis, his latest work being on the relation between Physics and prime numbers. If that doesn't mean anything to you, he was the chairman of the Princeton Math Department, considered one of the best in the world, and was a recurrent character in ``A Beautiful Mind'' (the book, not the movie).

Therefore, I find it very impressive that Berlekamp was able to continue to find new ideas and write about the game, even though he did not face adequate competition.

Dots comes of age

Two recent advances have completely changed the nature of Dots and Boxes.

The first is the fact that Dots and Boxes can now be played on the internet on Yahoo games on the Yahoo Dots site. Not only does this allow players from all over the world to meet and play, but it also ranks them according to performance, using a rating scheme similar to chess.

The second advance consists of two very useful computer programs. The first is the program Dabble, written by J.P. Grossman. It plays at a very high level (about 2200 Yahoo), and can be easily downloaded from this website. Dabble allows you endless hassle free practice against a worthy opponent (and without connection fees).

An equally significant program is a Dots and Boxes analysis program written by David Wilson. This program gives the optimal analysis for many positions and is very useful for understanding the openings.

These changes have transformed Dots and Boxes from a game played only by children and a few mathematicians, into a popular game with much more objective performance criteria.

To best understand the significance of this change, one examines the games played by mathematicians in the old days before Yahoo and programs, in particular, the final of the 1994 MSRI Dots tournament, recorded in Julian West's article. One must assume that the players were representative of the better Dots players of that time, since the tournament was organized during a workshop on combinatorial games attracting game experts from the world over. One can also assume that the 500 dollar winner take all purse was a motivating factor to sustain the play at the highest level possible.

However, the moves of game 2 reveal that the second player (who lost the game) was an almost complete beginner, since he did not follow the most basic principles of Dots openings. His first five moves consist of placing edges on the side of the board, totally ignoring the fight for the center which characterizes the opening of a well played game, and leaving his opponent a free hand to cut up the board into as many regions as he wants. There is a complete analysis of this game, after the openings moves, by David Wilson, using his analysis program.

In Yahoo Dots, such opening strategy is usually abandoned by players by the time they reach a rating of 1800, which roughly corresponds to a 1500 chess rating.

One can wonder at this strategy. Perhaps it was played in analogy with Go in which the opening moves are now always played near the edge of the board. Even that doesn't seem right, since opening moves on comparable size boards are usually played at or near the center, see some 9x9 games played by professional players.

But the surest sign that Dots and Boxes has finally come of age is that the top Yahoo players are almost all under 20 years old, some as young as 14 years. In the end, Berlekamp's title "Sophisticated Child's Play" has proved to be visionary.

The Myth of Dots and Boxes

In his books "Winning Ways" and "The Dots and Boxes Game," Berlekamp stresses that each of his new levels of Dots proficiency has corresponded to a new level of mathematical awareness of the game. This has become the mathematical canon, as it is being repeated in other articles about the game written by mathematicians. This progression, as quoted by Julian West, is:

  1. abandon the greedy approach in favour of double-dealing moves;
  2. learn the parity rule for long chains;
  3. become an expert at Strings-and-Coins;
  4. (and so) become an expert at Nimstrings;
  5. apply Twopins theory; become an expert at Kayles;
  6. recognize the exceptional cases where Nimstrings does not suffice to analyse Dots-and-Boxes.

In the notation of this work, Step 1 is learning about doublecrosses and control and Step 2 is the chain rule. Therefore, the first two steps are exactly the Basic Strategy recommended here. Nimstrings is exactly the same game as Nim Dots, while Twopins theory and Kayles belong to combinatorial games.

Well, I'm sure anyone with a little Dots experience will agree with the first two items, since they exactly comprise the basic strategy. However, I have yet to meet a player on Yahoo Dots who knows anything about the further items, except for maybe the last one, with the word "exceptional" removed (note the hybrid spelling of that item, perhaps a Canadian characteristic). One can compare the above description with what I believe to be my own Dots progression with the corresponding Yahoo rating (roughly equivalent to a 500 point lower chess rating).


  1. 1700-1800 My initial level. Knowledge of the basic strategy, but having difficulty "seeing" the board, e.g., overlooking simple captures.
  2. 1800-1900. Have completely understood the implementation of the basic strategy, but still making mistakes like as needlessly giving up boxes during the neutral phase.
  3. 1900-2100. Can consistently win the chain fight, yet will consistently lose these games to better players.
  4. 2100-2200 This roughly corresponds to the level at which I learned how to win a game despite losing the chain fight. This appears to be the first big hurdle in Dots separating experts from good players.
  5. 2200-2300. I begin to understand the quad (4-cycle) allowing me to reach the standard ties and so consistently tie as second player. To understand the quad, I start making a list of endgames with quads and figure out their values. This conceptual shift from short term strategical goals to plans based on achieving specific endgames appears to be the second and final hurdle required to achieve Dots expertise.
  6. 2400-2500 A complete understanding of all endgame combination with chains and cycles. Can apply Nimstring strategy in some rare cases. Still having difficulty in unusual openings and openings which do not have clear strategical options. About 10 people at this level, where about two thirds of games are ties.
  7. 2600-2700 An almost complete shift to analysis based on knowledge of endgames. Choice of openings minimizing strategical thinking and requiring most analytical skill and endgame knowledge. Can identify weaknesses in opponent's game and will adapt play. Very few players at this level. Must give almost all players a second player handicap.
  8. ? Optimal Dots. Players know everything about the game and optimize their winning chances by playing moves which maximize dynamic tension by keeping the number and nature of regions unresolved as high as possible and reducing the number of correct moves on both sides to a minimum. As before, players choose positions in which general strategy does not apply and correct moves can only be found by complete analysis. For an example of such play by both sides, see the perfect game, generated by David Wilson using computer analysis. This player will also try to set up pivot moves and knows all about Nimstring strategy. I have not observed any such players on Yahoo Dots.

The Failure of Nimstring

In fact, there are at least two important cases in which the loser of the Nimstring game will win or tie the Dots-and-Boxes game!

DIAGRAM

The first is the situation in which there are no chains or cycles. With even material, such a position will always favor the loser of the Nimstring game. The reason is that without any chains or cycles, the game ends with a greedy exchange of short chains (chains of length one or two), in which the players give up the smallest chains first and the largest last.

By definition, the Nimstring loser will be the last person to move, so he will always be favored in this exchange, that is, the worst he can do is tie. More precisely, with even material and no chains or cycles, the game will be a win for the loser of the Nimstring game unless there is an even number of 1-chains and also an even number of 2-chains.

I have called this observation the zero rule. Since cycles aren't counted as chains, the zero rule generalizes to some cases in which only cycles are present, as the reader may easily verify. Another interesting example of this principle is given by Berlekamp in Problem 11.19 of his Dots-and-Boxes book.

DIAGRAM

Here the first player has the choice between making a cycle or a chain. In the first case, he wins the chain fight (zero chains) and the Nimstring game, in the second case, he loses the chain fight (one chain) and the Nimstring game as well. But, it is easy to see that in either case, the boxes belonging to chains and cycles will be evenly split 8-8. The winner will therefore be the winner of the short chain battle preceding the first forced move into a chain or cycle. Since there is an odd number of 1-chains, this means that the winner of the game will be the loser of the Nimstring game, as above. The first player therefore wins by ensuring a unique chain, contrary to the 6x6 chain rule.

The other catastrophic failure of Nimstring theory is the preemptive sacrifice, a very effective chain reduction technique, and also a loony move which is always a loss in Nimstring. For example, the above position arises in Problem (c) on the Dots-and-Boxes Chapter of Winning Ways. The second player is faced with a lost position since the first player has managed to win the chain fight (Nimstring game) as well as ensuring a long chain of 6 boxes. In Winning Ways, this position is given as a 9-7 win for the first player.

However, the second player ensures a tie by making a preemptive sacrifice of three boxes. The idea is that the chain of three boxes on the right will quickly bloom to its full size of five, so the second player, who will have to move into this chain sooner or later, decides to do it sooner. This prevents the chain from growing further, and will allow the second player to take those extra two boxes for himself in the exchange of short chains (length less than three) preceding the first forced move into a chain. Players familiar with game theory will recognize this sacrifice as a loony move, that is, a move which always the player offered the sacrifice to decide which side he wants to continue the game as (strategy stealing). Obviously, this means that the player being offered this sacrifice will always win the corresponding Nimstring game, where box counts don't matter, only who plays the last move.

This move is a point of confusion for mathematicians who have read about Nimstring but have not played Dots-and-Boxes extensively. Thus, in Julian West's analysis of the second game of the final of the 1994 MSRI Dots tournament. In that game, the second player made a preemptive sacrifice and West goes on to state that it was equivalent to a resignation, since it was a loony Nimstring move. In fact, the preemptive sacrifice in this game is ineffective and does not influence the final score.

Game theorists should note, however, that the strategy stealing argument does imply that the preemptive sacrifice will always lose if you are not already ahead in captured boxes. Indeed, using it to tie requires at least a one box lead, while a win is possible only with a two box lead (odd total number of boxes) or a three box lead (even total number of boxes). See my proof of this result, and Problem (h) of Winning Ways for a 6x6 example.

One can argue that the first Nimstring counterexample is not a failure of Nimstring theory, since that example shows that Nimstring will still be a good (negative) indicator of the final Dots-and-Boxes result.

As for the second counterexample, it is important to note that Berlekamp is very well aware of the preemptive sacrifice, since he mentions it in his solutions to the Winning Ways problems.

Indeed, one can make a correct and convincing argument that the preemptive sacrifice is not relevant in endgame Nimstring computations, exactly where this theory is most useful. However, one cannot lose sight of the fact that able mathematicians have been confused about the application of Nimstring theory. It is therefore important to understand the role of Nimstring in actual Dots and Boxes play.

Nimstring in Practice

My Dots experience clearly indicates that the difference between a good player (< 2100 Yahoo rating) and an expert player (> 2200 rating) is that the expert is able to consistently win the Dots-and-Boxes game despite losing the corresponding Nimstring game. This is described in detail in my tutorial on expert play. In Dots terminology, you have to learn how to win the game despite losing the chain fight, that is, letting the opponent get the correct number of chains predicted by the chain rule.

This is confirmed by the fact that even when using Nimstring Strategy to obtain a winning position, one may have to abandon it in order to actually win the Dots-and-Boxes game. For example, in this model game Nimstring Strategy was used to obtain a winning position, but insisting on carrying it out would have only tied the game.

My Dots experience also seem to indicate that Nim type computations attain some degree of relevance, but only at the highest level of play, as I describe in the section for Masters and Non-Mathematicians in my Dots tutorial. Nim reasoning is most useful in endgame position in which there are a number of separate unresolved areas of the board, as a way determining delaying moves before life and death (deciding whether to make a chain) must be resolved. Since this theory is a a refinement of Life and Death, it must necessarily be studied subsequently. In fact, Life and Death itself requires a thorough understanding sacrifices and other tactics. One therefore concludes that the application of combinatorial game theory will come later rather than sooner, in the normal development of Dots technique. I will even venture to say that it will come last, as it does in my Dots tutorial.
Once again turning to practical 5x5 Dots play, my experience indicates that the unresolved regions are usually two 4-Corners, and that the first player will usually be able to win the Nimstring battle on the rest of the board, forcing the second player to commit himself first.
However, the second player can force the creation of a quads, that is a 4-cycle, usually ensure a tie. Indeed, in the subsequent position the first player loses if he tries to prevent a quad, since he will have to lose the chain battle in order to do so, and this after having sacrificed too many boxes, with a long chain around.
All this being said, the first player can play for this type of position, but in more favorable conditions such as the following, which is a win, since the second player can no longer force a quad.
This consideration has a significant effect on the opening of 5x5 Dots. In particular, the first player can play the following type of move in the opening, preventing the quad defence at a very early stage. The second player must now be aware of Nimstring type reasoning in order to avoid being stuck in a loss of the type given in the previous diagram. This game is an example Nimstring strategy in action.

Note that mathematical considerations ensure that the creation of a unique chain on the bottom of the board and two regions on the top guarantee that the first player will win the Nimstring battle, and, without special considerations such as odd number of short chains or cycles, the first player is ensured a win. Once again, expert players may be able to discover this fact for themselves, but the mathematical theory does seem to help assimilate this more efficiently.

However, such subtle considerations are only relevant to players who have completely mastered the technical aspects of the game. It illustrates my opinon that Dots, like Go and Chess, is dominated by details of implementation, such as tactics, and theory can only be applied once these overwhelming factors have been completely mastered. The relevance of this point can be seen by the fact that Berlekamp makes Nim comments about certain positions in which he has overlooked simple tactical points determining the outcome, see my corrections to Winning Ways problems.

As for the application of Nimstring theory to specific position, it seems to me that an experienced Dots player will be able to find the right move by direct analysis and will not require Nim transposition. This seems to be confirmed by the fact that I can solve many of the problems in Berlekamp's book without using Nim theory. I have little doubt that the top Yahoo Dots players can do the same, except much faster, though it seems clear that at the highest level a Dots player will have to construct a theory of delaying moves, and will create a table of key positions and their values, though it might perhaps more complicated without knowledge of the theory. This is consistent with my earlier point that I don't use Nim strategy to play Nim.

My conclusion is that knowing combinatorial game theory will simplify analysis, and help understand opening theory. It seems clear to me that this could also have been achieved without this knowledge, A good Dots player should be able to reach similar conclusions, perhaps without the same clarity. Perhaps the mathematics facilitated my progress due to my own mathematical sensibilities and ease with this type of reasoning.

Berlekamp himself raises doubts about the usefuleness of combinatorial game theory in the Preface of his book (page xi) where he states: "While teaching this course, I found a considerable gap between Nimstring theory (especially the composed `vine' problems which illustrate the power of this theory so well) and the advanced chain-counting techniques of Chapter 4, which prove so powerful in actual play."

I believe that Berlekamp has identified the problem exactly: Combinatorial theory becomes more relevant in very large boards with many small regions or problems to be resolved. In actual play on the 5x5 board, there are usually very few regions, and the few Nimstring type positions which come up are well known to top players.

Is there a Mathematical Road to Dots?

My main conclusions about the application of mathematics to Dots is the following: Mathematical analysis of Dots and Boxes is most relevant to the chain rule and its consequences. Indeed, understanding the proof of the chain rule allows one to assimilate the techniques of Dots at an accelerated pace.

It is true that all good Dots players know the chain rule and most of its consequences, and simply use it as as an umproved heuristic, but it seems clear that an understanding of the basic ideas of the proof definitely helps one attain an expert level of play, in particular, understanding the aftermath of a preemptive sacrifice and how a quad affects the chain count and the final phase.

However, I do not believe that mathematical analysis is of much help beyond this. In particular, I believe that combinatorial game theory is not required to be an expert player, as is confirmed by the fact that none of the best players I talked to on Yahoo Games knew anything about it, and that almost none of the games I played or observed ever applied any of its principles.

In fact, I believe that the most useful mathematical fact other than the chain rule is the rule concerning the minimal lead required to effect a preemptive sacrifice

In my opinion, Dots is a territorial game whose basic strategy is similar to Go, as I describe here. In the following part, I describe what I believe are fundamental principles of Dots play, all based on a typical heuristic "games" approach, like you would find in a Chess or Go manual.

I have two explanations for Berlekamp's use of combinatorial game theory. The first is that each person learns how to play Dots by using what he knows best. In Berlekamp's case, this was combinatorial game theory, and his knowledge and facility with various games like Nim and Kayles. The second is that, from a purely mathematical standpoint, Nimstring theory is the deepest and most interesting aspect of Dots, so a great mathematician will naturally gravitate towards this, rather than dwell on the myriad mundane technical points required to actually win a Dots game.

In conclusion, I would say that the mathematical structure of Dots allowed me to improve very quickly. By comparison, my progression at Go has been excruiciatingly slow, and after 3 months, I still feel that I have understood almost nothing about that game. In particular, I feel that I am completely unable to apply my mathematical skills when playing Go.

The Natural limitations of Dots

My experience with Dots seems to indicate that Dots is an easier game to master than Chess or Go, and that it is a more limited venue for competition. In particular, I reached a 2500 level and became one of the top Yahoo players in three months. By comparison, I reached a 12 kyu level (= -12 Dan) at Go in the same amount of time and with a similar amount of effort. Of course, this Go level is very far removed from the competent amateur level, which itself is very far below the professional level.

Perhaps this is due to a dirth of serious competition on Yahoo Dots: there are much fewer strong players than on Chess or Go servers. It also seems to me that there are natural limitation of 5x5 Dots means that there is not much further room for players to improve. Experience with 6x6 Dots indicates that this game does not present a significantly greater challenge. The real test of human ability would be to play against a program using exhaustive analysis, that is, a perfect player.

I consider this aspect of Dots a perfect justification for its use in testing mathematical theory: It implies that an almost complete understanding of the game can be achieved in a short period.

Specific Problems with Berlekamp's book

The book suffers from a general lack of precise definitions for Dots concepts. I have tried to give precise definitions in the glossary.

1