How to Create an Unbeatable Tic-Tac-Toe AI with Minimax

Tic-tac-toe might seem like a simple game, but creating an AI opponent that plays perfectly is no trivial task. Fortunately, the minimax algorithm provides an elegant solution. Using clever state space search and an evaluation function, minimax enables the computer to analyze future game states and determine the absolute best move.

In this article, we‘ll take a deep dive into the minimax algorithm and implement an unbeatable Tic Tac Toe AI step-by-step. By the end, you‘ll understand how this cornerstone of game theory outsmarts human opponents and never loses. Let‘s get started!

Origins of Minimax

Minimax was originally conceived in the 1920s by mathematician Emil Zermelo in the context of two-player games with perfect information, like tic-tac-toe and chess. Game theorist John Von Neumann further developed the algorithm in the 1940s, proving that minimax provides an optimal solution to zero-sum, turn-based games.

Essentially, minimax assumes both players are playing their best and always calculates the move that maximizes its own potential gain while minimizing the opponent‘s. Over the years, minimax has become a core technique not just in game AI but noncooperative game theory and decision making under uncertainty.

Key Concepts

Before diving into pseudocode, let‘s review some fundamental concepts that minimax relies on:

Game state: A snapshot configuration of the game at a given turn, like the arrangement of Xs and Os on a tic-tac-toe board.

State space search: The process of exploring potential future game states based on the available moves. This search forms a tree where each node is a game state and each branch is a move.

Terminal state: A game state that ends the game, either because a player has won or the game is a draw (like a full tic-tac-toe board). Terminal states are the "leaves" of the state space search tree.

Evaluation function: A scoring heuristic that estimates the favorability of a given game state for the AI player. For example, a winning state might score +1, a losing state -1, and a draw 0.

Minimax Algorithm

Now let‘s see how minimax utilizes these concepts to determine the optimal move. The core idea is elegant but tricky; minimax recursively simulates all possible game states for future moves and picks the one with maximum gain for the AI and minimum gain for the opponent.

Here‘s the pseudocode:

function minimax(state, depth, maximizingPlayer):
    if depth = 0 or state is a terminal state:
        return evaluation of state
if maximizingPlayer:
    maxEval = -∞
    for each child state:
        eval = minimax(child, depth-1, false)
        maxEval = max(maxEval, eval)
    return maxEval
else:
    minEval = +∞ 
    for each child state:
        eval = minimax(child, depth-1, true)
        minEval = min(minEval, eval)
    return minEval
The key aspects are:


The function takes the current game state, the search depth (number of future moves to analyze), and a boolean indicating if it‘s the AI player‘s turn.


The base case returns the evaluation score if the maximum search depth is reached or the game has ended (a terminal state). 


On the AI player‘s turns, it picks the maximum score of all possible moves, while on the opponent‘s turns it picks the minimum score. This is the "mini" and "max" in minimax.


The function calls itself recursively, alternating between the AI player and opponent, until it reaches the base case and returns a score. This score bubbles up the recursion tree to determine the best move.


Let‘s visualize this with an example Tic Tac Toe endgame:
The board:
X O X
O   O  
X   X

It‘s O‘s turn. Here‘s how minimax evaluates the state space to pick the optimal move:

As you can see, minimax recursively plays out every possible game state, assigning scores based on whether X or O wins. At each level of the tree, it alternatively picks the maximum and minimum score until finding the best move.
Tic Tac Toe AI in Python
Now that we understand the theory, let‘s implement an unbeatable Tic Tac Toe AI in Python. We‘ll represent the board as a 3×3 list, with 0 for empty cells, 1 for AI moves, and -1 for opponent moves.
First, let‘s define some helper functions:
def game_over(board):
    """Check if the game has ended"""
    winning_positions = [
        [board[0][0], board[0][1], board[0][2]],
        [board[1][0], board[1][1], board[1][2]],
        [board[2][0], board[2][1], board[2][2]],
        [board[0][0], board[1][0], board[2][0]],
        [board[0][1], board[1][1], board[2][1]],
        [board[0][2], board[1][2], board[2][2]],
        [board[0][0], board[1][1], board[2][2]],
        [board[2][0], board[1][1], board[0][2]],
    ]
if [1, 1, 1] in winning_positions:
    return 1
elif [-1, -1, -1] in winning_positions:  
    return -1
elif 0 not in board[0] and 0 not in board[1] and 0 not in board[2]:
    return 0
else:
    return None
def evaluate(board):

"""Score a board state"""

if game_over(board) == 1:

return 1

elif game_over(board) == -1:

return -1

else:

return 0
def empty_cells(board):

"""Get all empty cell coordinates"""

cells = []
for x, row in enumerate(board):

for y, val in enumerate(row):

if val == 0:

cells.append([x, y])

return cells
The game_over function checks for a winner by looking at all possible winning positions. It returns 1 if the AI wins, -1 if the opponent wins, 0 for a draw, or None if the game hasn‘t ended.
The evaluate function provides a simple scoring metric, returning 1, -1, or 0 for AI win, loss, or draw respectively.
The empty_cells function returns a list of all empty board coordinates, which we‘ll use to generate possible moves.
Now for the star of the show, the minimax function:
 
