What Is a Combinatorial Game?

In the opening of the first part of his book Games of No Chance, mathematician Richard Nowakowski answers the question of What Is a Combinatorial Game?

This is a game in which
  1. there are two players moving alternately;
  2. there are no chance devices and both players have perfect information;
  3. the rules are such that the game must eventually end; and
  4. there are no draws, and the winner is determined by who moves last.

In the normal game, the last player to move wins. In the misère variant, the last player to move is declared the loser.

The theory of combinatorial games arose from that of impartial games in which, at every stage, the same set of moves is available to both players, regardless of whose move it is. Nim is the prototypical impartial game. Chess is a combinatorial but clearly not an impartial game.

Impartial games have been studied in the 1930s by R. P. Sprague and P. M. Grundy. Combinatorial games came around with the publication of the two volumes of the Winning Ways for Your Mathematical Plays by E. R. Berlekamp, J. H. Conway, R. K. Guy (1982) and On Numbers and Games by J. H. Conway (1981). Here is a sample of what is available at this site:

The Hot Game of Nim · Date Game · Dawson's Chess · Dawson's Kayles · Fraction Game · Grundy's Game · Hex 7 · Kayles · Nim · Nimble · Northcott's game · One Pile · Plainim · Plainim Misère · Scoring · Scoring Misère · Scoring Misère: Two Heaps Perfect Strategy · Silver Dollar Game · Silver Dollar Game With No Silver Dollar · Sticks · Sticky Problem · Sticky Problem II · Subtraction Game · TacTix · Take-Away Games · Turning Turtles · Wythoff's Nim · Wythoff's Nim II ·

References

  1. A. Beck, M. N. Bleicher, D. W. Crowe, Excursions into Mathematics, Millennium Edition, A K Peters, 2000
  2. E. R. Berlekamp, The Dots and Boxes Game, A K Peters, 2000
  3. E. R. Berlekamp, J. H. Conway, R. K. Guy, Winning Ways for Your Mathematical Plays, Volume 1, A K Peters, 2001
  4. J. H. Conway, On Numbers And Games, A K Peters, 2001
  5. A. Fraenkel, Combinatorial Games: Selected Bibliography With A Succinct Gourmet Introduction, ever growing.
  6. M. Gardner, Hexaflexagons and Other Mathematical Diversions, The University of Chicago Press, 1988
  7. R. Guy, fair game, Comap's Explorations in Mathematics, 1989
  8. R. Nowakowski (Ed), Games of No Chance, Mathematical Sciences Research Institute Publications, No 29, Cambridge University Press, 1996

|Contact| |Front page| |Contents| |Geometry| |Up|

Copyright © 1996-2018 Alexander Bogomolny

71492927