2 Navigating the Space of Possibilities

Search Algorithms, Problem Solving, and the Architecture of Rational Action

CSC5350 · Artificial Intelligence

2.1 Opening Narrative

2.1.1 The Right Move in a Space Too Large to Count

In 1997, Deep Blue defeated Garry Kasparov — one of the greatest chess players who ever lived — in a six-game match. At the time, many observers interpreted this as evidence that AI had matched human intelligence. What was actually happening was both simpler and more remarkable: a machine was exploring the space of possible chess positions faster and more systematically than any human could, using search algorithms refined over decades, guided by an evaluation function tuned by grandmasters.

Chess has roughly 10^43 legal board positions. A human cannot examine them all — not in a lifetime, not in a million lifetimes. Deep Blue could not examine them all either. What it could do was explore the most promising subset of that space, pruning dead ends early, focusing computational effort on positions that were likely to matter, and using pattern-based evaluation to estimate the worth of positions it never fully explored.

This is the insight that unifies every problem in this chapter: intelligent search is not about finding the answer in an infinite space — it is about finding it in the right part of that space, quickly enough to matter.

Search underlies capabilities we now take for granted: the turn-by-turn directions on your phone, the move recommendations in a chess app, the route a robotic warehouse system plans to retrieve an order, the schedule an airline constructs to minimize delays. In each case, the problem is formulated as a search through a space of possible states, and the intelligence lies in navigating that space efficiently.

“Every intelligent agent is, at its core, a search process. The diversity of AI problems is the diversity of state spaces. The power of AI algorithms is the diversity of strategies for searching them.”

2.2 Learning Objectives

After completing this chapter, you will be able to:

Formulate any problem as a search problem by defining states, actions, transition models, and goal tests.
Implement and compare uninformed search strategies — BFS, DFS, UCS, and IDS — and predict their performance characteristics.
Explain why heuristics transform search and describe the properties that make a heuristic admissible.
Apply A* search and explain why an admissible heuristic guarantees optimal solutions.
Describe adversarial search and explain how minimax captures optimal two-player reasoning.
Explain alpha-beta pruning and quantify the speedup it provides over minimax.
Describe Monte Carlo Tree Search and explain why it excels in games where evaluation functions are hard to design.
Apply local search methods to optimization problems where the path does not matter, only the final state.
Build the IAAIS Search Engine — a general problem-solving component that navigates explicit state spaces.

2.3 Key Terminology

Term	Plain-Language Definition
State	A complete description of the world at a given moment — everything the agent needs to know to choose its next action. The state space is the set of all possible states.
Initial State	The state from which the agent begins its search.
Goal Test	A function that determines whether a given state is a solution to the problem. Some problems have a single goal state; others have many or a goal defined by a property.
Action	A choice available to the agent in a given state. Each action transforms one state into another.
Transition Model	A description of what state results from taking an action in a given state. Together with the initial state and actions, it defines the state space graph.
Path Cost	The cumulative cost of a sequence of actions. Search algorithms that optimize path cost are seeking the least-cost solution.
Search Tree	The tree generated by expanding states from the initial state, with each node representing a state and each edge representing an action.
Frontier	The set of nodes that have been generated but not yet expanded — the boundary between explored and unexplored territory.
Uninformed Search	Search strategies that use only the information available in the problem definition — not domain-specific knowledge about which directions are promising. Also called blind search.
Informed Search	Search strategies that use domain-specific knowledge (heuristics) to guide the search toward the goal more efficiently. Also called heuristic search.
Heuristic (h(n))	A function that estimates the cost from node n to the goal. The quality of the heuristic determines the efficiency of informed search.
Admissible Heuristic	A heuristic that never overestimates the true cost to the goal. Admissibility is the key property that guarantees A* finds optimal solutions.
Consistent Heuristic	A heuristic satisfying the triangle inequality: h(n) ≤ c(n, a, n’) + h(n’) for every action a from n to n’. Consistency implies admissibility and guarantees A* never expands a node twice.
BFS	Breadth-First Search. Explores all nodes at depth d before any nodes at depth d+1. Guaranteed to find the shallowest solution. Optimal for unit-cost actions.
DFS	Depth-First Search. Explores as deep as possible before backtracking. Memory-efficient but not guaranteed to find optimal solutions and may run forever on infinite state spaces.
UCS	Uniform-Cost Search. Expands the lowest-cost node first. Optimal and complete for any non-negative action costs. Equivalent to Dijkstra’s algorithm.
IDS	Iterative Deepening Search. Combines DFS’s memory efficiency with BFS’s completeness by repeatedly running DFS to increasing depth limits. Optimal with unit costs.
A*	Informed search using evaluation function f(n) = g(n) + h(n): actual cost to reach n plus heuristic estimate to goal. Optimal when h is admissible; typically the most efficient uninformed-to-informed tradeoff.
Minimax	An algorithm for two-player zero-sum games. MAX player chooses actions maximizing value; MIN player chooses actions minimizing it. Explores the game tree to compute optimal strategies.
Alpha-Beta Pruning	An optimization of minimax that eliminates branches that cannot influence the final decision, often reducing the search space from O(b^d) to O(b^{d/2}).
MCTS	Monte Carlo Tree Search. Builds a search tree by running random simulations (rollouts) to estimate state values. Excels in domains with large branching factors or where evaluation functions are hard to design.
Local Search	Search methods that explore the current state’s neighborhood, keeping only the current state in memory. Suited to optimization problems where the path doesn’t matter — only the destination.
Hill Climbing	A local search strategy that always moves to the highest-value neighboring state. Fast but susceptible to local optima, ridges, and plateaus.
Simulated Annealing	A probabilistic local search that occasionally accepts worse states, with acceptance probability decreasing over time (like cooling metal). Can escape local optima that trap hill climbing.

