Adversarial Search in Artificial Intelligence (AI)

Adversarial Search is the approach that an AI takes to make a decision on what move to make when another entity tries to beat it. All it does is simple – assumes that the other player always makes the best possible move for themselves and chooses the move which gives you the best result. This one principle forms the basis of all Chess programs, all Go programs, and all negotiation programs designed after 2016.

In this article, we will explore the two basic algorithms – the Minimax algorithm and the Alpha-Beta Pruning algorithm, both of which come with code implementation. We will also cover the algorithms which supersede Minimax in the most powerful programs for games created after 2016, something which is often not covered by most online guides on the same topic.

What Is Adversarial Search?

Adversarial search refers to the technique used in decision making in situations where two or more agents have different objectives. The success of each agent relies on the failure of the other.

Adversarial search contrasts with single-agent search techniques like the Breadth-First Search, the Depth-First Search, and A*. The single-agent search technique assumes that there is no opponent and that the environment is fixed.

There are three characteristics of an adversarial search problem:

1. There are two or more agents who act in turns.
2. Each move changes the outcome for the other agents.
3. There is at least one agent with less information; it means that at least one agent cannot anticipate what the opponent will do next.

Adversarial Search vs. Adversarial Examples: Two Different Concepts

Adversarial search and adversarial examples are two separate ideas with one similarity: their names. Adversarial search is a decision-making algorithm utilized in game-playing and planning. An adversarial example is a tampered-with input, often an image, which causes a machine learning classifier to give an erroneous result without being noticeable by a person.

The misunderstanding of these terms is widespread enough to be mentioned in FAQ information on rival websites. If someone finds this article through a search engine while seeking for the term “adversarial example” used in machine learning security, then adversarial search in game-playing AI is a completely different thing.

Why Adversarial Search Matters in AI

Adversarial search gives an AI agent a formal method for handling competition. Without it, an agent has no way to account for an opponent’s response before choosing a move.

Three functions define its role in AI systems:

Function	What It Does	Example
Strategic evaluation	Scores possible future game states	Assigning a numeric value to a chess board position
Opponent modeling	Assumes optimal play from the opposing agent	Assuming a chess opponent will always block a threatened checkmate
Move selection	Chooses the action with the best guaranteed outcome	Selecting the move that leads to the highest minimum score

The Minimax Algorithm

Minimax is an algorithm that recursively chooses the best move for a player, under the assumption that the opponent also makes the best choice. This algorithm was developed into game theory mathematics by John von Neumann as far back as 1928, many years prior to being implemented in computers playing games.

Key Terms in the Minimax Algorithm

Term	Definition
Game tree	A tree structure representing every possible move and resulting game state
MAX (Maximizer)	The player trying to achieve the highest possible score
MIN (Minimizer)	The player trying to achieve the lowest possible score for the Maximizer
Terminal state	A game state with no further legal moves — a win, loss, or draw
Heuristic evaluation function	A function that assigns a numeric score to a non-terminal game state

How the Minimax Algorithm Works

The Minimax procedure constructs a game tree and then traverses back from the terminal nodes up to the root node.

1. Create all possible moves from the current state of the game.
2. Continue generating moves for each of the resulting states until you reach a terminal node.
3. Calculate the numerical value of each terminal node using the evaluation function.
4. For each Minimizer node, pick the child node with the minimum value.
5. For each Maximizer node, pick the child node with the maximum value.
6. Get the move for the root node that has the maximum value.

FS: Minimax selects a move by assuming the opponent always plays optimally, then choosing the move that guarantees the best outcome against that optimal play.

Minimax Pseudocode

MINIMAX(node, depth, maximizingPlayer):

    if depth == 0 or node is a terminal node:

        return heuristic value of node

    if maximizingPlayer:

        bestValue = -INFINITY

        for each child of node:

            value = MINIMAX(child, depth - 1, FALSE)

            bestValue = max(bestValue, value)

        return bestValue

    else:

        bestValue = +INFINITY

        for each child of node:

            value = MINIMAX(child, depth - 1, TRUE)

            bestValue = min(bestValue, value)

        return bestValue

