MSRI Workshop on Combinatorial Games (2000)

We solve the problem of one-dimensional Peg Solitaire. In particular, we show that the set of configurations that can be reduced to a single peg forms a regular language, and that a linear-time algorithm exists for reducing any configuration to the minimum number of pegs.

We then look at the impartial two-player game, proposed by Ravikumar, where two players take turns making peg moves, and whichever play is left without a move loses. We calculate some simple nim-values and discuss when the game separates into a disjunctive sum of smaller games. In the version where a series of hops can be made in a single move, we show that the set of P-positions (wins for the second player) is not described by a regular or context-free language.

Click here to download (Postscript)

Click here to view a video of the talk given at the MSRI workshop (which does not contain all the results of the paper, but which also has a brief discussion of one-dimensional checkers).

Cris Moore <moore@santafe.edu>