What is a search problem?
Many AI problems can be framed as state-space search: possible situations are states, actions that move between them are operators, and the task is to find a sequence of operators from the start state to a goal state. Route finding, puzzles, robot path planning and games like chess all fit. The idea of a machine solving problems "intelligently" goes back to the Turing test debates about defining AI.
Uninformed search
- Breadth-first search (BFS): expands states nearest the start first. It finds the shortest path when all steps cost the same but uses a lot of memory.
- Depth-first search (DFS): follows one branch to the end before backtracking. It uses little memory but does not guarantee the shortest path and can get lost in infinite spaces.
- Uniform-cost search / Dijkstra's algorithm: expands the state with the lowest cost so far, g(n). Dijkstra (1959) showed this finds shortest paths when costs are non-negative.
The A* algorithm
A* was published in 1968 by Peter Hart, Nils Nilsson and Bertram Raphael at the Stanford Research Institute, growing out of path planning for the Shakey robot. It expands states in order of the evaluation function
f(n) = g(n) + h(n)
- g(n): the actual cost from the start to n.
- h(n): a heuristic estimate of the remaining cost from n to the goal, such as straight-line distance on a map or Manhattan distance on a grid.
- Admissibility: if h(n) never overestimates the true remaining cost, A* is guaranteed to find an optimal path.
- Consistency: if h never drops by more than the step cost between neighboring states, no state needs to be re-expanded, improving efficiency.
- With h(n)=0, A* reduces to Dijkstra's algorithm; the more accurate the heuristic, the fewer states are expanded.
Game search: minimax
In two-player games the opponent is also trying to win. Minimax scores the leaves of the game tree (or positions at a fixed depth), then passes up the maximum value on the player's turns (MAX) and the minimum on the opponent's turns (MIN) to choose the best move. Its theoretical basis is von Neumann's 1928 minimax theorem, and Claude Shannon's 1950 paper proposed using it with an evaluation function to let computers play chess.
Alpha-beta pruning
Because minimax examines the whole tree, its cost explodes with depth. Alpha-beta pruning tracks the best values found so far (α, the minimum MAX is assured of; β, the maximum MIN is assured of) and skips branches that cannot affect the result. It returns the same answer as minimax with far less work; Knuth and Moore (1975) showed that with perfect move ordering the number of nodes examined falls to roughly the square root.
Limits and later developments
- Combinatorial explosion limits minimax in very large games such as Go, which led to Monte Carlo tree search combined with neural-network evaluation.
- A* keeps its whole frontier in memory, so memory-saving variants such as IDA* are used for large problems.
- Designing good heuristics and evaluation functions is itself hard and requires domain knowledge.
References
- von Neumann, J. (1928). Zur Theorie der Gesellschaftsspiele. Mathematische Annalen, 100, 295–320.
- Shannon, C. E. (1950). Programming a computer for playing chess. Philosophical Magazine, 41(314), 256–275.
- Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1, 269–271.
- Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100–107.
- Knuth, D. E., & Moore, R. W. (1975). An analysis of alpha-beta pruning. Artificial Intelligence, 6(4), 293–326.