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.