Uninformed Search

1. Foundations of Search in AI

Search has historically been a central demonstration of intelligence, particularly through game playing

• States: These are descriptions of the system under consideration

• Goal: The agent must move from an initial configuration to a goal state by following specific rules

• Game Types: These include single-player puzzles (e.g., 8-puzzle, Sudoku) and two-player adversarial games (e.g., Chess, Tic Tac Toe)

2. Problem Instance: The n2−1 (8-Puzzle) Problem

A classic example is the 8-puzzle, consisting of a 3×3 board with one blank tile and eight numbered tiles

• Objective: Reach a target board configuration from a random start state using valid moves (Up, Down, Left, Right)

• Complexity: Finding an optimal solution is NP-hard, meaning brute-force methods are often the starting point before applying intelligent heuristics

3. Search Mechanics and Evaluation

To navigate a search tree, two primary functions are required:

• MoveGen(state): Returns the set of possible candidate moves or (state, cost) pairs for a given configuration

• GoalTest(state): Returns True if the agent has reached the goal

Strategies are evaluated based on four parameters:

• Completeness: Does it always find a solution if one exists?

• Time Complexity: How many nodes are generated?

• Space Complexity: How many nodes are stored in memory?

• Optimality: Does it always find the least-cost solution?

4. Handling Repeated States

To prevent infinite loops or redundant processing, agents maintain two lists:

• OPEN list: Contains candidates waiting to be explored

• CLOSED list: Contains states that have already been explored

. A new candidate is only added to the OPEN list if it is not already in either list. Varied implementations of the OPEN list define different search strategies

• Iterative Deepening: This strategy provides the best of both worlds, combining the space efficiency of DFS with the optimality of BFS by performing DFS with an increasingly large depth limit

• Uniform-Cost Search: Essential when candidate costs are variable; it uses a heap to always explore the least-cost successor first

• Bidirectional Search: Speeds up convergence by running two simultaneous searches: one from Start → Goal and another from Goal → Start, meeting in the middle