\documentclass{article}

\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{ds2}

\label{lastbibl}

\end{document}