Minimax in Python

def minimax(node, depth, is_maximizing, evaluate_fn, get_children_fn):

   if depth == 0 or not get_children_fn(node):

        return evaluate_fn(node)

    if is_maximizing:

        best_value = float('-inf')

        for child in get_children_fn(node):

            value = minimax(child, depth - 1, False, evaluate_fn, get_children_fn)

            best_value = max(best_value, value)

        return best_value

    else:

        best_value = float('inf')

        for child in get_children_fn(node):

            value = minimax(child, depth - 1, True, evaluate_fn, get_children_fn)

            best_value = min(best_value, value)

        return best_value

Minimax Time and Space Complexity

The minimax time complexity is O(b^m), where b is the branching factor and m is the maximum depth of the tree. The minimax algorithm considers all legal moves at each level of the tree, and the number of nodes analyzed therefore increases exponentially with depth.

The space complexity varies depending on the implementation used. Storing all nodes at once gives O(b^m) space complexity. The space complexity can be decreased to O(m) by generating and discarding one branch of nodes at a time, which is the common way to implement the algorithm.

PAA: What is the time complexity of the Minimax algorithm? The time complexity of the Minimax algorithm is O(b^m) where b represents the number of legal moves at each turn and m represents the maximum search depth.

Alpha-Beta Pruning: Making Minimax Practical

Alpha-Beta pruning is an enhanced form of Minimax where it eliminates branches of the game tree that have no impact on the final decision-making. This technique was analyzed and described by computer science researchers Donald Knuth and Ronald Moore in the year 1975, although prior versions were around even back in 1950s in the AI community.

The algorithm uses the following two parameters while searching for the solution:

• Alpha: Best value that can be assured by the Maximizer up to now.
• Beta: Best value that can be assured by the Minimizer up to now.

If at any stage, alpha >= beta, then the algorithm cuts off the further exploration of the branches of that node.

Alpha-Beta Pseudocode

ALPHA-BETA(node, depth, alpha, beta, maximizingPlayer):

    if depth == 0 or node is a terminal node:

        return heuristic value of node

    if maximizingPlayer:

        for each child of node:

            alpha = max(alpha, ALPHA-BETA(child, depth - 1, alpha, beta, FALSE))

            if beta <= alpha:

                break

        return alpha

    else:

        for each child of node:

            beta = min(beta, ALPHA-BETA(child, depth - 1, alpha, beta, TRUE))

            if beta <= alpha:

                break

        return beta

Alpha-Beta Pruning in Python

def alpha_beta(node, depth, alpha, beta, is_maximizing, evaluate_fn, get_children_fn):

 if depth == 0 or not get_children_fn(node):

        return evaluate_fn(node)

    if is_maximizing:

        value = float('-inf')

        for child in get_children_fn(node):

            value = max(value, alpha_beta(child, depth - 1, alpha, beta, False, evaluate_fn, get_children_fn))

            alpha = max(alpha, value)

            if beta <= alpha:

                break  # Beta cut-off

        return value

    else:

        value = float('inf')

        for child in get_children_fn(node):

            value = min(value, alpha_beta(child, depth - 1, alpha, beta, True, evaluate_fn, get_children_fn))

            beta = min(beta, value)

            if beta <= alpha:

                break  # Alpha cut-off

        return value

How Much Faster Is Alpha-Beta Pruning Than Minimax?

In the case of optimal ordering of moves, the pruning technique known as Alpha-Beta pruning changes the branching factor from b to b½ and the time complexity from O(bm) to O(b(m/2)).

This is because with Alpha-Beta pruning, one can perform searches twice as deep in the same period of time than what one can do with just the Minimax algorithm. The order in which the moves are made plays a crucial role in determining how close this optimal upper bound is approximated in practice.

Comparison: Minimax vs. Alpha-Beta Pruning

