AI Cannot Exist Without Searching + Hill Climbing on 8-Puzzle

Part 1: Justify That AI Cannot Exist Without Searching (4 marks)

Search is the process of systematically exploring a state space to find a sequence of actions leading from an initial state to a goal state.

Justification:

1. Problem formulation is universal in AI. Almost every AI problem is formulated as an initial state, a set of actions, a transition model, a goal test, and a path cost. Solving it means finding a path, which is search.

2. Intelligence requires choosing among alternatives. An intelligent agent faces many possible states and actions. Selecting the right action toward a goal inherently requires exploring alternatives, that is, searching.

3. Without search only two options remain, both non-intelligent:

   • Acting randomly (not rational), or
   • Using a fixed hardcoded response (not general, not adaptive).

4. All major AI subfields rely on search:

Conclusion: Whether uninformed (BFS, DFS), informed (A*, Hill Climbing), or adversarial (Minimax), every intelligent behavior reduces to navigating a problem space. Hence AI cannot exist without searching.

Part 2: 8-Puzzle Using Hill Climbing (6 marks)

Given Data

Initial State

1 2 4
5 _ 7
3 6 8

Goal State

1 4 7
2 5 8
3 6 _

Heuristic: number of misplaced tiles $h(n)$ (blank excluded). Hill Climbing moves to a neighbor with lower $h$.

Goal Positions (row, col)

Step 0: Evaluate Initial State

1 2 4
5 _ 7
3 6 8

$$h(\text{initial}) = 5$$

Step 1: Generate Successors (blank at (1,1))

UP (swap blank with 2):

1 _ 4
5 2 7
3 6 8

Misplaced: 4, 5, 2, 7, 8 → $h = 5$

DOWN (swap blank with 6):

1 2 4
5 6 7
3 _ 8

Misplaced: 2, 4, 5, 6, 7, 8 → $h = 6$

LEFT (swap blank with 5):

1 2 4
_ 5 7
3 6 8

Misplaced: 2, 4, 7, 8 → $h = 4$ ✓ (5 now correct at (1,1))

RIGHT (swap blank with 7):

1 2 4
5 7 _
3 6 8

Misplaced: 2, 4, 5, 7, 8 → $h = 5$

Best successor: LEFT, with $h = 4 < 5$. Move there.

Step 2: Current State $h = 4$ (blank at (1,0))

1 2 4
_ 5 7
3 6 8

Successors:

UP (swap with 1):

_ 2 4
1 5 7
3 6 8

Misplaced: 1, 2, 4, 7, 8 → $h = 5$

DOWN (swap with 3):

1 2 4
3 5 7
_ 6 8

Misplaced: 2, 4, 3, 7, 8 → $h = 5$

RIGHT (swap with 5, returns toward previous):

1 2 4
5 _ 7
3 6 8

$h = 5$ (the initial state)

Best successor $h = 5$, but current $h = 4$.

Since no neighbor improves on $h = 4$ (all are $\geq 5$), Hill Climbing halts here.

Result

Hill Climbing gets stuck at:

1 2 4
_ 5 7
3 6 8       h = 4

This is a local minimum (also a plateau/ridge situation): every move increases $h$. Therefore plain (steepest-ascent) Hill Climbing fails to reach the goal for this puzzle.

Why it fails: Hill Climbing is greedy and has no backtracking. When it reaches a state whose neighbors are all worse, it stops even though the global goal ($h=0$) is not reached. To escape, one would use techniques such as:

• Random-restart Hill Climbing
• Simulated Annealing
• Stochastic / sideways moves
• Or a complete search like A* with Manhattan distance.

Final answer: Using number-of-misplaced-tiles heuristic, Hill Climbing improves from $h=5$ to $h=4$ then gets stuck at a local minimum and cannot reach the goal state.

Expert System: Definition and Architecture

Definition

An Expert System is an AI-based computer program that simulates the knowledge and reasoning ability of a human expert in a specific domain to solve complex problems and provide expert-level advice or decisions.

Note: Standard AI/Knowledge Engineering content is used here as no specific curriculum notes were found.