2.4 Section 1 — Formulating Problems as Search

Before any search algorithm can run, the problem must be expressed in the language of search. This formulation step is where much of the intelligence lies — a well-chosen state representation can make a problem tractable; a poor one can make it intractable.

A search problem has five components. The state space is the set of all configurations the world can be in. In a navigation problem, each state is a (city, time) pair; in a chess problem, each state is a complete board position. The initial state is where the agent starts. The actions available in each state define the edges of the state space graph. The transition model specifies what state results from each action. The goal test determines when a solution has been found.

The path cost assigns a numeric cost to sequences of actions, allowing us to distinguish not just solutions from non-solutions, but better solutions from worse ones. In navigation, path cost might be distance or time; in a scheduling problem, it might be total delay or resource consumption.

Consider the classic 8-puzzle: eight tiles on a 3×3 grid, one space empty, goal to arrange tiles in numerical order. A natural state representation is the complete configuration of all nine positions. This gives 9! = 362,880 possible states — a large but searchable space. A poor representation — for instance, tracking only the empty cell’s position — loses the information needed to reason about which moves are available.

The choice of representation also determines the branching factor — how many actions are available in each state — and the depth at which solutions are found. These determine how feasible search will be. A branching factor of 35 (typical for chess) at depth 10 gives 35^10 ≈ 2.8 × 10^15 nodes — far too many to explore exhaustively. Efficient search algorithms are those that explore a small fraction of this space while still finding optimal or near-optimal solutions.

2.5 Section 2 — Uninformed Search: Navigating Without a Map

Uninformed search algorithms explore the state space systematically without any domain-specific knowledge about which directions are promising. They are guaranteed to find solutions (when solutions exist) but may take longer than informed methods.

2.5.1 The Fundamental Tradeoff: Memory vs. Optimality

The four classic uninformed search strategies each make a different tradeoff along this axis.

Breadth-First Search (BFS) explores all nodes at depth 1 before depth 2, all at depth 2 before depth 3, and so on. It uses a FIFO queue as the frontier. BFS is complete — it always finds a solution if one exists — and finds the shallowest solution, making it optimal when all actions have equal cost. Its weakness is memory: it must store all frontier nodes, which grows exponentially with depth. A tree with branching factor 10 at depth 12 requires storing 10^12 nodes.

Depth-First Search (DFS) always expands the deepest node in the frontier, using a LIFO stack (or recursion). It is dramatically more memory-efficient than BFS — it only needs to remember the current path from root to the deepest node. But DFS is not complete on infinite state spaces (it may follow an infinite path forever) and is not optimal (it may find a deep, expensive solution before a shallow, cheap one).

Uniform-Cost Search (UCS) expands the lowest-cost node first, using a priority queue ordered by path cost. This is the key generalization: UCS is optimal for any non-negative action costs, not just unit costs. When all actions cost 1, UCS reduces to BFS. UCS is essentially Dijkstra’s algorithm applied to AI search.

Iterative Deepening Search (IDS) runs DFS repeatedly with increasing depth limits: first allowing depth 1, then depth 2, and so on until a solution is found. This seems wasteful — it re-explores the shallower nodes on every iteration — but the analysis shows the overhead is small. Most of the work happens at the deepest level, and the total number of node generations is only about b/(b-1) times that of BFS. IDS combines DFS’s linear memory use with BFS’s completeness and optimality (for unit costs).

