Quite a few mathematicians share my interest in games, and there is
even a field devoted to it: Combinatorial Game Theory. Why the
"Combinatorial" you may ask. That is because the name "Game Theory"
has already been taken by economists, though that theory is really
about running a business than about playing actual games, which
explains why people in that field win Nobel Prizes.
That being said, there is a substantial number of world
class mathematicians devoting much of their research to the study of
actual games. Many people (including mathematics hiring
committees) wonder why a serious mathematician would put so
much effort into games. I will simply quote serious mathematician
Aviezri S. Frankel, who has spent a lifetime trying to understand
games, and who gave the following justification for his obsession:
``Perhaps it is rooted in our primal beastly instinct; the desire
to corner, torture, or at least dominate our peers. An intellectually
refined version of these dark desires, well hidden under the
facade of scientific research, is the consumming strive
to `beat them all', to be more clever than the most clever,
in short -- to create the tools to Math-master them all in hot
combinatorial combat!''
The mathematician in me can't help but distill Frankel's
"Math-master" into a single word,
giving as rationale for my interest:
Computer hackers will glibly say: "It's easy, just use LISP".
Everyone else read on.
As I said, the mathematical field of
Combinatorial Game Theory is entirely devoted to
analyzing mathematical games.
The basic work on the subject is the series of books
Winning Ways by
Elwyn Berlekamp, John Conway, and Richard Guy. The first volume
lays out the theoretical framework for games. .
The basic mathematical theory of games was discovered by
John Conway as described in
his book
On Numbers and Games in which
he develops the remarkable framework
in which numbers (rational,
real, etc.) and sets are unified with games.
The second volume applies the theory to various types
of games and the authors give much specific analysis on how best
to play such games. Further developments are given in the
two volumes Games of no Chance
and
More Games of no Chance
which are collections of articles about all aspects of
Combinatorial Game Theory.
However, over the years, I started having some lingering doubts
about the relevance of all this theory to actual game playing.
First of all, there was Nim,
the oldest and most venerable mathematical game, which
a hundred years ago
was shown
to have a very simple mathematical analysis giving the winning
strategy as a simple mathematical formula. Well, it turned out that
I had encountered that game long
before knowing this analysis and was able to
play perfectly (in the basic position) without it, and
learning the analysis didn't help my game.
Then, in the Spring of 2002, I organized a seminar on Numbers and Games
at the Institut Henri Poincare in Paris.
I decided to end the course with a mathematical games tournament and
chose the game
Domineering, because it best illustrated the theory taught
in the class. Interestingly, there were four people
tied for second, one of whom
was a very good mathematician with years of experience
with Conway's theory while another was the sister of one
of the members of the seminar. She was still in High School and
had not attended any of the lectures, she had just practiced a lot
with her brother.
At this point, I became much more interested in the subject of
verifiable performance in mathematical games and started to
notice that there seemed to be a number of mathematicians
claiming that they were very good at mathematical games without
any objective standard to back up their assertion. My basic
question was:
I found the perfect way to answer that question when
I discovered Yahoo Dots.
Dots and Boxes, or Dots, is a game played as follows: You connect
adjacent dots with lines, and when you make a box, you put your name
in it, and move again. The person with the most boxes at the end wins.
See an example game.
To play Dots right away, go to the
Yahoo Games
website, and
get an account. Then, go to
Yahoo Dots and start playing.
Though a traditional children's game, mathematicians recognized the
true potential of this game and developed interesting mathematical results governing its
strategy. These results can be divided into two separate parts: The
first is the chain rule, which dictates the
general strategy, and the second is
combinatorial game theory which can be used to evaluate
complicated Dots and Boxes endgames systematically
using the Nimstring Method.
The attraction of Dots to non-mathematicians is that it is a
board game which presents an intellectual challenge similar
to games like Chess and Go, but unlike these games,
Dots does not require tremendous study and effort
to acquire an appreciation
for the game and a achieve a good level of expertise. In fact,
Dots is an excellent preparation for the game of Go with which it
shares some similarities.
Dots has recently achieved a new level of popularity since it
can now be played on the Internet on the
Yahoo Games website.
This has allowed many players from all over the world to
play the game, introducing it to areas where it was completely
unknown. Moreover, Yahoo
rating system has finally given an objective standard by
which Dots players can compare their ability.
For this reason,
I decided to use 5x5 Dots as a proving ground to discover
what exactly is required to achieve expertise in a combinatorial game where
objective standards and strong competition is available.
To my knowledge, this is the first time a mathematical game
has been tested this way.
It is important to state that almost all of the mathematical
theory of Dots and Boxes is due to eminant mathematician
Elwyn Berlekamp, who has pursued a life long interest in
the game. Berlekamp has recently written a
book about the subject, based on an equally interesting
chapter of the book
Winning Ways, volume 2.
Berlekamp's work emphasize the mathematical aspects of the game and he
repeatedly claims that each advance in Dots and Boxes expertise
corresponds to a mathematical insight and his book on Dots, as well as
the Dots chapter of Winning Ways concentrate on combinatorial game theory in Dots. The
latter is not surprising, since Winning Ways is the basic text on that
subject, but one might might have thought that his Dots book should
have contained more material on actual game strategy. Indeed, on page
40 of his Dots book (as well as page 521 of Winning Ways)
Berlekamp writes: "To win a game of
Dots-and-Boxes...you should try to win the corresponding game of
Nimstring and at the same time arrange that there are some fairly long
chains about. In the rest of this chapter we'll teach you how to
become an expert at Nimstring." But Berlekamp never ends up saying how
one becomes an expert at arranging long chains. Indeed, chain length
is one of the basic points of contention in a well played Dots game,
and observation of expert play reveals a definite dirth of long
chains due to effective
chain reduction techniques such as the preemptive sacrfice. I mention
this technique now for a reason: Nimstring theory says that
the preemptive sacrifice
should always lose and this exact point was
a cause for
confusion in a mathematical account of
Dots and Boxes.
Finally, I realized that Yahoo Dots has
led to a big surge in players whose main interest in the game is
winning, as opposed to mathematical enlightenment.
My Dots tutorial will concern only 5x5 Dots (4x4 boxes), and it is
certainly legitimate to wonder why only this special case is
considered in detail. Well, my belief is that a thorough understanding
of this particular game generalizes to more general boards.
The 5x5 board also has the advantage that is poses a significant challenge,
yet, with a reasonable amount of effort, it can be almost completely
understood. This makes the game particularly satisfying to the
mathematicians, who like complete answers. It will also appeal
to Chess and Go players, who may be discouraged by their game,
which can never be fully mastered, even with years of study.
Introduction
What is that title?
OK, I am a mathematician and I like to play games. Well, it would be
more accurate to say that I like to win games, but I find it
especially satisfying if I can use my mathematical wiles to do so.
Like the time I was in Antonio's Nut House, a bar in Palo
Alto, California, and
won a game of pocket billiards by continued use of safety
plays, and my opponent told me: "You play like a mathematician."
This was the ultimate compliment, especially since I
suspect she meant it in the
Evil Professor Moriarty sense.
Well, if you're like her and you think that tactics and strategy
are "dirty pool" then there's no point reading any further.
But, if you agree with me and disagree with her, then
I'm sorry to break the news to you: you have just passed
a test certifying you to be a nerd. The good news is that you might
enjoy reading what I have to say.
Mathematical Games
Dots-and-Boxes
Why this site?
Table of Contents
Introduction
1.1 The Basic Strategy
1.2 Getting better
Practice
Stages of a Game
All About the Chain Rule
Getting to Know Chains
Sacrifices
Life and Death
How to Count
Openings
Common Mistakes
1.3 Becoming Expert
Beyond the Chain Rule
The Preemptive Sacrifice
Nibbling
The Quad
It's not Easy Being Green
1.4 Masters and Non-Mathematicians
6x6 Dots
Handicap Dots
Studying Games
Consulting the Oracle
Living on the Edge
The Nimstring Method
2. Mathematical Theory of Dots
The Chain Rule
Combinatorial Game Theory
Computer Analysis
3. Can you Mathter Mathematical Games?
Other Games
4. Yahoo Dots
Yahoo Ratings
Abuse
Suggestions for Improvement
Chat
Glossary
References and Comments