David Eppstein - Publications

Publications with Cristopher Moore

• One-dimensional peg solitaire, and duotaire.
  C. Moore and D. Eppstein.
  arXiv:math.CO/0006067 and math.CO/0008172.
  MSRI Combinatorial Game Theory Research Worksh., July 2000.
  Santa Fe Inst. working paper 00-09-050, September 2000.
  More Games of No Chance, R. J. Nowakowski, ed., MSRI Publications 42, pp. 341–350.

  We describe by a regular expression the one-dimensional peg-solitaire positions reducible to a single peg, and provide a linear-time algorithm (based on finding shortest paths in an associated DAG) for reducing any such position to the minimum number of pegs. We then investigate impartial games in which players alternate peg solitaire moves in an attempt to be the one to move last.

  (Cris' MSRI talk on streaming video – Cris' publications page)