Algorithm	Complete?	Optimal?	Time	Space
BFS	Yes	Yes (unit cost)	O(b^d)	O(b^d)
DFS	No	No	O(b^m)	O(bm)
UCS	Yes	Yes (any cost)	O(b^{1+C*/ε})	O(b^{1+C*/ε})
IDS	Yes	Yes (unit cost)	O(b^d)	O(bd)

b = branching factor, d = solution depth, m = maximum depth, C = optimal cost, ε = minimum action cost*

The practical takeaway: IDS is usually the best uninformed algorithm when you need both memory efficiency and optimality. UCS is the right choice when action costs vary significantly.

2.6 Section 3 — Informed Search: The Power of Heuristics

Uninformed search is principled but often impractical for large problems. The key to making search tractable is domain knowledge — specifically, a heuristic function h(n) that estimates the remaining cost from node n to the nearest goal.

2.6.1 What Makes a Good Heuristic?

A heuristic is admissible if it never overestimates the true cost to the goal — it is always optimistic. For the 8-puzzle, the number of misplaced tiles is admissible: you need at least one move per misplaced tile, so this is a lower bound on the remaining cost. The Manhattan distance (sum of horizontal and vertical distances each tile must travel) is also admissible and is typically a better heuristic — it is a tighter lower bound.

A heuristic is consistent if for every node n and its successor n’ via action a: h(n) ≤ c(n, a, n’) + h(n’). This is the triangle inequality: the estimated cost at n should be no more than the actual step cost plus the estimated cost at n’. Consistency implies admissibility and has an important consequence: A* with a consistent heuristic never expands the same node twice.

How do we design admissible heuristics? The most reliable method is the relaxed problem: remove one or more constraints from the original problem and compute the exact cost in the relaxed version. The exact solution to a relaxed problem is always an admissible heuristic for the original. The 8-puzzle’s Manhattan distance is the exact solution to the relaxed problem where tiles can slide through each other.

2.6.2 A*: Optimal Informed Search

A* combines the actual path cost g(n) with the heuristic estimate h(n) into an evaluation function f(n) = g(n) + h(n). It always expands the node with the lowest f(n) — the node that appears to be on the cheapest path to the goal.

With an admissible heuristic, A* is optimal: it never expands a node with f(n) > the optimal solution cost, so when it reaches the goal, it has found the cheapest path. With a consistent heuristic, its efficiency is as good as any optimal search algorithm using the same heuristic.

import heapq

def astar(start, goal, neighbors_fn, h):
    """
    A* search — finds the optimal path from start to goal.
    neighbors_fn(node) → list of (neighbor, step_cost)
    h(node) → admissible heuristic estimate to goal
    """
    # Priority queue: (f=g+h, g, node, path)
    frontier = [(h(start), 0, start, [start])]
    explored = {}   # node → best g seen

    while frontier:
        f, g, node, path = heapq.heappop(frontier)

        if node == goal:
            return path, g          # Optimal path found!

        if node in explored and explored[node] <= g:
            continue                # Already found a better path here
        explored[node] = g

        for neighbor, step_cost in neighbors_fn(node):
            new_g    = g + step_cost
            new_f    = new_g + h(neighbor)
            new_path = path + [neighbor]
            heapq.heappush(frontier, (new_f, new_g, neighbor, new_path))

    return None, float('inf')       # No path found

Expected output (Romanian cities example, Arad to Bucharest):

Calling astar('Arad', 'Bucharest', romania_graph, straight_line_distance)

Expansion order: Arad → Sibiu → Rimnicu Vilcea → Pitesti → Bucharest
Path:  Arad → Sibiu → Rimnicu Vilcea → Pitesti → Bucharest
Cost:  418 km  ✓ (optimal — same as shortest path)

Without heuristic (UCS), expansion order:
Arad → Zerind → Timisoara → Lugoj → Mehadia → Dobreta → ...
(Expands 11 nodes before finding Bucharest)

With Manhattan heuristic (A*): expands only 5 nodes
The heuristic eliminated 55% of node expansions.

The difference between A* and UCS illustrates the power of heuristics: they focus the search on the part of the state space most likely to contain the optimal solution.

2.7 Section 4 — Adversarial Search: Playing Against an Opponent

