Searching Technique

Introduction to Searching Techniques

Searching is a fundamental concept in Artificial Intelligence (AI) and Computer Science. It deals with finding a sequence of actions that leads from an initial state to a goal state.

In AI, search techniques are used to:

• Solve problems where the solution path is not known in advance
• Explore large problem spaces efficiently
• Make decisions in games and real-world applications

Key Components of a Search Problem

Component	Description
State	Representation of the problem at a given time
Initial State	Starting point of the problem
Goal State	Desired solution state
Actions	Possible moves from one state to another
Path Cost	Cost to move from one state to another

Problem Solving by Searching

Problem solving by searching means:

• Defining a problem clearly
• Representing it as a state space
• Applying a suitable search algorithm

Steps in Problem Solving

• Problem formulation
• State space representation
• Selection of search strategy
• Search execution
• Solution generation

State Space Representation (Diagram)

        Start
          |
      -----------
      |         |
    State A   State B
      |         |
   State C   Goal State

Searching for Solutions

A solution is a path from the initial state to the goal state.

Types of Solutions

Type	Meaning
Optimal	Lowest cost solution
Sub-optimal	Higher cost but acceptable
Complete	Guarantees a solution if one exists

Uninformed (Blind) Searching Techniques

These techniques do not use any domain knowledge. They only know:

• Initial state
• Actions
• Goal test

Common Uninformed Search Algorithms

Algorithm	Strategy	Complete	Optimal
Breadth First Search (BFS)	Level-wise	Yes	Yes
Depth First Search (DFS)	Depth-wise	No	No
Depth Limited Search	Fixed depth	Sometimes	No
Iterative Deepening DFS	BFS + DFS	Yes	Yes
Uniform Cost Search	Lowest path cost	Yes	Yes

BFS Diagram

       A
     /   \
    B     C
   / \   / \
  D   E F   G

Informed Searching Techniques

Informed search uses heuristic functions to estimate the cost to reach the goal.

Heuristic Function (h(n))

• Estimates distance from current node to goal

Informed Search Algorithms

Algorithm	Heuristic Used	Optimal
Best First Search	h(n)	No
A* Search	g(n) + h(n)	Yes
Greedy Best First	h(n) only	No

A Search Formula*

f(n) = g(n) + h(n)

Local Search Algorithms

Local search algorithms focus on improving the current state without keeping the full path.

Characteristics

• Uses one or few states
• Memory efficient
• Suitable for optimization problems

Common Local Search Algorithms

Algorithm	Description
Hill Climbing	Moves to better neighboring state
Simulated Annealing	Allows bad moves initially
Genetic Algorithm	Uses selection, crossover, mutation

Hill Climbing Diagram

   /
  /  Local Maximum
 /____

Adversarial Search Methods

Used when the environment has opponents with conflicting goals.

Examples

• Chess
• Tic-Tac-Toe
• Checkers

Minimax Algorithm

• One player tries to maximize gain
• Opponent tries to minimize gain

Minimax Tree

        MAX
       /   \
     MIN   MIN
    /  \   /  \
   3    5  2    9

Search Techniques Used in Games

Games are:

• Deterministic
• Turn-based
• Zero-sum

Techniques Used

Technique	Use
Minimax	Optimal play
Alpha-Beta Pruning	Efficiency
Heuristic Evaluation	Game state estimation

Alpha-Beta Pruning

Alpha-Beta pruning is an optimization of Minimax.

Key Idea

• Do not explore branches that cannot affect final decision

Alpha and Beta Values

Term	Meaning
Alpha (α)	Best value for MAX so far
Beta (β)	Best value for MIN so far

Alpha-Beta Diagram

        MAX
       /   \
     MIN   MIN
    /  \    X
   3    5  (Pruned)

Advantages

• Reduces time complexity
• Allows deeper game tree search

Summary Table

Category	Examples
Uninformed Search	BFS, DFS, UCS
Informed Search	A*, Best First
Local Search	Hill Climbing, GA
Game Search	Minimax, Alpha-Beta

Exam-Oriented Tips (MCA)

• Always define heuristic clearly
• Draw state space diagrams
• Compare BFS vs DFS
• Explain Alpha-Beta with example
• Use tables for advantages & disadvantages

---

End of Notes