Games of No Chance MSRI Publications Volume 29, 1996
Preface
Combinatorial Game Theory, as an academic discipline, is still in its infancy. Many analyses of individual games have appeared in print, starting in 1902 with C. L. Bouton’s analysis of the game of Nim. (For exact references to the works mentioned here, please see A. Fraenkel’s bibliography on pages 493–537 of this volume.) It is was not until the 1930’s that a consistent theory for impartial games was developed, independently, by R. Sprague and P. M. Grundy, later to be expanded and expounded upon by R. K. Guy and C. A. B. Smith. (Guy is still going strong, as evidenced by his energy at this Workshop.) J. H. Conway then developed the theory of partizan games, which represented a major advance. Based on this theory, D. Knuth wrote his modern moral tale, Surreal Numbers. The collaboration of E. R. Berlekamp, J. H. Conway and R. K. Guy gave us Winning Ways, which “set to music”, or at least to “rhyme”, the theory so far. In the process, many more games were discovered and analyzed: but more were discovered than solved! This Workshop, held from 11 to 21 July 1994, gave evidence of the growing interest in combinatorial games on the part of experts from many fields: mathematicians, computer scientists, researchers in artificial intelligence, economists, and other social scientists. Players, some of whom make their living from games, also attended. Visitors such as D. Knuth and H. Wilf dropped in for a few hours or days and gave impromptu lectures. There was much cross-fertilization of ideas, as could be expected from a meeting of people from such varied backgrounds. One major paper by A. Fraenkel (pages 417–431) was conceived and essentially written during the Workshop, being inspired by V. Pless’s talk. But the Workshop was not all seminars. There were books, games and puzzles on display. Two official tournaments, Dots-and-Boxes and Domineering, attracted a lot of participants, and carried $500 first prizes (funded by E. R. B.) The final matches were shown over closed-circuit TV, so that the spectators could have a running commentary! (See pages 79–89.) Neither game is completely solved: Dots-and-Boxes is played by many school children, yet still holds mysteries for adults. The articles in this volume are divided into four groups. Part I is introductory. Part II contains papers on some of the “classical” games, such as chess and xi
xii
PREFACE
Go. Part III studies many other games, of greatly varying degrees of difficulty. Part IV contains articles that push the traditional theory in new directions: for example, by considering games more general than the strict definition of combinatorial games allows (see pages 1 and 363). The book closes with a list of unsolved problems by R. K. Guy, and a Master Bibliography by A. Fraenkel. The increasing role of computers can be witnessed throughout, in areas ranging from the solution of particular games to the use of the computer in teaching humans. Many thanks must go the staff of MSRI, who helped make the Workshop a success. The facilities were wonderful. Thanks are due also to the Workshop chairs, E. R. Berlekamp and R. K. Guy. Together with the rest of the organizing committee (J. H. Conway, N. D. Elkies, A. S. Fraenkel, J. G. Propp, K. Thompson, and myself), they put together a wonderful and rich program. In the preparation of this book, we are especially grateful to Silvio Levy, who essentially rewrote two of the articles, edited all the others, found good placements for the more than 200 figures, redrew some of them, and arranged the typesetting. Richard J. Nowakowski
All Games Bright and Beautiful
What is a combinatorial game? The usual definition is a game in which (i) there are two players moving alternately; (ii) there are no chance devices and both players have perfect information; (iii) the rules are such that the game must eventually end; and (iv) there are no draws, and the winner is determined by who moves last. In this section, two master expositors lead us through many examples of such games, and introduce the theory that has been developed to deal with them (pages 13–78). As an appetizer, you may prefer to read first J. H. Conway’s charming study (pages 3–12) of a game that does not satisfy this definition, because it may well be endless. Or, if you already know the basic theory and are dying for action, turn to the reports of the Workshop tournament finals, on pages 79–89; or download the Gamesman’s Toolkit, described on pages 93–98. Have fun!
Strides on Classical Ground
The origins of chess and related games are lost in time; yet, in spite of hundreds of years of analysis, they remain as interesting as ever, because of their fantastically large configuration space. The articles presented here are steps in the continuing endeavor to master these games, an endeavor in which the computer nowadays is often a valuable tool. In fact, the “simpler” board game Nine Men’s Morris has succumbed to computer analysis, as reported by R. Gasser. Checkers may well be on its way: J. Schaeffer tells of the development of the program Chinook, and pays a tribute to the extraordinary (human!) player M. Tinsley. N. Elkies and L. Stiller write articles about chess, computerless in one case and computer-heavy in the other. Shogi, also called Japanese chess, is Y. Kawano’s subject. The last four articles of this section deal with Go, a game that has come under intense scrutiny recently. Although it is a territorial game and not, strictly speaking, a combinatorial game according to the definition on page 1, the board breaks up toward the end into a sum of smaller independent games, a situation that the theory of combinatorial games handles well. Other aspects of Go, such as ko, require extensions of the traditional theory, as explained in two of these articles.
Taming the Menagerie
This section collects seven analyses of “simple” games in their dizzying variety: from the hitherto ignored sowing games (where counters are distributed from one pile to others, without ever being removed from the game) to take-away games (where there is only one pile, but the rule specifying how many counters can be removed may be fiendishly complicated). Not surprisingly, complete analyses are hard to come by, but several interesting general results are proved. There is also a description of a computer interface for Domineering, that archetype of partizan board games, amazing in its economy and elegance.
New Theoretical Vistas
Many authors have examined games that do not satisfy one or more of the conditions on page 1, or have otherwise extended the framework of combinatorial games. No rule is sacred. In this section, Berlekamp introduces a methodology, based on the notion of auctions, to analyze a position in a possibly loopy game, in which play might continue forever. Blackwell relaxes the perfect-information condition. Loeb considers many-player games. Lazarus, Loeb, Propp, and Ullman replace the rule that players have alternate turns by an “auction-based” approach not unlike Berlekamp’s. The remaining articles represent significant theoretical advances, while remaining within the traditional framework.
Coda
Games of No Chance MSRI Publications Volume 29, 1996
The Angel Problem JOHN H. CONWAY
Abstract. Can the Devil, who removes one square per move from an infinite chessboard, strand the Angel, who can jump up to 1000 squares per move? It seems unlikely, but the answer is unknown. Andreas Blass and I have proved that the Devil can strand an Angel who’s handicapped in one of several ways. I end with a challenge for the solution the general problem.
1. Introduction The Angel and the Devil play their game on an infinite chessboard, with one square for each ordered pair of integers (x, y). On his turn, the Devil may eat any square of the board whatsoever; this square is then no longer available to the Angel. The Angel is a “chess piece” that can move to any uneaten square (X, Y ) that is at most 1000 king’s moves away from its present position (x, y)—in other words, for which |X − x| and |Y − y| are at most 1000. Angels have wings, so that it does not matter if any intervening squares have already been eaten. The Devil wins if he can strand the Angel, that is, surround him by a moat of eaten squares of width at least 1000. The Angel wins just if he can continue to move forever. What we have described is more precisely called an Angel of power 1000. The Angel Problem is this: Determine whether an Angel of some power can defeat the Devil. Berlekamp showed that the Devil can beat an Angel of power one (a chess King) on any board of size at least 32 × 33. However, it seems that it is impossible for the Devil to beat a Knight, and that would imply that an Angel of power two (which is considerably stronger than a Knight) will win. But can you prove it? Well, nobody’s managed to prove it yet, even when we make it much easier by making the Angel have power 1000 or some larger number. The main difficulty seems to be that the Devil cannot ever make a mistake: once he’s made some moves, no matter how foolish, he is in a strictly better position than he was at the start of the game, since the squares he’s eaten can only hinder the Angel. 3
4
JOHN H. CONWAY
(x + 1000, y + 1000)
(x − 1000, y − 1000) Figure 1. Left: An Angel about to fly; he can fly to any point in the square. Right: A Devil eating a square; three have already been eaten.
2. What’s Wrong with Some Potential Strategies Most people who think about this problem produce trial strategies for the Angel of the following general type. They advise the Angel to compute a certain “potential function” that depends on the eaten squares, and then to make a move that minimizes (or maximizes) this function. The Devil usually finds it easy to beat such strategies, by finding some feature to which this function is too sensitive. Suppose, for instance, that the function is very sensitive to eaten squares close to the Angel. Then the Devil should build a horseshoe-shaped trap a light-year across, far to the north of the starting position. This will, of course, cause the Angel to fly southwards as fast as possible, but no matter. When the trap is set up, the Devil just goads the Angel into it by repeatedly eating the square just to the south of him. The Angel feels the pain of these “jabs at his behind” so strongly that he blindly stumbles right into the trap! If the Angel switches to a new function that places great emphasis on eaten squares that are very far away, the Devil might build a mile-wide horseshoe and then scare the Angel into it by eating just a single square a megaparsec to the south of him. The exact details of the Devil’s strategy will of course depend on exact structure of the Angel’s potential function. It seems to be impossible to get the function just right, and if it isn’t just right, the Devil builds a trap that the potential function is insensitive to, and then steers the Angel into it using something to which the function is over-sensitive! A friend of mine, after hearing my talk of horseshoe-shaped traps, dreamed up a wonderful potential function that cleverly searched for horseshoe-shaped traps of all sizes and avoided them. I defeated it trivially by having the Devil use a modest little horseshoe that easily frightened the Angel into a trap of another shape!
THE ANGEL PROBLEM
5
3. Fools Rush On Where Angels Fear to Tread About twenty years ago in Angell Hall, Ann Arbor, Andreas Blass and I spent some time with the Angel. It is reasonable to think that the Angel should be able to win by moving northward as fast as he can, combined with occasional zigzags to the east or west to avoid any obvious traps. So Blass and I made the following definition: Definition. A Fool is an Angel who is required always strictly to increase his y coordinate. So a Fool can make precisely those Angel moves from (x, y) to (X, Y ) for which Y > y. Theorem 3.1. The Devil can catch a Fool . Proof. If the Fool is ever at some point P , he will be at all subsequent times in the “upward cone” from P , whose boundary is defined by the two upward 1 through P . Then we counsel the Devil to act as follows rays of slope ± 1000 (Figure 2): he should truncate this cone by a horizontal line AB at a very large height H above the Fool’s starting position, and use his first few moves to eat one out of every M squares along AB, where M is chosen so that this task will be comfortably finished when the Angel reaches a point Q on the halfway line that’s distant 12 H below AB (we’ll arrange H to be exactly divisible by a large power of two). At subsequent times, the Devil knows that the Fool will be safely ensconced in the smaller cone QCD, where CD is a subinterval of AB of exactly half its length, and for the next few of his moves, he should eat the second one of every M squares along the segment CD. He will have finished this by the time the Fool reaches a point R on the horizontal line 14 H below AB. At later times, the A
C
E
F
D
R
Q
P
Figure 2. A Fool travelling north with the Devil eating along AB.
B
6
JOHN H. CONWAY
Fool will be trapped inside a still smaller cone REF , with EF = 12 CD = 12 AB, and the Devil should proceed to eat the third one of every M squares along the segment EF of AB. If he proceeds in this way, then by the time the Fool reaches the horizontal line at distance H 0 = 2−M H below AB, the Devil will have eaten every square of the subsegment of AB that might still be reached by the Fool. The Devil should then continue, by eating the first out of every M squares on the segment A0 B 0 just below this one, a task which will be finished before the Fool reaches the horizontal line distant 12 H 0 below A0 B 0 , when he should start eating the second of every M squares on the portion C 0 D0 of A0 B 0 that is still accessible, and so on. We see that if we take H of the form 1000 × 2N , where N > 1000M , then before the Fool crosses the horizontal line that is 1000 units below AB, the Devil will have eaten all squares between this line and AB that the Fool might reach, and so the Fool will be unable to move.
4. Lax Fools and Relaxed Fools The kind of Fool we’ve been considering up to now is more precisely called a Plain Fool, since he may make only those Angel moves for which Y is strictly greater than y. Blass and I also showed how the Devil can beat some not-quite-so foolish Fools. Definition. A Lax Fool is a piece that can make precisely those Angel moves for which Y ≥ y. Theorem 4.1. The Devil can catch a Lax Fool . Proof. The Devil uses his odd-numbered moves to convert the Lax Fool into a Plain Fool (of a much higher power). He chooses two squares L and R a suitable distance D to the left and right of the Fool’s starting position, and eats inward alternately from L and R, so long as the Fool stays on the starting line (Figure 3). A
B
L
R Figure 3. A Lax Fool travelling north.
THE ANGEL PROBLEM
7
Whenever the Fool makes an upwards move, the Devil takes the horizontal line through his new position as a new starting line. Suppose that the Fool stays on the starting line for quite some time. Then he can use the four moves he has between two consecutive bites of the Devil at the left end of this line to move at most 4000 places. So, if we take D = 4,000,000, the Devil will have eaten 1000 consecutive squares at the left end of this line before the Fool can reach them. We now see that the Fool can stay on the starting line for at most 8,000,000 moves, since in 8,000,001 moves the Devil can eat every square between L and R. If the Devil adopts this strategy, then the Fool must strictly increase his y coordinate at least once in every 8,000,000 moves. If we look at him only at these instants, we see him behaving like a Plain Fool of power 8,000,000,000, since each of his moves can have carried him at most a 1000 places. So if the Devil uses the strategy that catches an 8,000,000,000-power Plain Fool on his even-numbered moves, he’ll safely trap the 1000-power Lax Fool. Suppose now that the Angel does occasionally allow himself to decrease his ycoordinate, but promises never to make any sequence of moves that decreases it by more than a million. Definition. A Relaxed Fool (of laxity 1,000,000) is an Angel who promises that if he’s ever at a position (X, Y ), he will never be later at a position (x, y) with y > Y − 1,000,000. Theorem 4.2. The Devil can catch a Relaxed Fool (of any laxity).
Figure 4. Funnelling the Relaxed Fool.
8
JOHN H. CONWAY
Proof. This time, the Devil eats away sunken caissons of depth 1,000,000 at a suitable distance to the Left and Right of the Fool (see Figure 4).
5. Variations on the Problem Because our problem was inspired by Berlekamp’s proof that the Devil can catch a chess King on all large enough boards, we’ve been using the chess King metric, in which the unit balls are squares aligned with the axes. However, the arguments that one meets early on in topology courses show that (provided one is allowed to change the number 1000) this really doesn’t matter. It makes no difference to our problem if we suppose that the Angel is positioned at any time on an arbitrary point of the Euclidean plane, and can fly in one move to any other point at most 1000 units away, while the Devil may eat out all points of an arbitrary closed unit disc in any one of his moves. In a similar way, we can prove that our problem is invariant under certain distortions. This happens for instance when the distorted image of every ball of radius R contains an undistorted ball of radius 12 R, and is contained in one of radius 2R. Suppose, for example, that the Angel promises always to stay inside the circular sector of Figure 5, and also that he will always increase his r-coordinate (his distance from the vertex O of this sector). Then the Devil can catch him, by distorting this sector into the triangle of the same figure, in such a way that the r-coordinate turns into the y-coordinate. But the transformation turns the Angel into a Plain Fool.
r
O
r
O
Figure 5. The transformation of regions.
6. Kaleidoscopes Catch Out-and-Out Fools. Definition. An Out-and-Out Fool is an Angel who promises always to increase his distance from the origin. Theorem 6.1. The Devil can catch an Out-and-Out Fool . Proof. The Devil should divide the plane into 2N sectors radiating from the origin, and pretend that the walls of these sectors are the mirrors of a kaleidoscope, as in Figure 6. There will then usually be 2N images of the Fool, one
THE ANGEL PROBLEM
9
Figure 6. The kaleidoscope strategy.
in each sector. The Devil correspondingly distributes his moves between 2N demons, bidding each one of these to take care of the Fool’s image in his own sector, which behaves like a Plain Fool of power 2000N confined as in Figure 5, and so can be caught by a slightly distorted Plain Fool strategy. Of course, the Devil can also catch the Relaxed Out-and Out Fool who merely promises never to make any sequence of moves that reduces his distance from the origin by more than 1,000,000 units.
7. An Extremely Diverting Strategy Theorem 7.1. There is a strategy for the Devil that , when used , has the following property. For each point P of the plane and each distance D, no matter how the Angel moves there will be two times at the latter of which the Angel will be at least D units nearer to P than he was at the former . Proof. It suffices to restrict P to the integral points of the plane, and the distances D to the integers. So we need only deal with countably many pairs (P, D), say (P0 , D0 ), (P1 , D1 ), (P2 , D2 ), . . . . The Devil uses his odd-numbered moves to defeat an Angel that behaves like a Relaxed Out-and-Out Fool who has promised never to move more than D0 units closer to P0 , his moves at twice odd numbers to catch one who promises never to move more than D1 units closer to P1 , his moves at four times odd numbers to catch one who promises never to move more than D2 units closer to P2 , and so on. Any sequence of moves by the real Angel that does not satisfy the conclusion of the theorem will lead to him being caught. It can be shown that, if the Devil employs our diverting strategy, there will be some very wiggly points on the Angel’s trajectory, in the sense that he must cross any line through such a point at least 1000 times—no matter how he plays.
10
JOHN H. CONWAY
Angel’s footprints
Devils footprints magnified
Figure 7. The Angel’s large and the Devil’s small footprints.
8. The Angel Is His Own Worst Enemy The Devil only eats one square for each move of the Angel: we shall show that there is a sense in which the Angel himself eats millions! Theorem 8.1. It does no damage to the Angel’s prospects if we require him after each move to eat away every square that he could have landed on at that move, but didn’t . Proof. Consider the 2001-by-2001 array of squares that is accessible to the Angel from his starting position. We first show that the Devil, without harming his own prospects, can ensure that the Angel only returns to this array a bounded number of times. If not, there will be indefinitely many times at which the Angel lands on some square of this array that he has already visited previously. At each such time, the Devil essentially has a free move, and he can use these moves to eat away a moat of width 1000 all around the array. Now suppose that the Angel has any winning strategy whatsoever, say W . Then we shall convert W into another strategy that does not require him to land on any square on which he could have landed at a previous move. When he is at any point P , the Angel considers all the circumstances under which his winning strategy W causes him to repeatedly reenter the 2001-by-2001 array of squares accessible from P . He imagines himself in one of those circumstances that makes him re-enter this array the maximal number of times, and then “short-circuits” W by making right now the moves he would make on and after the last of these times. (He is in a better position now than he would be then, because the Devil has eaten fewer squares.)
THE ANGEL PROBLEM
11
Figure 8. The straight and narrow path.
So the Angel is “really” burning out the path of all points within 1000 of each of his landing points as he moves. The Devil’s consumption seems meager by comparison (see Figure 7).
9. Can the Angel Really Win? If you’ve got this far, you’ve probably begun to wonder whether it’s really quite safe to trust your fortune to the Angel. But please consider very carefully before selling your soul to the Devil! The Blass–Conway “Diverting Strategy” does indeed force the Angel to travel arbitrarily large distances in directions he might not have wanted to. But it only does so at unpredictable times in the middle of much larger journeys. So for example, at some stage in a megaparsec’s journey north we can divert the Angel (say to the east) for a light-year or so; in the course of this smaller journey we might make him move south for an astronomical unit, with a mile’s westward wandering in that, inside which we might divert him a foot or so to the north, and so on. If he moves like this, then (see Figure 8) we have indeed produced a point about which his path spirals, but the spiral is a very loose one indeed, and an observer at a suitably large scale would only see a very slight wobble on an almost entirely straight Northward path. So, although we occasionally meet some unbelievers, and even after producing our Diverting Strategy, Blass and I remain firmly on the side of the Angel.
10. Kornering the Devil? So does Tom Korner, who thinks the Devil might be defeated by the following kind of “military strategy”. The Angel seconds from their places in Heaven a large number of military officers. He then puts a Private in charge of each individual square, and groups these by hundreds into 10-by-10 blocks in charge
12
JOHN H. CONWAY
of Corporals, which are again gathered by hundreds into 100-by-100 blocks in charge of Majors, 1000-by-1000 blocks in charge of Colonels, and so on. Each officer is required to make a report to his immediate superior on the status of the square array he is responsible for. He does this on the basis of the similar information he has received from his subordinates. He might for instance classify his array as Safe, Usable, or Destroyed, according to certain rules; perhaps it is Safe only if at least ninety of its immediate sub-arrays are safe, and at most five have been destroyed. An officer who has just reported that his region is Usable may be immediately telephoned by his superior with a message that a Very Important Person is now entering such-and-such a square on his south boundary and needs to be safely transported to some point on his north or east boundary. In this case he is to plot a suitable route and telephone his subordinates with similar requests. An officer of the n-th rank whose region is Safe may face a stronger demand: perhaps he is only told that the VIP might arrive at any time in the next 10n time units. Korner thinks that perhaps the rules can be so designed that these orders can always be safely executed, and that at any time all officers of sufficiently high rank will make Safe reports, so that on a large enough scale the Angel can move completely freely. So do I, but neither of us has been able to turn these ideas into an explicit strategy for the Angel. All we can say is that a “military strategy” of this type could allow for Blass–Conway diversionary tactics, and is not so easy to hoodwink as the potential-function strategies, and so there might well be one that solves our problem.
Join the Fun! This problem has been alive too long! So I offer $100 for a proof that a sufficiently high-powered Angel can win, and $1000 for a proof that the Devil can trap an Angel of any finite power. John H. Conway John H. Conway Department of Mathematics Princeton University Fine Hall Washington Road Princeton, NJ 08544
Games of No Chance MSRI Publications Volume 29, 1996
Scenic Trails Ascending from Sea-Level Nim to Alpine Chess AVIEZRI S. FRAENKEL
Abstract. Aim: To present a systematic development of part of the theory of combinatorial games from the ground up. Approach: Computational complexity. Combinatorial games are completely determined; the questions of interest are efficiencies of strategies. Methodology: Divide and conquer. Ascend from Nim to chess in small strides at a gradient that’s not too steep. Presentation: Informal; examples of games sampled from various strategic viewing points along scenic mountain trails illustrate the theory.
1. Introduction All our games are two-player perfect-information games (no hidden information) without chance moves (no dice). Outcome is (lose, win) or (draw, draw) for the two players, who play alternately. We assume throughout normal play, i.e., the player making the last move wins and his opponent loses, unless mis`ere play is specified, where the outcome is reversed. A draw is a dynamic tie, that is, a position from which neither player can force a win, but each has a nonlosing next move. As we progress from the easy games to the more complex ones, we will develop some understanding of the poset of tractabilities and efficiencies of game strategies: whereas, in the realm of existential questions, tractabilities and efficiencies are by and large linearly ordered, from polynomial to exponential, for problems with an unbounded number of alternating quantifiers, such as games, the notion of a “tractable” or “efficient” computation is much more complex. (Which is more tractable: a game that ends after four moves, but it’s undecidable who Invited one-hour talk at MSRI Workshop on Combinatorial Games, July, 1994. Part of this paper was prepared while visiting Curtin University, Perth, WA. Thanks to my host Jamie Simpson for everything, and to Brian White and Renae Batina for their expert help in preparing the overhead pictures of the mountain scenes displayed during the oral presentation of this paper.
13
14
AVIEZRI S. FRAENKEL
∗
∗
∗
∗
Figure 1. Beat Doug on this DAG (directed acyclic graph).
wins [Rabin 1957], or a game that takes an Ackermann number of moves to finish but the winner can play randomly, having to pay attention only near the end [Fraenkel, Loebl and Neˇsetˇril 1988]?) When we say that a computation or strategy is polynomial or exponential, we mean that the time it takes to evaluate the strategy is a polynomial or exponential function in a most succinct form of the input size. In Section 2 we review the classical theory (impartial games without draws, no interaction between tokens). On our controlled ascent to chess we introduce in Section 3 draws, on top of which we then add interaction between tokens in Section 4. In Section 5 we review briefly partizan games. In Section 6 we show how the approach and methodology outlined in the abstract can help to understand some of the many difficulties remaining in the classical theory (numerous rocks are strewn also along other parts of the trails ascending towards chess). This then leads naturally to the notion of tractable and efficient games, taken up in Section 7, together with some more ways in which a game can become intractable or inefficient. This paper is largely expository, yet it contains material, mainly in parts of Sections 6 and 7, not published before, to the best of our knowledge. The present review is less formal than [Fraenkel 1991]: the emphasis here is on examples that illustrate part of the theory. A fuller and more rigorous treatment is to appear in [Fraenkel ≥ 1997].
2. The Classical Theory Here we will learn to play games such as “Beat Doug” (Figure 1). Place one token on each of the four starred vertices. A move consists of selecting a token and moving it, along a directed edge, to a neighboring vertex on this acyclic digraph. Tokens can coexist peacefully on the same vertex. For the given position, what’s the minimum time to: (a) compute who can win;
SCENIC TRAILS ASCENDING FROM SEA-LEVEL NIM TO ALPINE CHESS
P
N
N
N
P
N
N
N
P
8
7
6
5
4
3
2
1
0
15
Figure 2. The game graph for Scoring, with initial score n = 8 and maximal step t = 3. Positions marked N are wins and P are losses for the player about to move.
(b) compute an optimal next move; (c) consummate the win? Following our divide and conquer methodology, let’s begin with a very easy example, before solving Beat Doug. Given n ∈ Z+ (the initial score) and t ∈ Z+ (the maximal step size), a move in the game Scoring consists of selecting i ∈ {1, . . . , t} and subtracting i from the current score, initially n, to generate the new score. Play ends when the score 0 is reached. The game graph G = (V, E) for Scoring is shown in Figure 2, for n = 8 and t = 3. A position (vertex) u ∈ V is labeled N if the player about to move from it can win; otherwise it’s a P -position. Denoting by the set of all P -positions, the set of all N -positions, and by F (u) the set of all (direct) followers or by options of any vertex u, we have, for any acyclic game,
P
N
P u∈N u∈
N, F (u) ∩ P 6= ?.
if and only if F (u) ⊆
(2.1)
if and only if
(2.2)
P
N
= {k(t + 1) : k ∈ Z0} and = As suggested by Figure 2, we have {{0, . . . , n} − }. The winning strategy consists of dividing n by t + 1. Then n ∈ if and only if the remainder r is zero. If r > 0, the unique winning move is from n to n − r. Is this a “good” strategy?
P
P
Input size: Θ(log n) (succinct input). Strategy computation: O(log n) (linear scan of the dlog ne digits of n). Length of play: dn/(t + 1)e. Thus the computation time is linear in the input size, but the length of play is exponential. This does not prevent the strategy from being good: whereas we dislike computing in more than polynomial time, the human race relishes to see some of its members being tortured for an exponential length of time, from before the era of the Spanish matadors, through soccer and tennis, to chess and Go! But there are other requirements for making a strategy tractable, so at present let’s say that the strategy is reasonable. Now take k scores n1 , . . . , nk ∈ Z+ and t ∈ Z+, where nj ≤ n for each j. A move consists of selecting one of the current scores and subtracting from it some i ∈ {1, . . . , t}. Play ends when all the scores are zero. Figure 3 shows an example. This is a sum of Scoring games, itself also a Scoring game. It’s easy to
16
AVIEZRI S. FRAENKEL
n2
n1
n3
n4 = nk
8
7
6
5
7
6
5
4
1
1
1
1
0
0
0
0
Figure 3. A Scoring game consisting of a sum of four Scoring games. Here k = 4, n1 = 8, n2 = 7, n3 = 6, n4 = 5, and t = 3. 0
3
2
1
0
3
2
1
0
∗8
∗7
∗6
∗5
4
3
2
1
0
Figure 4. A game on a graph, but not a game graph.
see that the game of Figure 3 is equivalent to the game played on the digraph of Figure 4, with tokens on vertices 5, 6, 7 and 8. A move consists of selecting a token and moving it right by not more than t = 3 places. Tokens can coexist on the same vertex. Play ends when all tokens reside on 0. What’s a winning strategy? We hit two snags when trying to answer this question:
P N
(i) The sum of N -positions is in ∪ . Thus a token on each of 5 and 7 is seen to be an N -position (the move 7 → 5 clearly results in a P -position), whereas a token on each of 3 and on 7 is a P -position. So the simple P -, N -strategy breaks down for sums, which arise frequently in combinatorial game theory. (ii) The game graph has exponential size in the input size Ω(k + log n) of the “regular” digraph G = (V, E) (with |V | = n + 1) on which the game is played with k tokens. However, this is not the game graph of the game: each tuple of k tokens on G corresponds to a single vertex of the game graph, whose vertex-set k+n thus has size n —the number of k-combinations of n + 1 distinct objects with n √ at least k repetitions. For k = n this gives 2n n = Θ(4 / n). The main contribution of the classical theory is to provide a polynomial strategy despite the exponential size of the game graph. On G, label each vertex u with the least nonnegative integer not among the labels of the followers of u (see top of Figure 4). These labels are called the Sprague–Grundy function of G, or
SCENIC TRAILS ASCENDING FROM SEA-LEVEL NIM TO ALPINE CHESS
17
the g-function for short [Sprague 1935–36; Grundy 1939]. It exists uniquely on every finite acyclic digraph. Then for u = (u1 , . . . , uk ), a vertex of the game graph (whose very construction entails exponential effort), we have g(u) = g(u1 ) ⊕ · · · ⊕ g(uk ),
P = {u : g(u) = 0},
N = {u : g(u) > 0},
where ⊕ denotes Nim-sum (summation over GF(2), also known as exclusive or). To compute a winning move from an N -position, note that there is some i for which g(ui ) has a 1-bit at the binary position where g(u) has its leftmost 1-bit. Reducing g(ui ) appropriately makes the Nim-sum 0, and there’s a corresponding move with the i-th token. For the example of Figure 4 we have g(5) ⊕ g(6) ⊕ g(7) ⊕ g(8) = 1 ⊕ 2 ⊕ 3 ⊕ 0 = 0, a P -position, so every move is losing. Is the strategy polynomial? For Scoring, the remainders r1 , . . . , rk of dividing n1 , . . . , nk by t+1 are the g-values, as suggested by Figure 4. The computation of each rj has size O(log n). Since k log n < (k + log n)2 , the strategy computation (items (a) and (b) at the beginning of this section) is polynomial in the input size. The length of play remains exponential. Now consider a general nonsuccinct digraph G = (V, E), by which we mean that the input size is not logarithmic. If the graph has |V | = n vertices and |E| = m edges, the input size is Θ((m + n) log n) (each vertex is represented by its index of size log n, and each edge by a pair of indices), and g can be computed in O((m + n) log n) steps (by a “depth-first” search; each g-value is at most n, of size at most log n). For a sum of k tokens on the input digraph, the input size is Θ((k + m + n) log n), and the strategy computation for the sum can be carried out in O((k + m + n) log n) steps (Nim-summing k summands of g-values). Note also that for a general digraph the length of play is only linear rather than exponential, as on a succinct (logarithmic input size) digraph. Since the strategy for Scoring is polynomial for a single game as well as for a sum, we may say, informally, that it’s a tractable strategy. (We’ll see in Section 7 that there are further requirements for a strategy to be truly “efficient”.) Our original Beat Doug problem is now also solved with a tractable strategy. Figure 5 depicts the original digraph of Figure 1 with the g-values added in. Since 2 ⊕ 3 ⊕ 3 ⊕ 4 = 6, the given position is in . Moving 4 → 2 is a unique winning move. The winner can consummate his win in polynomial time. Unfortunately, however, the strategy of classical games is not very robust: slight perturbations in various directions can make the analysis considerably more difficult. We’ll return to this subject in Sections 6 and 7. We point out that there is an important difference between the strategies of Beat Doug and Scoring. In both, the g-function plays a key role. But for the latter, some further property is needed to yield a strategy that’s polynomial, since the input graph is (logarithmically) succinct. In this case the extra ingredient is the periodicity modulo (t + 1) of g.
N
18
AVIEZRI S. FRAENKEL
∗
0 ∗3 1
1
0 ∗3
2 0
∗
∗2
∗4 1
∗
1
∗
0 2
1
Figure 5. The beaten Doug.
Figure 6. Beat Craig in this cyclic digraph.
3. Introducing Draws In this section we learn how to beat Craig efficiently. The four starred vertices in Figure 6 contain one token each. The moves are identical to those of Beat Doug, and tokens can coexist peacefully on any vertex. The only difference is that now the digraph G = (V, E) may have cycles, and also loops (which correspond to passing a turn). In addition to the P - and N -positions, which satisfy (2.1) and (2.2), we now may have also Draw-positions D, which satisfy
D
u∈
D
if and only if
F (u) ∩
P = ? and F (u) ∩ D 6= ?,
where is the set of all D-positions. Introducing cycles causes several problems: • Moving a token from an N -position such as vertex 4 in Figure 7 to a P position such as vertex 5 is a nonlosing move, but doesn’t necessarily lead to a win. A win is achieved only if the token is moved to the leaf 3. The digraph might be embedded inside a large digraph, and it may not be clear to which P -follower to move in order to realize a win. is not unique, as it is for and in the • The partition of V into , and classical case. For example, vertices 1 and 2 in Figure 7, if labeled P and N , would still satisfy (2.1) and (2.2), and likewise for vertices 8 and 9 (either can be labeled P and the other N ).
PN
D
P
N
Both of these shortcomings can be remedied by introducing a proper counter function attached to all the P -positions [Fraenkel ≥ 1977]. For handling sums, we would like to use the g-function, but there are two problems: • The question of the existence of g on a digraph G with cycles or loops is NPcomplete, even if G is planar and its degrees are ≤ 3, with each indegree ≤ 2 and each outdegree ≤ 2 [Fraenkel 1981] (see also [Chv´atal 1973; van Leeuwen 1976; Fraenkel and Yesha 1979]).
SCENIC TRAILS ASCENDING FROM SEA-LEVEL NIM TO ALPINE CHESS
?
?
∞( )
∞( )
0
1
0
2
1
5
4
3
D
D
P
N
P
?
∞( )
∞(1)
1
0
∞(0)
∞(0)
9
8
7
6
12
11
D
D
N
P
N
19
N 0 10 P
Figure 7. P -, N -, D- and γ-values for simple digraphs.
• The strategy of a cyclic game isn’t always determined by the g-function, even if it exists. This is one of those rare cases where two failures are better than one! The second failure opens up the possibility that perhaps there’s another tool that always works, and if we are optimistic, we might even hope that it is also polynomial. There is indeed such a generalized g-function γ. It was introduced in [Smith 1966], and rediscovered in [Fraenkel and Perl 1975]; see also [Conway 1976, Ch. 11]. Of the possible definitions of γ, we give a simple one below; see [Fraenkel and Yesha 1986] for two other definitions and a proof of the equivalence of all three. The γ-function is defined the same way as the g-function, except that it can assume not only values in Z0 = {n ∈ Z : n ≥ 0}, but also infinite values of the form ∞(K), as we now explain. We have γ(u) = ∞(K) if K is the set of finite γ-values of followers of u, and some follower v of u has the following properties: γ(v) is also infinite, and v has no follower w with γ(w) equal to the least nonnegative integer not in K. Figure 7 shows γ-values for some simple digraphs. Every finite digraph with n vertices and m edges has a unique γfunction that can be computed in O(mn log n) steps. This is a polynomial-time computation, though bigger than the g-values computation. We also associate a (nonunique) counter function to every vertex with a finite γ-value, for the reasons explained above. Here is a more formal definition of γ. Given a digraph G = (V, E) and a function γ : V → Z0 ∪ {∞}, set V f = u ∈ V : γ(u) < ∞ and γ 0 (u) = mex γ F (u) ,
20
AVIEZRI S. FRAENKEL
where, for any finite subset S ⊆ Z0, we define mex S = min(Z0 − S). The function γ is a generalized Sprague–Grundy function, or γ-function for short, with counter function c : V f → J, where J is an infinite well-ordered set, if the following conditions hold: A. If γ(u) < ∞, then γ(u) = γ 0 (u). B. If there exists v ∈ F (u) with γ(v) > γ(u), then there exists w ∈ F (v) satisfying γ(w) = γ(u) and c(w) < c(u). C. If, for every v ∈ F (u) with γ(v) = ∞, there is w ∈ F (v) with γ(w) = γ 0 (u), then γ(u) < ∞. Remarks. In B we have necessarily u ∈ V f ; and we may have γ(v) = ∞ as in C. If condition C is satisfied, then γ(u) < ∞, and so γ(w) = γ 0 (u) = γ(u) by A. Condition C is equivalent to the following statement: / K. C0 . If γ(u) = ∞, then there is v ∈ F (u) with γ(v) = ∞(K) such that γ 0 (u) ∈ To keep the notation simple, we write throughout ∞(0) for ∞({0}), ∞(0, 1) for ∞({0, 1}), and so on. To get a strategy for sums, define the generalized Nim-sum as the ordinary Nim-sum augmented by: a ⊕ ∞(L) = ∞(L) ⊕ a = ∞(L ⊕ a),
∞(K) ⊕ ∞(L) = ∞(?),
where a ∈ Z0 and L ⊕ a = {l ⊕ a : l ∈ L}. For a sum of k tokens on a digraph G = (V, E), let u = (u1 , . . . , uk ). We then have γ(u) = γ(u1 ) ⊕ · · · ⊕ γ(uk ), and = u : γ(u) = 0 , (3.1) = u : 0 < γ(u) < ∞ ∪ u : γ(u) = ∞(K) and 0 ∈ K , = u : γ(u) = ∞(K) and 0 ∈ /K .
P N D
Thus a sum consisting of a token on vertex 4 and one on 8 in Figure 7 has γ-value 1 ⊕ ∞(1) = ∞(1 ⊕ 1) = ∞(0), which is an N -position (the move 8 → 7 results in a P -position). Also one token on 11 or 12 is an N -position. But a token on both 11 and 12 or on 8 and 12 is a D-position of their sum, with γ-value ∞(?). A token on 4 and 7 is a P -position of the sum. With k tokens on a digraph, the strategy for the sum can be computed in O((k + mn) log n) steps. It is polynomial in the input size Θ((k + m + n) log n), since k + mn < (k + m + n)2 . Also, for certain succinct “linear” graphs, γ provides a polynomial strategy. See [Fraenkel and Tassa 1975]. Beat Craig is now also solved with a tractable strategy. From the γ-values of Figure 8 we see that the position given in Figure 6 has γ-value 0⊕1⊕2⊕∞(2, 3) = 3 ⊕ ∞(2, 3) = ∞(1, 0), so by (3.1) it’s an N -position, and the unique winning move is ∞(2, 3) → 3. Again the winner can force a win in polynomial time, and can also delay it arbitrarily long, but this latter fact is less interesting.
SCENIC TRAILS ASCENDING FROM SEA-LEVEL NIM TO ALPINE CHESS
21
∗0 ∗1
∗ ∞(2, 3)
∗2
0
∞
1
2
1
3
0
2
∞(1,2)
∞
∞(2) Figure 8. Craig has also been beaten.
A B C
D
E
Figure 9. Beat an even bigger Craig.
As a homework problem, beat an even bigger Craig: compute the labels P, N, D for the digraph of Figure 9 with tokens placed as shown, or for various other initial token placements.
4. Adding Interactions between Tokens Here we learn how to beat Anne. On the five-component digraph depicted in Figure 10, place tokens at arbitrary locations, but at most one token per vertex. A move is defined as in the previous games, but if a token is moved onto an occupied vertex, both tokens are annihilated (removed). The digraph has cycles, and could also have loops (passing positions). Note that the three components
22
z0
AVIEZRI S. FRAENKEL
z1
z0
z1
z4 ∗ ∗ z3
z2
y0
y1
∗
∗ y4
y4 ∗
∗ z2
z3
∗ z4
z4 ∗
y1
y0
z1
z0 ∗
z3
∗ z2
y3
y2
∗ y3
Figure 10. Beat Anne in this Ann-ihilation game. 3 2
3 2
1
4
4
1
5
Figure 11. Annihilation on simple cyclic digraphs.
having z-vertices are identical, as are the two y-components. The only difference between a z- and a y- component is in the orientation of the top horizontal edge. With tokens on the twelve starred vertices, can the first player win or at least draw, and if so, what’s an optimal move? How “good” is the strategy? The indicated position may be a bit complicated as a starter. So consider first a position consisting of four tokens only: one on z3 and the other on z4 in two of the z-components. Also consider the position consisting of a single token on each of y3 and y4 in each y-component. It’s clear that in these cases player 2 can at least draw, simply by imitating on one component what player 1 does on the other. Can player 2 actually win in one or both of these games? Annihilation games were proposed by Conway. It’s easy to see that on a finite acyclic digraph, annihilation can affect the length of play, but the strategy is the same as for the classical games. Since g(u) ⊕ g(u) = 0, the winner doesn’t need to use annihilation, and the loser cannot be helped by it. But the situation is quite different in the presence of cycles. In Figure 11 (left), a token on each of vertices 1 and 3 is clearly a D-position for the nonannihilation case, but it’s a P -position when played with annihilation (the second move is a winning annihilation move). In Figure 11 (right), with annihilation, a token on each of 1 and 2 is an N -position, whereas a token on each of 1 and 3 is a D-position. The theory of annihilation games is discussed in depth in [Fraenkel and Yesha 1982]; see also [Fraenkel 1974; Fraenkel and Yesha 1976; 1979; Fraenkel, Tassa and Yesha 1978]. Ferguson [1984] considered mis`ere annihilation play. The annihilation graph is a certain game graph of an annihilation game. The annihilation graph of the annihilation game played on the digraph of Figure 11 (left) consists of two components. One is depicted in Figure 12, namely, the com-
∗ y2
SCENIC TRAILS ASCENDING FROM SEA-LEVEL NIM TO ALPINE CHESS
23
1111 1001
0011
0101
1010
1100
0110 0000
Figure 12. The “even” component digraph of Figure 11 (left).
G
0
of the annihilation graph
t=4 z0 4
t=2 z1
y0
5
2
y1 3
z4
y4
7
4
5 z3
G of the
4 z2
3 y3
2 y2
Figure 13. The γ-function.
ponent G0 = (V 0 , E 0 ) with an even number of tokens. The “odd” component G1 also has 8 vertices. In general, a digraph G = (V, E) with |V | = n vertices has an annihilation graph G = (V , E) with |V | = 2n vertices, namely all ndimensional binary vectors. The γ-function on G determines whether any given position is in , or , according to (3.1); and γ, together with its associated counter function, determines an optimal next move from an N - or D-position. The only problem is the exponential size of G. We can recover an O(n6 ) strategy by computing an extended γ-function γ on an induced subgraph of G of size O(n4 ), namely, on all vectors of weight ≤ 4 (at most four 1-bits). In Figure 13, the numbers inside the vertices are the γ-values, computed by Gaussian elimination over GF(2) of an n × O(n4 ) matrix. This computation also yields the values t = 4 for Figure 13 (left) and t = 2 for Figure 13 (right): If γ(u) ≥ t, then γ(u) = ∞, whereas γ(u) < t implies γ(u) = γ(u).
PN D
24
z0 4
5 z3
AVIEZRI S. FRAENKEL
z1
z0
5
4
z1
z0
5
4
z1
y0
5
2
y1
y0
3
2
y1 3
z4
z4
z4
y4
y4
7
7
7
4
4
4 z2
5 z3
4 z2
5 z3
4 z2
3 y3
2 y2
3 y3
Figure 14. Poor beaten Anne. (Gray circles show initial token positions.)
Thus for Figure 13 (left), we have γ(z3 , z4 ) = 5 ⊕ 7 = 2 < 4, so γ(z3 , z4 ) = 2. Hence two such copies constitute a P -position (2 ⊕ 2 = 0). (How can player 2 consummate a win?) In Figure 13 (right) we have γ(y3 , y4 ) = 3 ⊕ 4 = 7 > 2, so γ(y3 , y4 ) = ∞, in fact, ∞(0, 1), so two such copies constitute a D-position. The position given in Figure 10 is repeated in Figure 14, together with the γ-values. From left to right we have: for the z-components, γ = 2 ⊕ 3 ⊕ 0 = 1; and for the y-components, ∞(0, 1) + 0 = ∞(0, 1), so the γ-value is ∞(0, 1) ⊕ 1 = ∞(0, 1). Hence the position is an N -position by (3.1). There is, in fact, a unique winning move, namely y4 → y3 in the second component from the right. Any other move leads to drawing or losing. For small digraphs, a counter function c is not necessary, but for larger ones it’s needed for consummating a win. The trouble is that we computed γ and c only for an O(n4 ) portion of G. Whereas γ can then be extended easily to all of G, this does not seem to be the case for c. We illustrate a way out on the digraph shown in Figure 13 (right). Suppose that the beginning position is u = (y0 , y1 , y2 , y3 ), which has γ-value 0, as can be seen from Figure 13. With u we associate a representation of vectors of weight ≤ 4, each with γ-value 0, in this case, u ˜ = (u1 , u2 ), where u1 = (y0 , y2 ) and u2 = (y1 , y3 ), with u = u1 ⊕ u2 . Representations can be computed in polynomial time, and a counter function c can be defined on them. Suppose player 1 moves from u to v = (y1 , y2 ). The representation v˜ is obtained by carrying out the move on the representation u ˜: F0,3 (u1 ) (i.e., moving from y0 to y3 ) gives u3 = (y2 , y3 ), so v˜ = (u3 , u2 ), with u3 ⊕ u2 = v. Now player 2 would like to move to some w with γ(w) = 0 and c(w) ˜ < c(˜ u), namely, w ˜ = (u2 ). However, we see that u2 is a predecessor (immediate ancestor) of v, rather than a follower of v. Player 2 now pretends that player 1 began play from u2 rather than from u, so arrived at v with representation F3,2 (u2 ) = v˜. This has the empty representation as follower, so player 2 makes the final annihilation move. Followers of representations can always be chosen with c-value smaller than the c-value of their grandfather, and they always correspond to either a follower or predecessor of a position. Since the initial counter value has value O(n5 ), player 2 can win in that many moves, using an O(n6 ) computation. This method can easily be extended to handle sums. Thus, according to our definition, we have a tractable strategy for annihilation games. Yet clearly it
2 y2
SCENIC TRAILS ASCENDING FROM SEA-LEVEL NIM TO ALPINE CHESS
25
would be nice to improve on the O(n6 ) and to simplify the construction of the counter function. Is there a narrow winning strategy that’s polynomial? A strategy is narrow if it uses only the present position u for deciding whether u is a P -, N -, or Dposition, and for computing a next optimal move. It is broad [Fraenkel 1991] if the computation involves any of the possible predecessors of u, whether actually encountered or not. It is wide if it uses any ancestor that was actually encountered in the play of the game. Kalm´ ar [1928] and Smith [1966] defined wide strategies, but then both immediately reverted back to narrow strategies, since both authors remarked that the former do not seem to have any advantage over the latter. Yet for annihilation games we were able to exhibit only a broad strategy that is polynomial. Is this the alpine wind that’s blowing? Incidentally, for certain (Chinese) variations of Go, for chess and some other games, there are rules that forbid certain repetitions of positions, or modify the outcome in the presence of such repetitions. Now if all the history is included in the definition of a move, then every strategy is narrow. But the way Kalm´ ar and Smith defined a move—much the same as the intuitive meaning—there is a difference between a narrow and wide strategy for these games. We also mention here the notion of “positional strategy” [Ehrenfeucht and Mycielski 1979; Zwick and Paterson ≥1996]. See also [Beck 1981; 1982; 1985; Chv´atal and Erd¨ os 1978]. As a homework problem, compute the label ∈ {P, N, D} of the stellar configuration marked by letters in “Simulation of the SL comet fragments’ encounter with Jupiter” (Figure 15), where J is Jupiter, the other letters are various fragments of the comet, and all the vertices are “space-stations”. A move consists of selecting Jupiter or a fragment, and moving it to a neighboring space-station along a directed trajectory. Any two bodies colliding on a space-station explode and vanish in a cloud of interstellar dust. Note the six space-stations without exit, where a body becomes a “falling star”. Is the given position a win for the (vicious) player 1, who aims at making the last move in the destruction of this subsystem of the solar system, or for the (equally vicious) player 2? Or is it a draw, so that a part of this subsystem will exist forever? And if so, can it be arranged for Jupiter to survive as well? (The encounter of the Shoemaker–Levy comet with Jupiter took place during the MSRI workshop.) Various impartial and partizan variations of annihilation games were shown to be NP-hard, Pspace-complete or Exptime-complete [Fraenkel and Yesha 1979; Fraenkel and Goldschmidt 1987; Goldstein and Reingold 1995]. We mention here only briefly an interaction related to annihilation. Electrons and positrons are positioned on vertices of the game Matter and Antimatter (Figure 16). A move consists of moving a particle along a directed trajectory to an adjacent station—if not occupied by a particle of the same kind, since two electrons (and two positrons) repel each other. If there is a resident particle, and the incoming particle is of opposite type, they annihilate each other, and both disappear from the play. It is not very hard to determine the label of any position on the
26
AVIEZRI S. FRAENKEL
H
N
G
A
F
M
J
B K E C
L
Q P
D
R S
Figure 15. Interstellar encounter with Jupiter.
SCENIC TRAILS ASCENDING FROM SEA-LEVEL NIM TO ALPINE CHESS
27
Figure 16. Matter and Antimatter.
given digraph. But what can be said about a general digraph? About succinct digraphs? Note that the special case where all the particles are of the same type, is the generalization of Welter played on the given digraph. Welter [Conway 1976, Ch. 13] is Nim with the restriction that no two piles have the same size. It has a polynomial strategy, but its validity proof is rather intricate. In Nim we are given finitely many piles. A move consists of selecting a pile and removing any positive number of tokens from it. The classical theory (Section 2) shows that the P -positions for Nim are simply those pile collections whose sizes Nim-add to zero.
5. Partizan Games A game is impartial if both players have the same set of moves for all game positions. Otherwise the game is partizan. Nim-like games are impartial. Chesslike games are partizan, because if Gill plays the black pieces, Jean will not let him touch the white pieces. In this section we shall refer to partizan games simply as games. The following two inductive definitions are due to Conway [1976; 1977; 1978a]. (i) If M L and M R are any two sets of games, there exists a game M = {M L | M R }. All games are constructed in this way. (ii) If LE and RI are any two sets of numbers and no member of LE is ≥ any member of RI, then there exists a number {LE | RI}. All numbers are constructed in this way. Thus the numbers constitute a subclass of the class of games. The first games and numbers are created by putting M L = M R = LE = RI = ?. Some samples are given in Figure 17, where L (Left) plays to the south-west and R (Right) to the south-east. If, as usual, the player first unable to move is the loser and his opponent the winner, then the examples suggest the following statements:
28
AVIEZRI S. FRAENKEL
{|} = 0
{ | 0} = −1
{0 | } = 1
{0 | 0} = ∗
{0 | 1} =
1 2
{0 | ∗} = ↑
Figure 17. A few early partizan games.
M M M M
>0 <0 =0 || 0
if if if if
L can win, R can win, player 2 can win, player 1 can win (for example in ∗).
We shall in fact define >, <, =, k by these conditions. The relations can be combined as follows: M ≥ 0 if L can win as player 2, M ≤ 0 if R can win as player 2, M pB 0 if L can win as player 1, M Cp 0 if R can win as player 1. Alternative inductive definitions of ≤ and k can be given. Let x = {xL | xR }. Then x ≤ y if and only if xL Cp y for all xL and x Cp y R for all y R , x = y if and only if x ≤ y and y ≤ x, x || y (x is fuzzy with y) if and only if x 6≤ y and y 6≤ x. One can also provide a consistency proof of both definitions. This enables one to prove many properties of games in a simple manner. For example, define −M = {−M R | −M L}. Then G− G = 0 (player 2 can win in G− G by imitating the moves of player 1 in the other game). Also: x ≤ y Cp z
or
x Cp y ≤ z ⇒ x Cp z
(consider the game z − x = (z − y) + (y − x), in which L can win as first player), and xL Cp x Cp xR (clearly L can win as player 1 in x − xL and in xR − x). If x is a number, then xL < x < xR . Most important is that a sum of games simply becomes a sum, defined by: M + H = {M L + H, M + H L | M R + H, M + H R }. Consider for example the game of Domineering [Conway 1976, Ch. 10; Berlekamp, Conway and Guy 1982, Ch. 5], played with dominoes each of which covers precisely two squares of an n × n chessboard. The player L tiles vertically, R
SCENIC TRAILS ASCENDING FROM SEA-LEVEL NIM TO ALPINE CHESS
{|} = 0
{ | 0} = −1
{0 | } = 1
{0 | 0} = ∗
{1 | −1} = ±1
29
{0, −1 | 1} =
Figure 18. A few values of a Domineering game.
horizontally. After Domineering is played for a while, the board may break up into several parts, whence the game becomes a sum of these parts. The values of several small configurations are given in Figure 18. Since the relation between the value of a game M and 0 determines the strategy for playing it, computing the value of M is fundamental to the theory. In this direction the Simplicity Theorem is helpful: Let x = {xL | xR } be a game. If there exists a number z such that xL
C z B xR
and no option of z satisfies this relation, then x = z. Thus {−1 | 99} = 0. There also exist algorithms for computing values associated with games that are not numbers. Partizan games with possible draws are discussed in [Li 1976; Conway 1978b; Shaki 1979; Fraenkel and Tassa 1982; Berlekamp, Conway and Guy 1982, Ch. 11]. Sums of partizan games are Pspace-complete [Morris 1981], even if the component games have the form {a||{b|c}} with a, b, c ∈ Z [Yedwab 1985; Moews 1994].
6. Sticky Classical Games As we mentioned in the penultimate paragraph of Section 2, the classical theory is nonrobust (the same holds, even more so, for nonclassical theories). Let’s examine a few of the things that can go wrong. First consider mis`ere play. The pruned game graph G, that is, the game graph from which all leaves have been pruned, gives the same full information for mis`ere play as the game graph gives for normal play: its P -, N -positions determine who can win. But in the nontrivial cases, G is exponentially large, so of little help. The game graph G is neither the sum of its components nor of its pruned components, which might explain why nobody seems to have a general theory for mis`ere play, though important advances have been made for many special subclasses and particular games. See, for example, [Berlekamp, Conway and Guy 1982, Ch. 13; Sibert and Conway 1992; Plambeck 1992; Banerji and Dunning 1992].
1 2
30
AVIEZRI S. FRAENKEL
The classical theory is also very sensitive to interaction between tokens, which again expresses itself as the inability to decompose the game into sums. We mention only two examples: annihilation and Welter. There’s an involved special theory for each of these games, but no general unifying theory seems to be known. Yet another problem is posed by the succinctness of the input size of many interesting games—for example, octal games. In an octal game, n tokens are arranged as a linear array (input size: Θ(log n)), and the array is reduced and/or subdivided according to rules encoded in octal [Guy and Smith 1956; Berlekamp, Conway and Guy 1982, Ch. 4; Conway 1976, Ch. 11]. It’s not known whether there’s an octal game with finitely many nonzero octal digits that doesn’t have a polynomial strategy, though for many such octal games no polynomial strategy has (yet?) been found. Some of them have such a huge period or preperiod that their polynomial nature asserts itself only for impractically high values of n. See [Gangolli and Plambeck 1989]. Of course all these and many more problems bestow upon the class of combinatorial games its distinctive, interesting and challenging flavor. Let us now examine in some more detail the difficulties presented by a particular classical game, played with just two piles: Wythoff’s game [Wythoff 1907; Yaglom and Yaglom 1967]. In this game there’s a choice between two types of moves: you can either take any positive number of tokens from a single pile, just as in Nim, or you can remove the same (positive) number of tokens from both piles. The first few g-values are depicted in Table 1. The structure of the 0’s is wellunderstood, and can be computed in polynomial time [Fraenkel 1982; Fraenkel and Borosh 1973]. But the nonzero values appear at positions that are not yet well-understood. Some structure of the 1-values is portrayed in [Blass and Fraenkel 1990]; see [Pink 1991] for further developments. But no polynomial construction of all the nonzero g-values seems to be known—not even whether such a construction is likely to exist or not. Why is this the case? The experts say that it’s due to the nondisjunctive move of taking from both piles. To test this opinion, let’s consider a game, to be called (k, k + 1)-Nimdi (for reasons to become clear later); see Table 2 for the first few g-values. In this game a move consists of either taking any positive 0 1 2 3 4 5 6
1 2 0 4 5 3 7
2 0 1 5 3 4 8
3 4 5 6 2 0 1
4 5 3 2 7 6 9
5 3 4 0 6 8 10
6 7 8 1 9 10 3
7 8 6 9 0 1 4
8 6 7 10 1 2 5
Table 1. (k, k)-Wythoff.
9 10 11 12 8 7 13
10 11 9 8 13 12 0
11 9 10 7 14 15 2
SCENIC TRAILS ASCENDING FROM SEA-LEVEL NIM TO ALPINE CHESS
31
number from a single pile, or else k from one and k + 1 from the other, for an arbitrary k ∈ Z+. It won’t take long for the reader to see that these values are exactly the same as those for Nim. The same holds if “for an arbitrary k” is replaced by “for a fixed k”, say k = 2. So Table 2 also gives the g-values for (2, 3)-Nimdi. Let’s now consider the same game, but with (2, 3) replaced by (1, 3). In other words, a move consists of taking any positive number of tokens from a single pile, or else 1 token from one pile and 3 from the other. The first few g-values are listed in Table 3. The next empty entry, for (2, 3), should be 2 ⊕ 3 = 1, according to the Nimsum rule. However, the true value is 4. The reason is that (2, 3) has a follower (2, 3) − (1, 3) = (1, 0), which already has value 1. In other words, the g-value 1 of Nim has been “short-circuited” in (1, 3)-Nimhoff! Note that in Wythoff, taking (k, k) short-circuits 0-values, but in (k, k + 1)-Nimdi, no g-values have been short-circuited. More generally, given piles of sizes (a1 , . . . , an ) and a move set of the form S = (b1 , . . . , bn ), where ai ∈ Z+ and bi ∈ Z0 for i ∈ {1, . . . , n} such that b1 + . . . + bn > 0, the moves of the game Take are of two types: (i) Taking any positive number m from a single pile, so (a1 , . . . , an ) → (a1 , . . . , ai−1 , ai − m, ai+1 , . . . , an ). (ii) Taking b1 , . . . , bn from all the piles, so (a1 , . . . , an ) → (a1 − b1 , . . . , an − bn ). Under what conditions is Take a Nimdi (Nim-in-disguise) game, i.e., a game whose g-values are exactly those of Nim? Blass and Fraenkel (to appear) have proved that Take is a Nimdi-game if and only if S is an odd set in the following sense: let m be the nonnegative integer such that ai 2−m is an integer for all i but Pn aj 2−m−1 is not an integer for some j. Then S is odd if k=1 ak 2−m is an odd integer. The divide and conquer methodology now suggests that we approach Wythoff gradually, by short-cicuiting only retricted sets of g-values of Nim, thus 0 1 2 3
1 0 3 2
2 3 0 1
3 2 1 0
4 5 6 7
5 4 7 6
6 7 4 5
7 6 5 4
8 9 10 11
9 8 11 10
10 11 8 9
11 10 9 8
Table 2. The first few g-values of (k, k + 1)-Nimdi. 0 1 2
1 0 3
2 3 0
3 2
4 5
5 4
6 7
7 6
8 9
9 8
10 11
11 10
Table 3. The first few g-values of (1,3)-Nimhoff.
32
AVIEZRI S. FRAENKEL
generating a family of non-Nimdi games. Several such case studies of Nimhoff games are included in [Fraenkel and Lorberbom 1991]. For example, consider Cyclic Nimhoff , so named because of the cyclic strucP ture of the g-values, where the restriction is 0 < ni=1 bi < h, where h ∈ Z+ is a fixed parameter. Thus h = 1 or h = 2 is Nim; n = 2, h = 3 is the fairy chess king-rook game; and n = 2, h = 4 is the fairy chess game king-rook-knight game. For a general cyclic Nimhoff game with pile sizes (a1 , . . . , an ), we have g(a1 , . . . , an ) = h(ba1 /hc ⊕ · · · ⊕ ban /hc) + (a1 + · · · + an ) mod h. This formula implies that cyclic Nimhoff has a polynomial strategy for every fixed h. Note the combination of Nim-sum and ordinary sum, somewhat reminiscent of the strategy of Welter. As another example, consider 2k -Nimhoff, where k is any fixed positive integer. In this game we can remove 2k tokens from two distinct piles, or remove a positive k b = number of tokens from any single pile. Define the k-Nim-sum by a a ⊕ b ⊕ ak bk . In other words, the k-Nim-sum of a and b is a ⊕ b, unless the k-th bits of a and b are both 1, in which case the least significant bit of a ⊕ b is complemented. The k-Nim-sum is not a generalization of Nim-sum, but it is associative. For 2k -Nimhoff with n piles we then have k ··· k an . g(a1 , . . . , an ) = a1
Now that we have gained some understanding of the true nature of Wythoff’s game, we can exploit it in at least two ways: 1. Interesting games seem to be obtained when we adjoin to a game its P positions as moves! For example, consider W 2 , which is Nim with the adjunction of (k, k) and Wythoff’s P -positions as moves. We leave it as an exercise to compute the P -positions of W 2 , and to iterate other games in the indicated manner. 2. A generalization of Wythoff to more than two piles has long been sought. It’s now clear what has to be done: for three-pile Wythoff, the moves are to either take any positive number of tokens from a single pile, or take from all three, say k, l, m (with k + l + m > 0), such that k ⊕ l ⊕ m = 0. This is clearly a generalization of the usual two-pile Wythoff’s game. Initial values of the P positions [Chaba and Fraenkel] are listed in Table 4, namely the cases j = 0 (one of the three piles is empty—the usual Wythoff game) and j = 1 (one of the three piles has size 1). Recall that for two-pile Wythoff the golden section plays an important role. The same holds for three-pile Wythoff, except that there are many “initial disturbances”, as in so many other impartial games. A rather curious variation of the classical theory is epidemiography, motivated by the study of long games, especially the Hercules–Hydra game; see the survey article [Neˇsetˇril and Thomas 1987]. Several perverse and maniacal forms of
SCENIC TRAILS ASCENDING FROM SEA-LEVEL NIM TO ALPINE CHESS
33
the malady were examined in [Fraenkel and Neˇsetˇril 1985; Fraenkel, Loebl and Neˇsetˇril 1988; Fraenkel and Lorberbom 1989]. The simplest variation is a mild case of Dancing Mania, called Nimania, sometimes observed in post-pneumonia patients. In Nimania we are given a positive integer n. Player 1 begins by subtracting 1 from n. If n = 1, the result is the empty set, and the game ends with player 1 winning. If n > 1, one additional copy of the resulting number n − 1 is adjoined, so at the end of the first move there are two (indistinguishable) copies of n − 1 (denoted (n − 1)2 ). At the k-th stage, where k ≥ 1, a move consists of selecting a copy of a positive integer m of the present position, and subtracting 1 from it. If m = 1, the copy is deleted. If m > 1, then k copies of m − 1 are adjoined to the resulting m − 1 copies. D0
j
B0
C0
D0
j
B0
C0
D1
j
B1
C1
D1
j
B1
C1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 3 4 6 8 9 11 12 14 16 17 19 21 22 24 25 27 29 30 32 33 35 37 38 40 42 43 45 46 48
0 2 5 7 10 13 15 18 20 23 26 28 31 34 36 39 41 44 47 49 52 54 57 60 62 65 68 70 73 75 78
31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
50 51 53 55 56 58 59 61 63 64 66 67 69 71 72 74 76 77 79 80 82 84 85 87 88 90 92 93 95 97 98
81 83 86 89 91 94 96 99 102 104 107 109 112 115 117 120 123 125 128 130 133 136 138 141 143 146 149 151 154 157 159
0 1 4 6 7 3 8 9 5 12 10 11 15 16 13 18 14 20 21 19 23 24 25 26 27 28 29 30 31 32 33
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 3 5 6 7 8 10 13 15 16 17 19 21 23 24 25 26 29 31 32 33 34 35 38 41 42 44 45 46 47 48
1 4 9 12 14 11 18 22 20 28 27 30 36 39 37 43 40 49 52 51 56 58 60 64 68 70 73 75 77 79 81
34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
50 53 54 55 57 59 61 62 63 65 66 67 69 71 72 74 76 78 80 82 83 85 86 87 89 91 93 94 96 97 99
84 88 90 92 95 98 101 103 105 108 110 112 115 118 120 123 126 129 132 135 137 140 142 144 147 150 153 155 158 160 163
Table 4. Initial P -positions in three-pile Wythoff.
34
AVIEZRI S. FRAENKEL
2 wins 17 3
2
2
1 wins
3
17
2, 1
2
2 wins 17
2, 1
2, 1
1 wins 2
17
Figure 19. Player 1 can win Nimania for n = 3 in 13 moves. Solid arrows indicate Player 1’s moves, and dashed arrows those of Player 2.
Since the numbers in successive positions decrease, the game terminates. Who wins? For n = 1 we saw above that player 1 wins. For n = 2, player 1 moves to 12 , player 2 to 1, hence player 1 again wins. For n = 3, Figure 19 shows that by following the lower path, player 1 can again win. Unlike the cases n = 1 and n = 2, however, not all moves of player 1 for n = 3 are winning. An attempt to resolve the case n = 4 by constructing a diagram similar to Figure 19 is rather frustrating. It turns out that for n = 4 the loser can delay the winner so that play lasts over 244 moves! We have proved, however, the following surprising facts: (i) Player 1 can win for every n ≥ 1. (ii) For n ≥ 4, player 1 cannot hope to see his win being consummated in any n−2 reasonable amount of time: the smallest number of moves is ≥ 22 , and the largest is an Ackermann function. (iii) For n ≥ 4, player 1 has a robust winning strategy: most of the time player 1 can make random moves; only near the end of play does player 1 have to pay attention (as we saw for the case n = 3). In view of (ii), where we saw that the length of play is at least doubly exponential, it seems reasonable to say that Nimania is not tractable, though the winning strategy is robust.
7. What’s a Tractable or Efficient Strategy? We are not aware that these questions have been addressed before in the literature. Since “Nim-type” games are considered to have good strategies, we now abstract some of their properties in an attempt to define the notions of a “tractable” or “efficient” game, in a slightly more formal way than the way we have used them above. The subset T of combinatorial games with a tractable strategy has the following properties. For normal play of every G ∈ T , and every position u of G:
SCENIC TRAILS ASCENDING FROM SEA-LEVEL NIM TO ALPINE CHESS
35
(a) The P -, N - or D-label of u can be computed in polynomial time. (b) The next optimal move (from an N - to a P -position; from D- to a Dposition) can be computed in polynomial time. (c) The winner can consummate the win in at most an exponential number of moves. (d) The set T is closed under summation, i.e., G1 , G2 ∈ T implies G1 + G2 ∈ T (so (a), (b), (c) hold for G1 + G2 ). The subset T 0 ⊆ T for which (a)–(d) hold also for mis`ere play is the subset of efficient games. Remarks. (i) Instead of “polynomial time” in (a) and (b) we could have specified some low polynomial bound, so that some games complete in P (see, for example, [Adachi, Iwata and Kasai 1984]), and possibly annihilation games, would be excluded. But the decision about how low that polynomial should be would be largely arbitrary, and we would lose the closure under composition of polynomials. Hence we preferred not to do this. (ii) In (b) we could have included also a P -position, i.e., the requirement that the loser can compute in polynomial time a next move that makes play last as long as possible. In a way, this is included in (c). A more explicit enunciation on the speed of losing doesn’t seem to be part of the requirements for a tractable strategy. (iii) In Section 2 we saw that, for Scoring, play lasts for an exponential number of moves. In general, for succinct games, the loser can delay the win for an exponential number of moves. Is there a “more natural” succinct game for which the loser cannot force an exponential delay? There are some succinct games for which the loser cannot force an exponential delay, such as Kotzig’s Nim [Berlekamp, Conway and Guy 1982, Ch. 15] of length 4n and move set M = {n, 2n}. This example is somewhat contrived, in that M is not fixed, and the game is not primitive in the sense of [Fraenkel, Jaffray, Kotzig and Sabidussi 1995, Section 3]. Is there a “natural” nonsuccinct game for which the loser can force precisely an exponential delay? Perhaps an epidemiography game with a sufficiently slowly growing function f (where at move k we adjoin f (k) new copies; see [Fraenkel, Loebl and Neˇsetˇril 1988; Fraenkel and Lorberbom 1989]), played on a general digraph, can provide an example. (iv) There are several ways of compounding a given finite set of games—moving rules and ending rules. See, for example, [Conway 1976, Ch. 14]. Since the sum of games is the most natural, fundamental and important among the various compounds, we only required in (d) closure under game sums. (v) One might consider a game efficient only if both its succinct and nonsuccinct versions fulfil conditions (a)–(d). But given a succinct game, there are often many different ways of defining a nonsuccinct variation; and given a nonsuccinct
36
AVIEZRI S. FRAENKEL
game, it is often not so clear what its succinct version is, if any. Hence this requirement was not included in the definition. A panorama of the poset of strategy efficiencies can be viewed by letting Murphy’s law loose on the tractability and efficiency definitions. Just about any perverse game behavior one may think of can be realized by some perturbation of (a)–(d). We have already met mis`ere play, interaction between tokens and succinctness. These tend to affect (d) adversely. Yet we are not aware that mis`ere play has been proven to be NP-hard, nor do we know of any succinct game that has been proven NP-hard; the complexity of so many succinct games is still open! But there are many interesting games involving interaction between tokens that have been proven Pspace-complete, Exptime-complete, or even Expspacecomplete. We have also seen that epidemiography games violate (c), and that Whythoff’s game is not known to satisfy (d). The same holds for Moore’s Nim [Moore 1909– 10; Berlekamp, Conway and Guy 1982, Ch. 15], so for both Wythoff’s game and Moore’s Nim we only have, at present, a reasonable strategy in the sense of Section 2. For partizan games (d) is violated conditionally, in the sense that sums are Pspace-complete. (It’s not more than a curiousity that certain sums of impartial Pspace-hard games are polynomial. Thus geography is Pspacecomplete [Schaefer 1978]. Yet given two identical geography games, player 2 can win easily by imitating on one copy what the opponent does on the other.) Incidentally, geography games [Fraenkel and Simonson 1993; Fraenkel, Scheinerman and Ullman 1993; Bodlaender 1993; Fraenkel, Jaffray, Kotzig and Sabidussi 1995] point to another weakness of the classical theory. The input digraph or graph is not succinct, the game does not appear to decompose into a sum, and the game graph is very large. This accounts for the completeness results of many geography games. While we’re at it, we point out another property of geography games. Their initial position, as well as an “arbitrary” mid-position, are Pspace-complete, since one is as complex as the other: the initial position has the same form as any mid-position. In fact, this is the case for their prototype, quantified Boolean satisfiability [Stockmeyer and Meyer 1973]. On the other hand, for board games such as checkers, chess, Go, Hex, Shogi or Othello, the completeness result holds for an arbitrary position, i.e., a “midgame” or “endgame” position, carefully concocted in the reduction proof. See, for example, [Fraenkel, Garey, Johnson, Schaefer and Yesha 1978; Lichtenstein and Sipser 1978; Fraenkel and Lichtenstein 1981; Robson 1984a; Robson 1984b; Adachi, Kamekawa and Iwata 1987; Iwata and Kasai 1994]. But for the initial position, which is rather simple or symmetric, the decision question who can win might be easier to solve. For poset games with a largest element and for Hex it’s in fact easy to see that player 1 can win, but the proof of this fact is nonconstructive. Yet one of these games, von Neumann’s Hackendot, has been given an interesting polynomial
SCENIC TRAILS ASCENDING FROM SEA-LEVEL NIM TO ALPINE CHESS
37
´ strategy by Ulehla [1980]. See also Bushenhack in [Berlekamp, Conway and Guy 1982, Ch. 17]. Still unresolved poset games include chomp [Gale 1974] and a power-set game [Gale and Neyman 1982]; see also [Fraenkel and Scheinerman 1991]. The outcome of certain games can be made to depend on open problems in mathematics. See, for example, [Jones 1982; Jones and Fraenkel ≥ 1996]. Lastly, but far from exhaustively, we mention a game in which “the loser wins”. Let Q = x1 − x2 x4 − x2 − x4 − 1. Two players alternately assign values to x1 , x2 , x3 , x4 in this order. Player 1 has to select x1 as a composite integer > 1 and x3 as any positive integer, and player 2 selects any positive integers. Player 2 wins if Q = 0; otherwise player 1 wins. It should be clear that player 2 can win, since Q = x1 − (x2 + 1)(x4 + 1) and x1 is composite. But if player 1 picks x1 as the product of 2 large primes of about the same size, then player 2 can realize his win in practice only if he can crack the RSA public-key cryptosystem [Rivest, Shamir and Adleman 1978]. Thus, in practice, the loser wins! Also note that player 2 has an efficient probabilistic method, such as those of [Solovay and Strassen 1977; Rabin 1976; 1980], to determine with arbitrarily small error that player 1 did not cheat, that is, that he indeed selected a composite integer.
References 1. [Adachi, Iwata and Kasai 1984] A. Adachi, S. Iwata and T. Kasai, “Some combinatorial game problems require Ω(nk ) time”, J. Assoc. Comput. Mach. 31 (1984), 361–376. 2. [Adachi, Kamekawa and Iwata 1987] H. Adachi, H. Kamekawa and S. Iwata, “Shogi on n×n board is complete in exponential time” (in Japanese), Trans. IEICE J70-D (1987), 1843–1852. 3. [Banerji and Dunning 1992] R. B. Banerji and C. A. Dunning, “On misere games”, Cybernetics and Systems 23 (1992), 221–228. 4. [Beck 1981] J. Beck, “On positional games”, J. Combin. Theory A30 (1981), 117– 133. 5. [Beck 1982] J. Beck, “Remarks on positional games, I”, Acta Math. Acad. Sci. Hungar. 40(1–2) (1982), 65–71. 6. [Beck 1985] J. Beck, “Random graphs and positional games on the complete graph”, Ann. Discrete Math. 28 (1985), 7–13. 7. [Berlekamp, Conway and Guy 1982] E. R. Berlekamp, J. H. Conway and R. K. Guy, Winning Ways for Your Mathematical Plays, Academic Press, London, 1982. 8. [Berlekamp and Wolfe 1994] E. Berlekamp and D. Wolfe, Mathematical Go: Chilling Gets the Last Point, A. K. Peters, Wellesley, MA, 1994. 9. [Blass and Fraenkel 1990] U. Blass and A. S. Fraenkel, “The Sprague–Grundy function of Wythoff’s game”, Theor. Comput. Sci. (Math Games) 75 (1990), 311– 333. 10. [Bodlaender 1993] H. L. Bodlaender, “Complexity of path forming games”, Theor. Comput. Sci. (Math Games) 110 (1993), 215–245.
38
AVIEZRI S. FRAENKEL
11. [Chv´ atal 1973] V. Chv´ atal, “On the computational complexity of finding a kernel”, Report No. CRM-300, Centre de Recherches Math´ematiques, Universit´e de Montr´eal (1973). 12. [Chv´ atal and Erd˝ os 1978] V. Chv´ atal and P. Erd˝ os, “Biased positional games”, pp. 221–229 in Algorithmic Aspects of Combinatorics (edited by B. Alspach et al.), Ann. Discrete Math. 2, North-Holland, Amsterdam, 1978. 13. [Conway 1976] J. H. Conway, On Numbers and Games, Academic Press, London, 1976. 14. [Conway 1977] J. H. Conway, “All games bright and beautiful”, Amer. Math. Monthly 84 (1977), 417–434. 15. [Conway 1978a] J. H. Conway, “A gamut of game theories”, Math. Mag. 51 (1978), 5–12. 16. [Conway 1978b] J. H. Conway, “Loopy games”, pp. 55–74 in Proc. Symp. Advances in Graph Theory (edited by B. Bollob´ as), Ann. Discrete Math. 3, North-Holland, Amsterdam, 1978. 17. [Ehrenfeucht and Mycielski 1979] A. Ehrenfeucht and J. Mycielski, “Positional strategies for mean payoff games”, Internat. J. Game Theory 8 (1979), 109–113. 18. [Ferguson 1984] T. S. Ferguson, “Mis`ere annihilation games”, J. Combin. Theory A37 (1984), 205–230. 19. [Fraenkel 1974] A. S. Fraenkel, “Combinatorial games with an annihiliation rule”, pp. 87–91 in The Influence of Computing on Mathematical Research and Education (edited by J. P. LaSalle), Proc. Symp. Appl. Math. 20, Amer. Math. Soc., Providence, RI, 1974. 20. [Fraenkel 1981] A. S. Fraenkel, “Planar kernel and Grundy with d ≤ 3, dout ≤ 2, din ≤ 2 are NP-complete”, Discrete Appl. Math. 3 (1981), 257–262. 21. [Fraenkel 1982] A. S. Fraenkel, “How to beat your Wythoff games’ opponents on three fronts”, Amer. Math. Monthly 89 (1982), 353–361. 22. [Fraenkel 1991] A. S. Fraenkel, “Complexity of games”, pp. 111–153 in Combinatorial Games (edited by R. K. Guy), Proc. Symp. Appl. Math. 43, Amer. Math. Soc., Providence, RI, 1991. 23. [Fraenkel ≥ 1997] A. S. Fraenkel, Adventures in Games and Computational Complexity, to appear in Graduate Studies in Mathematics, Amer. Math. Soc., Providence, RI. 24. [Fraenkel and Borosh 1973] A. S. Fraenkel and I. Borosh, “A generalization of Wythoff’s game”, J. Combin. Theory A15 (1973), 175–191. 25. [Fraenkel, Garey, Johnson, Schaefer and Yesha 1978] A. S. Fraenkel, M. R. Garey, D. S. Johnson, T. Schaefer and Y. Yesha, “The complexity of checkers on an n × n board – preliminary report”, pp. 55–64 in Proc. 19th Annual Symp. Foundations of Computer Science, IEEE Computer Soc., Long Beach, CA, 1978. 26. [Fraenkel and Goldschmidt 1987] A. S. Fraenkel and E. Goldschmidt, “Pspacehardness of some combinatorial games”, J. Combin. Theory A46 (1987), 21–38. 27. [Fraenkel, Jaffray, Kotzig and Sabidussi 1995] A. S. Fraenkel, A. Jaffray, A. Kotzig and G. Sabidussi, “Modular Nim”, Theor. Comput. Sci. (Math Games) 143 (1995), 319–333.
SCENIC TRAILS ASCENDING FROM SEA-LEVEL NIM TO ALPINE CHESS
39
28. [Fraenkel and Lichtenstein 1981] A. S. Fraenkel and D. Lichtenstein, “Computing a perfect strategy for n × n chess requires time exponential in n”, J. Combin. Theory A31 (1981), 199–214. Preliminary version appeared as pp. 278–293 in Automata, Languages and Programming, Acre, Israel, 1981 (edited by S. Even and O. Kariv), Lecture Notes Comp. Sci. 115, Springer, Berlin, 1981. 29. [Fraenkel, Loebl and Neˇsetˇril 1988] A. S. Fraenkel, M. Loebl and J. Neˇsetˇril, “Epidemiography, II. Games with a dozing yet winning player”, J. Combin. Theory A49 (1988), 129–144. 30. [Fraenkel and Lorberbom 1989] A. S. Fraenkel and M. Lorberbom, “Epidemiography with various growth functions”, Discrete Appl. Math. 25 (1989), 53–71. 31. [Fraenkel and Lorberbom 1991] A. S. Fraenkel and M. Lorberbom, “Nimhoff games”, J. Combin. Theory A58 (1991), 1–25. 32. [Fraenkel and Neˇsetˇril 1985] A. S. Fraenkel and J. Neˇsetˇril, “Epidemiography”, Pacific J. Math. 118 (1985), 369–381. 33. [Fraenkel and Perl 1975] A. S. Fraenkel and Y. Perl (1975), “Constructions in combinatorial games with cycles”, pp. 667–699 in Proc. Intern. Colloq. on Infinite and Finite Sets (edited by A. Hajnal et al.), vol. 2, Colloq. Math. Soc. J´ anos Bolyai 10 North-Holland, Amsterdam, 1975. 34. [Fraenkel and Scheinerman 1991] A. S. Fraenkel and E. R. Scheinerman, “A deletion game on hypergraphs”, Discrete Appl. Math. 30 (1991), 155–162. 35. [Fraenkel, Scheinerman and Ullman 1993] A. S. Fraenkel, E. R. Scheinerman and D. Ullman, “Undirected edge geography”, Theor. Comput. Sci. (Math Games) 112 (1993), 371–381. 36. [Fraenkel and Simonson 1993] A. S. Fraenkel and S. Simonson, “Geography”, Theor. Comput. Sci. (Math Games) 110 (1993), 197–214. 37. [Fraenkel and Tassa 1975] A. S. Fraenkel and U. Tassa, “Strategy for a class of games with dynamic ties”, Comput. Math. Appl. 1 (1975), 237–254. 38. [Fraenkel and Tassa 1982] A. S. Fraenkel and U. Tassa, “Strategies for compounds of partizan games”, Math. Proc. Camb. Phil. Soc. 92 (1982), 193–204. 39. [Fraenkel, Tassa and Yesha 1978] A. S. Fraenkel, U. Tassa and Y. Yesha, “Three annihilation games”, Math. Mag. 51 (1978), 13–17. 40. [Fraenkel and Yesha 1976] A. S. Fraenkel and Y. Yesha, “Theory of annihilation games”, Bull. Amer. Math. Soc. 82 (1976), 775–777. 41. [Fraenkel and Yesha 1979] A. S. Fraenkel and Y. Yesha, “Complexity of problems in games, graphs and algebraic equations”, Discrete Appl. Math. 1 (1979), 15–30. 42. [Fraenkel and Yesha 1982] A. S. Fraenkel and Y. Yesha, “Theory of annihilation games – I”, J. Combin. Theory B33 (1982), 60–86. 43. [Fraenkel and Yesha 1986] A. S. Fraenkel and Y. Yesha, “The generalized Sprague– Grundy function and its invariance under certain mappings”, J. Combin. Theory A43 (1986), 165–177. 44. [Gale 1974] D. Gale, “A curious Nim-type game”, Amer. Math. Monthly 81 (1974), 876–879. 45. [Gale and Neyman 1982] D. Gale and A. Neyman, “Nim-type games”, Internat. J. Game Theory 11 (1982), 17–20.
40
AVIEZRI S. FRAENKEL
46. [Gangolli and Plambeck 1989] A. Gangolli and T. Plambeck, “A note on periodicity in some octal games”, Internat. J. Game Theory 18 (1989), 311–320. 47. [Goldstein and Reingold 1995] A. S. Goldstein and E. M. Reingold, “The complexity of pursuit on a graph”, Theor. Comput. Sci. (Math Games) 143 (1995), 93–112. 48. [Grundy 1939] P. M. Grundy, “Mathematics and Games”, Eureka 2 (1939), 6–8. Reprinted in Eureka 27 (1964), 9–11. 49. [Guy and Smith 1956] R. K. Guy and C. A. B. Smith, “The G-values of various games”, Proc. Camb. Phil. Soc. 52 (1956), 514–526. 50. [Iwata and Kasai 1994] S. Iwata and T. Kasai, “The Othello game on an n×n board is PSPACE-complete”, Theor. Comput. Sci. (Math Games) 123 (1994), 329–340. 51. [Jones 1982] J. P. Jones, “Some undecidable determined games”, Internat. J. Game Theory 11 (1982), 63–70. 52. [Jones and Fraenkel ≥ 1996] J. P. Jones and A. S. Fraenkel, “Complexities of winning strategies in polynomial games”, J. Complexity, in press. 53. [Kalm´ ar 1928] L. Kalm´ ar, “Zur Theorie der abstrakten Spiele”, Acta Sci. Math. Univ. Szeged 4 (1928), 65–85. 54. [van Leeuwen 1976] J. van Leeuwen, “Having a Grundy-numbering is NPcomplete”, Report No. 207, Computer Science Dept., Pennsylvania State Univ., 1976. 55. [Li 1976] S.-Y. R. Li, “Sums of Zuchswang games”, J. Combin. Theory A21 (1976), 52–67. 56. [Lichtenstein and Sipser 1978] D. Lichtenstein and M. Sipser, “Go is PolynomialSpace hard”, J. Assoc. Comput. Mach. 27 (1980), 393–401. Earlier draft appeared as pp. 48–54 in 19th Annual Symposium on Foundations of Computer Science, Ann Arbor, MI, 1978, IEEE Computer Soc., Long Beach, CA, 1978. 57. [Moews 1994] Chapter 5 in [Berlekamp and Wolfe 1994]. 58. [Moore 1909–10] E. H. Moore, “A generalization of the game called nim”, Ann. of Math. 11, ser. 2 (1909–10), 93–94. 59. [Morris 1981] F. L. Morris, “Playing disjunctive sums is polynomial space complete”, Internat. J. Game Theory 10 (1981), 195–205. 60. [Neˇsetˇril and Thomas 1987] J. Neˇsetˇril and R. Thomas (1987), “Well quasi ordering, long games and combinatorial study of undecidability”, pp. 281–293 in Logic and Combinatorics (edited by S. G. Simpson), Contemp. Math. 65, Amer. Math. Soc., Providence, RI, 1987. 61. [Pink 1991] N. Pink, “Wythoff’s game and some properties of its Grundy scheme”, preprint, 1991. 62. [Plambeck 1992] T. E. Plambeck, “Daisies, Kayles, and the Sibert–Conway decomposition in mis`ere octal games”, Theor. Comput. Sci. (Math Games) 96 (1992), 361–388. 63. [Rabin 1957] M. O. Rabin, “Effective computability of winning strategies”, pp. 147– 157 in Contributions to the Theory of Games (edited by H. W. Kuhn and A. W. Tucker), Ann. of Math. Studies 39, Princeton Univ. Press, Princeton, 1957.
SCENIC TRAILS ASCENDING FROM SEA-LEVEL NIM TO ALPINE CHESS
41
64. [Rabin 1976] M. O. Rabin, “Probabilistic algorithms”, pp. 21–39 in Algorithms and Complexity: New Directions and Recent Results (edited by J. F. Traub), Academic Press, New York, 1976. 65. [Rabin 1980] M. O. Rabin, “Probabilistic algorithm for testing primality”, J. Number Theory 12 (1980), 128–138. 66. [Rivest, Shamir and Adleman 1978] R. L. Rivest, A. Shamir and L. Adleman, “A method for obtaining digital signatures and public-key cryptosystems”, Comm. ACM 21 (1978), 120–126. 67. [Robson 1984a] J. M. Robson, “Combinatorial games with exponential space complete decision problems”, pp. 498–506 in Math. Foundations of Computer Science 1984 (edited by M. P. Chytil and V. Koubek), Lecture Notes in Computer Science 176, Springer, Berlin, 1984. 68. [Robson 1984b] J. M. Robson, “N by N checkers is Exptime complete”, SIAM J. Comput. 13 (1984), 252–267. 69. [Schaefer 1978] T. J. Schaefer, “On the complexity of some two-person perfect-information games”, J. Comput. System Sci. 16 (1978), 185–225. 70. [Shaki 1979] A. S. Shaki, “Algebraic solutions of partizan games with cycles”, Math. Proc. Camb. Phil. Soc. 85 (1979), 227–246. 71. [Sibert and Conway 1992] W. L. Sibert and J. H. Conway, “Mathematical Kayles”, Internat. J. Game Theory 20 (1992), 237–246. 72. [Smith 1966] C. A. B. Smith, “Graphs and composite games”, J. Combin. Theory 1 (1966), 51-81. Reprinted in slightly modified form in A Seminar on Graph Theory (edited by F. Harary), Holt, Rinehart and Winston, New York, 1967. 73. [Solovay and Strassen 1977] R. Solovay and V. Strassen, “A fast Monte-Carlo test for primality”, SIAM J. Comput. 6 (1977), 84–85. Erratum, ibid. 7 (1978), 118. ¨ 74. [Sprague 1935–36] R. Sprague, “Uber mathematische Kampfspiele”, Tˆ ohoku Math. J. 41 (1935–36), 438–444. 75. [Stockmeyer and Meyer 1973] L. J. Stockmeyer and A. R. Meyer (1973), “Word problems requiring exponential time”, pp. 1-9 in Fifth Annual ACM Symp. on Theory of Computing, Assoc. Comput. Mach., New York, 1973. ´ ´ 76. [Ulehla 1980] J. Ulehla, “A complete analysis of von Neumann’s Hackendot”, Internat. J. Game Theory 9 (1980), 107–113. 77. [Wythoff 1907] W. A. Wythoff, “A modification of the game of Nim”, Nieuw Arch. Wisk. 7 (1907), 199–202. 78. [Yaglom and Yaglom 1967] A. M. Yaglom and I. M. Yaglom, Challenging Mathematical Problems with Elementary Solutions (translated by J. McCawley, Jr.; revised and edited by B. Gordon), vol. 2, Holden-Day, San Francisco, 1967. 79. [Yedwab 1985] L. J. Yedwab, “On playing well in a sum of games”, M.Sc. Thesis, MIT, 1985. Issued as MIT/LCS/TR-348, MIT Laboratory for Computer Science, Cambridge, MA. 80. [Zwick and Paterson ≥ 1996] U. Zwick and M. S. Paterson, “The complexity of mean payoff games on graphs”. Preprint at http://www.math.tau.ac.il/~ zwick. Preliminary version to appear in Proc. COCOON 1995, Xi’an, China. Final version submitted to Theor. Comput. Sci. (Math Games).
42
AVIEZRI S. FRAENKEL
Aviezri S. Fraenkel Department of Applied Mathematics and Computer Science Weizmann Institute of Science Rehovot 76100, Israel
[email protected] http://www.wisdom.weizmann.ac.il/˜ fraenkel/fraenkel.html
Games of No Chance MSRI Publications Volume 29, 1996
Championship-Level Play of Dots-and-Boxes JULIAN WEST
Abstract. A single-elimination Dots-and-Boxes tournament was held during the MSRI meeting, with a $500 purse. This is an analysis of the finals, in which Daniel Allcock defeated Martin Weber, playing both first and second player. A systematic notation is developed for the analysis.
Dots-and-Boxes, described in Chapter 16 of Winning Ways [Berlekamp et al. 1982], is a game played on a finite rectangular unit lattice of dots (or, in dualized form, on an arbitrary graph). A move consists of joining two adjacent dots, that is, dots at distance one; if this completes one or more squares, a point (“box”) is awarded for each and the player retains her turn. A move after which turn does not pass to the opponent is known as a complimenting move and, under socalled normal win conditions—last player to move wins—leads to so-called loony values (explained below). However, Dots-and-Boxes does not have a normal win condition; indeed, analysis is complicated considerably by the unusual who-dieswith-the-most-wins condition. Under various names, this game is popular with children in many countries. As played by most practitioners, it is a fairly uninteresting game, consisting of a phase of randomly segmenting the board followed by a phase of greedily dividing up the spoils. So it would seem an odd choice for a tournament between serious game theory researchers. But Dots-and-Boxes is a classic example of a game that is Harder Than You Think. Winning Ways (p. 535) gives an account of all the stages you will go through in becoming a Dots-and-Boxes expert: • abandon the greedy approach in favour of double-dealing moves; • learn the parity rule for long chains; • become an expert at Strings-and-Coins; • (and so) become an expert at Nimstrings; • apply Twopins theory; become an expert at Kayles; • recognize the exceptional cases where Nimstrings does not suffice to analyse Dots-and-Boxes. 79
80
JULIAN WEST
Finally, it goes on to demonstrate that Dots-and-Boxes, played on general graphs, is NP-hard (p. 543). This is rather daunting, but for our present purposes we shall only really need to know the parity rule and one observation drawn from Nimstrings. We’ll be able to illustrate each by using the games to hand, so we exhibit these games now: see Figure 1. The games were played on a grid of six dots by six, and are shown here near completion, well beyond the point where the outcome has become obvious. (Since future play by a sensible player can now be predicted, these diagrams give a complete account of each game. Nevertheless, we’ll also present a diagram of one game at an earlier stage, in order to illustrate crucial stages in the play.) In each of these games, the moves of the first player (Dodie) are shown with Dotted lines; therefore the first edge drawn is the dotted one numbered 1, and the second edge drawn is the solid one numbered 1. Sometimes multiple edges are played in one turn; when this happens we have labelled them as, say, 15a, 15b, 15c. When either player claims a square, a D (for Dodie) or an E (for Evie) is entered; we have placed the letter slightly off centre in the direction of the edge that completed the square. Every edge approached by a D or an E bears a letter, since it was a complimenting move, though not every edge bearing a letter completed a square, since it may have been the last edge of a turn. Note that (by coincidence) Dodie’s move 16a completed two boxes in each game. Moves that claim two boxes are called double-crossing moves; they are fundamental in the analysis of Dots-and-Boxes. Consider the situation in Figure 1, top. Evie has just claimed the box at upper right (18a) and with her move at 18b opens up two boxes for Dodie. Such a move is called a hard-hearted handout; Dodie has no reason not to take the two free boxes, and therefore no real choice. But after this she is stuck: she must either move in the four-box chain or the six-box loop, and any move here allows Evie to capture boxes. We say that Evie has control. In either region, Evie will be able to retain control by “politely declining” the last squares, making a double-dealing move—that is, one that invites a double-crossing one in reply. If you don’t know how to decline the last two boxes in a chain, you should work it out as an exercise: you will then be able to defeat most casual players of Dots-and-Boxes! So if Dodie moves in the chain, Evie has a choice between taking all four boxes and surrendering the remaining six, or taking only two boxes and getting the remaining six on her following turn. Alternatively, if Dodie moves in the loop, Evie can either claim six boxes and surrender four, or claim only two boxes (since it requires four boxes—in other words, two double-dealing moves—to decline a loop) and get four on her next turn. Evie thus has a chance to get eight boxes if Dodie moves in the chain, and at best six if Dodie moves in the loop, so Dodie should move in the loop. Nevertheless, Evie will win the game, with 13 boxes to Dodie’s 12.
CHAMPIONSHIP-LEVEL PLAY OF DOTS-AND-BOXES
t
14b
11
E
t
12
E 14a
t
12
14c
t
D
14b
D 15a
t
9
t
E 15c
t
t
4
18b
t
t
t
5
8
D
t
1
D 14a
t
15a
t
6
E
15b
t
13
E
10
10
E 15b
7
t
1
t
13b
D
t
18a
t
11
E
18
t
9b
t
9a
t
2
t
6
2
t 8
t
t
t
3
16
3
t
t
t
16a
t
7
D
5
16b
t
13a
t
15d
t
4
t
17
t
t
t
13
t
10
t
18a
t
18b
t
17
12
11
E
18c
E
13
t
t
17
t
16b
t
12 9
t
9
2
t
16
t
4
E 14b
t
t
1
t
14a
18c
t
t 8
7
D 18a
t 17
t
10
D 18b
t
14
E
11
t
3
t
7
15
t
t
1 2
D
t 14c
t
16a
t
15c
D
8
t
3
t
6
D 15a
D 15b
t
t
5
4
t
t
6
t
5
t
Figure 1. Near-ending position in the two games of the MSRI Dots-and-Boxes tournament finals. Dodie (D) to move in each case; dashed lines indicate her moves.
81
82
JULIAN WEST
If there were two long chains on this 6 × 6 dot board, they would both be claimed by Dodie, not Evie. (A long chain is one with at least three boxes in it, so that it is always possible to decline the last two with a double-dealing move.) This is because of the parity rule mentioned earlier: Dodie wishes to make the number of initial dots plus double-crossed moves odd, whereas Evie wishes to make it even. In the most straightforward type of game, the number of double-crossing moves is one fewer than the number of long chains, and we have 36 dots, so a single long chain is (usually) a win to Evie. If the players feel that the number of eventual long chains will be just one or two, Evie will try to keep the chain intact, and Dodie will try to split it up. If they feel that the board is headed for two or three long chains, it is Evie who will be trying to split things up. A game of Dots-and-Boxes is usually a fight to gain control by forcing the number of evenutal long chains to have the right parity. Generally, there are enough long chains, and the chains sufficiently long, that this is where the game is settled. However, in game 1 very few of the boxes were claimed in long chains: there is the chain of length four at upper right, and the chain of length three that went at Evie’s move 15. (There is also the loop of length six). Game 1 was a game dominated by sacrifices; both players had to surrender boxes in their efforts to gain control. After the game, Evie announced that she had won by counting individual boxes, rather than paying exclusive attention to the parity rule. The outcome of game 2 is confusing at first sight: there appears to be a single long chain, but it will be claimed by Dodie, not Evie as we might expect. The reason is that one long chain has already been claimed, as can be seen from Dodie’s double-crossed move at 16a. (Evie will make two more double-crossed moves, because Dodie’s next move will be to decline the loop. But the total number will be odd, as Dodie wants it to be.) By turn 11, both players could see that there was one chain of at least six boxes, and another, at the bottom, of at least four boxes. Since there will be at least two long chains, Evie hoped to create a third one, but Dodie prevented this with a series of strong moves. First she extended the six-box chain to nine boxes with her moves 11, 12 and 13. This left only two boxes at the upper left not in this chain—not enough to form a long chain on their own. Then, by sacrificing two boxes with a hard-hearted handout at turn 14, she prevented the development of a long chain at the upper right. At this point, Evie surrendered and moved at turn 14c in a long chain— an explicitly suicidal move, as we will explain. Even though she didn’t have to move in a long chain yet, she knew she would have to eventually, because of the parity rule. So her turn 14c is much like a player resigning in chess as soon as the checkmate becomes evident. Both players then played out the game with intentionally cavalier moves—the two boxes that Dodie takes on turn 16 could have been taken by either player on turn 15, but both declined as a gesture of futility. For clarity, we redraw in Figure 2 the situation just after this move.
CHAMPIONSHIP-LEVEL PLAY OF DOTS-AND-BOXES
t
t
13
t
10
12
t
t
t
9
t
t
9
2
t
t
4
E 14b
t
t
15
t
13
t
1
t
14a
7
t
t
10
t
14
E
11
t
3
t
7
t
t
t
11
12
t
t
1 2
t
6
t
t
8
14c
5
4
t
t
t
t
8
6
t
t
t
83
3
5
t
Figure 2. Position in game 2 just after Evie (full lines) plays her move 14c, at which point both players knew Dodie would win.
The reason Evie’s move 14c is suicidal comes from a simple strategy-stealing argument in the theory of Nimstrings. Nimstrings is just Dots-and-Boxes with the normal win condition of last-to-move-wins. Move 14c allows the choice of two replies (those edges labelled 15a and 15b in our example). Consider the entire game position with the exception of these two boxes: it must be a win for either the first player or the second player (though it may in general be very hard to know which). Arrange to be the appropriate player by either: moving at 15a, then 15b, then going on to be player 1 on the remaining position; or moving at 15b, then stopping so as to become player 2 on the remaining position. (One player or another will eventually claim the two free boxes left by this second option, but in Nimstrings we don’t care who.) In Nimstrings, 14c is therefore an example of a loony move. The value loony is an extension to the field of nimbers from Sprague–Grundy theory. It has the peculiar property that its sum with any nimber is again loony. This can be seen in action here, because leaving a loony position is a losing move, whatever is happening elsewhere on the board. (Note that also the sum of two loonies is loony.) In the language of Dots-and-Boxes, a move such as Evie’s 14c is called a half-hearted handout. Since it is fatal (i.e., loony) in Nimstrings, it is nearly always fatal in Dots-and-Boxes, amounting as it does to offering your opponent
84
JULIAN WEST
the choice of parity of the number of double-crossed moves, and thus of eventual long chains. Understanding about hard-hearted handouts enables us to see why a chain of length three or more counts as long, while one of length two does not. If you are forced to move in a chain of length two, you have the choice between making a half-hearted handout (generally suicidal) or taking the middle edge to make a hard-hearted handout. Moving in a chain of length three or more, drawing even an interior edge creates a suicidal situation on at least one side of the edge. Therefore, the first player to offer up boxes in a long chain has lost control, and will almost always lose. When these two games were actually played at MSRI, Daniel Allcock, a Berkeley graduate student in geometric group theory, was Evie in game 1 and Dodie in game 2. His opponent was Martin Weber, a differential geometer. The pictures in this note were set in LATEX with some assistance from Jennifer Overington.
Reference [Berlekamp et al. 1982] E. R. Berlekamp, J. H. Conway, and R. K. Guy, Winning Ways For Your Mathematical Plays, vol. II, Academic Press, London, 1982. Julian West Julian West Malaspina University-College and Department of Mathematics and Statistics University of Victoria Victoria, B.C. Canada V8W 3P4
[email protected]
Games of No Chance MSRI Publications Volume 29, 1996
Championship-Level Play of Domineering JULIAN WEST
Abstract. A single-elimination Domineering tournament was held at the MSRI meeting, with a $500 purse. This is an analysis of the finals of that tournament, in which Dan Calistrate defeated David Wolfe by three games to one. An algebraic notation for commenting games is introduced.
Domineering is a game played on subsets of the square lattice by two players, who alternately remove connected two-square regions (dominoes) from play. Left may only place dominoes vertically; Right must play horizontally. The normal win-condition applies, so that the first player unable to move loses. It is difficult to analyse general Domineering positions, even for quite small boards. One way to gain insight into the nature of the problem is to watch actual games between expert players. To determine who were the strongest players available, an open-registration tournament was held. To insure that the players gave proper consideration to their play, a prize of $500 was awarded the winner. The finalists were Dan Calistrate of Calgary and David Wolfe of Berkeley. The format for the final was to play two games, each player taking the first turn once; if the series was split, two more games would be played, and so on until one player won both games of a round. As in chess, it would be expected that one set of pieces would provide an advantage, therefore winning with the favoured set would be like holding serve in tennis. In the event, the first round produced two first-player wins, and Calistrate won both second-round games. An 8 × 8 board was selected as large enough to be beyond the range of current analysis, and therefore apt to provide an interesting game. It seems quite likely that analysis of the general position is genuinely hard, so that the solution of the 8 × 8 board would simply necessitate a move to 9 × 9 or 10 × 10 to retain interest. Because of symmetry, the square board must be either a first-player or a second-player win (as opposed to a win for Left or a win for Right). Indeed, because of this symmetry, we can always orient the board so that the player who
85
86
JULIAN WEST
starts is considered to be Left; we have adopted this convention for clarity. The 5 × 5 board is known to be a second-player win (that is, it has value 0; see On Numbers and Games [Conway 1976]). Conway observes that for larger boards “0 is an infinitely unlikely value”, because this value would only obtain if Left’s best move is to a position of net value to Right. This becomes less and less likely the more options Left is given. 1 Furthermore, the actual opening move generally agreed on as strongest appears to be quite strong. It leaves the board in the position shown at the right, which is at least as good for Left as 1− (the 8 × 8 board with a 2 × 2 bite out of the corner). That board is also likely to be of net value to the first player, but presumably has value less than 1. A word about notation: we have numbered the dominoes in the order in which they were placed on the board. Thus Left (vertical) dominoes have odd numbers. When it is possible to compute the game-value of a contiguous region, we will write it in. In actual play, the game appears to go through three stages: an early game, a middle game, and an end game. Nearly all of the interest appears to be in the middle game. The early game lasts about eight moves (half-turns), and consists of corner moves similar to the opening explained above. It appears that experts cannot distinguish between the relative values of these openings, seeing them rather as variants. The choice of which variant to play may be as much psychological as anything, trying to guess a terrain that may be less familiar for the opponent. Unfortunately, we do not have as rich a vocabulary for our textbook openings as does the chess world, but the actual positions reached in the championship games were as shown in Figure 1. In the early game, every move reserves a future move for the same player by creating a space in which only that player can place a domino. This suggests that Domineering on a spacious board is very hot, explaining the difficulty of a thorough analysis.
4
6
1
3 6
2
7
3
6 1
4
3
4
5
8 Game 1
5 2
8
8 1
5
7
Game 2
4
5
6
8 3
7 Game 3
2
1
2
7
Game 4
Figure 1. Position at end of opening for each of the four games in the finals. In games 1 and 3, Wolfe is Left (vertical) and Calistrate is Right (horizontal). In games 2 and 4, the roles are reversed.
CHAMPIONSHIP-LEVEL PLAY OF DOMINEERING
87
In the middle game, in the space of about six moves, the board is converted from the relatively large open space of the “textbook” opening into a fractured board consisting entirely of numbers and switches. Since such a position is easy to analyse and to play flawlessly, the end game need not be played out. As the large, difficult to analyse region of the board is sectioned, it is rarely broken into two hot regions; therefore it is usually apparent in which component a player should play. Finding the correct move can be subtle, and a mistake is often fatal, since the game is really decided in about six moves. Since the game is presumably a win for Left, and since it is decided in the space of six moves, it is very unlikely that control will be exchanged even twice. Therefore, Left wins exactly those games in which Left makes no errors. Right wins games in which Left makes an error, and Right successfully exploits it. These games can be viewed as “service breaks”. Since any winning move is a good move, wins for Left consist entirely of good moves. Wins for Right contain exactly one bad move. So there is only one bad move to be pointed out in these four games. In one sense, the onus is on the first player to initiate the transition to the middle-game. Imagine the board divided into 2 × 2 squares. If no dominoes ever cross the borders between these squares, the second player will be able to win by claiming half of the squares. The early game consists of moves that respect these borders, so the transition to the middle game is the breaking of this respect, and it is the first player who benefits. Note that the opening of game 4 is an odditiy in this respect, in that it is the second player who breaks symmetry (at move 8). Game 3, the only one that led to a second-player win, breaks this expectation in the other sense: the first player failed to break symmetry. Since this was the “service break” game, it is the only one in which we can definitively say that a mistake was made, and it thus proves interesting to analyse. After twelve moves, the situation shown at the top in Figure 2 was reached. In actual play, Left played as in the bottom left diagram of Figure 2. It looks like a reasonable move, since as it continues the paradigm of reserving a free move for Left; but it leaves a devastating future move for Right in the six-square region. The correct move, the only winner, is not easy to spot; it is shown on in the bottom right diagram of Figure 2. Notice that this fulfils our expectation that this is the moment at which the first player must break out of the division into 2 × 2 cells. The other three games simply demonstrate the considerable latitude that the first player has for securing the (assumed) win. Figure 3 shows the positions reached just as they become susceptible to analysis. Figure 4 shows the games again as they cool down to sums of numbers and switches. In game 2, Left’s move 13 is indeed the optimal move (to 7| 11 2 ||5, {5, 4}). Right’s reply selects the option +5.
88
JULIAN WEST
1 4
6
+2
5
9 10
+3
8 11
{0 || 0 | −2, {0 | −2}}−3
12 3
7
2 −2
1 4
1
6
4
+2
6
5
9
5
9
10 +3
11
13
3
7
10 8
0 | −2
12
Actual move
+2
13
−1+2
+3
2 −2
8
−3
11
12 3
7
2 −2
Correct move
Figure 2. Left’s fatal mistake in Game 3: Wolfe is Left (vertical) and Calistrate is Right (horizontal).
CHAMPIONSHIP-LEVEL PLAY OF DOMINEERING
89
−3
1 4
3
6
6
10
2
1,{1 | − 12 } ||| 1 | − 12 || −1 | − 52
7
11 10
+3
9
11
8
7 | 11 2 || 5,{5 | 4} |||
5
8 3
{ 92
|
25 7 8 },{5 | 2
||
13 4
|
5 2}
2
−2,{− 12
+1
9
12
| −2} || − 52
4 1
| −4
5
7
−1
−2
1 4
3
6
5 4
+2
6 13 2
5 10 +3
10
8
8 11
12 11
{0 || 0 | −2,{0 | −2}}−3
12 3
| 5 || 92 | 3
9
7
2 −2
2 1
−1
9
7
Figure 3. Positions reached in games 1–4 just as they become susceptible to analysis.
90
JULIAN WEST
−3
−1
1 4
3
6
6
13
10
+3 2 | 12
7
11
10 +3
14
11
5
13
8
2
4 1
−1 12 | −3
5
−3
14 5
−1
3
6
5 4
+2
6 11 2
2|0
|4
9 10
+3
7
−2
1 4
8
+2
12 3
+1
9
12
−1
9
2
11
13
3
7
10
8
8
0 | −2
12 13
12
2 −2
11
+1
2 1
−1
9
7
Figure 4. Positions reached in games 1–4 just as they cool down to sums of numbers and switches.
CHAMPIONSHIP-LEVEL PLAY OF DOMINEERING
91
Values were computed using David Wolfe’s games software. Boards were typeset using Jennifer Turney’s awk scripts for domineering, which produce LATEX code.
Reference [Conway 1976] J. H. Conway, On Numbers And Games, Academic Press, London, 1976. Julian West Malaspina University-College and Department of Mathematics and Statistics University of Victoria Victoria, B.C. Canada V8W 3P4 julianmath.uvic.ca
Games of No Chance MSRI Publications Volume 29, 1996
The Gamesman’s Toolkit DAVID WOLFE
Abstract. Tired of all those hand calculations? Of converting to canonical forms? Of calculating means and temperatures? Of wondering if you’ve goofed? Wanted to play with the overheating operator, but don’t have any patience? The Gamesman’s Toolkit, written in C under UNIX, implements virtually all of the material in finite combinatorial game theory. It is invaluable in analyzing games, and in generating and testing hypotheses. Several of the results presented at the 1994 Combinatorial Games Workshop were discovered using this program. The Gamesman’s Toolkit is useful and fun. This paper is an overview of its features.
1. Overview The Gamesman’s Toolkit, written in C and running under UNIX, implements virtually all of the material in finite combinatorial game theory. The toolkit can be used in one of two ways: as a “games calculator”, by the gamesman who wishes to do standard algebraic manipulations on games; and as a programming toolkit, to analyze a particular game, for instance. A broad base of game-theoretic functions is provided, along with a parser and output routines. Either way, the program has proved to be a versatile and powerful tool for the student and the researcher.
2. Use As a Games Calculator Table 1 shows a sample run of the Toolkit, and gives an idea of its functionality as a games calculator. Here is the input notation, in a nutshell: • The caret, ^, represents ↑; the letter v is reserved for ↓. Triple-up can be typed as either ^^^ or ^3. • You can assign variables to games and later reuse them. For example, you can set g = 2|1 and later reuse g in another expression.
93
94
DAVID WOLFE
unix% games Type ’help’ and...
The program is executed from the UNIX prompt. You are told how to get help; the prompt > appears.
> * ? ^ <>
How does ∗ compare with ↑ ? Answer: they are incomparable
> * ? ^^ <
How does ∗ compare with ↑↑ ? Answer: ∗ is less than ↑↑
> -2 + 3/8 + vvv + *6 Compute −2+ 38 +↓↓↓+∗6 + + -13/8v3*6 Answer: − 13 8 ↓↓↓ ∗6 (v3 is short for vvv) > +[2],*|-2
Find the canonical form of {2 , ∗| −2};
0,*|-2
brackets indicate subscripts, so +[2] is tiny-two
> $[1/2] -1/2|-3/2
Cool the last result ($) by 12 {0, ∗| −2} cooled by 12 is {− 12 | − 32 }
> g = $ g = -1/2|-3/2
Assign a variable g to the last result
> mean g -1 > temp g 1/2
Calculate g’s mean and temperature
> (1|||0||-1|-3)[1/2] Cool 1|||0|| −1| −3 by 12 1/2||0|g The program uses the value of g to shorten the answer > no ups > ^* 0,*|0
Please do not print out ↑ in canonical forms What’s the canonical form of ↑∗ ? It’s {0, ∗|0}
> domino Enter domin... xxxx xx xxxx
Enter a domineering position
-3/2|-4
The input is ended with an extra carriage return The ten-box position has value {− 32 | −4}
Table 1. Sample run of the Gamesman’s Toolkit. The first column is the computer dialogue, and the second contains comments. What the computer prints is in typewriter font, and what the user types is underlined. Most commonly, the user enters a game expression, and the computer converts the expression to canonical form.
THE GAMESMAN’S TOOLKIT
95
• Subscripts in games notation are typically enclosed by brackets for the toolkit. Thus, the input format for 2 (tiny-2) is +[2], and that for g3 (i.e., g cooled by 3) is g[3]. • Similarly, superscripts are enclosed by angle brackets < and >. • The symbol % represents the heating (integral) symbol. Thus, %[1*]<1>g R1 denotes 1∗ g, that is, g overheated from 1∗ to 1 [Berlekamp 1988; Berlekamp and Wolfe 1994, p. 214].
3. Use As a Programmer’s Toolkit The Gamesman’s Toolkit can be extended to analyze a particular game: the user implements the rules to that game, the program can then evaluate positions of that game. If you are an experienced (or patient) programmer you should find the Toolkit quite versatile. (Unfortunately, the extensibility mechanism was not designed for users without programming experience.) Several people have written such extensions. Konane (programmed by Michael Ernst), Toads and Frogs (Jeff Erickson) and Domineering (David Wolfe) come with the Toolkit. Dan Garcia has written a wonderful interface using Tcl for playing domineering on an X-window system [Garcia 1996]. To get you started, Table 2 summarizes the most useful files and functions you’ll need. The listing on page 97 contains a program for evaluating positions in Wyt Queens. (Wyt Queens, or Wythoff’s game [Berlekamp et al. 1982, p. 61], is played on a quarter-infinite chess board. One or more queens occupy a square each, and move independently. A move consists of moving a queen north, west, or northwest any number of squares. The last player to move wins.)
4. Availability The Gamesman’s toolkit is free, and is available by request: send e-mail to me at
[email protected]. I’ve chosen to distribute it in this way, rather than by posting it publicly, so that I can maintain a mailing list for notifying you of significant improvements in the program. You can also download it from http:// http.cs.berkeley.edu/˜wolfe/games.tar.gz. Enjoy!
Acknowledgement Elwyn Berlekamp first encouraged me to write the toolkit in a course at UC Berkeley in Spring of 1989. Many people have since contributed ideas and code to the program, including Dan Calistrate, Raymond Chen, Jeff Erickson, Michael Ernst, Dan Garcia, Yonghoan Kim, David Moews, and Martin Mueller.
96
DAVID WOLFE
gameops.h: Performs operations on games (game type) init()
must be called once to initialize the game routines
make(list type, list type)
constructs a game from two lists of options and converts it to canonical form; destroys its arguments
zero
the zero game
num(Q type), up(int), star(int)
construct games consisting numbers, ups and star
plus(game type, game type)
add two games
minus(game type, game type)
subtract two games
negative(game type)
negate a game
eq(game type, game type), ge( . . . ), compare games (equal, ≥, etc.) etc. is int(game type), is num(game type) true if game is an integer, number list type left options(game type)
game’s list of left options
list type right options(game type)
game’s right options
output.h: Output routines for games and lists game printf(game type)
output a game plus a newline
game print(game type)
output a game without the newline
game sprintn(game type)
print a game to a string without newline, maximum of n characters
list.h: Manipulates lists of integers or games (list type) list make()
returns an empty list
list insert(list type, int or game type)
insert an element into a sorted list
list prepend(list type, int or game type) prepend to an unsorted list int or game type list nth(list type)
find the nth element of a list
list copy(list type)
return a copy of a list
list free(list type)
destroy a list and free its space
rational.h: Manipulates low precision rational numbers (Q type) Q(int, int)
construct a rational p/q
int Q p(Q type), Q q(Q type)
numerator or denominator of a rational
hash.h: Maintains a hash table keyed by an (int, list type) pair boolean hash test(int, list type)
true if the hash table contains entry
game type hash get last()
get the last entry tested positive
hash put(int, list type, game type)
put a value into the hash table; destroys its list argument
Table 2. Most common functions used by a programmer of the toolkit.
THE GAMESMAN’S TOOLKIT
97
/* A programming example: The game of Wyt Queens */ #include "games.c" /* Includes all the needed .h files */ #define QUEENS_KEY 1001 /* Hash table keys below 1000 are reserved. */ game_type queens (int x, int y) { list_type posn_as_list, left, right; game_type g; int n, min; /* Encode the position as a list of integers, in order to use the hash table to store computed positions and avoid recomputing positions */ posn_as_list = list_make(); list_prepend (posn_as_list, x); list_prepend (posn_as_list, y); if (hash_test (QUEENS_KEY, posn_as_list)) { /* If pos’n previously computed */ list_free (posn_as_list); /* Free space used by the list */ return hash_get_last(); /* Return computed value */ } /* Position wasn’t already computed, so evaluate the position recursively. */ left = list_make(); for (n=0; n<x; n++) list_insert (left, queens (n, y)); /* Horizontal moves */ for (n=0; n
Listing 1. Sample extension program for the Toolkit. Lines marked with a vertical bar on the margin relate to the hash table, and may be ignored on a first reading, or omitted if efficiency is not an issue. The hash table is used to avoid the exponential cost of reevaluating the same positions over and over during recursion.
98
DAVID WOLFE
References [Berlekamp 1988] E. R. Berlekamp, “Blockbusting and Domineering”, J. Combin. Theory (Ser. A) 49 (1988), 67–116. [Berlekamp and Wolfe 1994] E. Berlekamp and D. Wolfe, Mathematical Go: Chilling Gets the Last Point, A. K. Peters, Wellesley, MA, 1994. [Berlekamp et al. 1982] E. R. Berlekamp, J. H. Conway and R. K. Guy, Winning Ways for Your Mathematical Plays, Academic Press, London, 1982. [Garcia 1996] D. Garcia, “Xdom: A graphical, X-based front-end for Domineering”, pp. 311–313 in this volume. David Wolfe Computer Science Division UC Berkeley, CA 94720
[email protected]
Games of No Chance MSRI Publications Volume 29, 1996
Solving Nine Men’s Morris RALPH GASSER
Abstract. We describe the combination of two search methods used to solve Nine Men’s Morris. An improved retrograde analysis algorithm computed endgame databases comprising about 1010 states. An 18-ply alphabeta search then used these databases to prove that the value of the initial position is a draw. Nine Men’s Morris is the first non-trivial game to be solved that does not seem to benefit from knowledge-based methods.
1. Introduction In recent years, a number of games have been solved using computers, including Qubic [Patashnik 1980], Connect-4 [Allen 1989; Allis 1988] and Go-Moku [Allis et al. 1993]. All these games were solved using knowledge-based methods. These methods are successful because all these games have a low decision complexity [Allis et al. 1991], that is, the right move is often easy to find. Not all games profit to the same extent. For instance, in checkers, chess and go a multitude of moves often seem fairly equal. Brute-force search is often the most viable means of playing or solving this type of game. This observation is supported by the fact that the best programs for both chess [Hsu 1990] and checkers [Schaeffer 1992] rely heavily on search. Search methods are not only useful for playing games: they are ubiquitous in many aspects of problem solving. Some of these algorithms are among the best understood in computer science. However, not all search algorithms are equally well studied; in particular, exhaustive search in large state spaces is still in its infancy. Partly this is because the hardware has only recently progressed to a point where interesting problems are within reach. Due to the continual improvement in hardware and software, search methods must be constantly reevaluated and adapted to new system designs [Stiller 1991; Lake 1992]. Games are ideal for gaining expertise in this area, because they are played in a restricted domain, where the problem difficulty can be controlled and the effectiveness of the approach measured. 101
102
RALPH GASSER
We describe the combination of two brute-force search methods used to solve Nine Men’s Morris. An improved retrograde analysis algorithm computed endgame databases comprising about 1010 states. An 18-ply alpha-beta search then used these databases to prove that the value of the initial position is a draw. Nine Men’s Morris is the first non-trivial game to be solved that does not seem to benefit from knowledge-based methods.
2. Nine Men’s Morris Nine Men’s Morris is one of the oldest games a b c d e f g still played today [Bell 69]. Boards have been found on many historic buildings throughout the 7 world. The oldest (about 1400 BC) was found 6 carved into a roofing slate on a temple in Egypt. 5 Others have been found as widely strewn as Cey4 lon, Troy and Ireland. The game is played on a board with 24 points 3 where stones may be placed. Initially the board 2 is empty and each of the two players hold nine stones. The player with the white stones starts. 1 During the opening, players alternately place Figure 1. After the opening. their stones on any vacant point (Figure 1). After all stones have been placed, play proceeds to the midgame. Here a player may slide one of her stones to an adjacent vacant point. If at any time during the game a player succeeds in arranging three of her stones in a row—this is known as closing a mill —she may remove any opponent’s stone that is not part of a mill. In Figure 2, if White closes a mill in the opening by playing to b6, she can now remove Black’s stone on a1, but not the one on d2. As soon as a player has only three stones left, the endgame commences. When it is her turn, the player with three stones may jump one of her stones to any vacant point on the board. a
b
c
d
e
f
g
a
7
7
6
6
5
5
4
4
3
3
2
2
1
1
Figure 2. After b6, White removes a1 or b4.
b
c
d
e
f
g
Figure 3. Black has no moves.
SOLVING NINE MEN’S MORRIS
103
The game ends in the following ways: • A player who has less than three stones loses. • A player who cannot make a legal move loses (Figure 3). • If a midgame or endgame position is repeated, the game is a draw. Two points are subject to debate among Nine Men’s Morris enthusiasts. The first hinges on the observation that in the opening it is possible to close two mills simultaneously. Should the player then be allowed to remove one or two opponent’s stones? Our implementation only allows one stone to be removed. The second point concerns positions where the player to move has just closed a mill, but all the opponent’s stones are also in mills. May she then remove a stone or not? In our implementation she may remove any stone. It seems unlikely that either of these rule variations affect the value of the game.
3. Solving Nine Men’s Morris Nine Men’s Morris can be divided into two distinct phases. The opening, where stones are placed on the board and the mid- and endgame, where stones are moved. These two phases lead to a state space graph with specific characteristics. Most importantly, the opening phase induces an acyclic graph, whereas in the mid- and endgame phase move cycles can occur. Another difference is the search depth. The opening is clearly defined to be 18 plies deep for every path; by contrast, the time spent in the mid- and endgame depends on the chosen moves. These different properties suggest the use of different search methods. We decided to use retrograde analysis to construct databases containing all midand endgame positions. This seems advantageous because retrograde analysis handles cycles more efficiently than forward search. In addition the opening search will require the values of many positions. Due to the interdependencies, this probably means computing the value for all or nearly all mid- and endgame positions, an ideal task for retrograde analysis. Computing further databases for the opening is not reasonable, because their size would be even larger than for the mid- and endgame. In addition, because the value of only a single position (the empty board) is of interest in the opening phase, no intermediate position values must be stored. Alpha-beta search [Knuth and Moore 1975] is ideal for this type of problem.
4. Mid- and Endgame Databases 4.1. State space. To see if applying retrograde analysis is feasible, we must construct an appropriate state space. Each of the 24 board points can either be unoccupied or occupied by a black or white stone, so an upper bound for the state space size is 324 , or approximately 2.8 × 1011 , states. This rather loose bound can be improved by taking the following game constraints into account:
104
RALPH GASSER
• players have three to nine stones on the board, • there are unreachable positions, and 9-9 • the board is symmetrical. 9-8
The first observation allows us to split the 9-7 8-8 state space into 28 subspaces. Figure 4 shows these subspaces and their dependencies; thus 9-6 8-7 the 7-5 positions (seven stones against five) can 9-5 8-6 7-7 only be computed after the values for all 7-4 and 6-5 positions have been determined. 9-4 8-5 7-6 Not all states in these subspaces are reach9-3 8-4 7-5 6-6 able in the course of a legal game. For example, if one player has a closed mill, her opponent 8-3 7-4 6-5 cannot have all nine stones on the board (Fig7-3 5-5 6-4 ure 5). Similar considerations can be made if two or three closed mills are on the board. The 5-4 6-3 9-9, 9-8, 9-7, 9-6, 9-5, 9-4, 9-3, 8-8, 8-7 and 8-6 4-4 5-3 subspaces contain such unreachable states. The subspaces also contain many symmetri4-3 cal positions. In general there are five symme3-3 try axes (Figure 6). In the special case of the 3-3 subspace, there are additional symmetries, Figure 4. Database dependencies. because all rings are interchangeable. Since one of these five axis is redundant— for example, π4 = π1 ◦ π2 ◦ π3 , we can expect about a 16-fold reduction in the state space size from the symmetries. Taking all three reductions into account leaves a total of 7,673,759,269 states in the mid- and endgame phase. For such large state spaces, a memory-efficient storage method is needed. The standard method used in retrograde analysis is to construct a perfect hash function, which, given a state, returns a unique index. This makes it unnecessary to store the state description along with the state value, because the state de-
π5
π2
π3 Figure 5. An unreachable state.
π1
π4
Figure 6. Symmetry axes.
SOLVING NINE MEN’S MORRIS
105
scription is encoded in the index. Ideally the perfect hash function ranges from 0 to the number of states minus 1, and can be computed rapidly. Constructing such a hash function can be difficult. Therefore, as rapid computation is critical, it seems reasonable to loosen the requirements and allow hash functions with slightly larger ranges. This means that some unused entries are included in the file, but this will not impede the computation as long as the file size does not become too large. The hash function we decided to use maps the 7,673,759,269 states into a range of 9,074,932,579 indices. 4.2. Calculation. The first step in retrograde analysis is to initialize all easily recognizable won and lost positions. In Nine Men’s Morris there are two types of terminal positions, both of which are losses for the player to move: positions where the player cannot move, and positions where the player has less than three stones. Therefore, if the player to move is blocked, we mark that state as a loss. We would also like to mark positions where the player to move has less than three stones as losses, but because we eliminated these positions from the state space, we mark positions where the player to move can close a mill and reduce the opponent to two stones as wins. We also mark positions where the player with three stones loses in two plies. Such positions are easy to recognize and belong to one of the following categories: • the opponent has two open mills with no stones in common; • the opponent has two open mills and the player to move cannot close a mill; or • the player to move must remove a stone blocking an opponent’s mill. After the initialization has set these wins and losses, it sets the value of all remaining positions to a draw. An iterative process then determines the real values of these “drawn” states. As a first step, consider how wins and losses are propagated in two-player games. If a position is lost for the player to move, all the position’s predecessors can be marked as wins for the opponent. Similarly, if a position is won for the player to move, all predecessors are potential losses for the opponent. They are only true losses if all of their successors are also won for the player (Figure 7). It would be inefficient to check all successors to determine if a position is a loss or not. This can be avoided by using a Count field for each state, to store the number of successors that have not yet been proved a win for the opponent. Then, instead of checking all successors every time a position occurs, we simply decrement Count. When it reaches zero, all successors have been proved wins for the opponent, and the position can be marked a loss. The cost of this improvement is the additional memory used for the Count array. Since we compute the depth of the wins and losses, one byte is used to store the value of each state, in a Val array. In practice the Count and Val array can use the same memory, since the two pieces of information are never needed
106
RALPH GASSER
C
A
B
D
...
Figure 7. Determining predecessor values. Position A is won for White (to play) since some successor, say B, is lost for Black. Position C is lost for Black since all of it successors D are won for White.
simultaneously: the Count array is only needed while a position’s value may still be drawn. In other words, the Count and Val values are stored as a “union”; see Table 1. Table 2 shows the algorithm by which we determine the value of all states. The first database was computed in 1989 on a Macintosh IIx, the last on a Macintosh Quadra 800 in 1993. In between, the algorithm was improved and ported to various machines. These include a Cray X-MP/28, a DEC VAX 9000420, an IBM RS/6000, a 16-Transputer (T805) system, a 30-Processor MUSIC system (Motorola DSP 96000) and a DEC 3000 (Alpha). Only the DEC 3000 showed better performance than the Apple Macintosh. There are various reason for this surprising result. Many machines executed our code at low priority because of their multi-user environments. Also, many of the more powerful machines are optimized to deal with floating-point and vector operations, whereas their integer performance is not as highly tuned. The parallel machines additionally suffered from insufficient main memory and no direct disk access. This made the Macintosh front-end an I/O bottleneck.
Val entry 0 = loss in 1 = win in 2 = loss in 3 = win in ......
0 1 2 3
Count entry ................................. 252 = “draw” (3 successors unknown) 253 = “draw” (2 successors unknown) 254 = “draw” (1 successor unknown) 255 = “draw” (all successors unknown)
Table 1. All known information for a position fits in one byte.
SOLVING NINE MEN’S MORRIS
Backupable ← [ ]; {initialization} for all states do Val[state] ← Initialize(state); Count[state] ← 0; if Val[state] 6=draw then Put(state,Backupable); end; {if} end; {for} while not Empty(Backupable) do {iteration} state ← GetState(Backupable); for all Predecessors(state) do if Val[pred] = draw then if Val[state] = loss then Val[pred] ← win; Put(pred, Backupable); else {Val(state) = win} if Count[pred] = 0 then for all Successors(pred) do {count successors} Count[pred] ← Count[pred]+1; end; {for} end; {if} Count[pred] ← Count[pred]−1; if Count[pred] = 0 then Val[pred] ← loss; Put(pred,Backupable); end; {if} end; {if} end; {if} end; {for} end; {while}
Table 2. This algorithm shows how the initialization and iteration determine the value of all states. For simplicity, we don’t show the merging of the Count and Val arrays, nor the computation of the depth of the wins and losses.
107
108
RALPH GASSER
4.3. Verification. Computations of this size almost inevitably contain some errors. The most common cause are software bugs in the retrograde analysis code, the system software, or the compiler. Hardware problems, such as disk errors or memory glitches, occur as well. For these reasons, the databases were verified on a cluster of 30 Sun Sparcstations [Balz 1994]. This took approximately three months. The verification found half a dozen hardware errors. Additionally, an error was found in the Nine Men’s Morris code, which allowed some positions to be classified as draws instead of losses. These errors induced further inconsistencies, so that thousands of positions had to be corrected. The verification only checked that the wins, losses and draws were consistent. The depth information was not checked, because the additional memory needed to store the databases increases the disk I/O and slows the verification dramatically. Presently, we are running a depth verification algorithm on a new parallel machine which may enable the complete verification. Even if depth verification finds no additional errors, how can we ascertain that none exist? A basic idea behind the verification is to use a different algorithm (forward search) and independent code to verify the data. But there are still some procedures common to both algorithms, such as the file indexing function or the initial state values. Ideally, our results should be independently verified.
5. Opening Search Now that all mid- and endgame position values are computed and stored in databases, the value of the initial position can be found with a simple 18ply alpha-beta search. In principle, the 18-ply opening can lead to any of the databases except 8-3, 9-3 and 9-4. This comprises approximately 9 GBytes of data. Since our machine only had 72 MBytes, accessing database values becomes an I/O bottleneck. The following methods were applied to alleviate this problem: • reduce the size of the databases, • reduce the number of used databases, and • reduce the number of disk accesses. Because no cycles occur in the opening, it is not necessary to compute the depth of the win or loss. Therefore a first idea is to reduce the size of the databases by packing five positions into one byte (35 = 243). However, in order to further minimize storage requirements, we decided to pack eight states into a byte. Although we then have only one bit per state, this is sufficient to compute the game-theoretic value if we do two alpha-beta searches. In the first search we determine if the initial position is won or not. If it is not won, we do a second search (with different databases) to determine if the initial position is lost or not. While this reduces the size of the databases by a factor of eight, it still leaves files totaling about 1 GByte. To Nine Men’s Morris players, it is clear that most
SOLVING NINE MEN’S MORRIS
8 plies
109
Opening database 18 plies
16 plies
Transposition table
9-9
9-8
8-8
Figure 8. The opening search.
reasonable games will result in at most one or two mills being closed during the opening. For this reason we decided to try to prove the draw using only the 9-9, 9-8 and 8-8 databases, a total of 115 MBytes. It is then no longer possible to compute the correct value for every position. But in a position with White to move, we can compute an upper bound on the correct value by assuming all positions not in the databases are won for white and a lower bound if we assume all such positions are won for black. To prove that the game-theoretic value is a draw, we must show that White has both an upper and lower bound of a draw. We inserted a transposition table at the 16-ply level to further reduce the number of database accesses. Normally, a transposition table includes positions from any ply, possibly even giving priority to those higher up in the tree. We chose to include only the 16-ply positions because it is far more important to reduce disk I/O than the total number of nodes in the tree. See Figure 8. Finally, all positions that were visited by the alpha-beta searches at the 8-ply level were stored in an intermediate database. This allows games to be played in real time, because for the first 8 plies only a search to the intermediate database must be performed. Here is the number of 8-ply positions alpha-beta visited in each of the two searches:
White at least draws White at most draws
proved 15,501 4,364
not proved 12 29
110
RALPH GASSER
Figure 9. Black to move. Loss in 26 plies.
Figure 10. White to move and win. Mill closure in 187 plies.
We differentiate between positions that could be proved to be at least (or at most) a draw and those that could not. This does not mean the positions are lost (or won); only that using three databases was insufficient to show otherwise. Of the approximately 3.5 million positions at the 8-ply level, the table shows that only 19,906 were evaluated. The time for a node evaluation ranged from 2 seconds to 15 minutes. The total run-time was about three weeks on a Macintosh Quadra 800. Examining the table, one might be inclined to assume that most positions are drawn. This must not be the case; perhaps the move-ordering heuristic was simply successful in selecting drawish moves.
6. Results 6.1. Database Positions. Sifting through the final databases in search of “interesting” positions is a daunting task. Since we have no real intuition about what makes a position interesting, we decided to gather results in a more statistical fashion. The next two figures show examples of positions with long winning sequences. The 3-3 position in Figure 9 is an example of the longest sequence in that database. The 8-7 position in Figure 10 shows a won position with the longest move sequence until a mill is closed. Figure 11 shows the percentage of positions that are won for the player to move. They are grouped according to the number of stones on the board, and normalized accordingly. The figure shows that the win probability strongly correlates with the stone difference: more stones are better. There seems to be a cut-off at about seven stones, so that having less makes winning difficult. The statistics also show that the 3-3 database seems to be special. This is probably because both players are allowed to jump, essentially making this a different game. One must keep in mind that these statistics can be misleading. For instance, in the 4-3 database, if the player with four stones is to move, it seems she has a small chance of winning. Upon closer examination of the database, we see that all wins are trivial positions where the player can close a mill immediately.
SOLVING NINE MEN’S MORRIS
111
9 8 7 6 3
5
4 5
4
6 7
3
8 9
Figure 11. Win percentages for the player to move, as a function of the initial number of stones. The highest percentage, for 3-3 games, is about 83%. The absence of a column (as for 3-9 games) indicates a zero percentage.
These positions will not occur in a real game, so actually the player with three stones has a small advantage. Similar reservations apply to all these databases. It is not clear how the realistic positions can be filtered from the rest. 6.2. Opening Positions. It is now also possible to examine some common opening positions. Between equally matched players, games tend to be very drawish during the opening, that is, most possible moves result in a draw, as for the example in Figure 12. However, occasional blunders do occur. Figure 13 shows a position that occurred in a match our Nine Men’s Morris program played against Mike Sunley (British Champion) at the Second Computer Olympiad in London, 1990. The program, which was then still based on heuristics, won four games and drew two.
Figure 12. Opening position with black to move. Any move leads to a drawn position.
112
RALPH GASSER
9
5
Figure 13. White 9 loses.
Figure 14. White 5 loses.
Since the initial position is a draw, a natural question to ask is how soon a mistake can be made. The position in Figure 14 shows one of the earliest losing moves we have found. This positions refutes a common misconception, namely that closing mills is a desirable opening strategy. White follows this strategy with her first two moves, while Black ignores the potential mill threats. Subsequently, White’s third move loses even though she will now easily be able to close two mills during the opening.
7. Conclusion Nine Men’s Morris is a draw. This result was achieved using a combination of alpha-beta search and endgame databases. Our new efficient retrograde analysis algorithm allowed the 1010 database states to be solved on a desktop computer. This makes Nine Men’s Morris the first classic board game to be solved that does not profit from knowledge-based methods. The expertise gained in the management and use of large, pre-computed databases can also be applied to other problems. Many games and puzzles profit from combining databases with search, for instance Awari, Checkers, the 15-Puzzle or Rubik’s Cube. Since games and puzzles are a restricted problem domain, future work will examine how more general optimization problems can be made amenable to this approach.
References [Allen 1989] J. D. Allen, “A note on the computer solution of connect-four”, pp. 134–135 in Heuristic Programming in Artificial Intelligence: The First Computer Olympiad (edited by D. N. L. Levy and D. F. Beal), Ellis Horwood, Chichester, England, 1989. [Allis 1988] L. V. Allis, “A knowledge-based approach to connect-four. The game is solved: White wins”, M.Sc. thesis, Faculty of Mathematics and Computer Science, Vrije Universiteit, Amsterdam, 1988.
SOLVING NINE MEN’S MORRIS
113
[Allis et al. 1991] L. V. Allis, H. J. van den Herik, and I. S. Herschberg, “Which games will survive”, pp. 232–243 in Heuristic Programming in Artificial Intelligence: The Second Computer Olympiad (edited by D. N. L. Levy and D. F. Beal), Ellis Horwood, Chichester, England, 1991. [Allis et al. 1993] L. V. Allis, H. J. van den Herik, and M. P. H. Huntjens, “Go-Moku solved by new search techniques”, pp. 1–9 in Proc. AAAI Fall Symposium on Games: Planning and Learning, AAAI Press Tech. Report FS93-02, Menlo Park, CA. [Balz 1994] G. Balz, “Verification of state databases”, Diploma thesis, ETH Z¨ urich, 1994. [Bell 1969] R. C. Bell, Board and Table Games from Many Civilisations, Oxford University Press, Oxford, 1969. [Hsu 1990] F. H. Hsu, “Large-scale parallelization of alpha-beta search: an algorithmic study with computer chess”, Ph.D. thesis, Carnegie-Mellon University, Pittsburgh, 1990. [Knuth and Moore 1975] D. E. Knuth and R. W. Moore, “An analysis of alpha-beta pruning”, Artificial Intelligence 6 1975, 293–326. [Lake et al. 1992] R. Lake, P. Lu, and J. Schaeffer, “Using retrograde analysis to solve large combinatorial search spaces”, pp. 181–188 in The 1992 MPCI Yearly Report: Harnessing the Killer Micros (edited by E. D. Brooks et al.), Lawrence Livermore National Laboratory (UCRL-ID-107022-92), 1992. [Patashnik 1980] O. Patashnik, “Qubic: 4 × 4 × 4 tic-tac-toe”, Math. Mag. 53 (1980), 202–216. [Schaeffer et al. 1992] J. Schaeffer et al., “A World Championship caliber checkers program”, Artificial Intelligence 53 (1992), 273–290. [Stiller 1991] L. Stiller, “Group graphs and computational symmetry on massively parallel architecture”, J. Supercomputing 5 (1991), 99–117. Ralph Gasser ¨ r Theoretische Informatik Institut fu ¨ ssische Technische Hochschule (ETH) Eidgeno ¨ rich 8092 Zu Switzerland
Games of No Chance MSRI Publications Volume 29, 1996
Marion Tinsley: Human Perfection at Checkers? JONATHAN SCHAEFFER
Marion Tinsley died on April 3, 1995, at the age of 68. Why does the death of this checkers (8 × 8 draughts) player attract our attention? His record speaks for itself: Since an accidental loss in the 1950 U.S. Championship, Tinsley finished in undivided first place in every tournament that he played in, except the last (in the 1994 U.S. Championship, he tied for first place with the computer program Chinook and Don Lafferty). He contested nine World Championship matches, winning each usually by an embarrassingly large margin. Over the last fortyfive years of his life, comprising thousands of tournament, World Championship, match, exhibition and casual games, Tinsley lost the unbelievable number of seven games. Seven games!? In forty-five years? This is as close to perfection as is humanly possible. Tinsley once remarked that he had become bored playing humans; there wasn’t any challenge left. When he was young, he began to acquire the reputation of being unbeatable. For forty-five years, most of his opponents would play for the draw; going for a win was unthinkable. Tinsley’s enjoyment of checkers waned, and at one point he retired from the game for twelve years because of a lack of competition. When the program Chinook came on the scene, Tinsley relished the opportunity to play it. Chinook had no respect for Tinsley’s abilities, willingly taking risks: anything to increase the chances of winning. Tinsley said that playing Chinook made him feel like a young man again. In 1990, Chinook earned the right to play Tinsley for the (human) World Checkers Championship. The American Checker Federation and English Draughts Association (A.C.F. and E.D.A., the governing bodies for international checkers) refused to sanction the Chinook –Tinsley match, retroactively deciding that computers were ineligible for the World Championship. He was unable to change their decision, and he took what he perceived to be his only option. In 1992 he resigned as World Champion, then immediately turned around and signed a contract to play the match 115
116
JONATHAN SCHAEFFER
with Chinook . Although this match was not the “official” World Championship, Tinsley was the champion and Chinook the official challenger. In their embarrassment, the A.C.F. and E.D.A. hastily created a new Man-Machine World Championship title so they could be part of the Chinook –Tinsley match. The two governing bodies were now faced with the prospect of crowning a new human World Champion, which was meaningless as long as Tinsley was alive. They decided to award him the title World Champion Emeritus. The match was held in London in August 1992, and was sponsored by Silicon Graphics. The final result was four wins and two losses for Tinsley, with 33 draws. These were only the sixth and and seventh losses by Tinsley since 1950. In August 1994, Tinsley battled Chinook again for the Man-Machine title. After six games, all draws, Tinsley resigned the match and the title to Chinook , citing health reasons. A week later he was diagnosed with cancer, and after seven months he succumbed to the disease. In the domain of competitive mind games, such as chess or bridge, Tinsley’s record is unparalleled. Strong players come to the fore frequently, but their tenure at the top is usually short-lived. Emmanuel Lasker, chess World Champion for over twenty years, is an isolated exception. Being the best over a 45-year period is unprecedented. Was the Tinsley of 1994 as good a player as the Tinsley of, say, 1950 or 1970? Knowledgeable checkers players say the answer is yes. However, in old age he became lazy, winning the minimum number of games needed to carry a tournament or match, and then effortlessly drawing the rest (even not bothering to follow through in won positions because it required too much effort). What made Tinsley such a strong player? I asked him that question several times, without getting an adequate answer. Like many strong game players, he would say that when playing a game he just “knew” the right move to make. The solution to a problem was immediately obvious to him, even without having analyzed all the ramifications of the move. He was rarely wrong. Having observed him for several years, I can make a few comments on his strength. First, there is no doubt that Tinsley had an incredible memory. Before I first met him, I was acquainted with the stories—apocryphal, I assumed— concerning his memory. One man reported that, when Tinsley was young, he studied checkers eight hours a day, five days a week. As he got older, this dropped to one day a week. This person claimed that Tinsley could recall every one of those sessions. Needless to say, I found this difficult to believe. After Chinook ’s first game against Tinsley in 1990, we started analyzing the game. He began recounting the history of the opening line we played, recalling games he had played in the 1940’s! The move sequences flowed easily from him, without hesitation, sometimes annotated with the name of the opponent, date or place where the game was played! Games played in 1947 were as vivid in his memory as if it they had taken place only yesterday.
MARION TINSLEY:UMAN PERFECTION AT CHECKERS?
117
The second facet to his play was his incredible sixth sense. A glance at a position was sufficient to tell him everything he needed to know. For example, in 1990 Chinook was playing Tinsley the tenth game of a fourteen-game match (won by Tinsley 1–0 with thirteen draws). I reached out to play Chinook ’s tenth move. I no sooner released the piece than he looked up in surprise and said “You’re going to regret that”. Being inexperienced in the ways of the great Tinsley, I sat there silent, thinking “What do you know? My program is searching twenty moves deep and says it has an advantage”. Several moves later, Chinook ’s assessment dropped to equality. A few moves later, it said Tinsley was better. Later Chinook said it was in trouble. Finally, things became so bad we resigned. In his notes to the game, Tinsley revealed that he had seen to the end of the game and knew he was going to win on move 11, one move after our mistake. Chinook needed to look ahead sixty moves to know that its tenth move was a loser. My observations of tournament chess and checkers players have led me to conclude that the sixth sense is experience. It is well known how intensely Tinsley studied checkers, analyzing anything from a grandmaster game to a game between novices. His uncanny ability to know good from bad and safe from dangerous is the direct result of all his hard work. Strong chess players have the same ability, but perhaps it is not quite as evident as it was with Tinsley. What made Tinsley special was his play away from the board. He was universally liked. He was kind and gentle, eager to talk equally with checkers master and checkers novice. The first time I met him is indelibly imprinted on my mind. I was attending Chinook ’s first human tournament, the 1990 Mississippi Open. I had never attended such an event before, and knew no one. I walked in the door, tried to get my bearings, but must have looked lost. A tall slim man walked up to me and said “You look like a checkers player. Can I help you?” He proceeded to introduce me to the tournament organizer and director, and asked whether I needed any help with the hotel. This kind stranger turned out to be Marion Tinsley. I was a stranger walking in off the street and was treated royally by the World Champion. Even though Tinsley was our adversary over the checkerboard, away from it he was our friend. Professionally, Tinsley was a professor of mathematics at the University of Florida at Tallahassee. Away from work and the checkers board, he was a Baptist minister. Tinsley could have said no when faced with the prospect of defending his title against a computer. Instead he bravely said yes, setting a precedent that we hope will serve as an example to champions in other competitive games. It was Tinsley’s fervent wish to remain an undefeated champion. As long as his health remained sound, he claimed he would never lose a match to Chinook or anyone else. It was the Chinook team’s wish to defeat Tinsley and become the first computer World Champion (in any game). Ironically, in the end both sides
118
JONATHAN SCHAEFFER
saw their wishes realized, although under less happy circumstances than both would have liked. Chinook reluctantly became the first computer World Champion by winning on forfeit from Tinsley. Tinsley, however, remained undefeated over-the-board by resigning a drawn match. Jonathan Schaeffer Department of Computing Science University of Alberta Edmonton, Alberta Canada T6G 2H1
Games of No Chance MSRI Publications Volume 29, 1996
Solving the Game of Checkers JONATHAN SCHAEFFER AND ROBERT LAKE
Abstract. In 1962, a checkers-playing program written by Arthur Samuel defeated a self-proclaimed master player, creating a sensation at the time for the fledgling field of computer science called artificial intelligence. The historical record refers to this event as having solved the game of checkers. This paper discusses achieving three different levels of solving the game: publicly (as evidenced by Samuel’s results), practically (by the checkers program Chinook , the best player in the world) and provably (by considering the 5 × 1020 positions in the search space). The latter definition may be attainable in the near future.
1. Introduction Checkers is a popular game around the world, with over 150 documented variations. Only two versions, however, have a large international playing community. What is commonly known as checkers (or draughts) in North America is widely played in the United States and the British Commonwealth. It is played on an 8×8 board, with checkers moving one square forward and kings moving one square in any direction. Captures take place by jumping over an opposing piece, and a player is allowed to jump multiple men in one move. Checkers promote to kings when they advance to the last rank of the board. So-called international checkers is popular in the Netherlands and the former Soviet Union. This variant uses a 10 × 10 board, with checkers allowed to capture backwards, and kings allowed to move many squares in one direction, much like bishops in chess. This paper is restricted to the 8 × 8 variant, but many of the ideas presented here also apply to the 10 × 10 game. People enjoy playing games of skill because of the intellectual challenge and the satisfaction derived from playing well. Many board games, such as chess and checkers, have too many possibilities for a human to understand them all. Hence they use knowledge and search to make their decisions at the board. The person with the best “algorithm” for playing the game wins in the long run. Without perfect knowledge, mistakes are made, and even World Champions will 119
120
JONATHAN SCHAEFFER AND ROBERT LAKE
lose occasionally (for example, the world chess champion, Gary Kasparov, may lose three or four games a year). This gives rise to an intriguing question: is it possible to program a computer to play a game perfectly? Can the game-theoretic value of checkers be determined? In other words, is it possible to solve the game? In recent years, some games have been solved, including Connect-Four [Allen 1989; Allis 1988], Qubic [Patashnik 1980], Nine Men’s Morris [Gasser 1994] and Go-Moku [Allis et al. 1993]. This paper describes three ways in which it is possible to solve the game of checkers. Section 2 deals with publicly solving the game, creating the impression in the media that checkers has been solved. Section 3 deals with practically solving the game, creating a computer player that is better than all humans but is not perfect. Section 4 deals with provably solving the game, determining the game-theoretic value and a strategy for always achieving that value. For the game of checkers, publicly solving the game is a thing of the past, practically solving it is the present, and provably solving it is the near future.
2. Publicly Solving Checkers In the late 1950’s and early 1960’s, Arthur Samuel did pioneering work in artificial intelligence using the game of checkers as his experimental testbed [Samuel 1959; Samuel 1967]. Thirty years later, his work is still remembered, both for the significance of his research contributions, and for the legacy of his checkersplaying program. In 1962, Robert Nealy, blind checkers champion of Stamford, Connecticut, lost a single game to Dr. Samuel’s program. For the fledgling field of artificial intelligence, this event was viewed as a milestone and its significance was misrepresented in the media. Reporting of this event resulted in the game of checkers being labeled as “solved”: computers were better than all humans. Thus, a 1965 article by Richard Bellin in the Proceedings of the National Academy of Sciences declared that “ . . . it seems safe to predict that, within ten years, checkers will be a completely decidable game” (vol. 53, p. 246), while Richard Restak, in the influential book The Brain: The Last Frontier (1979), stated that “ . . . an improved model of Samuel’s checker-playing computer is virtuall