BSc CSIT (TU) Science Artificial Intelligence (BSc CSIT, CSC261) Question Paper 2077 Nepal

Adversarial Search

Adversarial search is a search technique used in competitive, multi-agent environments (typically two-player, turn-taking, zero-sum games like chess, tic-tac-toe or checkers) where agents have conflicting goals. One player (MAX) tries to maximize the outcome (utility) while the opponent (MIN) tries to minimize it. The agent must therefore plan against an opponent who actively works against it.

A game is formalized as:

• Initial state $S_0$, PLAYER(s) (whose turn), ACTIONS(s), RESULT(s,a) (transition model), TERMINAL-TEST(s), and UTILITY(s,p) (payoff at a terminal/leaf node).

Minimax Algorithm

Minimax computes the optimal move by assuming both players play optimally. It recursively propagates utility values up the game tree:

• At a MAX node, choose the child with the maximum value.
• At a MIN node, choose the child with the minimum value.

function MINIMAX-DECISION(state) returns an action
    return argmax over a in ACTIONS(state) of MIN-VALUE(RESULT(state,a))

function MAX-VALUE(state):
    if TERMINAL-TEST(state): return UTILITY(state)
    v = -infinity
    for each a in ACTIONS(state): v = max(v, MIN-VALUE(RESULT(state,a)))
    return v

function MIN-VALUE(state):
    if TERMINAL-TEST(state): return UTILITY(state)
    v = +infinity
    for each a in ACTIONS(state): v = min(v, MAX-VALUE(RESULT(state,a)))
    return v

Minimax performs a depth-first exploration of the tree. Time complexity is $O(b^m)$ and space is $O(bm)$, where $b$ = branching factor and $m$ = maximum depth.

Alpha-Beta Pruning

Alpha-Beta pruning is an optimization of Minimax that returns the same result but prunes branches that cannot affect the final decision, so fewer nodes are evaluated. It maintains two values:

• $\alpha$ = best (highest) value found so far for MAX along the path.
• $\beta$ = best (lowest) value found so far for MIN along the path.

Whenever $\alpha \ge \beta$, the remaining children are pruned (cut off), because the opponent would never allow that line.

Example Game Tree

Consider a MAX root with three MIN children, each having two leaf values:

           MAX (root)
         /    |     \
      MIN-A  MIN-B  MIN-C
      / \    / \    / \
     3   5  6   9  1   2

Minimax evaluation (bottom-up):

• MIN-A = min(3,5) = 3
• MIN-B = min(6,9) = 6
• MIN-C = min(1,2) = 1
• Root (MAX) = max(3,6,1) = 6 → optimal move is towards MIN-B.

Alpha-Beta on the same tree (left to right):

• Explore MIN-A: leaf 3 → $\beta=3$; leaf 5 → MIN-A = 3. Root $\alpha=3$.
• Explore MIN-B: leaf 6 → $\beta=6$ (not $\le\alpha=3$, continue); leaf 9 → MIN-B = 6. Root $\alpha=6$.
• Explore MIN-C: first leaf = 1 → $\beta=1$. Now $\beta=1 \le \alpha=6$, so the second leaf of MIN-C (value 2) is pruned — it cannot raise MIN-C above 1, which is already worse than 6.
• Final answer = 6, identical to Minimax, but with one leaf skipped.

With optimal move ordering, Alpha-Beta reduces complexity to $O(b^{m/2})$, effectively doubling the search depth for the same cost.

Expert System

An expert system is an AI program that emulates the decision-making ability of a human expert in a narrow domain. It solves complex problems by reasoning over a body of domain knowledge represented mainly as IF-THEN rules, and can explain its reasoning. Examples: MYCIN (medical diagnosis), DENDRAL (chemical analysis), XCON/R1 (computer configuration).

Architecture and Components

   [User] <--> [User Interface] <--> [Inference Engine] <--> [Knowledge Base]
                                            ^                      ^
                                            |                      |
                                   [Explanation Facility]   [Knowledge Acquisition]
                                            |                      ^
                                      [Working Memory]        [Human Expert]

Main components:

1. Knowledge Base — Stores the domain knowledge: facts and heuristic rules (IF condition THEN action/conclusion) acquired from human experts. It is the heart of the system.
2. Inference Engine — The reasoning component (brain). It applies the rules in the knowledge base to the known facts to derive new conclusions or recommendations.
3. Working Memory (Fact Database) — Holds the current facts about the problem being solved during a session.
4. User Interface — Lets the non-expert user enter queries/facts and receive answers in a friendly form.
5. Explanation Facility — Explains how a conclusion was reached and why a question was asked, increasing user trust.
6. Knowledge Acquisition Subsystem — Tools used by the knowledge engineer to capture and update knowledge from human experts.

Role of the Inference Engine

The inference engine matches rules against facts and fires applicable rules. It uses two reasoning strategies:

• Forward chaining (data-driven): starts from known facts and applies rules to reach a goal/conclusion.
• Backward chaining (goal-driven): starts from a hypothesized goal and works backward to find facts that support it. It also handles conflict resolution when multiple rules are eligible to fire.

