GATE DA — Section 7
Artificial Intelligence
Comprehensive preparation notes on search algorithms, adversarial game playing, logic representations, and probabilistic reasoning under uncertainty for GATE Data Science & AI.
1. Uninformed & Informed Search Strategies
Problem-solving agents formulate state spaces characterized by an initial state, actions, transition model, goal test, and path cost c(s, a, s'):
- Uninformed (Blind) Search:
- Breadth-First Search (BFS): Expands shallowest node using FIFO queue. Time & space:
O(b^d). Complete and optimal for uniform step costs. - Depth-First Search (DFS): Expands deepest node using LIFO stack. Space:
O(bm). Not guaranteed complete on infinite graphs; not optimal. - Uniform Cost Search (UCS): Expands node with minimum path cost
g(n). Equivalent to Dijkstra's algorithm. Optimal for general positive edge costs.
- Breadth-First Search (BFS): Expands shallowest node using FIFO queue. Time & space:
- Informed (Heuristic) Search: Utilizes problem-specific estimate
h(n)of remaining cost to goal:- Greedy Best-First: Expands lowest
h(n). Fast but neither optimal nor complete. - A* Search: Evaluates
f(n) = g(n) + h(n)(actual cost so far + estimated cost to goal).
- Greedy Best-First: Expands lowest
- Heuristic Properties:
- Admissibility:
h(n) \le h^*(n)(never overestimates true cost). Guarantees optimality in A* tree search. - Consistency (Monotonicity): For every node
nand successorn'generated by actiona:h(n) \le c(n, a, n') + h(n'). Ensures thatf(n)values along any path are non-decreasing. Guarantees optimality in A* graph search without node reopening.
- Admissibility:
2. Adversarial Search & Alpha-Beta Pruning
Used for two-player deterministic, zero-sum perfect-information games (e.g., Chess, Tic-Tac-Toe):
- Minimax Principle: MAX seeks moves maximizing the payoff; MIN seeks moves minimizing MAX's payoff:
V(s) = max_{a} V(Result(s, a)) [at MAX nodes] | min_{a} V(Result(s, a)) [at MIN nodes]
- Alpha-Beta Pruning: Prunes subtrees without altering the final optimal move choice:
\alpha: Best value (highest payoff) found so far along the path for MAX. Initialized to-\infty.\beta: Best value (lowest payoff) found so far along the path for MIN. Initialized to+\infty.- Pruning Condition: Prune the branch whenever
\alpha \ge \beta. - With ideal move ordering, time complexity drops from
O(b^m)toO(b^{m/2}), effectively doubling the search depth.
3. Knowledge Representation & Logic
- Propositional Logic:
- Entailment (
\alpha \vDash \beta): In every model where sentence\alphais true, sentence\betais also true. Equivalently:(\alpha \land \neg \beta)is unsatisfiable. - Conjunctive Normal Form (CNF): Conjunction of clauses (disjunction of literals), e.g.,
(A \lor B) \land (\neg B \lor C). - Resolution Rule: Given
(P \lor Q)and(\neg P \lor R), derive the resolvent(Q \lor R). Empty clause\squareproves refutation.
- Entailment (
- First-Order Predicate Logic (FOL):
- Uses objects, relations (predicates), functions, and quantifiers: Universal (
\forall x) and Existential (\exists x). - Conversion to Clause Form requires eliminating implications, moving negation inwards, Standardizing variables, Skolemization (replacing
\existswith Skolem constants or functions), and dropping universal quantifiers.
- Uses objects, relations (predicates), functions, and quantifiers: Universal (
4. Reasoning Under Uncertainty & Bayesian Networks
A Bayesian Network is a Directed Acyclic Graph (DAG) whose nodes represent random variables and directed edges represent conditional dependencies. The joint probability distribution factors as:
D-Separation (Conditional Independence in DAGs)
A path between nodes X and Y is blocked by a conditioning set Z if any of the following node triples occurs on the path:
| Structure | Triple Form | Condition for Path Blocking |
|---|---|---|
| Causal Chain | A → B → C | Blocked if intermediate node B ∈ Z (is observed). |
| Common Cause (Fork) | A ← B → C | Blocked if common parent B ∈ Z (is observed). |
| Common Effect (Collider / V-Structure) | A → B ← C | Blocked if neither B nor any descendant of B is in Z. (Observing a collider opens the path!). |
5. Exact & Approximate Probabilistic Inference
- Exact Inference via Variable Elimination: Avoids exponential summation by caching intermediate factor products. Repeatedly chooses an elimination ordering, multiplies all factors containing variable
Y, and sums outY:m_Y(X) = \sum_{y} \prod f_j(X, y)Running time is exponential in the size of the largest factor created (treewidth of the moralized graph). - Approximate Inference via Sampling:
- Prior Sampling: Generates samples from topological order without evidence.
- Rejection Sampling: Drops samples that do not match observed evidence
E = e. Inefficient when evidence is rare. - Likelihood Weighting: Fixes evidence variables and weights each sampled state by the conditional probability of the evidence given its parents:
w = \prod_{i} P(e_i \mid parents(E_i)). - Gibbs Sampling / MCMC: Generates sequence of dependent samples by repeatedly sampling one variable conditioned on its Markov blanket.
6. Worked Step-by-Step Examples
Worked Example 1: Alpha-Beta Pruning Cutoff Trace
Problem: In a depth-2 game tree, root MAX has left child N1 (MIN) and right child N2 (MIN). N1's terminal leaf children have values 4 and 7. The first inspected child of N2 has terminal value 3. Will any subsequent children of N2 be pruned?
Solution:
1. Evaluate left child N1 (MIN node): \min(4, 7) = 4. Hence, MAX root receives value 4. Root \alpha updates to \alpha = 4, \beta = +\infty.
2. Pass [\alpha=4, \beta=+\infty] down to right child N2 (MIN node).
3. N2 inspects its first child value 3. Because N2 is a MIN node, its upper bound drops: \beta = \min(+\infty, 3) = 3.
4. Check cutoff condition: \alpha \ge \beta \iff 4 \ge 3 (True!).
Conclusion: Prune immediately. The remaining children of N2 are never evaluated because MAX would never choose N2 (which offers at most 3) over N1 (which guarantees 4).
7. GATE Exam Traps & Common Distractors
- The Collider Pitfall: Remember that two unconditionally independent causes become conditionally dependent once their shared effect (collider) is observed:
P(A \mid C, B) \ne P(A \mid C). - Heuristic Consistency implies Admissibility: If a heuristic is consistent, it is always admissible. The reverse is NOT true: an admissible heuristic can be inconsistent.
- Markov Blanket Composition: The Markov blanket of variable
Xconsists of: (1) its parents, (2) its children, and (3) other parents of its children (spouses). Forgetting spouse nodes leads to incorrect conditional independence assertions.
8. Practice & Topic Tracking
Practice exam-pattern AI problems:
Practice AI Questions or review the GATE DA Syllabus Index.