Create a Connect Four AI using Python

Connect Four is a classic two-player connection board game. Players take turns dropping colored discs into a vertical grid, aiming to be the first to form a horizontal, vertical, or diagonal line of four of one‘s own discs. While it has simple rules, Connect Four involves planning and decision-making that make it an interesting challenge for artificial intelligence.

In this article, we‘ll walk through how to create an expert-level Connect Four AI using Python. The AI will use the minimax algorithm with alpha-beta pruning to select the optimal move by looking several steps ahead. By the end, you‘ll understand the key concepts needed to create AIs for Connect Four and other similar games.

Representing the Game State

First, we need a way to represent the game board and state in Python. We can model the board as a 2D list (list of lists), where each inner list is a column that can hold up to 6 pieces. A simple representation could look like:

board = [
    [0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0], 
    [0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0]
]

Here 0 represents an empty slot, 1 can represent player 1‘s pieces, and 2 can represent player 2‘s pieces. To place a piece, we find the next open slot in the selected column (scanning from bottom to top) and place the player‘s number there.

We‘ll also keep track of the current player (1 or 2) and whether the game is won yet or not. Together, the board, current player, and game-over state represent a game state that the AI will evaluate.

Basic Game Functions

Next, let‘s write some basic functions to manage the game:

• drop_piece(board, row, col, piece): Adds a new piece to the board at the given location
• is_valid_location(board, col): Checks if a column has any open slots left
• get_next_open_row(board, col): Finds the next open row in a given column (to place a new piece)
• print_board(board): Displays the board on the screen
• winning_move(board, piece): Checks if the given player has a winning configuration

These are the essential operations we need to run the game. The winning_move function will check for four-in-a-row patterns horizontally, vertically, and diagonally.

Implementing the Minimax AI

Now we get to the interesting part – giving our AI strategic decision-making abilities! We‘ll use the classic minimax algorithm, which works by:

1. Generating all possible next moves from the current game state
2. Recursively simulating each next move to find all possible ways the game could end
3. Evaluating the desirability of each end-game state for the AI
4. Choosing the next move that leads to the most favorable outcome for the AI

The key is the evaluation function, which looks at a game state and assigns it a score based on how good it is for the AI player. A simple evaluation could just be:

• +1000 if the AI wins
• -1000 if the opponent wins
• 0 for a draw or non-terminal state

To choose its move, the AI generates all valid next moves. For each move, it plays out the game to completion (by calling minimax recursively) and finds the minimum score of all the potential outcomes. This represents the opponent playing optimally in response to each of the AI‘s possible moves.

The AI then picks the move that has the maximum minimum score, the move that leads to the best worst-case outcome. This is the core of the minimax algorithm – maximizing the AI‘s minimum gain.

Here‘s a basic implementation of minimax for Connect Four in Python:

def minimax(board, depth, maximizingPlayer):
    valid_locations = get_valid_locations(board)
    is_terminal = is_terminal_node(board)
    if depth == 0 or is_terminal:
        if is_terminal:
            if winning_move(board, 2):
                return (None, 100000000000000)
            elif winning_move(board, 1):
                return (None, -10000000000000)
            else: # Game is over, no more valid moves
                return (None, 0)
        else: # Depth is zero
            return (None, score_position(board, 2))
    if maximizingPlayer:
        value = -math.inf
        column = random.choice(valid_locations)
        for col in valid_locations:
            row = get_next_open_row(board, col)
            b_copy = board.copy()
            drop_piece(b_copy, row, col, 2)
            new_score = minimax(b_copy, depth-1, False)[1]
            if new_score > value:
                value = new_score
                column = col
        return column, value

    else: # Minimizing player
        value = math.inf
        column = random.choice(valid_locations)
        for col in valid_locations:
            row = get_next_open_row(board, col)
            b_copy = board.copy()
            drop_piece(b_copy, row, col, 1)
            new_score = minimax(b_copy, depth-1, True)[1]
            if new_score < value:
                value = new_score
                column = col
        return column, value

This version of minimax also includes a depth limit and a separate scoring function score_position to evaluate non-terminal states. The is_terminal_node function checks if the game has ended (someone has won or the board is full).

Optimizing with Alpha-Beta Pruning

While minimax works, it can quickly become inefficient as the game tree grows exponentially with each additional ply of depth. A clever optimization is alpha-beta pruning, which eliminates branches that the algorithm has determined cannot influence the final decision.

