Mathter of the Game

by

Ilan Vardi

(ilanpi on Yahoo Dots)






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.

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:

Become Mathter of the Game

Computer hackers will glibly say: "It's easy, just use LISP". Everyone else read on.

Mathematical Games

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:

Is there an objective way to tell if mathematics helps you play a mathematical game?

I found the perfect way to answer that question when I discovered Yahoo Dots.

Dots-and-Boxes

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.

Why this site?

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.







Table of Contents






Introduction

  1. What is that Title?
  2. Mathematical Games
  3. Dots-and-Boxes
  4. Why this site?




Table of Contents




1. Dots Tutorial


  1. An example game
  2. What's your level?
  3. Basic notation




1.1 The Basic Strategy


  1. Chains
  2. Doublecrosses
  3. Control and how to keep it
  4. The Chain Rule



1.2 Getting better

Practice


  1. Yahoo
  2. Dabble

Stages of a Game


All About the Chain Rule


  1. The Chain Rule for Other Boards
  2. The Non-Chain Rule
  3. Good Greed
  4. The Short Chain Rule
  5. The Zero Rule

Getting to Know Chains


  1. Recognizing Chains
  2. Cutting and Connecting
  3. Beware the join!
  4. Chain invasions

Sacrifices

  1. Tactical Sacrifices
  2. Positional Sacrifices

Life and Death


  1. The 4-Corner

How to Count


  1. Using the Chain Rules
  2. Cost of Living

Openings


  1. Basic Concepts
  2. The Fight for the Center
  3. Standard Openings
  4. The Yahoo Opening
  5. The Wilson Opening

Common Mistakes



  1. Forgetting who you are
  2. Sacrificing for Non-Chains
  3. The Doubletrap
  4. Errors in Winning Ways



1.3 Becoming Expert


Beyond the Chain Rule

The Preemptive Sacrifice


  1. Aftermath
  2. Prevention
  3. Care and Feeding of Chains
  4. Skip This Proof

Nibbling


The Quad


  1. One Quad
  2. Two Quads

It's not Easy Being Green

  1. The Standard Ties
  2. The Standard Losses



1.4 Masters and Non-Mathematicians

6x6 Dots

Handicap Dots


Studying Games


  1. Using Dabble
  2. Scoresheet for 5x5 Dots
  3. Scoresheet for 6x6 Dots

Consulting the Oracle

Living on the Edge

  1. The Third Chain
  2. Pivot Moves

The Nimstring Method


  1. Beyond Life and Death
  2. The Mirror Strategy
  3. When are Two Regions Equal?
  4. Beyond Parity
  5. Nimdots: The Theory of Delaying Moves
  6. Nimdots Values
  7. Using Nimdots Values
  8. The Value of the 4-Corner
  9. Nimdots and 5x5 Dots
  10. Nimstring Strategy in Action




2. Mathematical Theory of Dots




The Chain Rule


  1. Proof of the Chain Rule
  2. Euler's Theorem
  3. Toroidal Dots and Other Games



Combinatorial Game Theory


  1. Strings and Coins
  2. Nimstring
  3. Nim
  4. Combinatorial Games



Computer Analysis




3. Can you Mathter Mathematical Games?


  1. The Unreasonable Ineffectiveness of Combinatorial Game Theory
  2. A Brief History of Dots
  3. Dots come of age
  4. The myth of Dots and Boxes
  5. The Failure of Nimstring
  6. Nimstring in Practice
  7. Is there a Mathematical Road to Dots?
  8. The Natural Limitations of Dots
  9. Specific Problems with Berlekamp's book



Other Games


  1. Go




4. Yahoo Dots

Yahoo Ratings


  1. The Rating System

  2. Dots Hierarchy

  3. Chess Ratings

  4. Comparison with Chess

Abuse


  1. Boosting
  2. Impostors
  3. Dealing with cheating
  4. Being a good games player

Suggestions for Improvement

Chat

  1. Jargon
  2. ASL
  3. Trash Talk




Glossary




References and Comments







Counter







1