def minimax(board, depth, maximizing):
    """Minimax algorithm"""
    # Base case
    if depth == 0 or game_over(board) is not None:
        return evaluate(board)
# Recursive case - maximizing player
if maximizing:
    max_eval = -100
    for cell in empty_cells(board):
        x, y = cell[0], cell[1]
        board[x][y] = 1
        eval = minimax(board, depth-1, False)
        board[x][y] = 0
        max_eval = max(max_eval, eval)
    return max_eval

# Recursive case - minimizing player 
else:
    min_eval = 100
    for cell in empty_cells(board):
        x, y = cell[0], cell[1]
        board[x][y] = -1
        eval = minimax(board, depth-1, True)
        board[x][y] = 0
        min_eval = min(min_eval, eval)
    return min_eval
The logic follows our pseudocode closely. The base case returns the score if we‘ve reached the maximum search depth or a terminal state. 
The recursive cases alternatively maximize and minimize the evaluation score for each possible move. To simulate moves, we modify the board, recursively call minimax, then undo the move. This allows us to search the state space without altering the actual game.
To choose the optimal AI move, we use minimax like so:
def ai_move(board):
    """Get the AI‘s best move"""
    max_score = -100
    best_move = None
    for cell in empty_cells(board):
        x, y = cell[0], cell[1]
        board[x][y] = 1
        score = minimax(board, 5, False)
        board[x][y] = 0
        if score > max_score:
            max_score = score
            best_move = [x, y]
return best_move
We call minimax on each possible AI move, then select the one with the maximum score as the best move. We pass a search depth of 5, which analyzes all future game states since there are at most 9 moves in tic-tac-toe.
And there you have it – an unbeatable Tic Tac Toe AI using minimax! The computer will always either win or draw, proving minimax‘s mathematical effectiveness.
Optimizing with Alpha-Beta Pruning
One downside of minimax is that the state space grows exponentially with search depth, leading to long computations. For games more complex than Tic Tac Toe, we need to optimize.
The most common optimization is alpha-beta pruning. The idea is to ignore branches of the search tree that can‘t influence the final decision, pruning irrelevant states.
Alpha-beta pruning tracks two values:

Alpha: The maximum score the maximizing player can guarantee at a given level
Beta: The minimum score the minimizing player can guarantee at a given level

While recursively searching, if we find a node where alpha is greater than beta, we can stop searching that branch, since the current player will never choose it.
Here‘s the alpha-beta enhanced minimax in Python:
def minimax(board, depth, alpha, beta, maximizing):
if depth == 0 or game_over(board):
    return evaluate(board)

if maximizing:
    max_eval = -100
    for cell in empty_cells(board):
        x, y = cell[0], cell[1]
        board[x][y] = 1
        eval = minimax(board, depth-1, alpha, beta, False)
        board[x][y] = 0
        max_eval = max(max_eval, eval)
        alpha = max(alpha, eval)
        if beta <= alpha:
            break
    return max_eval

else:
    min_eval = 100
    for cell in empty_cells(board):
        x, y = cell[0], cell[1]
        board[x][y] = -1
        eval = minimax(board, depth-1, alpha, beta, True)
        board[x][y] = 0
        min_eval = min(min_eval, eval)
        beta = min(beta, eval)
        if beta <= alpha:
            break
    return min_eval
Alpha-beta pruning can drastically reduce computation time without impacting the final result. Intuitively, it avoids wasting time on moves that are obviously bad.
Beyond Tic Tac Toe
Minimax is a powerful technique that extends far beyond simple games like Tic Tac Toe. With optimizations like alpha-beta pruning, it forms the basis of many champion-level chess, checkers, and othello AIs.
The core minimax logic can be customized for different games by:

Defining an appropriate state representation (like piece positions on a chessboard)
Implementing game-specific move generation (like legal chess moves)
Creating a robust evaluation function that accurately scores states (like counting pieces and positional advantages)
Tuning search depth and other parameters

Developing an effective evaluation function is arguably the most challenging part, often involving complex heuristics and machine learning.
Moreover, minimax has applications outside of game AI, such as in economics, negotiations, and cybersecurity. Any domain requiring robust decision-making under uncertainty can potentially leverage minimax‘s state space search approach.
Conclusion
Congratulations on reaching the end of this deep dive into minimax! We covered the algorithm‘s origins, core concepts like game states and evaluation functions, pseudocode implementation, and optimization techniques. 
Most importantly, you now understand how to use minimax to create an unbeatable Tic Tac Toe AI. You can implement it from scratch in Python and impress your friends with your superior game bot.
Minimax is just the beginning of the game AI rabbit hole. I encourage you to explore more advanced techniques like Monte Carlo tree search and reinforcement learning. But minimax remains an elegant foundation that every game developer should understand.
I hope this tutorial has demystified minimax and inspired you to level up your game AIs. Remember, smart algorithms are indistinguishable from magic. Now go forth and create some wizardry!


	
Related