Hexapawn

abc
3a3 black pawnb3 black pawnc3 black pawn3
2a2b2c22
1a1 white pawnb1 white pawnc1 white pawn1
abc
3x3 Hexapawn setup
a4 black pawnb4 black pawnc4 black pawnd4 black pawn
a3b3c3d3
a2b2c2d2
a1 white pawnb1 white pawnc1 white pawnd1 white pawn
4x4 Octopawn setup

Hexapawn is a deterministic two-player game invented by Martin Gardner. It is played on a rectangular board of variable size, for example on a 3×3 board or on a regular chessboard. On a board of size n×m, each player begins with m pawns, one for each square in the row closest to them. The goal of each player is to either advance a pawn to the opposite end of the board or leave the other player with no legal moves (akin to stalemate), including by capturing all of their pawns.

Hexapawn on the 3×3 board is a solved game; with perfect play, White will always lose in 3 moves (1.b2 axb2 2.cxb2 c2 3.a2 c1#). Indeed, Gardner specifically constructed it as a game with a small game tree in order to demonstrate how it could be played by a heuristic AI implemented by a mechanical computer based on Donald Michie's Matchbox Educable Noughts and Crosses Engine (MENACE).

A variant of this game is octopawn, which is played on a 4×4 board with 4 pawns on each side. It is a forced win for White in 5.5 moves with optimal play (beginning with 1.a2 or 1.d2).

Only 24 matchboxes are required for a hexapawn version of Matchbox Educable Noughts and Crosses Engine.