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.
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.
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.
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).
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.
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.
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.
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.
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.
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.
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.
The book suffers from a general lack of precise definitions
for Dots concepts. I have tried to give precise definitions
in the glossary.
What is given is a number of at the bottom left-hand corner of each
Dots diagram giving the number of
moves played, that is, how many edges there are on the
board. However, this number could be interpreted as the number of turns that have been played, since
this is would more directly indicate whose turn it is to play.
The fact that the moves = turns when no boxes are present reinforces
this belief. That is, until one gets to the diagrams for
Problem 5.4, 5.5, and Problem 5.14, where the number of moves
and the number turns have different parity since one box
has already been taken. This increases the possibility of
making the mistake of
forgetting which side you are.
Since the notation is not explained anywhere in the book, one has to
actually count the number of edges already placed then subtract the
number of boxes taken in order to know who is to play.
However, this method does not always work!
Whenever there is a board in which two adjacent boxes belong to
the same player, it is not possible to determine who is to play
without further information. This is because the boxes could have
been captured one by one, or by a doublecross. Therefore, in
the following problems, it is possible that either side is
to play:
Problems 3.15, 5.6, 5.7, 11.3, 11.6, 11.7, 11.20, 12.2.
Nimstring in Practice
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.
Is
there a Mathematical Road to Dots?
The Natural limitations of Dots
Specific Problems with Berlekamp's book