Combinatorial Game Theory
Combinatorial Game Theory studies strategies and mathematics of
twoplayer games of perfect knowledge such as chess or go (but
often either concentrating instead on simpler games such as nim, or
solving endgames and other special cases). An important distinction
between this subject and
classical game theory (a branch of economics) is that game
players are assumed to move in sequence rather than simultanously,
so there is no point in randomization or other informationhiding
strategies.
The bible of combinatorial game theory is Winning Ways for
your Mathematical Plays, by
E. R.
Berlekamp, J. H. Conway, and
R. K. Guy; the mathematical foundations of the field are provided
by Conway's earlier book On Numbers and Games. Many papers
from the more recent collections Games
of No Chance and
More Games of No Chance
are now also available online. If you haven't read
these, get thee to a library!
Recent additions:
Older stuff:
 Abstract Games
Magazine
 Akron,
connection game similar to hex but based on stacking balls in 3d over a
square lattice.
 Amazons:
chess queens use up squares by shooting arrows.
See also Amazong,
Jens Lieberum's Java Amazons program.

Basic Research  Combinatorial Game Theory. A. Bachem, U.
Koeln.

Best play for imperfect players (and part II),
W.D. Smith, NEC.
 Bibliography of abstract games. From
Neil Bowers at U. New Mexico.
 Binary
games, K. S. Brown. One player chooses a sequence of binary
digits, trying to avoid certain divisibility patterns that could be
taken advantage of by the other player. The other player gets to
sit and wait. Perhaps this would be more like a combinatorial game
if the players alternated choosing digits...
 Blet:
a mathematical puzzle.

Bridges, Dick Christoph's implementation of the Shannon
switching game for grid graphs.
 Bryan's
interactive Nim page
 Chessgo, a hybrid game discussed in
Winning Ways in which one player moves a chess piece in an
attempt to evade another player who forms blockades by placing go
stones.
 Chomp, a game played by removing sets
of dominated points in a square or cubical lattice. Bill Taylor and
others discuss play on infinite boards and the nonconstructivity of
strategystealing arguments on such boards. I invent a disguised
version that looks like Mancala.
See also D. Zeilberger's paper on threerow chomp.

Clever games for clever people. Rules for some games from On
Numbers and Games.
 Clobber
problem composition contest. See also David
Wolfe's Clobber page and
Toby Gottfried's
Clobber applet.
 Combinatorial
game theory foundations applied to digraph kernels, A. Fraenkel.
 Combinatorial
game theory in Maple.
 Competitive graph coloring. The
four color theorem says that if one person colors the vertices of a
planar graph, only four colors are needed to avoid getting stuck
with an uncolorable vertex. What if two players take turns, and
only one of them is trying to avoid getting stuck?
 Computational Complexity of Games and
Puzzles. Many puzzles are NPcomplete; many combinatorial games
are PSPACEcomplete. How does complexity relate to puzzle or game
quality? What does it imply about the difficulty of analyzing
games?
 Connect4. This
is a tictactoe like game in which players drop pieces onto
columns and try to get four in a row. John Tromp collects resources
including tips for expert play, an applet which plays perfectly on the
standard 7x6 board, and gametheoretic outcomes on various board sizes.
 Connect & Capture
game design by Rick Nordal combining features of chess and dots+boxes.
 Connection
Games: Variations on a Theme. Book by Cameron Browne.
 Cut
the knot. A. Bogomolny's site has several pages on combinatorial
games.
 Dagstuhl seminar on algorithmic
combinatorial game theory.
 Erik Demain's
combinatorial games page.
 Dino's mathematical games
page. Theory of impartial misère octal games, and a
Javascript implementation that allows you to play against the computer.
 Dodgem, a game from Winning Ways
involving moving cars forward across a board and blocking one's
opponent from doing the same.
 Dots and Boxes
analysis, David Wilson, and
game playing
Java applet, Dan Heller.
See also
Berlekamp's
dotsandboxes page.
 Errorcorrecting codes
derived from combinatorial games, A. Fraenkel.
 Evolution of
