\documentclass[12pt]{article} \usepackage{e-jc} \specs{DS2}{}{2009} \def\here/{in: {\it Games of No Chance}} % \parskip 1pt plus 1pt % %\pagestyle{myheadings} %\markright{\sc the electronic journal of combinatorics \#DS2\hfill} \def\NP{N\hskip -2pt P} \font\amsy=msbm10 \newcommand\IZ{\hbox{\amsy\char'132}} \begin{document} %\thispagestyle{empty} %\title[Selected Bibliography] \title{Combinatorial Games: Selected Bibliography with a Succinct Gourmet Introduction} %%Added for DS: %\section*{\sc \ \ \ the electronic journal of combinatorics 1 (1994), %\#DS2\hfill} %%Changed for DS. Note, in particular: \maketitle{} below. %\address{Aviezri S.\ Fraenkel\\ %Department of Applied Mathematics and Computer Science\\ %Weizmann Institute of Science\\ %Rehovot 76100, Israel} %\email{fraenkel@wisdom.weizmann.ac.il\\\indent\ %http:/$\!$/www.wisdom.weizmann.ac.il/\tilde fraenkel/fraenkel.html} \author{Aviezri S.\ Fraenkel\\ \\ Department of Applied Mathematics and Computer Science\\ Weizmann Institute of Science\\ Rehovot 76100, Israel\\ {\tt fraenkel@wisdom.weizmann.ac.il}\\ {\tt http:/$\!$/www.wisdom.weizmann.ac.il/$\sim$fraenkel}\\ \\} \date{} \maketitle \section{What are Combinatorial Games?} Roughly speaking, the family of {\it 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 difficult chess are examples of combinatorial games. And so is go. The shorter terminology {\it game\/}, {\it games\/} is used below to designate combinatorial games. \section{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 {\sl P}space, {\sl E}xptime and {\sl E}xpspace, 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, biology --- and analysis and design of mathematical and commercial games!\eject But when the chips are down, it is this ``natural appeal" that lures 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. A common expression of these vile cravings is found in the passions roused by local, national and international tournaments. An intellectually refined version of these dark desires, well hidden beneath the fa\c cade of scientific research, is the consuming drive ``to beat them all", to be more clever than the most clever, in short --- to create the tools to {\it Math}ter them all in hot {\it comb\/}inatorial {\it comb\/}at! Reaching this goal is particularly satisfying and sweet in the context of combinatorial games, in view of their inherent high complexity.\medskip With a slant towards artificial intelligence, Pearl wrote that games ``offer a perfect laboratory for studying complex problem-solving methodologies. With a few parsimonious 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.''\medskip To further explore the nature of games, we consider, informally, two subclasses. \begin{itemize} \item[(i)] Games People Play ({\it playgames}): games that are challenging to the point that people will purchase them and play them. \item[(ii)] Games Mathematicians Play ({\it 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''. %They %are usually tractable. \end{itemize} 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. \begin{itemize} \item[I.] {\sf 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 {\it Wonderland\/}: we are wondering about their as yet unknown complexity. Roughly speaking, however, NP-hardness is a necessary but not a sufficient 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.) \item[II.] {\sf Boardfeel}. None of us may know an exact strategy from a midgame position of chess, but even a novice, merely by looking at the board, gets some feel who of the two players is in a stronger position -- even what a strong or weak next move is. This is what we loosely call {\it 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 when defeat is imminent, only one or two moves away, 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. %Its lack causes mathgames not to be %played by ``the man in the street'', but the appeal to mathematicians. %(Of course there %are exceptions. Some games on Boolean formulas are Exptime-complete, %and there is a growing number of other games that are Pspace-hard, %yet none of them seems to have the potential of commercial marketability. %In the other direction, the exceptions are perhaps rarer: Gale's game %Bridg-it has been shown to be polynomial by Oliver Gross. Martin Gardner %has informed me that it is the {\it only\/} polynomial game he knows %which has enjoyed commercial success.) \item[III.] {\sf 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 somewhat 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 mathematicians 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. \item[IV.] {\sf Existence}. There are relatively few successful 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. \end{itemize}\medskip 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 human 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, 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: $\exists$ a cryptosystem such that $\forall$ 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: ``$\exists\forall\exists\forall\cdots$ move: White wins?'', expressing the question whether White has an opening winning move --- with an unbounded number of alternating quantifiers. This makes games the more challenging and fascinating of the two, besides being fun! See also the next section.\medskip 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. \section{Why are Combinatorial Games Hard?} Existential decision problems, such as graph hamiltonicity and Traveling Salesperson (Is there a round tour through specified cities of cost $\leq C$?), involve a single existential quantifier (``Is there\dots?''). In mathematical terms an existential 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-{\it complete\/}. This means that they are {\it conditionally intractable}, i.e., the best way to solve them seems to require 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 efficient solution will ever be found for any NP-complete problem, then all NP-complete problems will be solvable efficiently. 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 {\it every\/} move of Black there is a move of White such that for {\it every\/} move of Black there is a move of White $\dots$ 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 {\sl P}space-hard. The problem for generalized chess on an $n\times n$ board, and even for a number of seemingly simpler mathgames, is, in fact, Exptime-complete, which is a {\it 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 difficult. 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 raffiniert" (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!\medskip Another manifestation of the high complexity of games is associated with a most basic tool of a game : its {\it 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 {\it 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 {\it a priori\/} exponential, quite unlike many present-day interesting existential problems. A fundamental notion is the {\it 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 {\it normal\/} play, the player first unable to move loses and the opponent wins. The outcome is reversed in {\it mis\`ere\/} play. If a game decomposes into a {\it 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 biological 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). Thane Plambeck has recently made progress with mis\`ere play, and we will be hearing more about this shortly. The hardness of games is eased somewhat by the efficient freeware package ``Combinatorial Game Suite'', courtesy of Aaron Siegel. \section{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\over 2},{1\over 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. \section{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, 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 \S2(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 difficult to come by (Richard Guy and Cedric Smith's 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. \section{Why Isn't it Larger?} The bibliography below is a {\sl 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 compendium 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 combinatorial games are included liberally, as long as they are interesting and retain a combinatorial flavor. These are vague and hard to define criteria, yet combinatorialists usually recognize a combinatorial game when they see it. Besides, it is interesting to break also this rule sometimes! We have included some references 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. High-class meetings on combinatorial games, such as in Columbus, OH (1990), at MSRI (1994, 2000), at BIRS (2005) resulted in books, or a special issue of a journal -- for the Dagstuhl seminar (2002). During 1990--2001, {\it 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 2002, {\it Integers---Electronic J.\ of Combinatorial Number Theory\/} began publishing a Combinatorial Games Section. The combinatorial games community is growing in quantity and quality! \section{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 {\it Electronic Journal of Combinatorics\/} (ElJC) and {\it The World Combinatorics Exchange\/} (WCE). The ElJC and WCE are on the World Wide Web (WWW), and the DS can be accessed at\hfill\break http://www.combinatorics.org/\hfill\break (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\hfill\break http://www.emis.de/tech/mirrors.html\smallskip \section{An Appeal} I ask readers to continue sending to me corrections and comments; and inform me of significant omissions, remembering, however, that it is a {\it selected\/} 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 search engine, such as Google. \section{Idiosyncrasies} 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 {\it 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 unpublished theses have normally been excluded; but some exceptions have been made. Abbreviations of book series and journal names usually follow the {\it 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. \medskip 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 {\it Combinatorial Games}, AMS Short Course Lecture Notes, Summer 1990, Ohio State University, Columbus, OH, {\it Proc.\ Symp.\ Appl.\ Math.}\ {\bf 43} (R.\ K.\ Guy, ed.), AMS 1991, pp.\ 191--226 with 400 items, and in the {\it Dynamic Surveys\/} section of the {\it Electronic J.\ of Combinatorics\/} in November 1994 with 542 items (updated there at odd times). It also appeared as the master bibliography in {\it 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 {\it 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. \section{Acknowledgments} Many people have suggested additions to the bibliography, or contributed to it in other ways. Ilan Vardi distilled my {\it Math-mas}ter (\S2) into {\it Math}ter. Among those that contributed more than two or three items are: Akeo Adachi, Ingo Alth\"ofer, Thomas Andreae, Eli Bachmupsky, Adriano Barlotti, J\'ozsef Beck, the late Claude Berge, Gerald E.\ Bergum, H.\ S.\ MacDonald Coxeter, Thomas S.\ Ferguson, James A.\ Flanigan, Fred Gal\-vin, Martin Gardner, Alan J.\ Goldman, Solomon W.\ Golomb, Richard K.\ Guy, Shigeki Iwata, David S.\ Johnson, 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, Mark D. Ward, Y\=ohei Yamasaki and others. Thanks to all and keep up the game! Special thanks to Mark Ward who went through the entire file with a fine comb in late 2005, when it contained 1,151 items, correcting errors and typos. Many thanks also to various anonymous helpers who assisted with the initial \TeX\ file, to Silvio Levy, who has edited and transformed it into \LaTeX2e 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. Keen users of the bibliography will notice that there is a beginning of MR references, due to Richard Guy's suggestion, facilitated by his student Alex Fink. %\newcount\pointnum %\pointnum = 0 %\def\pointbegin{\pointnum = 0 \point } % %\setbox0\hbox{111.\enspace} %\newdimen\thehangindent \thehangindent=\wd0 % %\def\point{\par\global\advance\pointnum by 1 % \noindent\hangindent \thehangindent \hbox to % \thehangindent{\hfill\the\pointnum .\enspace}\ignorespaces} \nocite{*} \sloppy \bibliographystyle{gb} \bibliography{gb} \label{lastbibl} \end{document} .