Role of the Knowledge Base

The knowledge base is the repository of expertise. Its quality directly determines the system's competence. Separating the knowledge base from the inference engine allows knowledge to be updated without reprogramming the reasoning logic.

Applications

• Medical diagnosis (MYCIN), fault diagnosis in machinery, financial / loan approval advising, mineral exploration (PROSPECTOR), configuration of systems, and agricultural advisory systems.

Advantages / Limitations

• Advantages: consistent, always available, preserves expert knowledge, explains decisions.
• Limitations: costly to build, brittle outside its narrow domain, cannot learn on its own, depends on quality of acquired knowledge.

Fuzzy Logic

Fuzzy logic is a form of multi-valued logic (introduced by Lotfi Zadeh, 1965) in which truth values are not restricted to crisp 0/1 but can take any value in the range $[0,1]$. It handles imprecise, vague or approximate reasoning the way humans do (e.g., "the water is fairly hot"), making it ideal for control systems where exact mathematical models are hard to obtain.

Fuzzy Sets

In classical (crisp) set theory an element either belongs to a set or it does not. In a fuzzy set $A$, each element $x$ has a degree of membership $\mu_A(x)\in[0,1]$:

For example, the set "Tall" may assign $\mu(170\text{cm})=0.5$ and $\mu(190\text{cm})=0.9$, instead of a hard cut-off.

Membership Functions

A membership function (MF) maps each input value to its membership degree. Common shapes:

• Triangular, Trapezoidal, Gaussian, and Sigmoid functions.

Example triangular MF for "Warm" temperature, peaking at 25 C:

Structure of a Fuzzy Inference System (FIS)

Crisp input --> [Fuzzifier] --> [Inference Engine] --> [Defuzzifier] --> Crisp output
                                      ^
                                 [Rule Base] + [Knowledge/DB of MFs]

1. Fuzzification: converts crisp inputs into fuzzy membership degrees using the MFs.
2. Rule Base: stores expert IF-THEN rules, e.g. IF temperature is High AND humidity is High THEN fan speed is Fast.
3. Inference Engine: applies fuzzy rules (using AND = min, OR = max, implication) to obtain a fuzzy output set (e.g., Mamdani inference).
4. Defuzzification: converts the aggregated fuzzy output back into a single crisp value, commonly by the centroid (center of gravity) method: $z^*=\dfrac{\int z\,\mu(z)\,dz}{\int \mu(z)\,dz}$.

Example: Fan-Speed Controller

• Input temperature = 30 C → fuzzified: Warm 0.5, Hot 0.5.
• Rules fire: IF Warm THEN Medium (0.5), IF Hot THEN Fast (0.5).
• Aggregating and applying centroid defuzzification gives a crisp fan speed of, say, 70%.

Applications: washing machines, air conditioners, anti-lock braking, camera auto-focus, and industrial process control.

Semantic Network

A semantic network is a graphical, structured method of knowledge representation in which knowledge is shown as a directed graph: nodes represent objects, concepts or events, and labelled arcs (edges) represent the relationships between them.

Common relations include:

• is-a (subclass / class membership, supporting inheritance),
• has-a / part-of (composition),
• and other property links (e.g., can, colour).

A key feature is property inheritance: a node inherits properties from the more general node it is linked to via is-a.

Example

   [Animal] <--is-a-- [Bird] <--is-a-- [Canary]
      |can             |has               |colour
      v                v                  v
  (breathe)         (feathers)         (yellow)

From this network we infer that a Canary is-a Bird, which is-a Animal; therefore a Canary has feathers and can breathe (inherited), and additionally is yellow. This inheritance avoids storing every property at every node.

Frame-Based Knowledge Representation

A frame (proposed by Marvin Minsky, 1975) is a data structure that represents a stereotyped object, situation or concept by grouping all related knowledge about it together. It is similar to a record or an object in OOP.

Structure

A frame consists of a frame name and a collection of slots, where each slot stores an attribute, and each slot may have facets and a value (or a default value, or an attached procedure called a demon).

Frame: Car
  is-a:        Vehicle          (inheritance link)
  Wheels:      4                (default value)
  Fuel:        Petrol
  Engine:      [pointer to Engine frame]
  Max-Speed:   <to be filled>   (slot value)
  if-needed:   compute_speed()  (procedural attachment)

Key Features

• Slots and facets: attributes and their constraints/defaults.
• Inheritance: frames are organized in an is-a hierarchy, so a child frame inherits slot values from its parent (e.g., a Sports-Car frame inherits Wheels = 4 from Car).
• Default values: used when specific data is unknown.
• Procedural attachment (demons): if-needed and if-added procedures compute or update slot values automatically.

Advantages

Natural, modular grouping of knowledge; supports inheritance and defaults; efficient and easy to understand. It is widely used in expert systems and object-oriented AI representations.

Activation Function

An activation function is a mathematical function applied to the weighted sum of inputs of a neuron in a neural network. It decides whether (and to what degree) the neuron should be activated, and crucially introduces non-linearity so the network can learn complex, non-linear mappings. Without it a multi-layer network would collapse into a single linear transformation.