neural networks to play the game of dotsandboxes, L. Weaver
and T. Bossomaier.
 Tom Ferguson's home page
includes links to his CGT papers, electronic texts, and problems.
 Fibonacci nim. Winning Ways
describes this game, in which each move removes beans from a pile,
with a limit at step n of at most 2n beans. The
winning strategy involves Fibonacci numbers. Tal Kubo discusses
generalizations with other limit functions, with a conjectural
connection to the recurrence
a(n)=a(a(n1))+a(na(n1)).
 Aviezri
Fraenkel, researcher in CGT at Weizmann Inst.
 Fraenkel
Festschrift of EJC has a lot of papers on CGT.
 G13GAM
combinatorial game theory course notes by A. N. Walker.
 Gess,
a game resembling chess played by moving 3x3 groups of
stones around a Go board.
 GoMoku. Darse
Billings summarizes results on this tictactoe like game.
 Graph
Ramsey game implemented in Java by Zhu, Beer, and Slany.
 Hare
and Hounds. Java implementation of the chase game from Winning Ways.
 Hex frequently
asked questions, D. Boll, and
infrequently asked
questions, H. D. Enderton.

A history of traditional games, by James Masters.
 Integers
electronic journal featuring a combinatorial game theory section.
 Introductory
Combinatorial Game Theory.
Lecture notes by Lim Chu Wee.
 Java
Jive. Several nimlike games programmed by Martin Chlond.
 Joust, a
game in which two knights use up the squares of a chessboard until
one is stuck.

Kayles on special classes of graphs  an application of
SpragueGrundy theory, H. L. Bodlaender, Utrecht.

Lines of Action, a connectivity game played with go stones on a
checkerboard.

Links, an impartial pathextending game programmed in Java by
Dick Christoph. A simple matching strategy works for a square
board, but Christoph's version foils that by adding obstacles.
 Daniel
Loeb, researcher in CGT at U. Bordeaux
 Mancala connectivity
Bill Taylor and others prove that one can always reach any nstone
position from any other in certain Mancalalike games.
 Fabian Mäser
has two combinatorial games on his web page: CGTchess
(push pawns without capturing), and
Combinatorial Regio (remove a square and its neighbors from a
rectangular board)
 Mathematical
Games, Madras College.

Mathematical Games, Toys, and Puzzles. Jeff Erickson,
Berkeley.

Mathematical Go: Chilling Gets the Last Point. Reviewed by R.
Nowakowski and R. K. Guy in Bull. AMS 32 (1995).

Minesweeper solitaire game and its use in teaching mathematical
reasoning.
 David
Moews research in combinatorial games, especially Go endgames.
 MSRI Combinatorial Game Theory Research Workshop,
July 2000, and
streaming
video archive of MSRI CGT workshop talks.
 Martin
Müller, mathematical go theorist.
 J.
Nievergelt group research in games, combinatorics, and exhaustive
search.
 Nimbers. C++
implementation of Conway's "nimber" arithmetic.
 Nimstring
calculator, Freddy Mang.
 Nine men's morris. Ralph Gasser
announces that this has been proven to be drawn with best play. He
has a postscript
paper with details.
 Octal periodicity. Thane Plambeck and
Anil Gangolli announce computational proofs of the periodicity of
some sequences of Nimvalues for taking and breaking games.
 Onedimensional
peg solitaire, Cris Moore.
 Othello (aka Reversi). Othello Java applet, M.
Barkocy. Announcement of complete analysis
of 6x6 game, J. Feinstein.
 Ed Pegg's
combinatorial game theory page
 Papers
by Jim Propp including a section on combinatorial games.
 Thane
Plambeck's combinatorial games page.
 Playing
Nim on a simplicial complex. R. Ehrenborg and E. Steingrimsson
(Elect. J. Combinatorics)
introduce a variation of nim in which a single move can affect all
piles of tokens on the vertices of a simplex in a complex. See also
N.
Reading's followon paper.
 Projective
hex. A variant by Dan Hoey and Bill Taylor, with more symmetric
winning conditions and board than standard hex.
 Put or take a prime. In this game, a position
