Game Trees

Suppose you have a game on an \(n\times n\) board with some rules and players take turns. Assume no randomness in the game.

For most such games, there exists an algorithm that can tell you how to play perfectly. Given the state of the game, you can tell who can win with certainty.

We define the game state as follows:

• A game state is good if either the current player has already won, or if the current player can move to a bad state for the opposing player.
• A game state is bad if either the current player has already lost, or if every available move leads to a good state for the opposing player.

We’ll represent the game as a tree, with each node being the state.

Thus, a non-leaf node in the game tree is good if it has at least one bad child, and a non-leaf node is bad if all its children are good. By induction, any player that finds the game in a good state on their turn can win the game, even if their opponent plays perfectly; on the other hand, starting from a bad state, a player can win only if their opponent makes a mistake.

So what is the algorithm?

def play_game(state, player):
    if has_won(player):
        return Good
    if has_lost(player):
        return Bad
    for next_state in possible_moves(state):
        if play_game(next_state, other_player) == Bad:
            return Good
    return Bad

For most games, though, the search space is huge and this is an impractical algorithm.