Hexapawn

Hexapawn is a simple game designed by Martin Gardner to illustrate mechanical game-players. Its rules appeared in `Mathematical Games`, Scientific American, March 1962, and were reprinted in The Unexpected Hanging and Other Mathematical Diversions .

Hexapawn is played on a mere 3x3 board. The near rank contains your three pawns, and the far rank contains those of your opponent. Pawns move as in chess, but with no double-step. You win if you get one of your pawns to the far rank. You lose if it is your turn and you cannot move. Since each pawn can only move forward, there is no need for a draw by repetition rule.

Variants

The rules can be extended naturally to larger boards. Also, the pawns can be replaced by Berolina pawns or Berolina Plus pawns.

Zillions of Games

• hexapawn.zip

Spoiler

Since this is a two-player perfect-information game that always ends in a win for one player or the other, each variant has a perfect strategy for one of the players. A little analysis shows that the 3x3 version is a win for Black: If White moves a side pawn, Black captures and will promote unless White captures, after which Black moves his unmoved pawn and stalemates. If White instead advances his center pawn, Black captures (say, with the pawn to White's left). To prevent promotion, White must capture. If White captures with his left pawn, Black advances and stalemates. If White captures with his right pawn, Black still advances; White can't prevent his promotion on the next move.

Zillions completes this analysis in a tiny fraction of a second. It can also solve the other small variants in a reasonable amount of time. The savegames below are included in the archive above, so users with Zillions can peruse one line of the perfect strategy, and explore deviations. Those without Zillions can click on the savegame files below to view them; they are human-readable. Unfortunately, Zillions doesn't play perfectly once it detects a loss. For example, in the given 3x3 Berolina game, Black wins on his first move. However, it is possible for White to prolong the game until Black's second move, by moving a side pawn instead of the center one.

Zillions examined 2.8 billion states of 5x6 Berolina Hexapawn (at about 400,000 states per second on an Athlon 1GHz) before I gave up on it.