The search problems we have examined so far are single-agent: one agent, one goal, no opposition. Games introduce a second agent with conflicting objectives. The framework for reasoning about this is adversarial search.

2.7.1 Minimax: Optimal Reasoning in Zero-Sum Games

Consider a two-player, zero-sum, perfect-information game like chess or tic-tac-toe. One player (MAX) wants to maximize the final outcome value; the other (MIN) wants to minimize it. If MAX plays optimally, it chooses the action leading to the state with the highest minimax value. If MIN plays optimally, it chooses the action leading to the state with the lowest minimax value.

The minimax algorithm computes these values by recursively expanding the game tree: - At MAX nodes: return the maximum value of the children - At MIN nodes: return the minimum value of the children - At leaf nodes (terminal states or depth limit): return the utility or evaluation function value

Minimax captures a fundamental insight: the optimal move for MAX is the one that is best assuming MIN also plays optimally. It is the conservative choice — MAX assumes the worst opponent.

The problem with pure minimax is computational: for a game with branching factor b and search depth d, it explores O(b^d) nodes. For chess with b ≈ 35 and d ≈ 50 for a complete game, this is astronomically large.

2.7.2 Alpha-Beta Pruning: Cutting Without Missing Anything

Alpha-beta pruning reduces minimax’s search space by eliminating branches that cannot affect the final decision. Two values are maintained during search:

α (alpha): The best value MAX has found so far on the current path (MAX’s lower bound)
β (beta): The best value MIN has found so far on the current path (MIN’s upper bound)

When a MIN node’s value drops below α, MAX would never choose the path leading to this MIN node — so we can prune it. When a MAX node’s value exceeds β, MIN would never allow the path leading here — so we can prune it.

With perfect move ordering (best moves examined first), alpha-beta reduces the effective branching factor from b to approximately √b, doubling the searchable depth for the same computation. This is why Deep Blue could search to depth 12-14 even in the mid-1990s.

2.7.3 Monte Carlo Tree Search: When You Cannot Evaluate Positions

Minimax requires an evaluation function — a way to assign values to non-terminal positions. For chess, decades of grandmaster knowledge can be encoded. For Go, the game’s complexity made good evaluation functions essentially impossible to design until deep learning.

Monte Carlo Tree Search (MCTS) sidesteps the need for evaluation functions by estimating position values through random simulation. From any position, simulate many random games to completion (rollouts) and use the win rate across simulations as the position value estimate.

MCTS builds its search tree asymmetrically — expanding nodes that are both promising (high win rate) and under-explored (few simulations). The UCB1 formula balances this exploitation-exploration tradeoff:

UCB1(n) = Q(n)/N(n) + C × √(ln N(parent) / N(n))

where Q(n)/N(n) is the win rate and the second term rewards under-explored nodes.

MCTS enabled the first Go programs to reach amateur-level play, and formed the backbone of AlphaGo before deep learning provided accurate position evaluation. It remains valuable whenever good evaluation functions are unavailable.

2.8 Section 5 — Local Search: When the Path Doesn’t Matter

For many practical problems, we care about the destination, not the journey. Finding the best configuration of 1,000 hospital staff shifts, the optimal layout of components on a circuit board, or the weights of a neural network — in each case, we want the best final state and the sequence of moves to get there is irrelevant.

Local search algorithms explore the neighborhood of the current state, keeping only the current state in memory. They scale to problems where systematic search is computationally infeasible.

Hill climbing always moves to the highest-value neighbor. It is fast and memory-efficient, but gets stuck at local optima — states better than all neighbors but not the global optimum. It also struggles with plateaus (regions of equal value) and ridges (narrow paths where the algorithm must move sideways before it can continue climbing).

Simulated annealing introduces a controlled randomness inspired by the physical process of slowly cooling a metal to its lowest-energy state. The algorithm occasionally accepts worse states, with acceptance probability:

P(accept worse state) = exp(−ΔE / T)

where ΔE is how much worse the new state is and T is the current “temperature.” At high temperature, almost any move is accepted. As temperature decreases, only moves that are better (or slightly worse) are accepted. Eventually the algorithm settles into a configuration near the global optimum. Theoretical guarantees exist: if temperature decreases slowly enough, simulated annealing finds the global optimum with probability approaching 1.

Genetic algorithms maintain a population of candidate solutions and evolve them through selection, crossover (combining parts of two solutions), and mutation. They are particularly effective for complex optimization problems with many interacting variables.

2.9 Section 6 — Search in the Real World

2.9.2 Game Playing

