Game Trees

Understanding the game constraints

Consider the following simple two-player game played on an $n × n$ square grid with a border of squares; let’s call the players Horace Fahlberg-Remsen and Vera Rebaudi. Each player has $n$ tokens that they move across the board from one side to the other. Horace’s tokens start in the left border, one in each row, and move horizontally to the right; symmetrically, Vera’s tokens start in the top border, one in each column, and move vertically downward. The players alternate turns. In each of his turns, Horace either moves one of his tokens one step to the right into an empty square or jumps one of his tokens over exactly one of Vera’s tokens into an empty square two steps to the right. If no legal moves or jumps are available, Horace simply passes. Similarly, Vera either moves or jumps one of her tokens downward in each of her turns, unless no moves or jumps are possible. The first player to move all their tokens off the edge of the board wins. (It’s not hard to prove that as long as there are tokens on the board, at least one player can legally move, and therefore, someone eventually wins.)

Unless we’ve seen this game before, we probably don’t have any idea how to play it well. Nevertheless, there’s a relatively simple backtracking algorithm that can play this game or any two-player game without randomness or hidden information that ends after a finite number of moves perfectly. That is, if we’re dropped into the middle of a game, and it is possible to win against another perfect player, the algorithm will tell us how to win.

What is a state?

A state of the game consists of the locations of all the pieces and the identity of the current player. These states can be connected into a game tree, which has an edge from state $x$ to state $y$ if, and only if, the current player in state $x$ can legally move to state $y$. The root of the game tree is the initial position of the game, and every path from the root to a leaf is a complete game.

Good and bad game states

To navigate through this game tree, we recursively define a game state to be good or bad as follows:

• A game state is good if

...