The idea is to keep track of two additional values:

• alpha: The maximum score the maximizing player is assured of
• beta: The minimum score the minimizing player is assured of

As the algorithm searches, it updates alpha whenever the maximum score increases and beta whenever the minimum score decreases. Before evaluating a new node, it checks if the current alpha is greater than or equal to the current beta. If so, it stops evaluating that node (prunes it) because the maximizing player will never choose it.

Here‘s minimax with alpha-beta pruning added:

def minimax(board, depth, alpha, beta, maximizingPlayer):
    valid_locations = get_valid_locations(board)
    is_terminal = is_terminal_node(board)
    if depth == 0 or is_terminal:
        if is_terminal:
            if winning_move(board, 2):
                return (None, 100000000000000)
            elif winning_move(board, 1):
                return (None, -10000000000000)
            else: # Game is over, no more valid moves
                return (None, 0)
        else: # Depth is zero
            return (None, score_position(board, 2))
    if maximizingPlayer:
        value = -math.inf
        column = random.choice(valid_locations)
        for col in valid_locations:
            row = get_next_open_row(board, col)
            b_copy = board.copy()
            drop_piece(b_copy, row, col, 2)
            new_score = minimax(b_copy, depth-1, alpha, beta, False)[1]
            if new_score > value:
                value = new_score
                column = col
            alpha = max(alpha, value)
            if alpha >= beta:
                break
        return column, value

    else: # Minimizing player
        value = math.inf
        column = random.choice(valid_locations)
        for col in valid_locations:
            row = get_next_open_row(board, col)
            b_copy = board.copy()
            drop_piece(b_copy, row, col, 1)
            new_score = minimax(b_copy, depth-1, alpha, beta, True)[1]
            if new_score < value:
                value = new_score
                column = col
            beta = min(beta, value)
            if alpha >= beta:
                break
        return column, value

Alpha-beta pruning can dramatically reduce the number of nodes evaluated without changing the final result, making the AI much more efficient. The effectiveness depends on the order in which nodes are examined – ideally we want to search better nodes first to trigger more pruning.

Analyzing the AI‘s Performance

So how strong is this Connect Four AI? With a sufficiently high depth limit, it should play a perfect game. Connect Four has been solved – with perfect play, the first player can always force a win. Our minimax AI will essentially traverse the entire game tree to find the guaranteed winning moves.

In practice, the depth limit constrains how far ahead the AI can look. At lower depths like 3-5, the AI can still be beaten by a skilled human taking advantage of its limited planning. The evaluation function also becomes more important at lower depths to assess positions the AI can‘t see to the end.

The time complexity of minimax is O(b^m), where b is the branching factor (number of legal moves at each point) and m is the maximum depth. Connect Four has a branching factor of about 4, so searching 8 plies deep means evaluating 4^8 = 65,536 nodes. Alpha-beta pruning reduces this by a constant factor that depends on move ordering.

The space complexity is O(bm) since minimax recurses m levels deep and needs b space at each level to generate the next moves. With alpha-beta pruning, the space is limited to O(m) since branches are cut off.

Extending the Concepts

The ideas behind this Connect Four AI – minimax, alpha-beta pruning, evaluation functions – are the core of many game-playing AIs. Chess, checkers, Othello, and more can use these same algorithms with game-specific modifications.

The evaluation function is key to tuning AIs for different games. More sophisticated evaluation functions consider things like piece mobility, control of the center, pawn structure, king safety, etc. These factors are combined into a single score, often using carefully tuned weights.

More advanced game AIs also use additional techniques:

• Iterative deepening: Searching with gradually increasing depth limits to better use time
• Transposition tables: Caching previously seen positions to avoid redundant searches
• Move ordering: Searching more promising moves first to maximize pruning
• Endgame tablebases: Precomputed perfect results for endgame positions
• Monte Carlo methods: Using randomized playouts to estimate the value of positions

I hope this dive into Connect Four AI has given you a taste of how game-playing programs work under the hood. Try implementing it yourself, experiment with different evaluation functions, and see how deep you need to search to beat it. Then take these concepts and apply them to your favorite strategy games!

Here are some additional resources to learn more:

• Minimax on Wikipedia
• Game Tree on Wikipedia
• Chess Programming on Chessprogramming.org
• Monte Carlo Tree Search on Baeldung

Happy AI gaming!