is represented by a number, and one moves by either adding or
subtracting the largest prime number less than or equal to the
position. This file analyzes positions 0 through 150, using a short C program.
 Puzzles /
oneplayer games. A. Marzetta, ETH Zurich.
 Restoring
Fairness to DukeGo, Greg Martin.

Rockslide, an impartial game programmed in Java by Dick
Christoph. Players take turns dropping balls through a system of
gates, scoring points when the balls make it through to the
bottom.
 Roshambo Run
puzzle combining aspects of sokoban and rockscissorspaper.
 Dave
Rusin's mathematical games page
 Scenic trails
ascending from sealevel Nim to alpine chess, Avi Fraenkel.
 Selected
Bibliography on Combinatorial Games, Avi Fraenkel, in the
Electronic J. of Combinatorics.
 Sokoban
blockpushing puzzle.
 Solitaire Clobber,
Demaine, Demaine, and Fleischer.
 SpragueGrundy
Values of Grundy's Game and
SpragueGrundy Values
of Additively Periodic NimGames, Achim Flammenkamp.

Sprouts, a game invented by Conway and Paterson in which
players construct a degreethree planar graph by drawing twoedge
ears. Tech. report of computer analysis by Applegate, Jacobson, and
Sleator. See also Dan Hoey's game notation,
discussions in the Geometry Forum,
Danny Purvis'
World Game of Sprouts
Association,
the Madras
college math games site,
Ivar
Peterson's Mathland, and
Peter Alfeld's Java implementation (user interface only, you need to think about which
move to make yourself).
 Subtract a square. A game in which
each position is represented by a positive integer and one moves by
subtracting any nonzero square. David Bush discusses some curious
number theory related to the winning positions of this game.
 Surreal numbers. This is a field
extension of the real numbers arising from Conway's theory of
games. Nick Saldanha discusses the definition of surreal
transcendental functions. See also WDJ's surreal
number page.

Sylver coinage. Col. G. L. Sicherman summarizes his results on
this game, described in Winning Ways, in which players
cooperate to construct a monetary system, at each step choosing a
denomination that can not be represented as a combination of
earlier choices. I also have some earlier
postings on the subject.
 Tablut aka
Hnefatafl. Viking checkers: a small set of defenders helps move a
king from the center to the corner of a board while attackers try
to capture the king.
 Taming
the wild in impartial combinatorial games. Thane
Plambeck has a deep mathematical theory of miseré octal games.
 Tetris is Hard, Even to
Approximate, paper by Demaine, Hohenberger, and LibenNowell.
 Tetris
research. Heidi Burgiel, U. Illinois.
 Mark
Thompson's abstract games page
 3d Go,
Fritz Obermeyer.
 Trax
resource index, D. Bailey.
 Trellis, Anchor,
and Orbit, three connection games from the magazines Games and
Abstract Games, Steven Meyers.
 Troll, a game by JeanClaude Rosa
combining features of Hex and Othello.
 Twixt. A game involving placing
diagonal bridges to connect two sides of a board.
See also >Twixt Fanatic,
David Bush's page of Twixt information (wiith links on other games
including Dots+Boxes and Hex).
 Greg Van Patten's home
page includes rules for many new abstract games.
 Venice
connection tileplacing game.
 The Voronoi Game.
Description, articles, references, and demonstration applet on
problems of competitive facility location, where two players place
sites in hopes of being nearest to as much area as possible.
 Who
wins domineering on rectangular boards?, Cris Moore.
 A
winning strategy for the Ramsey graph game, A. Pekec,
DIMACS.
 David Wolfe's
combinatorial game theory page.
 Wythoff's game. A garbled message
about threedimensional versions of Wythoff's nim.
 XiStrat
opensource clientserver board game platform.
 Zigzag. A game in which players
extend a path in a grid one edge at a time in an attempt to reach
their home bases. I suspect that it should not be hard to prove
drawn.
 A
zillion connection games. Column by Ed Pegg Jr. discussing the games
in Cameron Browne's book and some related online resources.
David Eppstein, Dept. Inf.
& Comp. Sci., UC
Irvine.
Last update: