How does a computer plan ahead? It builds a map of the future. In computer science, this map is not a straight line, but a Tree.

The Decision Tree (Game Tree)

Imagine the current position as the root of a tree:

• Root Node: The current chessboard.

• Branches: Each possible move generates a branch.

• Child Nodes: The new board positions after each move.

• Leaves: The end of the game (Checkmate, Stalemate) or the point where we stop calculating.

Visual Representation

                    [Initial Position]       ← Root Node (Level 0)
                    /        |        \
                   /         |         \
              [e2-e4]    [d2-d4]    [Nf3]    ← Level 1 (White's moves)
              /    \       |          |
         [e7-e5] [c7-c5] [d7-d5]   [e7-e6]   ← Level 2 (Black's responses)
            |        |      |          |
           ...      ...    ...        ...    ← Subsequent levels

Nodes and Links in Python

Each node in the tree represents a game "State". We can represent it as a dictionary:

# Representation of a game tree node
node = {
    "board": current_board,      # Board state
    "move": (r1, c1, r2, c2),    # Move that led here
    "children": [],              # List of child nodes
    "value": None                # Position evaluation
}

The Problem of Combinatorial Explosion

In chess, the tree grows exponentially. After only 4 half-moves (2 for White, 2 for Black), there are hundreds of thousands of possible positions:

Level 0: 1 position
Level 1: ~20 possible moves
Level 2: ~400 positions (20 × 20)
Level 3: ~8,000 positions
Level 4: ~160,000 positions
...
After 10 moves: billions of positions!

This is why chess engines use algorithms to "prune" useless branches, like obviously bad moves. The most famous algorithm is Alpha-Beta Pruning.

Evaluation Function

To decide which move is better, the computer must assign a "score" to each position. The simplest evaluation function counts material:

def evaluate_position(board):
  """
    Simple evaluation based on material.
    Positive score = White advantage
    Negative score = Black advantage
    """
    values = {
        'P': 1, 'N': 3, 'B': 3, 'R': 5, 'Q': 9, 'K': 0,  # White (positive)
        'p': -1, 'n': -3, 'b': -3, 'r': -5, 'q': -9, 'k': 0   # Black (negative)
    }
    
    score = 0
    for row in board:
        for square in row:
            if square in values:
                score += values[square]
    
    return score

# Example: If White captured a Black Queen,
# the score will be about +9 (material advantage)