For a neuron, $y=f\left(\sum_i w_i x_i + b\right)$, where $f$ is the activation function.

Two Activation Functions

1. Sigmoid: $\;f(x)=\dfrac{1}{1+e^{-x}}\;$ — outputs in range $(0,1)$, smooth, used for probabilities.
2. ReLU (Rectified Linear Unit): $\;f(x)=\max(0,x)\;$ — fast, mitigates vanishing gradients; widely used in deep networks.

(Other examples: tanh, Softmax, Leaky ReLU, Step function.)

Supervised vs Unsupervised Learning

Summary: Supervised learning learns from labelled examples to predict outputs, whereas unsupervised learning finds patterns in unlabelled data without predefined outputs.

Overfitting in Machine Learning

Overfitting occurs when a machine-learning model learns the training data too well, including its noise and random fluctuations, instead of the underlying general pattern. As a result the model gives very high accuracy on training data but poor accuracy on unseen (test) data — it fails to generalize.

Symptoms: low training error but high validation/test error; an overly complex decision boundary.

Causes: model too complex (too many parameters/features), too little training data, training for too long, or noisy data.

Bias-variance view: overfitting corresponds to low bias but high variance.

Remedies (how to reduce overfitting):

• Use more / augmented training data.
• Cross-validation (e.g., k-fold).
• Regularization (L1/L2) to penalize large weights.
• Pruning (decision trees) or reducing model complexity.
• Dropout and early stopping in neural networks.
• Feature selection to remove irrelevant features.

(The opposite problem, where the model is too simple to capture the pattern, is called underfitting — high bias.)

Genetic Algorithm (GA)

A Genetic Algorithm is a heuristic search and optimization technique inspired by Darwin's theory of natural selection and evolution. It works on a population of candidate solutions (called chromosomes/individuals, usually encoded as bit strings), and iteratively evolves better solutions guided by a fitness function. It is used for optimization problems where the search space is large and complex.

General Cycle

Initialize population (random)
Repeat until termination:
    Evaluate fitness of each individual
    Select parents (based on fitness)
    Apply crossover
    Apply mutation
    Form new generation
Return best individual

Basic Operators

1. Selection (Reproduction): Chooses fitter individuals as parents for the next generation. Methods include Roulette-wheel, Tournament, and Rank selection. Higher fitness → higher chance of being selected.

2. Crossover (Recombination): Combines genetic material of two parents to produce offspring. In single-point crossover, a point is chosen and segments are swapped:

   • Parents: 1100|1010 and 1010|0111
   • Offspring: 1100 0111 and 1010 1010 It promotes exploitation of good building blocks.

3. Mutation: Randomly flips one or more bits of a chromosome (e.g., 10010 → 10110) with a small probability. It maintains genetic diversity and helps escape local optima (exploration).

(A fourth element, the fitness function, evaluates how good each solution is and drives selection.)

Wumpus World Problem

The Wumpus World is a classic AI knowledge-representation and reasoning test bed (from Russell & Norvig). It is a grid world (typically 4×4 cells) in which an intelligent agent must explore, avoid hazards, grab gold, and exit safely using logical inference.

Environment

• A Wumpus (a monster) hides in one cell; entering it kills the agent.
• Several pits; falling into one kills the agent.
• A heap of gold in one cell.
• The agent starts at cell (1,1) and has one arrow to shoot the Wumpus.

Percepts (the agent senses only adjacent cells)

• Stench — the Wumpus is in an adjacent square.
• Breeze — a pit is in an adjacent square.
• Glitter — gold is in the current square.
• Bump — the agent walked into a wall.
• Scream — the Wumpus has been killed by the arrow.

Goal / PEAS

The agent must find and grab the gold and return to (1,1) safely, maximizing reward (+1000 for gold/exit, −1000 for death, −1 per step, −10 for using the arrow). Because the world is partially observable, the agent uses propositional logic and inference (e.g., no breeze in (1,1) ⇒ (1,2) and (2,1) are safe) to deduce safe cells.

Significance: It demonstrates how a logical/knowledge-based agent reasons under uncertainty and incomplete information.

Depth-First Search vs Best-First Search

Summary: DFS blindly dives into one branch using a stack with no domain knowledge, whereas Best-First Search uses a heuristic function to always expand the most promising node, making it generally more efficient toward the goal.

Goal of Unification

Unification is the process of finding a substitution that makes two (or more) predicate-logic expressions / literals identical. The substitution found is called the Most General Unifier (MGU) — the simplest substitution that unifies the expressions.

Purpose

The goal of unification is to enable automated reasoning and inference, specifically:

• It is the core step in resolution and in applying Generalized Modus Ponens, allowing rules to be matched against facts.
• It binds variables to terms so that two clauses can be combined.

Example

The substitution $\theta=\{x/Mary\}$ makes both expressions identical:

So $\theta=\{x/Mary\}$ is the unifier (MGU).

Unification fails if the predicate symbols/arities differ, or if a variable would have to be bound to a term containing itself (the occurs check fails). In short, unification's goal is to match logical patterns by variable substitution, which is essential for theorem proving and inference engines.