An expert system captures the knowledge of human specialists and makes it available to non-experts, enabling them to solve problems that would otherwise require human expertise (e.g., medical diagnosis, fault detection, financial planning).

Architecture of an Expert System

The major components of an expert system are:

+---------------------------+
|      User Interface       |
+---------------------------+
           |
+---------------------------+
|     Inference Engine      |
+---------------------------+
     |              |
+----------+   +----------+
| Knowledge|   | Working  |
|   Base   |   | Memory   |
+----------+   +----------+
     |
+----------+
|Knowledge |
|Acquisition|
|  Module  |
+----------+
     |
[Domain Expert / Knowledge Engineer]

1. Knowledge Base

• Stores domain-specific knowledge in the form of:
  • IF-THEN rules (production rules)
  • Facts, heuristics, and procedures
• It is the core of the expert system
• Example: IF fever > 102 AND cough = yes THEN diagnose = flu

2. Inference Engine

• The brain of the expert system
• Applies logical rules to the knowledge base to derive conclusions
• Uses two main reasoning strategies:
  • Forward Chaining: Starts from known facts and derives conclusions (data-driven)
  • Backward Chaining: Starts from a goal and works backward to find supporting facts (goal-driven)

3. Working Memory (Database)

• Stores temporary facts and intermediate results during a consultation session
• Updated dynamically as the inference engine processes rules

4. User Interface

• Allows the user to interact with the expert system
• Accepts queries and displays results/recommendations in a user-friendly manner

5. Explanation Module (Justifier)

• Explains how a conclusion was reached
• Answers questions like "Why?" and "How?" to build user trust

6. Knowledge Acquisition Module

• Facilitates the process of adding, updating, or modifying knowledge in the knowledge base
• Acts as an interface between the domain expert and the knowledge base

Summary Table

Advantages

• Available 24/7, consistent, and does not forget
• Can handle complex, domain-specific problems
• Useful where human experts are scarce

Alpha-Beta Pruning

Purpose

The purpose of alpha-beta pruning is to reduce the number of nodes evaluated in the minimax search tree without affecting the final result. It allows the minimax algorithm to search deeper in the same amount of time by eliminating (pruning) branches that cannot possibly influence the final decision.

Note: Reference notes were not available for this topic; the following is based on standard AI curriculum material consistent with TU BSc CSIT syllabus.

Background

The Minimax algorithm explores the entire game tree to find the optimal move, but this is computationally expensive. For a game tree with branching factor b and depth d, minimax evaluates O(b^d) nodes.

Alpha-beta pruning reduces this to approximately O(b^(d/2)) in the best case, effectively doubling the searchable depth.

Key Concepts

How It Works

1. The algorithm performs a standard depth-first minimax search.
2. At each node, it maintains the α and β values.
3. Pruning occurs when:
   • At a MIN node: if the current value becomes ≤ α, prune remaining children (Alpha cutoff).
   • At a MAX node: if the current value becomes ≥ β, prune remaining children (Beta cutoff).

Pruning Conditions

At MAX node:  if value >= β  → PRUNE (Beta cutoff)
At MIN node:  if value <= α  → PRUNE (Alpha cutoff)

Example

Consider the following minimax tree:

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

• MAX evaluates left MIN node → gets min(3,5) = 3, so α = 3
• MAX evaluates right MIN node → sees value 2
  • Since 2 < α (3), the right subtree value cannot exceed 3
  • The remaining child (9) is pruned -- no need to evaluate it
• Final answer: MAX chooses 3

Advantages

1. Efficiency: Reduces time complexity from O(b^d) to O(b^(d/2)).
2. Same result: Always produces the same optimal move as full minimax.
3. Deeper search: Allows AI to look further ahead within the same time limit.
4. Practical use: Widely used in game-playing AI (chess, checkers, tic-tac-toe).

Summary

Alpha-beta pruning is an optimization technique for the minimax algorithm that prunes branches which cannot affect the outcome, using two boundary values α and β. It makes game-tree search significantly faster while guaranteeing the same optimal decision as the full minimax search.