Modern game-playing AI has moved beyond pure search. AlphaZero (Chapter 11) replaced hand-crafted evaluation functions with deep neural networks trained by self-play, but search remains central — the neural network guides MCTS, and MCTS produces the training data that improves the neural network. Search and learning reinforce each other.

2.9.3 Planning in Robotics

A robot navigating a warehouse must plan paths that avoid dynamic obstacles (moving humans and forklifts), minimize travel time, and respect battery constraints. The state space includes the robot’s position, orientation, remaining battery, and the positions of known obstacles — a high-dimensional space where exact A* may be too slow. Rapidly-exploring Random Trees (RRT) and Probabilistic Roadmaps (PRM) sample the state space randomly to build approximate search structures that scale to high-dimensional robot planning problems.

2.10 Section 7 — IAAIS Integration: The Search Engine

This week you add the IAAIS Search Engine — a general problem-solving component that finds paths and solutions in any problem expressible as a search problem.

The Search Engine provides a uniform interface: give it a start state, a goal test, and an action function, and it finds the optimal (or near-optimal) path. In later chapters, this component is called by the Planner to find action sequences, by the Decision Agent to reason about future states, and by the Expert Module to chain inference rules.

Chapter	Module	Capability
Ch 2	Search Engine	Finds paths through explicit state spaces

Design decisions for this week: - Which search algorithm is right for your domain’s state space size? - What is the branching factor? What is the typical solution depth? - If informed search: what admissible heuristic captures domain knowledge? - If adversarial: do you need minimax (deterministic) or MCTS (probabilistic evaluation)?

2.11 Hands-On Exploration: Solving the 8-Puzzle with A*

2.11.1 The Activity

Open hands_on_ch2.ipynb from the course repository.

Part 1 — Problem Formulation (10 minutes): Implement the state representation, action generator, and goal test for the 8-puzzle. Before running any search, count the number of reachable states from the initial configuration. Is this number manageable with BFS?

Part 2 — Algorithm Comparison (20 minutes): Run BFS, DFS, IDS, and A* (with both the misplaced-tiles and Manhattan-distance heuristics) on the same puzzle instance. Record: number of nodes expanded, memory used, time taken, solution cost. Plot these results in a comparison table.

Part 3 — Heuristic Quality (15 minutes): The number of nodes A* expands is determined by the heuristic’s quality. For 20 random puzzle instances, compare the nodes expanded by A* with (a) h=0 (reduces to UCS), (b) misplaced tiles, (c) Manhattan distance, (d) linear conflict (Manhattan distance plus a correction for tiles that block each other on the same row/column). What pattern do you observe?

2.11.2 Reflection Questions

DFS found a solution for the 8-puzzle but it was far from optimal. Describe a real application where you would deliberately choose DFS despite its suboptimality — and one where this would be unacceptable.
A* with h=0 is equivalent to UCS. A* with a perfect heuristic h=h* expands only the nodes on the optimal path. Your Manhattan distance heuristic is somewhere between these extremes. How would you measure how “good” your heuristic is relative to these bounds?
The 15-puzzle (4×4 grid) has 10^13 reachable states. BFS is infeasible. A* with Manhattan distance may still be feasible. At what point does even A* become intractable, and what approaches exist beyond A* for very large state spaces?
For your IAAIS Search Engine, describe a domain-specific search problem. What is the state? What are the actions? What makes a good heuristic for this problem?

2.12 Case Study: Google Maps and the Engineering of Route Planning

2.12.1 The Problem at Scale

In 2023, Google Maps processed approximately 1 billion navigation requests per day across road networks with hundreds of millions of edges. A naive A* implementation on a graph this large would take minutes per query. Google Maps returns answers in milliseconds.

The gap between textbook A* and production route planning is closed by a combination of algorithmic techniques and massive precomputation.

Contraction hierarchies precompute a hierarchical structure that identifies “important” nodes — highway junctions, major interchanges — that appear on many shortest paths. Queries then search upward through the hierarchy, dramatically reducing the number of nodes examined. Preprocessing takes hours; queries take milliseconds.

Landmark-based heuristics (ALT) precompute exact distances from a set of carefully chosen landmark nodes to all other nodes. These precomputed distances provide tight admissible lower bounds — better than straight-line distance — dramatically reducing the nodes A* must examine.

Multi-criteria search handles the fact that “best route” means different things to different users: shortest distance, fastest time, most scenic, least tolls, most accessible for wheelchairs. Each criterion produces a different search problem with different action costs.

2.12.2 The Ethical Dimension

