Home / Articles / Game Trees

Game Trees

Game trees are a fundamental concept in AI for two-player games. The minimax algorithm uses a game tree to choose the optimal move by looking ahead several turns and assuming both players play perfectly.

What Is a Game Tree?

A game tree is a tree structure where:

• Each node represents a game state (board position)
• Each edge represents a legal move
• The root is the current game state
• Leaf nodes are terminal states (win, loss, or draw)

For a game like tic-tac-toe, the full tree is small enough to explore completely. For chess, the tree is astronomically large — so we search only a few levels deep.

The Minimax Algorithm

The core idea: one player tries to maximize the score, the other tries to minimize it.

• The MAX player (you) picks the move with the highest score
• The MIN player (opponent) picks the move with the lowest score

The algorithm recursively evaluates all possible future states to a given depth, then backs up scores to the root.

Scoring

At leaf nodes (or at the depth limit), a heuristic evaluation function assigns a score:

• Positive values favor MAX
• Negative values favor MIN
• Zero means equal

For chess, this might be based on material count. For tic-tac-toe, +1 for X wins, -1 for O wins, 0 for draw.

Minimax in C

Here's a basic minimax implementation with a configurable lookahead depth:

#include <stdio.h>
#include <limits.h>

#define MAX_DEPTH 4

/* Returns the score of the best move for the current player.
   is_max: 1 if the current player is maximizing, 0 if minimizing. */
int minimax(int board[], int depth, int is_max) {
    int score = evaluate(board);

    /* Terminal conditions */
    if (score == 10)  return score;  /* MAX wins */
    if (score == -10) return score;  /* MIN wins */
    if (no_moves_left(board)) return 0;  /* Draw */
    if (depth == 0) return score;  /* Depth limit reached */

    if (is_max) {
        int best = INT_MIN;
        for (int i = 0; i < 9; i++) {
            if (board[i] == 0) {
                board[i] = 1;  /* MAX plays */
                int val = minimax(board, depth - 1, 0);
                if (val > best) best = val;
                board[i] = 0;  /* Undo move */
            }
        }
        return best;
    } else {
        int best = INT_MAX;
        for (int i = 0; i < 9; i++) {
            if (board[i] == 0) {
                board[i] = -1;  /* MIN plays */
                int val = minimax(board, depth - 1, 1);
                if (val < best) best = val;
                board[i] = 0;  /* Undo move */
            }
        }
        return best;
    }
}

/* Find the best move for MAX */
int best_move(int board[]) {
    int best_val = INT_MIN;
    int best_pos = -1;

    for (int i = 0; i < 9; i++) {
        if (board[i] == 0) {
            board[i] = 1;
            int move_val = minimax(board, MAX_DEPTH, 0);
            board[i] = 0;

            if (move_val > best_val) {
                best_val = move_val;
                best_pos = i;
            }
        }
    }
    return best_pos;
}

Lookahead Depth

The depth controls how far ahead the algorithm looks. A higher depth means better play but exponentially more computation. The number of nodes examined grows as b^d, where:

• b = branching factor (average number of legal moves)
• d = depth

For chess, b ≈ 35, so depth 4 means examining roughly 35^4 ≈ 1.5 million nodes. This is why commercial chess engines use advanced techniques like alpha-beta pruning and iterative deepening on top of minimax.

Alpha-Beta Pruning

Alpha-beta pruning is an optimization that prunes branches of the tree that cannot possibly influence the final decision. It achieves the same result as minimax but examines far fewer nodes — in the best case, the number of nodes is roughly b^(d/2) instead of b^d.

The idea: maintain two values during the search:

• Alpha: the best score MAX can guarantee
• Beta: the best score MIN can guarantee

When beta <= alpha, the current branch can be cut off — neither player would choose to go down it.

Applications

Game trees apply to any perfect-information two-player zero-sum game:

• Tic-tac-toe (tree is fully explorable)
• Chess and checkers (depth-limited with evaluation functions)
• Go (very high branching factor; modern approaches use Monte Carlo Tree Search + neural networks)
• Connect Four
• Reversi / Othello

The same framework extends to multi-player games and stochastic (chance-based) games with modifications like the expectimax algorithm.