Hexapawn - the rules

Hexapawn is a game inspired by chess invented, for educational purposes, by the mathematician Martin Gardner in 1962. It is designed as an extreme simplification of chess: the board is only 3x3 squares and there are only 6 pieces (3 per player): 3 black pawns and 3 white pawns. For the purpose of this game, since there are no other pieces, we have represented the pawns as checkers pieces:

The pawns move as in chess: one square ahead if that square is free, or one square in diagonal if that square is occupied by an opposite-colored pawn, capturing this in the process. The two-step initial move (and en-passant, for the chess experts), is not permitted:

In the configuration above, black’s two pawns on the left and right can either move one step forward or capture white’s central pawn. Black’s center pawn cannot move. As in chess, white moves first.

The goal of the game is to either

1. Capture all of the opponent’s pieces
2. Reach the opponent’s starting rank (row) with one own pawn
3. Leaving the opponent with no legal moves (a situation that in chess would cause a stalemate).

Hexapawn - the strategy

The game is designed such that

1. The possible number of board configurations is extremely small
2. If playing optimally, black always wins

The optimal strategy for black can be quickly retrieved via a very simple brute force reinforcement learning algorithm, which can be reproduced without the use of a proper computer.

As in Gardner’s original instructions, on this board we have printed all possible configurations that black might encounter. We have also indicated all possible moves for black with colored arrows. Next to each configuration, there is a box with colored marbles inside, each color corresponding to one specific move. The algorithm by can be trained by repeatedly playing agains a human opponent. We randomly select a move for each configuration we encounter during a game. If white wins the game, then we proceed to remove the marble corresponding to the latest move played by black:

In the figure above, black has 3 possible moves, indicated with the white, red, and yellow arrows. A yellow marble is extracted, so the bottom-right pawn moves forward 1 square. As a result of this, white wins by moving the sole pawn on black’s beginning rank. Thus, the yellow marbe is removed from the pool of possible moves in the previous configuration:

Indeed, either the red or the white moves would cause black to win: so, the next time this configuration is reached, black will certainly win, since the yellow move will not be available anymore. As a human player, and black’s trainer, white should try to vary the moves they make during the various games, so that black encounters as many different configurations as possible (exploration of the state space), and can thus learn the optimal strategy.