Route planning AI makes consequential choices that aggregate into large social effects. When Google Maps routes millions of drivers through a neighborhood to avoid highway congestion, that neighborhood experiences increased traffic, noise, and pedestrian risk. The people experiencing those impacts did not participate in the system’s optimization.

Navigation AI optimizes for individual travel efficiency. Its externalities — neighborhood impact, emissions from suboptimal routes at the fleet level, effects on public transit ridership — are not in its objective function. This is a concrete instance of the optimization-versus-values gap that appears throughout AI: the system maximizes what it is told to maximize, not what actually matters.

2.13 Chapter Summary

We began this chapter with Deep Blue defeating Kasparov — a victory of systematic search guided by domain knowledge over human intuition, at a scale human computation cannot approach.

Problem formulation translated intuitive descriptions into the formal language search algorithms require: state space, initial state, actions, transition model, goal test, and path cost. This translation is not mechanical — a well-chosen representation can make a problem tractable; a poor one can make it intractable.

Uninformed search explored the fundamental algorithms: BFS for shallow solutions with memory to spare, DFS for memory-constrained settings where optimality is unnecessary, UCS for varying action costs, and IDS for the best balance when both memory efficiency and optimality matter.

Informed search showed how heuristics transform search. A* with an admissible heuristic guarantees optimal solutions while expanding only the nodes that could plausibly be on the optimal path. Admissibility and consistency are not just theoretical properties — they are engineering requirements for any application where wrong answers are costly.

Adversarial search extended the framework to two-player games: minimax captures optimal reasoning against a rational opponent; alpha-beta pruning eliminates branches that cannot affect the outcome; MCTS provides value estimates through simulation when evaluation functions cannot be designed. These algorithms underlie every serious game-playing program.

Local search addressed the class of problems where the path does not matter — only the final configuration — providing practical methods for optimization problems too large for systematic search.

In Chapter 3, we ask what happens when search is not enough — when the agent needs not just to find a path but to reason about a complex, uncertain, and symbolic world. Knowledge representation is the foundation of that reasoning.

2.14 Discussion Questions

The curse of dimensionality: A robot planning its path in 2D space has a manageable search problem. A robot arm with 7 joints has a 7-dimensional configuration space. How does search complexity scale with dimensionality, and what strategies address this?
Heuristic design: You are designing A* for a hospital scheduling system. The state is a partial assignment of patients to rooms; the goal is a complete valid assignment. Propose an admissible heuristic and prove its admissibility.
Adversarial search ethics: Alpha-beta minimax assumes the opponent plays optimally. Human opponents don’t. When a chess engine plays against a beginner, should it play its minimax-optimal move or adapt to the opponent’s level? What ethical considerations apply?
Local optima in practice: Neural network training is a local search problem — gradient descent is hill climbing in weight space. What mechanisms have been developed to escape local optima in neural network training? How do these connect to simulated annealing?
Route planning and equity: Google Maps optimizes individual travel efficiency. Propose a metric for equitable route planning that accounts for neighborhood impacts. What data would you need? What tradeoffs would it impose on individual users?
Completeness vs. optimality: Design a scenario where you would deliberately choose an incomplete search algorithm. What properties of the problem would make this choice reasonable?
MCTS and simulation quality: MCTS estimates position values through random rollouts. The quality of the estimate depends on the quality of the rollout policy. How does using a better rollout policy change the tradeoff between simulation count and exploration depth?
Your IAAIS Search Engine: Identify a problem in your IAAIS domain that can be formulated as search. Define the state space, actions, goal test, and path cost. Estimate the branching factor and solution depth, and choose the most appropriate search algorithm with justification.

2.15 Further Reading

2.15.1 Foundational Texts

Russell, S., & Norvig, P. (2020). Artificial Intelligence: A Modern Approach (4th ed.). Pearson. Chapters 3–5 are the authoritative treatment of search in AI.

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. The original A* paper.

2.15.2 Game Playing

Shannon, C. E. (1950). Programming a computer for playing chess. Philosophical Magazine, 41(314), 256–275. The paper that started computer game playing — still readable and insightful.

Silver, D., et al. (2018). A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play. Science, 362(6419), 1140–1144. AlphaZero — search guided by learned evaluation.

2.15.3 Planning and Optimization

Goldberg, A. V., & Harrelson, C. (2005). Computing the shortest path: A* search meets graph theory. Proceedings of SODA 2005. ALT heuristics for road network routing.

Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220(4598), 671–680. The original simulated annealing paper.

— End of Chapter 2 —