Combinatorial Game Theory
Combinatorial Game Theory studies strategies and mathematics of
two-player 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 information-hiding
The bible of combinatorial game theory is Winning Ways for
your Mathematical Plays, by
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!
- Abstract Games
connection game similar to hex but based on stacking balls in 3d over a
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.
Best play for imperfect players (and part II),
W.D. Smith, NEC.
- Bibliography of abstract games. From
Neil Bowers at U. New Mexico.
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...
a mathematical puzzle.
Bridges, Dick Christoph's implementation of the Shannon
switching game for grid graphs.
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
- 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
strategy-stealing arguments on such boards. I invent a disguised
version that looks like Mancala.
See also D. Zeilberger's paper on three-row chomp.
Clever games for clever people. Rules for some games from On
Numbers and Games.
problem composition contest. See also David
Wolfe's Clobber page and
game theory foundations applied to digraph kernels, A. Fraenkel.
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 NP-complete; many combinatorial games
are PSPACE-complete. How does complexity relate to puzzle or game
quality? What does it imply about the difficulty of analyzing
- Connect-4. This
is a tic-tac-toe 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 game-theoretic outcomes on various board sizes.
- Connect & Capture
game design by Rick Nordal combining features of chess and dots+boxes.
Games: Variations on a Theme. Book by Cameron Browne.
the knot. A. Bogomolny's site has several pages on combinatorial
- 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
- 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
Java applet, Dan Heller.
- Error-correcting codes
derived from combinatorial games, A. Fraenkel.
- Evolution of
neural networks to play the game of dots-and-boxes, 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
Fraenkel, researcher in CGT at Weizmann Inst.
Festschrift of EJC has a lot of papers on CGT.
combinatorial game theory course notes by A. N. Walker.
a game resembling chess played by moving 3x3 groups of
stones around a Go board.
- Go-Moku. Darse
Billings summarizes results on this tic-tac-toe like game.
Ramsey game implemented in Java by Zhu, Beer, and Slany.
and Hounds. Java implementation of the chase game from Winning Ways.
- Hex frequently
asked questions, D. Boll, and
questions, H. D. Enderton.
A history of traditional games, by James Masters.
electronic journal featuring a combinatorial game theory section.
Combinatorial Game Theory.
Lecture notes by Lim Chu Wee.
Jive. Several nim-like 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
Sprague-Grundy theory, H. L. Bodlaender, Utrecht.
Lines of Action, a connectivity game played with go stones on a
Links, an impartial path-extending 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.
Loeb, researcher in CGT at U. Bordeaux
- Mancala connectivity
Bill Taylor and others prove that one can always reach any n-stone
position from any other in certain Mancala-like games.
- Fabian Mäser
has two combinatorial games on his web page: CGT-chess
(push pawns without capturing), and
Combinatorial Regio (remove a square and its neighbors from a
Games, Madras College.
Mathematical Games, Toys, and Puzzles. Jeff Erickson,
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
Moews research in combinatorial games, especially Go endgames.
- MSRI Combinatorial Game Theory Research Workshop,
July 2000, and
video archive of MSRI CGT workshop talks.
Müller, mathematical go theorist.
Nievergelt group research in games, combinatorics, and exhaustive
- Nimbers. C++
implementation of Conway's "nimber" arithmetic.
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 Nim-values for taking and breaking games.
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
by Jim Propp including a section on combinatorial games.
Plambeck's combinatorial games page.
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
Reading's follow-on paper.
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 /
one-player games. A. Marzetta, ETH Zurich.
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
- Roshambo Run
puzzle combining aspects of sokoban and rock-scissors-paper.
Rusin's mathematical games page
- Scenic trails
ascending from sea-level Nim to alpine chess, Avi Fraenkel.
Bibliography on Combinatorial Games, Avi Fraenkel, in the
Electronic J. of Combinatorics.
- Solitaire Clobber,
Demaine, Demaine, and Fleischer.
Values of Grundy's Game and
of Additively Periodic Nim-Games, Achim Flammenkamp.
Sprouts, a game invented by Conway and Paterson in which
players construct a degree-three planar graph by drawing two-edge
ears. Tech. report of computer analysis by Applegate, Jacobson, and
Sleator. See also Dan Hoey's game notation,
discussions in the Geometry Forum,
World Game of Sprouts
college math games site,
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
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.
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 Liben-Nowell.
research. Heidi Burgiel, U. Illinois.
Thompson's abstract games page
- 3d Go,
resource index, D. Bailey.
- Trellis, Anchor,
and Orbit, three connection games from the magazines Games and
Abstract Games, Steven Meyers.
- Troll, a game by Jean-Claude 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.
connection tile-placing 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.
wins domineering on rectangular boards?, Cris Moore.
winning strategy for the Ramsey graph game, A. Pekec,
- David Wolfe's
combinatorial game theory page.
- Wythoff's game. A garbled message
about three-dimensional versions of Wythoff's nim.
open-source client-server 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
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
04 Feb 2013, 17:49:27 PST