Property	Minimax	Alpha-Beta Pruning
Time complexity (worst case)	O(b^m)	O(b^m)
Time complexity (best case, optimal ordering)	O(b^m)	O(b^(m/2))
Nodes explored	All nodes at every level	Subset of nodes; unpromising branches skipped
Search result	Identical optimal move	Identical optimal move
Additional inputs required	None	Alpha and beta values passed through recursion

Alpha-beta pruning returns the exact same result as Minimax. It changes the number of nodes examined, not the outcome.

Beyond Minimax: Expectimax and Monte Carlo Tree Search

Minimax and alpha-beta pruning assume a deterministic, two-player, zero-sum game with perfect information. Many real games and real search problems do not meet these conditions.

Expectimax: Handling Chance

Expectimax is a modified form of Minimax in which chance nodes are introduced into the game tree when a game contains elements of luck, like dice and card games. Rather than choosing the maximum or minimum values at a chance node, the expectation is calculated, which is basically the sum of all the possible values.

Backgammon is one common example of this kind of game. The player will not have any control over the dice roll, unlike in the Minimax process where there was some specific move made by the opponent.

Monte Carlo Tree Search and Modern Game-Playing Systems

The Monte Carlo Tree Search (MCTS) is a type of search algorithm that constructs the game tree using repeated simulations instead of exhaustive searches along all branches. The MCTS performs many random or guided playouts of the game starting from a particular position and estimates the move that will yield the best outcome based on the results.

MCTS became the primary search strategy for Go programs due to Go’s enormous branching factor of about 250 legal moves per turn, which makes the exhaustive Minimax search intractable even with alpha-beta pruning.

DeepMind’s AlphaGo won a match against Go world champion Lee Sedol in 2016 using MCTS combined with neural networks trained through self-play. In 2017, DeepMind’s AlphaZero applied MCTS with an evaluation function learned using neural networks in chess and shogi games.

Chess engines that use classical Minimax algorithm and alpha-beta search have not been fully displaced by MCTS search algorithm. The Stockfish chess engine, the strongest public chess engine in 2026, employs alpha-beta search together with the NNUE (Efficiently Updatable Neural Network) evaluation function. The Stockfish’s direct competitor powered by MCTS search algorithm is the Leela Chess Zero that uses the AlphaZero algorithm.

Adversarial search algorithm selection by game type

Game Type	Example	Recommended Algorithm
Deterministic, low branching factor	Tic-Tac-Toe, Connect-4	Minimax with Alpha-Beta pruning
Deterministic, high branching factor	Chess	Alpha-Beta pruning with move ordering, or Minimax with a learned evaluation function
Chance-based	Backgammon, card games	Expectimax
Very high branching factor	Go	Monte Carlo Tree Search

Adversarial Search in Practice: Connect-4 Implementation

Connect-4 is a two-player game with the property of being zero-sum and deterministic, whereby the game is played using a grid of seven columns and six rows. 

The implementation below is used to determine the possible moves, evaluate the board state, and use Minimax to find the best move for player O.

Step 1: Check for Available Moves

def is_moves_left(board):

    for row in board:

        for cell in row:

            if cell == '':

                return True

    return False

Step 2: Evaluate the Board

def evaluate(b):

  for row in range(6):

        for col in range(4):

            if b[row][col] == b[row][col+1] == b[row][col+2] == b[row][col+3] == 'o':

                return 10

    for col in range(7):

        for row in range(3):

            if b[row][col] == b[row+1][col] == b[row+2][col] == b[row+3][col] == 'o':

                return 10

    for row in range(3):

        for col in range(4):

            if b[row][col] == b[row+1][col+1] == b[row+2][col+2] == b[row+3][col+3] == 'o':

                return 10

    for row in range(3, 6):

        for col in range(3):

            if b[row][col] == b[row-1][col+1] == b[row-2][col+2] == b[row-3][col+3] == 'o':

                return 10

    return 0

Step 3: Apply Alpha-Beta Pruning to Select the Optimal Move

