# Q&A with Elwyn Berlekamp

re: Dots-and-Boxes, Choppy Waves, and Psi Day.

Elwyn Berlekamp

MM: Apart from your early experience with Dots-and-Boxes, in what ways does it stand out to you as an interesting game to study?

EB: It’s closely modeled as an impartial game, Nimstring. Yet its deviations from that model become significant at higher levels of play. It’s also a game on which traditional methodologies for computer strategies, involving lookahead over limited depth, or sampled longer lookaheads, have all failed to date, and seem destined to continue to fail.

I now think mathematical Go and Coupon Go are even more interesting in some respects.

Dots-and-Boxes

MM: Is there a Dots-and-Boxes puzzle, a gem of a move, anecdote, or just a fun fact about the game that you could share with us?

EB: My favorite example appears on the cover of my booklet. Its explanation appears near the end of the booklet.

MM: Is there a winning strategy for Dots-and-Boxes?

Yes. But only for small sizes of boards, and only a few of us know what it is.  Chapter 1, page 9 of my booklet explains how second player can guarantee a win on the board with 16 dots, ending with 9 boxes.

MM: Will you tell us a little bit about combinatorial game theory in general?

EB: There are lots of games for which one can find a mathematical strategy that guarantees a win, at least from many endgame or middle-game positions if not from the starting position. Usually this is because the position can be partitioned into several components, each of which can be analyzed separately. The results of these analyses are often reasonably sophisticated mathematical objects, more complicated than “numbers”. But combinatorial game theory provides a way to add them. The sum then falls into one of these four categories:

• ZERO, which implies that whichever player goes second can win.
• POSITIVE, which implies that no matter who plays next, the player playing Black (often called “Left”) can win.
• NEGATIVE, which implies that no matter who plays next, the player playing White (often called “Right”) can win.
• FUZZY, (meaning it is a non-number of a sort which is incomparable with zero), which implies that whoever makes the next move can win.

It’s a very beautiful theory, once you learn the basics of it.  (But that’s not easy.)

MM: Could you tell us some about how you were involved in starting the “Gatherings for Gardner”?

EB: I went to a Puzzlers’ convention in the late 1980s and met Tom Rodgers. Circa 1990, he called me and explained his vision for the first Gathering, now denoted as G4G1.  He wanted me to recruit some mathematicians who might be interested. I agreed, and did so. The first gathering was a success, and we decided to do a second three years later. After that we’ve continued every other year. The eleventh will happen in Atlanta in spring 2014.

MM: You have worn and wear a lot of different hats in your working life—researcher, entrepreneur, teacher, author, board member. Could you tell us about the kinds of things you do now on a “typical” day?

EB: No day is typical. One unique task today is answering this questionnaire.

I still have several “irons in the fire”. Preparations for my talk coming up to some collegiate Go enthusiasts from many colleges and universities who are convening at Harvard on March 23. That talk will entail another trip to the east coast, on which I’m arranging to see several other people at different locations on different adjacent days. Another talk I’m giving to an audience of academically-based engineers at Stanford on April 5 requires a different preparation.

MM: What current projects are you involved in that you’re excited about?

EB: Both of the talks just mentioned. It would be great if I could connect with some enthusiastic grad (or conceivably undergrad) student who is versed in combinatorial game theory, computer science, and who plays Go as a high ranking amateur. I think there’s some chance such a person might surface on March 23-24.

I’m also engaged in several efforts trying to help broaden the outreach of mathematicians/engineers/scientists into the general public. All such attempts pose many challenges, but some have been showing some signs of hope.

MM: Can you compare the kind of thinking involved in doing research mathematics and the kind of thinking involved in working in finance?

EB: I’ll give an indirect answer: With many mathematicians, I sometimes try to get more of them interested in some of my own favorite topics. But I’ve found it to be even harder to get most financial types interested in much of anything except immediate profit. Many of them also tend to be quite arrogant. Most of the hardest problems in the world, as well as in many people’s personal lives, aren’t solvable by money alone.

MM: Who are your mathematical heroes?

EB: John L. Kelly, Jr (actually a physicist by training) was my first and most influential boss and mentor at Bell Labs. He died of a heart attack in his early 40s. Peter Elias was head of the EE department at MIT, where, in the very early 1960s, he led a program to inject significant amounts of discrete mathematics into their undergraduate curriculum. I was perhaps the biggest early beneficiary of that effort.  Claude Shannon was perhaps the most awesome and legendary of all the folks I had the opportunity to work with.

As a high school student and then as an undergraduate, I followed Martin Gardner’s references to papers by Richard Guy and Sol Golomb, and was quite awed by each of them, even after they became my close friends and collaborators starting in the mid-1960s. Richard Guy connected me with John Horton Conway at a 1969 conference in Oxford, and we then certainly had major influence on each other. Other personal heros are Gus Solomon and Lloyd Welch, who together taught me most the algebra I learned between 1964 and 1968. And my brother-in-law Charlie Warden, who died in 2011 without ever finishing his PhD, but who answered all of my many questions and taught me lots over Christmas vacation 1957, when he was a math graduate student and I was a senior in high school.

Among those who came and passed before my time, I’d have to include Charles Bouton, who solved “Nim” in 1901, which I credit as the beginning of combinatorial game theory. And Sprague and Grundy, whose works greatly expanded the subject in the 1930s.  And Cedric A. Smith, an early collaborator of Richard Guy.

In algebra, I’d mention Dickson and van der Waerden in the early 20th century and Mathieu and Galois in the 19th. And we’re all forever indebted to Gauss, Euler, and to various Arabs who invented Al-gebra and Al-gorithms when their culture thrived during Western Europe’s “Dark Ages”, and others all the way back to Euclid and Pythagoras.

MM: What do you like to do besides math in your spare time?

EB: 1. Bicycle riding.  2. Politics, especially in defense of science, including biological evolution and the emerging science of disruptive climate change.

MM: Many of our Math Munch readers are young people. Are there any closing thoughts you’d like to share with them?

EB: 1. Seek out and find one or more mentors. My first was an engineer named Herb Fuldner, who got me interested in a now-classic penny-weighing problem when I was in the fifth grade.  (See below.)

2. Find a source of problems or puzzles which are too hard to solve in a single sitting. Work on them for at least a couple days before asking your mentor for help.

3. Follow your curiosity and interests, even if they stray from the conventional. But don’t neglect the basics either.

*****

EB: Here’s the penny-weighing problem that caught my interest when it was popular in the late 1940s:

You are given 12 coins, of which 11 are genuine and 1 is counterfeit. They are all mixed up and they all look the same. The weights of the 11 genuine coins are identical, but the weight of the counterfeit coin is known to be slightly different, but you don’t know whether it’s heavy or light. You are also given a balance scale, on which you can way any two subsets of coins against each other. Can you find a strategy which ensures that you will find the counterfeit coin in at most three weighings?

### 4 responses »

1. how long did it take you to think of this theory?
was it hard to put the boxes and dots in a specific place

2. What thoughts did you have accomplishing this theory?
What was your motivation behind establishing this game?