Adversarial Search Algorithms in Artificial Intelligence (AI)

Adversarial Search Algorithms in Artificial Intelligence (AI)

Adversarial search algorithms support strategic choice in AI, especially in competitive settings where agents pursue opposing goals. They appear often in two-player zero-sum games—one side’s gain is the other’s loss, and no mutual win exists. By forecasting an opponent’s moves and replies, adversarial search helps AI agents pick strong strategies.

This image illustrates how Minimax scores candidate moves by accounting for the opponent’s replies and then choosing the move with the highest guaranteed score.

Role of Adversarial Search in AI

• Strategic Thinking: Lets AI forecast an opponent’s likely moves and counters.
• Conflicting Objectives: Manages competitive cases where agents’ goals clash.
• Decision-Making: Scores candidate actions to pick the strongest strategy against a rival.
• State-Space Search: Models game positions and moves as a search tree.
• Game Playing: Underpins AI play in chess, Go, checkers, poker, and similar games.

Components

• Initial state: The game’s starting configuration.
• Players: The agents taking part in the game.
• Actions: The legal moves each player may choose.
• Result function: Maps an action to the resulting state.
• Terminal test: Checks whether the game has ended.
• Utility function: Assigns a numeric score to a terminal state.
• Game tree: Captures possible sequences of moves.

Adversarial search algorithms

Methods such as DFS, BFS, and A* mainly suit single-agent problems without rivalry. In competitive settings—including two-player zero-sum games—adversarial search explores game states while factoring in the opponent’s choices and the depth available for search.

1. Minimax algorithm

The Minimax algorithm is a recursive adversarial search method for decisions in two-player, zero-sum games. It walks the game tree and picks the move that maximizes the AI’s chance of a good outcome, assuming the opponent also plays optimally.

Working

• MAX Node: Stands for the AI player and seeks to maximize the evaluation score.
• MIN Node: Stands for the opponent and seeks to minimize the evaluation score.
• Game Tree Exploration: The algorithm expands possible states until a terminal position or a fixed depth is reached.
• Value Propagation: Scores are passed back up the tree so the best move can be identified.

The basic decision process can be represented as:

Current Game State → Possible Moves → Opponent's Responses → Evaluate Outcomes → Select Best Move

Example: in chess, the AI scores its candidate moves while assuming the opponent’s best replies, then selects the move that remains strongest under that assumption.

2. Alpha-beta pruning

Alpha-beta pruning optimizes Minimax by cutting the number of nodes evaluated in the game tree. Branches that cannot change the final decision are discarded, so the search can go deeper in less time while matching standard Minimax results.

Working

While traversing the tree, the algorithm tracks two values, Alpha (α) and Beta (β):

• Alpha: the best score the maximizer can currently guarantee at this level or above.
• Beta: the best score the minimizer can currently guarantee at this level or below.

When a branch cannot beat a result already found, it is pruned without evaluating remaining nodes. Pruning happens when α ≥ β.

Alpha-beta pruning does not alter Minimax’s answer; it only skips useless branches and speeds up the search.

3. Expectimax algorithm

Expectimax is a Minimax variant for decisions that involve randomness or uncertainty. Unlike Minimax, which assumes an always-optimal opponent, Expectimax can model chance events.

Working

• MAX Nodes: Capture AI decisions that maximize expected utility.
• Chance Nodes: Capture random events with outcomes and probabilities.
• Expected Value Calculation: Outcomes are scored according to their probabilities.
• Action Selection: The action with the highest expected utility is chosen.

The basic decision process can be represented as:

Current Game State → Possible Actions → Random Outcomes → Calculate Expected Values → Select Best Action

Example: with dice rolls, the AI may move without knowing the next roll. Expectimax weighs possible outcomes and probabilities to pick the move with the highest expected value.

4. Depth-Limited Search

Depth-Limited Search (DLS) extends Depth-First Search (DFS) by capping search at a fixed depth. It expands the tree recursively but stops beyond that limit, avoiding needless deep exploration.

Working

• Limited Search Depth: DLS looks only a limited number of moves ahead instead of the full game tree.
• Computational Efficiency: That lowers the cost of searching large trees.
• Depth Limit: Once the limit is hit, that branch is not expanded further.
• State Evaluation: An evaluation function can score the resulting state.

The basic search process can be represented as:

Current Game State → Explore Possible Moves → Check Depth Limit → Evaluate State / Continue Search → Select Action

If the depth limit arrives before a terminal state, DLS evaluates the current state rather than going deeper. It separates cutoff (depth limit reached) from failure (no solution found).

5. Monte-Carlo Tree Search (MCTS)

Monte Carlo Tree Search (MCTS) suits decisions in huge, complex spaces, especially games. Instead of walking the entire tree, MCTS grows it gradually and uses random simulations to estimate move quality, focusing compute on promising regions.

Working

• Selection: Picks a promising node already in the tree.
• Expansion: Adds child nodes for possible actions from that node.
• Simulation: Runs a possible outcome from the new state.
• Backpropagation: Sends the simulation result back up the tree and updates node statistics.

The basic decision process can be represented as:

Current Game State → Selection → Expansion → Simulation → Backpropagation → Select Best Move

Example: in Go, where the state space is enormous, MCTS runs many simulations to estimate promising moves instead of scoring every state.

Implementation of Connect-4 using Minimax algorithm

Connect-4 is a two-player, zero-sum game on a 7×6 grid. Players drop discs into columns and try to form four in a row horizontally, vertically, or diagonally.

In this example, Minimax finds an optimal strategy for Connect-4. Player X uses red and player O uses blue. It is O’s turn; Minimax will choose O’s best move.

Step 1: Check if there are any moves left

The is_moves_left function tests whether any empty cells remain on the board. If an empty cell exists, it returns True (moves are still available). Otherwise it returns False (the board is full).

def is_moves_left(board):
    for row in board:
        for cell in row:
            if cell == '':
                return True
    return False