HEXAPAWN

Copyright (c) 1962 Martin Gardner 

Hexapawn is played on a NxM square board. Here is the simpler version setup:

 
MOVE - All stones move one cell forward to an empty cell.
CAPTURE - Stones capture diagonal forward. 
Captures are not mandatory!
GOAL - Wins the player who reaches the last rank with one stone.

Robert Price says: Hexapawn was designed to illustrate mechanical game-players by Martin Gardner, the well-known Scientific American mathematics columnist (`Mathematical Games`, Scientific American, March 1962; reprinted in `The Unexpected Hanging and Other Mathematical Diversions`, Chapter 8). University Students of Computer Science are frequently given the problem of designing a program to play Hexapawn against a human. I saw such a program in an old book full of BASIC programs. It let the user make the first move, because it was a `good sport`. Little does the unsuspecting user know, there exists a perfect strategy for the second player (in the 3x3 version)! [...] The game is guaranteed to terminate, because no move can ever be `undone`, and a draw is impossible. Therefore, one player can find a winning strategy (The 4x4 and 5x5 version are wins for the first player).

An example

White advances b2 to b3, then a4:b3, c2:b3, c5-c4, b3:c4, b5:c4, d3:c4 and White wins!

There is a ZRF to play Hexapawn with Zillions, which presents several variants of the game. There is a related game called Breakthrough.