def minimax_ab(board, depth, alpha, beta, is_max):

 score = evaluate(board)

    if score == 10:

        return score - depth

    if not is_moves_left(board):

        return 0

    if is_max:

        best = float('-inf')

        for col in range(7):

            for row in range(5, -1, -1):

                if board[row][col] == '':

                    board[row][col] = 'o'

                    best = max(best, minimax_ab(board, depth + 1, alpha, beta, False))

                    board[row][col] = ''

                    alpha = max(alpha, best)

                    break

            if beta <= alpha:

                break

        return best

    else:

        best = float('inf')

        for col in range(7):

            for row in range(5, -1, -1):

                if board[row][col] == '':

                    board[row][col] = 'x'

                    best = min(best, minimax_ab(board, depth + 1, alpha, beta, True))

                    board[row][col] = ''

                    beta = min(beta, best)

                    break

            if beta <= alpha:

                break

        return best


def find_optimal_move(board):

    best_move = None

    best_val = float('-inf')

    for col in range(7):

        for row in range(5, -1, -1):

            if board[row][col] == '':

                board[row][col] = 'o'

                move_val = minimax_ab(board, 0, float('-inf'), float('inf'), False)

                board[row][col] = ''

                if move_val > best_val:

                    best_val = move_val

                    best_move = (row, col)

                break

    return best_move

In contrast to pure minimax, pruning is used in this implementation. On average, when considering a Connect-4 game position in the middle of the game where there are 15-20 free positions on the board, alpha-beta pruning evaluates fewer than half as many nodes as pure minimax.

Where Adversarial Search Is Used Today

Applications of Adversarial search are not limited to board games; they can apply to any area where multiple agents perform competitive decision making.

1. Applications to board games and chess playing software. Chess engine Stockfish uses alpha beta tree search algorithm along with neural networks for move generation.
2. Robotics and pathfinding. Autonomous robots use adversarial search in order to find paths around other agents who have conflicting goals.
3. Cybersecurity. Adversarial search helps to detect the attacks by simulating them and predicting the most probable paths of the attacks.
4. Self-driving cars. Adversarial search is used to predict actions of other vehicles in intersections and lane merges.
5. Financial modeling. In order to predict price changes, algorithmic trading software simulates the behaviors of competing market participants.
6. Negotiation systems. AI-based negotiation agents use adversarial search in order to choose the best counteroffers and proposals.

Common Challenges and Limitations

Computational Complexity

Game trees increase exponentially with increase in depth. The average number of moves that can be made in chess is about 35 per position; therefore, at depth 10, there would be about 35^10 positions searched.

The Horizon Effect

The horizon effect happens when the depth-limited search cannot find a relevant event that occurs just outside of the limited depth, such as a capture. The algorithm rates the position as positive, but does not realize that the position is destroyed after another move.

Quiescence Search

The quiescence search increases the depth of a limited search in case of instability — e.g., when exchanging pieces — in order to avoid the horizon effect. Instead of making the limited search in all positions up to a certain level of depth, the algorithm will search in noisy positions until they reach their stability.

Heuristic Evaluation Accuracy

The heuristic evaluation function gives a numeric value to a non-terminal state of a game. The badly chosen heuristic will give wrong moves even when the algorithm is right. The accuracy of the evaluation function plays a bigger role than the depth of the search in most cases.

Real-Time Decision Constraints

Real-life adversarial search algorithms run under strict time constraints. The chess engine, given three minutes for each move, has to make compromises between search depth and time left by performing iterative deepening, going from search to depth 1, then depth 2 and so on.

Frequently Asked Questions

Conclusion

Adversarial search algorithms like minimax and alpha-beta pruning continue to be the initial consideration when dealing with games of this kind, even now they are the two techniques currently used in the most powerful chess engine ever created. There are other techniques used for more complex games: expectimax for games that have any random aspects to them and MCTS for those with very large branching factors. The first decision to make about which to use is whether there is a chance element to the game.