Search Algorithms: Uninformed, Informed, and Adversarial
Search is a fundamental concept in Artificial Intelligence, tackling the problem of how an agent can navigate from an initial state to a goal state.
What is a Search Problem?
Before we can solve a search problem, we need to define it formally. A search problem consists of several key components:
Uninformed Search
Uninformed search algorithms, also known as blind search, have no additional information about the state space other than how to traverse it. They only know if a state is a goal or not.
Two of the most common uninformed search algorithms are Depth-First Search (DFS) and Breadth-First Search (BFS).
- DFS uses a Stack (Last-In, First-Out). It explores as deeply as possible along each branch before backtracking.
- BFS uses a Queue (First-In, First-Out). It explores the neighbor nodes first, before moving to the next level neighbors.
DFS is not guaranteed to find the shortest path and can get stuck in infinite loops if the state space is infinite. BFS guarantees the shortest path (if step costs are equal) but requires significantly more memory.
Informed Search
Informed search algorithms use problem-specific knowledge to find solutions more efficiently. They use a heuristic function, $h(n)$, which estimates the cost of the cheapest path from node $n$ to the goal.
A* Search
A* (A-star) is one of the most popular informed search algorithms. It evaluates nodes by combining $g(n)$, the cost to reach the node, and $h(n)$, the estimated cost to get from the node to the goal.
$$f(n) = g(n) + h(n)$$
Adversarial Search
When dealing with multi-agent environments, especially games where players have conflicting goals (like Tic-Tac-Toe, Chess, or Checkers), we use adversarial search.
Minimax
The Minimax algorithm assumes two players: MAX and MIN. MAX tries to maximize the score, while MIN tries to minimize it. The algorithm explores the entire game tree to the leaves, then backtracks the scores up the tree.
Alpha-Beta Pruning
Minimax explores the entire game tree, which is often computationally impossible for complex games like Chess. Alpha-Beta Pruning is an optimization technique for the minimax algorithm that reduces the number of nodes evaluated by the minimax algorithm in its search tree.
It maintains two values: $\alpha$ (the best choice so far for MAX) and $\beta$ (the best choice so far for MIN).
Configure your leaf nodes, then press Start Search to observe evaluation behavior.
Alpha-beta pruning does not change the final decision of the minimax algorithm. It only speeds it up by ignoring branches of the game tree that can't possibly influence the final decision.