COMBINATORIAL GAMES

Selected Bibliography With A Succinct Gourmet Introduction by: A. S. Fraenkel Department of Applied Mathematics and Computer Science Weizmann Institute of Science 1. What are Combinatorial Games? Roughly speaking, the family of combinatorial games consists of two-player games with perfect information (no hidden information as in some card games), no chance moves (no dice) and outcome restricted to (lose, win), (tie, tie) and (draw, draw) for the two players who move alternately. Tie is an end position such as in tic-tac-toe, where no player wins, whereas draw is a dynamic tie: any position from which a player has a nonlosing move, but cannot force a win. Both the easy game of Nim and the seemingly diAEcult chess are examples of combinatorial games. And so is go. The shorter terminology game, games is used below to designate combinatorial games. 2. Why are Games Intriguing and Tempting? Amusing oneself with games may sound like a frivolous occupation. But the fact is that the bulk of interesting and natural mathematical problems that are hardest in complexity classes beyond NP , such as Pspace, Exptime and Expspace, are two-player games; occasionally even one-player games (puzzles) or even zero-player games (Conway's "Life"). Some of the reasons for the high complexity of two-player games are outlined in the next section. Before that we note that in addition to a natural appeal of the subject, there are applications or connections to various areas, including complexity, logic, graph and matroid theory, networks, error-correcting codes, surreal numbers, on-line algorithms and biology. 1 the electronic journal of combinatorics #DS2 2 But when the chips are down, it is this "natural appeal" that compels both amateurs and professionals to become addicted to the subject. What is the essence of this appeal? Perhaps the urge to play games is rooted in our primal beastly instincts; the desire to corner, torture, or at least dominate our peers. An intellectually refined version of these dark desires, well hidden under the fa,cade of scientific research, or passions for local, national or international tour- naments, is the consuming strive "to beat them all", to be more clever than the most clever, in short -- to create the tools to Math-master them all in hot combinatorial combat! Reaching this goal is particularly satisfying and sweet in the context of combinatorial games, in view of their inherent high complexity. With a slant towards artificial intelligence, Pearl wrote that games "offer a perfect laboratory for studying complex problem-solving methodologies. With a few parismonious rules, one can create complex situations that require no less insight, creativity, and expertise than problems actually encountered in areas such as business, government, scientific, legal, and others. Moreover, unlike these applied areas, games offer an arena in which computerized decisions can be evaluated by absolute standards of performance and in which proven human experts are both available and willing to work towards the goal of seeing their expertise emulated by a machine. Last, but not least, games possess addictive entertaining qualities of a very general appeal. That helps maintain a steady influx of research talents into the field and renders games a convenient media for communicating powerful ideas about general methods of strategic planning." To further explore the nature of games, we consider, informally, two sub- classes. (i) Games People Play (PlayGames): games that are challenging to the point that people will purchase them and play them. (ii) Games Mathematicians Play (MathGames): games that are challenging to mathematicians or other scientists to play with and ponder about, but not necessarily to "the man in the street". Examples of PlayGames are chess, go, hex, reversi; of MathGames: Nim- type games, Wythoff games, annihilation games, octal games. Some "rule of thumb" properties, which seem to hold for the majority of PlayGames and MathGames are listed below. I. Complexity. Both PlayGames and MathGames tend to be computationally intractable. There are a few tractable MathGames, such as Nim, but most games still live in Wonderland: we are wondering about their as yet unknown complexity. Roughly speaking, however, NP-hardness is a necessary but not a suAEcient condition for being a PlayGame! (Some games on Boolean formulas are Exptime-complete, yet none of them seems to have the potential of commercial marketability.) the electronic journal of combinatorics #DS2 3 II. Boardfeel. None of us may know an exact strategy from a midgame position of chess, but even a novice gets some feel who of the two players is in a stronger position, merely by looking at the board. This is what we loosely call boardfeel. Our informal definition of PlayGames and MathGames suggests that the former do have a boardfeel, whereas the latter don't. For many MathGames, such as Nim, a player without prior knowledge of the strategy has no inkling whether any given position is "strong" or "weak" for a player. Even two positions before ultimate defeat, the player sustaining it may be in the dark about the outcome, which will stump him. The player has no boardfeel. (Even many MathGames, including Nim-type games, can be played, equivalently, on a board.) Thus, in the boardfeel sense, simple games are complex and complex games are simple! This paradoxical property also doesn't seem to have an analog in the realm of decision problems. The boardfeel is the main ingredient which makes PlayGames interesting to play. III. Math Appeal. PlayGames, in addition to being interesting to play, also have considerable mathematical appeal. This has been exposed recently by the theory of partizan games established by Conway and applied to endgames of go by Berlekamp, students and associates. On the other hand, MathGames have their own special combinatorial appeal, of a some- what different flavor. They appeal to and are created by mathematicians of various disciplines, who find special intellectual challenges in analyzing them. As Peter Winkler called a subset of them: "games people don't play". We might also call them, in a more positive vein, "games mathe- maticians play". Both classes of games have applications to areas outside game theory. Examples: surreal numbers (PlayGames), error correcting codes (MathGames). Both provide enlightenment through bewilderment, as David Wolfe and Tom Rodgers put it. IV. Existence. There are relatively few PlayGames around. It seems to be hard to invent a PlayGame that catches the masses. In contrast, MathGames abound. They appeal to a large subclass of mathematicians and other scientists, who cherish producing them and pondering about them. The large proportion of MathGames-papers in the games bibliography below reflects this phenomenon. We conclude, inter alia, that for PlayGames, high complexity is desirable. Whereas in all respectable walks of life we strive towards solutions or at least approximate solutions which are polynomial, there are two less respectable hu- man activities in which high complexity is appreciated. These are cryptography (covert warfare) and games (overt warfare). The desirability of high complexity in cryptography -- at least for the encryptor! -- is clear. We claim that it is also desirable for PlayGames. It's no accident that games and cryptography team up: in both there are adversaries, who pit their wits against each other! But games are, in general, the electronic journal of combinatorics #DS2 4 considerably harder than cryptography. For the latter, the problem whether the designer of a cryptosystem has a safe system can be expressed with two quantifiers only: 9 a cryptosystem such that 8 attacks on it, the cryptosystem remains unbroken? In contrast, the decision problem whether White can win if White moves first in a chess game, has the form: "9898 \Delta \Delta \Delta move: White wins?", expressing the question whether White has an opening winning move--with an unbounded number of alternating quantifiers. See also the next section. Thus, it's no surprise that the skill of playing games, such as checkers, chess, or go has long been regarded as a distinctive mark of human intelligence. 3. Why are Combinatorial Games Hard? Existential decision problems, such as graph hamiltonicity and Traveling Sales- person (Is there a round tour through specified cities of cost ^ C?), involve a single existential quantifier ("Is there. . . ?"). In mathematical terms an exis- tential problem boils down to finding a path--sometimes even just verifying its existence--in a large "decision-tree" of all possibilities, that satisfies specified properties. The above two problems, as well as thousands of other interesting and important combinatorial-type problems are NP-complete. This means that they are conditionally intractable, i.e., the best way to solve them seems to re- quire traversal of most if not all of the decision tree, whose size is exponential in the input size of the problem. No essentially better method is known to date at any rate, and, roughly speaking, if an eAEcient solution will ever be found for any NP-complete problem, then all NP-complete problems will be solvable eAEciently. The decision problem whether White can win if White moves first in a chess game, on the other hand, has the form: Is there a move of White such that for every move of Black there is a move of White such that for every move of Black there is a move of White : : : such that White can win? Here we have a large number of alternating existential and universal quantifiers rather than a single existential one. We are looking for an entire subtree rather than just a path in the decision tree. Because of this, most nonpolynomial games are at least Pspace-hard. The problem for generalized chess on an n \Theta n board, and even for a number of seemingly simpler MathGames, is, in fact, Exptime-complete, which is a provable intractability. Put in simple language, in analyzing an instance of Traveling Salesperson, the problem itself is passive: it does not resist your attempt to attack it, yet it is diAEcult. In a game, in contrast, there is your opponent, who, at every step, attempts to foil your effort to win. It's similar to the difference between an autopsy and surgery. Einstein, contemplating the nature of physics said, "Der Allm"achtige ist nicht boshaft; Er ist raAEniert" (The Almighty is not mean; He is sophisticated). NP-complete existential problems are perhaps sophisticated. But your opponent in a game can be very mean! Another reason for the high complexity of games is associated with a most the electronic journal of combinatorics #DS2 5 basic tool of a game : its game-graph. It is a directed graph G whose vertices are the positions of the game, and (u; v) is an edge if and only if there is a move from position u to position v. Since every combination of tokens in the given game is a single vertex in G, the latter has normally exponential size. This holds, in particular, for both Nim and chess. Analyzing a game means reasoning about its game-graph. We are thus faced with a problem that is a priori exponential, quite unlike many present-day interesting existential problems. A fundamental notion is the sum (disjunctive compound) of games. A sum is a finite collection of disjoint games; often very basic, simple games. Each of the two players, at every turn, selects one of the games and makes a move in it. If the outcome is not a draw, the sum-game ends when there is no move left in any of the component games. If the outcome is not a tie either, then in normal play, the player first unable to move loses and the opponent wins. The outcome is reversed in mis`ere play. If a game decomposes into a disjoint sum of its components, either from the beginning (Nim) or after a while (domineering), the potential for its tractability increases despite the exponential size of the game graph. As Elwyn Berlekamp remarked, the situation is similar to that in other scientific endeavors, where we often attempt to decompose a given system into its functional components. This approach may yield improved insights into hardware, software or biolog- ical systems, human organizations, and abstract mathematical objects such as groups. In most cases, there are interesting issues concerning the interactions between subsystems and their neighbors. If a game doesn't decompose into a sum of disjoint components, it is more likely to be intractable (Geography or Poset Games). Intermediate cases happen when the components are not quite fixed (which explains why mis`ere play of sums of games is much harder than normal play) or not quite disjoint (Welter). 4. Breaking the Rules As the experts know, some of the most exciting games are obtained by breaking some of the rules for combinatorial games, such as permitting a player to pass a bounded or unbounded number of times, i.e., relaxing the requirement that players play alternately; or permitting a number of players other than two. But permitting a payoff function other than (0,1) for the outcome (lose, win) and a payoff of ( 1 2 ; 1 2 ) for either (tie, tie) or (draw, draw) usually, but not always, leads to games that are not considered to be combinatorial games; or to borderline cases. 5. Why Is the Bibliography Vast? In the realm of existential problems, such as sorting or Traveling Salesperson, most present-day interesting decision problems can be classified into tractable, conditionally intractable, and provably intractable ones. There are exceptions, the electronic journal of combinatorics #DS2 6 to be sure, such as graph isomorphism, whose complexity is still unknown. But the exceptions are few. In contrast, most games are still in Wonderland, as pointed out in x2(I) above. Only a few games have been classified into the complexity classes they belong to. Despite recent impressive progress, the tools for reducing Wonderland are still few and inadequate. To give an example, many interesting games have a very succinct input size, so a polynomial strategy is often more diAEcult to come by (Richard Guy and Cedric Smith' octal games; Grundy's game). Succinctness and non-disjointness of games in a sum may be present simultaneously (Poset games). In general, the alternating quantifiers, and, to a smaller measure, "breaking the rules", add to the volume of Wonderland. We suspect that the large size of Wonderland, a fact of independent interest, is the main contributing factor to the bulk of the bibliography on games. 6. Why Isn't it Larger? The bibliography below is a partial list of books and articles on combinatorial games and related material. It is partial not only because I constantly learn of additional relevant material I did not know about previously, but also because of certain self-imposed restrictions. The most important of these is that only papers with some original and nontrivial mathematical content are considered. This excludes most historical reviews of games and most, but not all, of the work on heuristic or artificial intelligence approaches to games, especially the large literature concerning computer chess. I have, however, included the com- pendium Levy [1988], which, with its 50 articles and extensive bibliography, can serve as a first guide to this world. Also some papers on chess-endgames and clever exhaustive computer searches of some games have been included. On the other hand, papers on games that break some of the rules of combi- natorial games are included liberally, as long as they are interesting and retain a combinatorial flavor. These are vague and hard to define criteria, yet combi- natorialists usually recognize a combinatorial game when they see it. Besides, it is interesting to break also this rule sometimes! We have included some ref- erences to one-player games, e.g., towers of Hanoi, n-queen problems, 15-puzzle and peg-solitaire, but only few zero-player games (such as Life and games on "sand piles"). We have also included papers on various applications of games, especially when the connection to games is substantial or the application is interesting or important. During 1990-2001, Theoretical Computer Science ran a special Mathematical Games Section whose main purpose was to publish papers on combinatorial games. TCS still solicits papers on games. In 2001, INTEGERS--Electronic J. of Combinatorial Number Theory has started a Combinatorial Games Section. Lately, Internat. J. Game Theory has begun an effort to publish more papers on combinatorial games. It remains to be seen whether any of these forums, or others, will become focal points for high-class research results in the field of combinatorial games. the electronic journal of combinatorics #DS2 7 7 The Dynamics of the Literature The game bibliography below is very dynamic in nature. Previous versions have been circulated to colleagues, intermittently, since the early 1980's. Prior to every mailing updates were prepared, and usually also afterwards, as a result of the comments received from several correspondents. The listing can never be "complete". Thus also the present form of the bibliography is by no means complete. Because of its dynamic nature, it is natural that the bibliography became a "Dynamic Survey" in the Dynamic Surveys (DS) section of the Electronic Journal of Combinatorics (ElJC) and The World Combinatorics Exchange (WCE). The ElJC and WCE are on the World Wide Web (WWW), and the DS can be accessed.(click on "Surveys"). The ElJC has mirrors at various locations. Furthermore, the European Mathematical Information Service (EMIS) mirrors this Journal, as do all of its mirror sites (currently over forty of them). See 8. An Appeal Hereby I ask the readers to continue sending to me corrections and comments; and inform me of significant omissions, remembering, however, that it is a se- lected bibliography. I prefer to get reprints, preprints or URLs, rather than only titles -- whenever possible. Material on games is mushrooming on the Web. The URLs can be located using a standard searcher, such as Google. 9. Idiosyncrasies A year or so after the bibliography became available electronically, I stopped snailmailing hard copies to potential readers. Most of the bibliographic entries refer to items written in English, though there is a sprinkling of Danish, Dutch, French, German, Japanese, Slovakian and Russian, as well as some English translations from Russian. The predominance of English may be due to certain prejudices, but it also reflects the fact that nowadays the lingua franca of science is English. In any case, I'm soliciting also papers in languages other than English, especially if accompanied by an abstract in English. On the administrative side, Technical Reports, submitted papers and un- published theses have normally been excluded; but some exceptions have been made. Abbreviations of book series and journal names follow the Math Reviews conventions. Another convention is that de Bruijn appears under D, not B; von Neumann under V, not N, McIntyre under M not I, etc. the electronic journal of combinatorics #DS2 8 Earlier versions of this bibliography have appeared, under the title "Selected bibliography on combinatorial games and some related material", as the master bibliography for the book Combinatorial Games, AMS Short Course Lecture Notes, Summer 1990, Ohio State University, Columbus, OH, Proc. Symp. Appl. Math. 43 (R. K. Guy, ed.), AMS 1991, pp. 191-226 with 400 items, and in the Dynamic Surveys section of the Electronic J. of Combinatorics in November 1994 with 542 items (updated there at odd times). It also appeared as the master bibliography in Games of No Chance, Proc. MSRI Workshop on Combinatorial Games, July, 1994, Berkeley, CA (R. J. Nowakowski, ed.), MSRI Publ. Vol. 29, Cambridge University Press, Cambridge, 1996, pp. 493-537, under the present title, containing 666 items. The version published in the palindromic year 2002 contained the palindromic number 919 of references. It constituted a growth of 38%. It appeared in ElJC and as the master bibliography in More Games of No Chance, Proc. MSRI Workshop on Combinatorial Games, July, 2000, Berkeley, CA (R. J. Nowakowski, ed.), MSRI Publ. Vol. 42, Cambridge University Press, Cambridge, pp. 475-535. The current update (mid-2003), in ElJC, contains 1001 items, another palindrome. 10. Acknowledgments Many people have suggested additions to the bibliography, or contributed to it in other ways. Among those that contributed more than two or three items are: Akeo Adachi, Ingo Alth"ofer, Thomas Andreae, Eli Bachmupsky, Adriano Bar- lotti, J'ozsef Beck, Claude Berge, Gerald E. Bergum, H. S. MacDonald Coxeter, Thomas S. Ferguson, James A. Flanigan, Fred Galvin, Martin Gardner, Alan J. Goldman, Solomon W. Golomb, Richard K. Guy, Shigeki Iwata, David S. John- son, Victor Klee, Donald E. Knuth, Anton Kotzig, Jeff C. Lagarias, Michel Las Vergnas, Hendrik W. Lenstra, Hermann Loimer, F. Lockwood Morris, Richard J. Nowakowski, Judea Pearl, J. Michael Robson, David Singmaster, Wolfgang Slany, Cedric A. B. Smith, Rastislaw Telg'arsky, Y_ohei Yamasaki and others. Thanks to all and keep up the game! Special thanks are due to various helpers who assisted with the initial T E X file, to Silvio Levy, who has edited and transformed it into L A T E X2e in 1996, and to Wolfgang Slany, who has transformed it into a BIBTeX file at the end of the previous millenium, and solved a "new millenium" problem encountered when the bibliography grew beyond 999 items. 11. The Bibliography