Hexapawn is a deterministic two-player game

Game

A game is structured playing, usually undertaken for enjoyment and sometimes used as an educational tool. Games are distinct from work, which is usually carried out for remuneration, and from art, which is more often an expression of aesthetic or ideological elements...

 invented by Martin Gardner

Martin Gardner

Martin Gardner was an American mathematics and science writer specializing in recreational mathematics, but with interests encompassing micromagic, stage magic, literature , philosophy, scientific skepticism, and religion...

. It is played on a rectangular board of variable size, for example on a 3×3 board or on a chessboard

Chessboard

A chessboard is the type of checkerboard used in the board game chess, and consists of 64 squares arranged in two alternating colors...

. On a board of size n×m, each player begins with m pawn

Pawn (chess)

The pawn is the most numerous and weakest piece in the game of chess, historically representing infantry, or more particularly armed peasants or pikemen. Each player begins the game with eight pawns, one on each square of the rank immediately in front of the other pieces...

s, one for each square

Square (geometry)

In geometry, a square is a regular quadrilateral. This means that it has four equal sides and four equal angles...

 in the row closest to them. The goal of each player is to advance one of their pawns to the opposite end of the board or to prevent the other player from moving.

Hexapawn on the 3×3 board is a solved game

Solved game

A solved game is a game whose outcome can be correctly predicted from any position when each side plays optimally. Games which have not been solved are said to be "unsolved"...

; if both players play well, the first player to move will always lose. Also it seems that any player cannot capture all enemy's pawns. Indeed, Gardner specifically constructed it as a game with a small game tree

Game tree

In game theory, a game tree is a directed graph whose nodes are positions in a game and whose edges are moves. The complete game tree for a game is the game tree starting at the initial position and containing all possible moves from each position; the complete tree is the same tree as that...

, in order to demonstrate how it could be played by a heuristic

Heuristic

Heuristic refers to experience-based techniques for problem solving, learning, and discovery. Heuristic methods are used to speed up the process of finding a satisfactory solution, where an exhaustive search is impractical...

 AI

Artificial intelligence

Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...

 implemented by a mechanical computer. A variant of this game is octapawn.

Rules

As in chess

Chess

Chess is a two-player board game played on a chessboard, a square-checkered board with 64 squares arranged in an eight-by-eight grid. It is one of the world's most popular games, played by millions of people worldwide at home, in clubs, online, by correspondence, and in tournaments.Each player...

, each pawn may be moved in two different ways: it may be moved one square forward, or it may capture a pawn one square diagonally ahead of it. A pawn may not be moved forward if there is a pawn in the next square. Unlike chess, the first move of a pawn may not advance it by two spaces. A player loses if he/she has no legal moves or the other player reaches the end of the board with a pawn.

Dawson's chess

Whenever a player advances a pawn to the penultimate rank (unless it is an isolated pawn

Isolated pawn

In chess, an isolated pawn is a pawn which has no friendly pawn on an adjacent file. An isolated queen's pawn is often called an isolani. Isolated pawns are usually a weakness because they cannot be protected by other pawns...

) there is a threat to proceed to the final rank by capture. The opponent's only sensible responses are therefore either to capture the advanced pawn or to advance the threatened one, the latter only being sensible in the case that there is one threatened pawn rather than two. If one restricts 3× hexapawn with the additional rule that the capture is always compulsory, the result is the game Dawson's chess.

Dawson's chess reduces to the impartial game

Impartial game

In combinatorial game theory, an impartial game is a game in which the allowable moves depend only on the position and not on which of the two players is currently moving, and where the payoffs are symmetric...

 denoted .137 in Conway's notation. This means that it is equivalent to a Nim

Nim

Nim is a mathematical game of strategy in which two players take turns removing objects from distinct heaps. On each turn, a player must remove at least one object, and may remove any number of objects provided they all come from the same heap....

-like game in which:

• on a turn, the player may remove one to three objects from a heap,
• removing just one object is a legal move only if the removed object is the only object in the heap, and
• when removing three objects from a heap of five or more, the player may also split the remainder into two heaps.

The initial position is a single heap of size .
The nim-sequence for this game is

0.1120311033224052233011302110452740
1120311033224455233011302110453748
1120311033224455933011302110453748
1120311033224455933011302110453748
1120311033224455933011302110453748 ...,

where bold entries indicate the values that differ from the eventual periodic behavior of the sequence.

External links

• Hexapawn - an article by Robert Price.
• Hexapawn java applet - source code included.