Artificial Intelligence (AL-304) Unit 4 Notes

How unit 4 is examined

Minimax, alpha-beta, the block world and NLP carry the marks; the other topics are short.

Game playing techniques like minimax procedure

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. <mark>Minimax is a recursive procedure for two-player, zero-sum games in which MAX picks the move that maximises the utility and MIN, assumed to play optimally, picks the move that minimises it.</mark>

Diagram.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u4-01" viewBox="0 0 336 198" width="336" height="198" role="img" aria-label="Tic-tac-toe tree of the example. Root MAX (X to move); MIN children are X in 6, 7, 9."><style>#dsfig-u4-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u4-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u4-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u4-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u4-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u4-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u4-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u4-01 .t{fill:#16181D;font-weight:500}#dsfig-u4-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u4-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u4-01 .dot{fill:#16181D}#dsfig-u4-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u4-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u4-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u4-01 .ah{fill:#454C5A}#dsfig-u4-01 .ah.hi{fill:#2340B8}#dsfig-u4-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u4-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u4-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u4-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u4-01 .e{stroke:#B1B7C3}html.dark #dsfig-u4-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u4-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u4-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u4-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u4-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u4-01 .t{fill:#E6E8ED}html.dark #dsfig-u4-01 .t.inv{fill:#0F1115}html.dark #dsfig-u4-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u4-01 .dot{fill:#E6E8ED}html.dark #dsfig-u4-01 .ann{fill:#8FA3FF}html.dark #dsfig-u4-01 .lbl{fill:#858D9C}html.dark #dsfig-u4-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u4-01 .ah{fill:#B1B7C3}html.dark #dsfig-u4-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u4-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u4-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u4-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah11" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh11" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="156" y1="39" x2="56" y2="103"/><line class="e" x1="156" y1="39" x2="156" y2="103"/><line class="e" x1="156" y1="39" x2="256" y2="103"/><line class="e" x1="56" y1="103" x2="31" y2="167"/><line class="e" x1="56" y1="103" x2="81" y2="167"/><line class="e" x1="156" y1="103" x2="131" y2="167"/><line class="e" x1="156" y1="103" x2="181" y2="167"/><line class="e" x1="256" y1="103" x2="231" y2="167"/><line class="e" x1="256" y1="103" x2="281" y2="167"/><circle class="n" cx="156" cy="39" r="17"/><text class="t" x="156" y="39" dy=".35em" text-anchor="middle">+1</text><circle class="n" cx="56" cy="103" r="17"/><text class="t" x="56" y="103" dy=".35em" text-anchor="middle">-1</text><circle class="n" cx="31" cy="167" r="17"/><text class="t" x="31" y="167" dy=".35em" text-anchor="middle">+1</text><circle class="n" cx="81" cy="167" r="17"/><text class="t" x="81" y="167" dy=".35em" text-anchor="middle">-1</text><circle class="n" cx="156" cy="103" r="17"/><text class="t" x="156" y="103" dy=".35em" text-anchor="middle">-1</text><circle class="n" cx="131" cy="167" r="17"/><text class="t" x="131" y="167" dy=".35em" text-anchor="middle">+1</text><circle class="n" cx="181" cy="167" r="17"/><text class="t" x="181" y="167" dy=".35em" text-anchor="middle">-1</text><circle class="n" cx="256" cy="103" r="17"/><text class="t" x="256" y="103" dy=".35em" text-anchor="middle">+1</text><circle class="n" cx="231" cy="167" r="17"/><text class="t" x="231" y="167" dy=".35em" text-anchor="middle">+1</text><circle class="n" cx="281" cy="167" r="17"/><text class="t" x="281" y="167" dy=".35em" text-anchor="middle">+1</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Tic-tac-toe tree of the example. Root MAX (X to move); MIN children are X in 6, 7, 9.</figcaption></figure>

Key points.

A game has an initial state, legal moves, a terminal test and a utility (+1 MAX win, 0 draw, -1 loss); MIN minimises the number MAX maximises.
The game tree alternates MAX and MIN levels, each one ply.
The search is depth-first to terminal states or a depth limit; a MAX node takes the maximum of its children and a MIN node the minimum.
The root MAX plays the move to the child with the highest backed-up value, guaranteeing at least that utility against a perfect opponent.
In chess a state is a board position and an action a legal move; with about $10^{43}$ positions and a $10^{120}$-node tree (Shannon), search stops at a fixed depth and scores leaves with $Eval(s)=w_1f_1(s)+w_2f_2(s)+\dots$, a weighted linear sum of features such as material, mobility and king safety.
A fixed depth causes the horizon effect (a loss pushed just past the depth looks avoided); quiescence search fixes it by searching on in unstable positions such as pending captures.
Time complexity is $O(b^m)$ and space is $O(bm)$, where $b$ is the branching factor and $m$ the maximum depth.

Formula.

$$MINIMAX(s)=\begin{cases}UTILITY(s) & s \text{ terminal}\\ \max_{a} MINIMAX(RESULT(s,a)) & s \text{ is MAX}\\ \min_{a} MINIMAX(RESULT(s,a)) & s \text{ is MIN}\end{cases}$$

Steps.

Step 1: Generate the game tree down to terminal states or the depth limit.
Step 2: Score every leaf with the utility or static evaluation function.
Step 3: Back values up: a MIN node takes the minimum of its children, a MAX node the maximum.
Step 4: Repeat up to the root; MAX plays the move to the child equal to the root value.

Example (tic-tac-toe). Cells are numbered 1-9 row by row; X is to move and cells 6, 7, 9 are empty.

Now (X to move)   X in 6   X in 7   X in 9 (chosen)
O O X             O O X    O O X    O O X
X O .             X O X    X O .    X O .
. X .             . X .    X X .    . X X

X plays	O's replies and terminal results	MIN value
6	O 9 completes 1-5-9 (-1); O 7, X 9 completes 3-6-9 (+1)	-1
7	O 9 completes 1-5-9 (-1); O 6, X 9 completes 7-8-9 (+1)	-1
9	O 6, X 7 completes 7-8-9 (+1); O 7, X 6 completes 3-6-9 (+1)	+1

Root = $\max(-1,-1,+1)=+1$: X plays cell 9, which blocks O's diagonal and forks two X lines.

Answer frame. Define minimax; draw the 2-ply tree with values; develop points 1-6, then the steps; close with $O(b^m)$ and the need for alpha-beta. For tic-tac-toe, draw the child boards, back the values up and name the root move.

Short note: Frames and Scripts (Jun 2025). A frame is a slot-and-filler structure for a stereotyped object; a slot holds a value, a default or a procedure (if-needed computes on demand, if-added runs when a value is stored), and is-a links give inheritance: Hotel-Room is-a Room, Cost if-needed = tariff x nights. A script is a stereotyped event sequence with entry conditions, props, roles, scenes, tracks and results. Restaurant: entry hungry customer with money; props menu, food, bill; roles customer, waiter, cook; scenes entering, ordering, eating, leaving; result customer fed, with less money.

Short note: Heuristic search (Jun 2025). A heuristic $h(n)$ estimates the cost from $n$ to the goal. Best-first search is the general scheme: a priority queue ordered by an evaluation $f(n)$ always expands the lowest-$f$ node. Greedy best-first uses $f=h$; it is fast but not optimal, and complete on finite graphs as graph search, while tree search can loop. A* uses $f=g+h$, $g(n)$ being the cost so far; it is complete for finite $b$ and step costs $\ge\epsilon>0$, optimal when $h$ is admissible (never overestimates), and a consistent $h$ ($h(n)\le c(n,n')+h(n')$) keeps $f$ non-decreasing along a path.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u4-02" viewBox="0 0 424 252" width="424" height="252" role="img" aria-label="Heuristic values h(S)=7, h(A)=6, h(B)=4, h(G)=0 (admissible and consistent)"><style>#dsfig-u4-02 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u4-02 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u4-02 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u4-02 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u4-02 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u4-02 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u4-02 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u4-02 .t{fill:#16181D;font-weight:500}#dsfig-u4-02 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u4-02 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u4-02 .dot{fill:#16181D}#dsfig-u4-02 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u4-02 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u4-02 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u4-02 .ah{fill:#454C5A}#dsfig-u4-02 .ah.hi{fill:#2340B8}#dsfig-u4-02 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u4-02 .wl .t{font-size:12px;font-weight:700}#dsfig-u4-02 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u4-02 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u4-02 .e{stroke:#B1B7C3}html.dark #dsfig-u4-02 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u4-02 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u4-02 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u4-02 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u4-02 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u4-02 .t{fill:#E6E8ED}html.dark #dsfig-u4-02 .t.inv{fill:#0F1115}html.dark #dsfig-u4-02 .kd{stroke:#E6E8ED}html.dark #dsfig-u4-02 .dot{fill:#E6E8ED}html.dark #dsfig-u4-02 .ann{fill:#8FA3FF}html.dark #dsfig-u4-02 .lbl{fill:#858D9C}html.dark #dsfig-u4-02 .ptr{fill:#8FA3FF}html.dark #dsfig-u4-02 .ah{fill:#B1B7C3}html.dark #dsfig-u4-02 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u4-02 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u4-02 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u4-02 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah12" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh12" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M57,117.5 L195,48.5"/><path class="e" d="M57,134.5 L195,203.5"/><path class="e" d="M212,59 L212,193"/><path class="e" d="M229,48.5 L367,117.5"/><path class="e" d="M229,203.5 L367,134.5"/><g class="wl"><rect x="116.4" y="74" width="19.2" height="18" rx="9"/><text class="t" x="126" y="83" dy=".35em" text-anchor="middle">1</text></g><g class="wl"><rect x="116.4" y="160" width="19.2" height="18" rx="9"/><text class="t" x="126" y="169" dy=".35em" text-anchor="middle">4</text></g><g class="wl"><rect x="202.4" y="117" width="19.2" height="18" rx="9"/><text class="t" x="212" y="126" dy=".35em" text-anchor="middle">2</text></g><g class="wl"><rect x="284.8" y="74" width="26.4" height="18" rx="9"/><text class="t" x="298" y="83" dy=".35em" text-anchor="middle">12</text></g><g class="wl"><rect x="288.4" y="160" width="19.2" height="18" rx="9"/><text class="t" x="298" y="169" dy=".35em" text-anchor="middle">5</text></g><circle class="n" cx="40" cy="126" r="18"/><text class="t" x="40" y="126" dy=".35em" text-anchor="middle">S</text><circle class="n" cx="212" cy="40" r="18"/><text class="t" x="212" y="40" dy=".35em" text-anchor="middle">A</text><circle class="n" cx="212" cy="212" r="18"/><text class="t" x="212" y="212" dy=".35em" text-anchor="middle">B</text><circle class="n" cx="384" cy="126" r="18"/><text class="t" x="384" y="126" dy=".35em" text-anchor="middle">G</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Heuristic values h(S)=7, h(A)=6, h(B)=4, h(G)=0 (admissible and consistent)</figcaption></figure>

Greedy picks B (h 4 below 6): S-B-G, cost 9. A*: f(A)=7, f(B)=8; expanding A gives B at f=7; expanding B gives G at f=8. A returns S-A-B-G, cost 8 (optimal); greedy's 9 is not.*

Pitfall: Swapping MAX and MIN levels; the player to move at the root is always MAX.

Asked: [7 marks] (Jun 2023, Dec 2024, Dec 2025) Discuss Mini-Max algorithm steps in detail; explain the minimax procedure, its objective and how it works in chess Asked: [7 marks] (Jun 2024) Given a simplified tic-tac-toe game tree, apply minimax to find the optimal move Asked: [7 marks] (Dec 2025) Explain minimax algorithm and alpha-beta pruning Asked: [14 marks] (Jun 2025) Short notes (any two): a) Minimax algorithm, b) Frames and Scripts, c) Heuristic search algorithm, d) Components of NLP

Alpha-beta cut-offs

Definition. <mark>Alpha-beta pruning is minimax with two bounds, $\alpha$ (the best value found so far for MAX) and $\beta$ (the best value found so far for MIN), which cuts off every branch that cannot change the final decision, whenever $\alpha \ge \beta$.</mark>

Key points.

Plain minimax visits every node; pruning discards branches that cannot affect the answer, so alpha-beta returns the same root value and move while visiting fewer nodes.
$\alpha$ starts at $-\infty$ and rises only at MAX nodes; $\beta$ starts at $+\infty$ and falls only at MIN nodes.
Alpha cut-off: when a MIN node's value falls to $\le\alpha$ of an ancestor MAX node, its remaining children are skipped, as MAX will never choose it.
Beta cut-off: when a MAX node's value rises to $\ge\beta$ of an ancestor MIN node, its remaining children are skipped, as MIN will never allow it.
With the worst move ordering nothing is pruned, giving $O(b^d)$; random ordering gives about $O(b^{3d/4})$; the best ordering (best move first) gives $O(b^{d/2})$.

Steps.

Step 1: Start at the root with alpha = -inf, beta = +inf.
Step 2: Go depth-first; pass alpha and beta down to each child.
Step 3: A MAX node raises alpha to its best child value; a MIN node lowers beta.
Step 4: If alpha >= beta, skip the remaining children (cut-off); else return the value to the parent.

Example (Dec 2023 tree). R is MAX, Q1 and Q2 MIN, P1-P4 MAX, then eight MIN nodes named by their leaves: 2, 8, 3, 1, 6, 9, 8, 9, 3, 10, 2, 14, 16, 8, 15, 18. Windows are those passed down.

Node	Window	Working	Value
R, Q1, P1, Q(2,8)	$[-\infty,+\infty]$	$\min(2,8)$; then $\alpha=2$ at P1	2
Q(3,1)	$[2,+\infty]$	3, then $1\le\alpha=2$	1
P1		$\max(2,1)$; Q1 now has $\beta=2$	2
P2, Q(6,9)	$[-\infty,2]$	$\min(6,9)=6$; at P2 $6\ge\beta=2$	cut Q(8,9); P2 returns bound 6 (true 8)
Q1		$\min(2,\ge 6)$; root $\alpha=2$	2
Q2, P3, Q(3,10)	$[2,+\infty]$	$\min(3,10)=3$; $\alpha=3$ at P3	3
Q(2,14)	$[3,+\infty]$	after 2, $2\le\alpha=3$	cut leaf 14
P4, Q(16,8)	$[2,3]$	$\min(16,8)=8$; at P4 $8\ge\beta=3$	cut Q(15,18); P4 returns bound 8 (true 15)
Q2, then R		$\min(3,\ge 8)=3$; $\max(2,3)$	3

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u4-03" viewBox="0 0 2779 326" width="2779" height="326" role="img" aria-label="Dec 2023 tree with backed-up values. Pruned: leaf 14, the MIN node holding leaves 8, 9, and the MIN node holding leaves 15, 18."><style>#dsfig-u4-03 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u4-03 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u4-03 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u4-03 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u4-03 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u4-03 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u4-03 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u4-03 .t{fill:#16181D;font-weight:500}#dsfig-u4-03 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u4-03 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u4-03 .dot{fill:#16181D}#dsfig-u4-03 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u4-03 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u4-03 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u4-03 .ah{fill:#454C5A}#dsfig-u4-03 .ah.hi{fill:#2340B8}#dsfig-u4-03 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u4-03 .wl .t{font-size:12px;font-weight:700}#dsfig-u4-03 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u4-03 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u4-03 .e{stroke:#B1B7C3}html.dark #dsfig-u4-03 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u4-03 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u4-03 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u4-03 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u4-03 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u4-03 .t{fill:#E6E8ED}html.dark #dsfig-u4-03 .t.inv{fill:#0F1115}html.dark #dsfig-u4-03 .kd{stroke:#E6E8ED}html.dark #dsfig-u4-03 .dot{fill:#E6E8ED}html.dark #dsfig-u4-03 .ann{fill:#8FA3FF}html.dark #dsfig-u4-03 .lbl{fill:#858D9C}html.dark #dsfig-u4-03 .ptr{fill:#8FA3FF}html.dark #dsfig-u4-03 .ah{fill:#B1B7C3}html.dark #dsfig-u4-03 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u4-03 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u4-03 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u4-03 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah13" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh13" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="1377.5" y1="39" x2="771.5" y2="103"/><line class="e" x1="1377.5" y1="39" x2="2185.5" y2="103"/><line class="e" x1="771.5" y1="103" x2="367.5" y2="167"/><line class="e" x1="771.5" y1="103" x2="1175.5" y2="167"/><line class="e" x1="367.5" y1="167" x2="165.5" y2="231"/><line class="e" x1="367.5" y1="167" x2="569.5" y2="231"/><line class="e" x1="165.5" y1="231" x2="64.5" y2="295"/><line class="e" x1="165.5" y1="231" x2="266.5" y2="295"/><line class="e" x1="569.5" y1="231" x2="468.5" y2="295"/><line class="e" x1="569.5" y1="231" x2="670.5" y2="295"/><line class="e" x1="1175.5" y1="167" x2="973.5" y2="231"/><line class="e" x1="1175.5" y1="167" x2="1276.5" y2="231"/><line class="e" x1="973.5" y1="231" x2="872.5" y2="295"/><line class="e" x1="973.5" y1="231" x2="1074.5" y2="295"/><line class="e" x1="2185.5" y1="103" x2="1781.5" y2="167"/><line class="e" x1="2185.5" y1="103" x2="2589.5" y2="167"/><line class="e" x1="1781.5" y1="167" x2="1579.5" y2="231"/><line class="e" x1="1781.5" y1="167" x2="1983.5" y2="231"/><line class="e" x1="1579.5" y1="231" x2="1478.5" y2="295"/><line class="e" x1="1579.5" y1="231" x2="1680.5" y2="295"/><line class="e" x1="1983.5" y1="231" x2="1882.5" y2="295"/><line class="e" x1="1983.5" y1="231" x2="2084.5" y2="295"/><line class="e" x1="2589.5" y1="167" x2="2387.5" y2="231"/><line class="e" x1="2589.5" y1="167" x2="2690.5" y2="231"/><line class="e" x1="2387.5" y1="231" x2="2286.5" y2="295"/><line class="e" x1="2387.5" y1="231" x2="2488.5" y2="295"/><circle class="n" cx="1377.5" cy="39" r="17"/><text class="t" x="1377.5" y="39" dy=".35em" text-anchor="middle">3</text><circle class="n" cx="771.5" cy="103" r="17"/><text class="t" x="771.5" y="103" dy=".35em" text-anchor="middle">2</text><circle class="n" cx="367.5" cy="167" r="17"/><text class="t" x="367.5" y="167" dy=".35em" text-anchor="middle">2</text><circle class="n" cx="165.5" cy="231" r="17"/><text class="t" x="165.5" y="231" dy=".35em" text-anchor="middle">2</text><circle class="n" cx="64.5" cy="295" r="17"/><text class="t" x="64.5" y="295" dy=".35em" text-anchor="middle">2</text><circle class="n" cx="266.5" cy="295" r="17"/><text class="t" x="266.5" y="295" dy=".35em" text-anchor="middle">8</text><circle class="n" cx="569.5" cy="231" r="17"/><text class="t" x="569.5" y="231" dy=".35em" text-anchor="middle">1</text><circle class="n" cx="468.5" cy="295" r="17"/><text class="t" x="468.5" y="295" dy=".35em" text-anchor="middle">3</text><circle class="n" cx="670.5" cy="295" r="17"/><text class="t" x="670.5" y="295" dy=".35em" text-anchor="middle">1</text><circle class="n" cx="1175.5" cy="167" r="17"/><text class="t" x="1175.5" y="167" dy=".35em" text-anchor="middle">6</text><circle class="n" cx="973.5" cy="231" r="17"/><text class="t" x="973.5" y="231" dy=".35em" text-anchor="middle">6</text><circle class="n" cx="872.5" cy="295" r="17"/><text class="t" x="872.5" y="295" dy=".35em" text-anchor="middle">6</text><circle class="n" cx="1074.5" cy="295" r="17"/><text class="t" x="1074.5" y="295" dy=".35em" text-anchor="middle">9</text><rect class="n" x="1239" y="216" width="75" height="30" rx="8"/><text class="t" x="1276.5" y="231" dy=".35em" text-anchor="middle">cut 8 9</text><circle class="n" cx="2185.5" cy="103" r="17"/><text class="t" x="2185.5" y="103" dy=".35em" text-anchor="middle">3</text><circle class="n" cx="1781.5" cy="167" r="17"/><text class="t" x="1781.5" y="167" dy=".35em" text-anchor="middle">3</text><circle class="n" cx="1579.5" cy="231" r="17"/><text class="t" x="1579.5" y="231" dy=".35em" text-anchor="middle">3</text><circle class="n" cx="1478.5" cy="295" r="17"/><text class="t" x="1478.5" y="295" dy=".35em" text-anchor="middle">3</text><circle class="n" cx="1680.5" cy="295" r="17"/><text class="t" x="1680.5" y="295" dy=".35em" text-anchor="middle">10</text><circle class="n" cx="1983.5" cy="231" r="17"/><text class="t" x="1983.5" y="231" dy=".35em" text-anchor="middle">2</text><circle class="n" cx="1882.5" cy="295" r="17"/><text class="t" x="1882.5" y="295" dy=".35em" text-anchor="middle">2</text><rect class="n" x="2051" y="280" width="67" height="30" rx="8"/><text class="t" x="2084.5" y="295" dy=".35em" text-anchor="middle">cut 14</text><circle class="n" cx="2589.5" cy="167" r="17"/><text class="t" x="2589.5" y="167" dy=".35em" text-anchor="middle">8</text><circle class="n" cx="2387.5" cy="231" r="17"/><text class="t" x="2387.5" y="231" dy=".35em" text-anchor="middle">8</text><circle class="n" cx="2286.5" cy="295" r="17"/><text class="t" x="2286.5" y="295" dy=".35em" text-anchor="middle">16</text><circle class="n" cx="2488.5" cy="295" r="17"/><text class="t" x="2488.5" y="295" dy=".35em" text-anchor="middle">8</text><rect class="n" x="2645" y="216" width="91" height="30" rx="8"/><text class="t" x="2690.5" y="231" dy=".35em" text-anchor="middle">cut 15 18</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Dec 2023 tree with backed-up values. Pruned: leaf 14, the MIN node holding leaves 8, 9, and the MIN node holding leaves 15, 18.</figcaption></figure>

Pruned nodes: leaf 14, leaves (8, 9) and leaves (15, 18); root value = 3.

Answer frame. Open with "alpha-beta prunes branches that cannot affect the minimax result"; define $\alpha$ and $\beta$; draw a small tree with cut branches crossed; give both cut conditions; close with $O(b^{d/2})$. Variation question: each variation with its gain and cost, PVS with its example.

Variations (Dec 2024).

Principal Variation Search (PVS; NegaScout is its equivalent negamax form) searches the first move with a full window and the rest with a null window $[\alpha,\alpha+1]$. Example: the first move B gives 5, so $\alpha=5$; C's probe with $[5,6]$ returns 7, which is $\ge 6$ (fails high), so C is re-searched with $[5,+\infty]$, gives exactly 7 and becomes the best move; a probe returning $\le 5$ (fails low) is discarded without re-search. Poor ordering makes re-searches costly.
A transposition table stores evaluated positions so repeated states are not searched again, at the cost of memory.
A killer move caused a beta cut-off at the same ply in a sibling branch, so it is tried first there; it costs only two move slots per ply and a legality check, but helps only when sibling positions are similar.
The history heuristic scores every (from, to) move, adding depth squared whenever it causes a cut-off anywhere, and orders moves by that score.
Iterative deepening (depth 1, 2, 3, ...) tries the previous iteration's best move first, an ordering source separate from killer moves.
Aspiration windows search the root with a narrow window around the previous value and widen it only if the result falls outside. Assessment. All push the search towards $O(b^{d/2})$, giving the same move with far fewer nodes and about twice the depth; the costs are table memory, re-search when a PVS or aspiration guess fails, and repeated shallow iterations.

Pitfall: Pruning only when $\alpha > \beta$; the cut is at $\alpha \ge \beta$, and bounds are passed down, not recomputed.

Asked: [7 marks] (Nov 2022, Jun 2023, Jun 2025, Dec 2025) Explain the alpha-beta cut-off; what is pruning; describe alpha-beta pruning and its advantage Asked: [7 marks] (Dec 2023) Apply alpha-beta pruning to the given 16-leaf tree and identify all pruned nodes Asked: [7 marks] (Dec 2024) Propose a variation of alpha-beta pruning that further optimises the search and assess its advantages

Planning

Definition. <mark>Planning is finding an action sequence that takes the world from an initial state to a goal state.</mark>

Key points.

A STRIPS problem gives the initial state, the goal and operators; an operator applies only when its preconditions hold, then adds its add list and removes its delete list.
Forward (progression) planning searches from the initial state; backward (regression) planning starts from the goal.
Goal-stack planning (STRIPS) pushes goals on a stack and replaces each unsatisfied goal by an operator achieving it.

Study of the block world problem in robotics

Definition. <mark>The block world is a planning domain with a table, a set of blocks and a robot arm that moves one block at a time; the task is to find the operator sequence that turns a given arrangement of blocks into a goal arrangement.</mark>

Diagram.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u4-04" viewBox="0 0 652 262" width="652" height="262" role="img" aria-label="Sussman anomaly. Top: initial (C on A; A and B on the table). Bottom: goal (A on B, B on C). A child rests on its parent."><style>#dsfig-u4-04 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u4-04 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u4-04 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u4-04 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u4-04 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u4-04 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u4-04 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u4-04 .t{fill:#16181D;font-weight:500}#dsfig-u4-04 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u4-04 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u4-04 .dot{fill:#16181D}#dsfig-u4-04 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u4-04 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u4-04 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u4-04 .ah{fill:#454C5A}#dsfig-u4-04 .ah.hi{fill:#2340B8}#dsfig-u4-04 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u4-04 .wl .t{font-size:12px;font-weight:700}#dsfig-u4-04 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u4-04 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u4-04 .e{stroke:#B1B7C3}html.dark #dsfig-u4-04 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u4-04 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u4-04 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u4-04 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u4-04 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u4-04 .t{fill:#E6E8ED}html.dark #dsfig-u4-04 .t.inv{fill:#0F1115}html.dark #dsfig-u4-04 .kd{stroke:#E6E8ED}html.dark #dsfig-u4-04 .dot{fill:#E6E8ED}html.dark #dsfig-u4-04 .ann{fill:#8FA3FF}html.dark #dsfig-u4-04 .lbl{fill:#858D9C}html.dark #dsfig-u4-04 .ptr{fill:#8FA3FF}html.dark #dsfig-u4-04 .ah{fill:#B1B7C3}html.dark #dsfig-u4-04 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u4-04 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u4-04 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u4-04 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah14" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh14" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="186.5" y1="39" x2="117.5" y2="103"/><line class="e" x1="186.5" y1="39" x2="255.5" y2="103"/><line class="e" x1="117.5" y1="103" x2="48.5" y2="167"/><rect class="n" x="157" y="24" width="59" height="30" rx="8"/><text class="t" x="186.5" y="39" dy=".35em" text-anchor="middle">Table</text><circle class="n" cx="117.5" cy="103" r="17"/><text class="t" x="117.5" y="103" dy=".35em" text-anchor="middle">A</text><circle class="n" cx="48.5" cy="167" r="17"/><text class="t" x="48.5" y="167" dy=".35em" text-anchor="middle">C</text><circle class="n" cx="255.5" cy="103" r="17"/><text class="t" x="255.5" y="103" dy=".35em" text-anchor="middle">B</text><line class="e" x1="579.5" y1="39" x2="510.5" y2="103"/><line class="e" x1="510.5" y1="103" x2="441.5" y2="167"/><line class="e" x1="441.5" y1="167" x2="372.5" y2="231"/><rect class="n" x="550" y="24" width="59" height="30" rx="8"/><text class="t" x="579.5" y="39" dy=".35em" text-anchor="middle">Table</text><circle class="n" cx="510.5" cy="103" r="17"/><text class="t" x="510.5" y="103" dy=".35em" text-anchor="middle">C</text><circle class="n" cx="441.5" cy="167" r="17"/><text class="t" x="441.5" y="167" dy=".35em" text-anchor="middle">B</text><circle class="n" cx="372.5" cy="231" r="17"/><text class="t" x="372.5" y="231" dy=".35em" text-anchor="middle">A</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Sussman anomaly. Top: initial (C on A; A and B on the table). Bottom: goal (A on B, B on C). A child rests on its parent.</figcaption></figure>

Key points.

Predicates describe a state: $ON(x,y)$ block x is on y, $ONTABLE(x)$, $CLEAR(x)$ nothing is on x, $HOLDING(x)$ and $ARMEMPTY$.
The four operators Stack(x,y), Unstack(x,y), PickUp(x) and PutDown(x) each have preconditions, an add list and a delete list (table below; in Rich and Knight's form a held block stays CLEAR).
A state is a set of these predicates and a goal is a set of predicates that must hold, such as $ON(A,B)\wedge ON(B,C)$.
It is a small, clean benchmark for planning with interacting goals; STRIPS (Fikes and Nilsson, SRI, 1971) was built for the Shakey robot, and the blocks world became its classic test domain.
The Sussman anomaly shows that goals solved one at a time undo each other, so the planner must interleave them.
Real robotics adds sensing errors, grasping and uncertainty, which the symbolic model ignores.
Partial-order planning solves the Sussman anomaly by leaving step order open; the domain remains a testbed for PDDL and task-and-motion planners.

Operator	Preconditions	Add list	Delete list
Stack(x,y)	CLEAR(y), HOLDING(x)	ON(x,y), ARMEMPTY	CLEAR(y), HOLDING(x)
Unstack(x,y)	ON(x,y), CLEAR(x), ARMEMPTY	HOLDING(x), CLEAR(y)	ON(x,y), ARMEMPTY
PickUp(x)	CLEAR(x), ONTABLE(x), ARMEMPTY	HOLDING(x)	ONTABLE(x), ARMEMPTY
PutDown(x)	HOLDING(x)	ONTABLE(x), ARMEMPTY	HOLDING(x)

Example (Sussman plan, state after each step). Start: ON(C,A), ONTABLE(A), ONTABLE(B), CLEAR(B), CLEAR(C), ARMEMPTY.

Step	State after it
1 Unstack(C,A)	HOLDING(C), ONTABLE(A), ONTABLE(B), CLEAR(A), CLEAR(B), CLEAR(C)
2 PutDown(C)	ONTABLE(A), ONTABLE(B), ONTABLE(C), CLEAR(A), CLEAR(B), CLEAR(C), ARMEMPTY
3 PickUp(B)	HOLDING(B), ONTABLE(A), ONTABLE(C), CLEAR(A), CLEAR(B), CLEAR(C)
4 Stack(B,C)	ON(B,C), ONTABLE(A), ONTABLE(C), CLEAR(A), CLEAR(B), ARMEMPTY
5 PickUp(A)	HOLDING(A), ON(B,C), ONTABLE(C), CLEAR(A), CLEAR(B)
6 Stack(A,B)	ON(A,B), ON(B,C), ONTABLE(C), CLEAR(A), ARMEMPTY

Goal-stack planning on the same example (top of stack first):

Step 1: Stack = ON(B,C); ON(A,B); ON(A,B)^ON(B,C).
Step 2: ON(B,C) false: replace by Stack(B,C) under its preconditions CLEAR(C); HOLDING(B).
Step 3: CLEAR(C) false: push Unstack(C,A); its preconditions hold, so apply it.
Step 4: HOLDING(B) needs PickUp(B), which needs ARMEMPTY: apply PutDown(C), PickUp(B), Stack(B,C).
Step 5: Stack = ON(A,B); ON(A,B)^ON(B,C): push Stack(A,B), PickUp(A); apply both.
Step 6: The compound goal holds; the plan is the 6 steps above.

Pushing ON(A,B) on top instead builds A on B first, which must be undone to reach ON(B,C): the Sussman anomaly.

Recent advances (Dec 2024). Classical STRIPS assumes exact symbols (ON, ONTABLE, CLEAR, HOLDING, ARMEMPTY) and exact actions; each advance fixes a gap:

Deep RL and vision-based grasping learn continuous control from reward; QT-Opt (Google, 2018) learned closed-loop grasping from camera images (about 96% success on unseen objects after 580,000 real grasps), and DeepMind RGB-Stacking (2021) stacked irregular shapes.
CNN 6-DoF pose estimation (PoseCNN, DOPE, or RGB-D pose) gives each block's position and orientation, replacing hand-written ON/CLEAR facts.
Sim2Real trains in simulation with domain randomisation (colours, lighting, physics), avoiding slow, unsafe real trials.
Tactile sensing gives touch and slip feedback when vision is blocked.
Foundation models (SayCan, PaLM-E, RT-2) turn "stack the red block on the blue one" into robot skills.
Limitations: learning is sample-inefficient, the sim-to-real gap remains, learned policies give no safety or correctness guarantee, and LLM planners can output infeasible plans.

Aspect	Classical STRIPS	Modern system
State	Given symbols	Estimated from pixels
Actions	Perfect, discrete	Noisy, continuous, learned
Goal	Predicates	Natural language

Answer frame. Define the domain; draw the initial and goal stacks; give the predicates, the operator table and the traced plan; close with its benchmark role. Advances: classical baseline, the five advances, then their limitations.

Asked: [7 marks] (Jun 2024, Jun 2025, Dec 2025) Discuss the block world problem in robotics and planning Asked: [7 marks] (Jun 2024, Jun 2025) What is the block world problem in robotics and why is it a significant challenge in AI; explain with an example Asked: [7 marks] (Dec 2024) Investigate recent advancements in robotic systems for solving the block world problem

Introduction to understanding

Definition. <mark>Language understanding is the process of converting an input utterance into an internal meaning representation the machine can act on.</mark>

Key points.

Understanding is hard because natural language is ambiguous at the word, sentence and reference levels.
It proceeds in stages (words, structure, meaning, context), and world knowledge resolves ambiguity such as what "it" refers to.
The result is a frame, script or logical form that later reasoning uses.

Natural language processing (NLP)

Definition. <mark>Natural Language Processing is the branch of AI that enables computers to understand, interpret and generate human language.</mark>

Key points.

NLP has two parts: NLU maps text to meaning and NLG produces text from meaning.
It matters today because it powers assistants (Siri, Alexa), chatbots, search engines and large language models such as ChatGPT.
Machine translation converts text between languages (Google Translate: "Bonjour" to "Hello").
Sentiment analysis finds opinion ("battery is superb" is positive); information extraction pulls out names, places and dates ("Meet Ravi in Bhopal on 5 May").
Speech recognition converts speech to text, spell checking corrects "recieve", and summarisation shortens an article to its main lines.
The main challenges are ambiguity, dependence on context, idioms and sarcasm; "Great, my train is late again" looks positive to a word-based tool but is negative.
Ethics: NLP surveillance risks privacy invasion, mass monitoring, censorship, false positives (innocent people flagged), false negatives (threats missed) and bias, since training data under-represents dialects and minority languages. Remedies are anonymisation, differential privacy, explainable models and audits under the GDPR, India's DPDP Act 2023, the EU AI Act and the Puttaswamy judgment (2017, privacy a fundamental right). Oversight needs judicial warrants or independent authorisation before targeting, published transparency reports, and redress and appeal for flagged individuals, guided by the OECD AI Principles (2019) and the UNESCO Recommendation on the Ethics of AI (2021). Monitoring is justified only when necessary, proportionate and reviewed, never in bulk.

Rule-based chatbot (Jun 2025). Architecture: input, preprocessing (lowercase, tokenise, remove stop words, stem), rule matching, response and a fallback reply. Lemmatization, the alternative to stemming, maps a word to its dictionary form ("studies" to "study") instead of chopping a suffix. The ELIZA rule matches the raw lowercased input, before stop-word removal and stemming lose "my" or "am", and reflects pronouns (I to you, my to your, am to are).

import re
STOP = {"the", "a", "an", "is", "are", "what", "please", "me", "to"}
REFLECT = {"i": "you", "my": "your", "am": "are", "me": "you"}
RULES = [(r"\b(hi|hello|hey)\b", "Hello! How can I help?"), (r"\bfee\b", "Fees are on the college website."),
         (r"\b(exam|result)\b", "See the RGPV portal."), (r"\b(bye|exit|quit)\b", None)]   # None = exit
stem = lambda w: re.sub(r"(ing|s)$", "", w) if len(w) > 3 else w
def reply(text):                              # "I feel sad about my exam" -> "Why do you feel sad about your exam?"
    if m := re.match(r"i feel (.*)", raw := text.lower().strip(" .!?")):   # ELIZA rule on raw text
        return "Why do you feel " + " ".join(REFLECT.get(w, w) for w in m.group(1).split()) + "?"
    words = " ".join(stem(t) for t in re.findall(r"[a-z']+", raw) if t not in STOP)
    for pattern, answer in RULES:                                      # tokenise, stop words, stem
        if re.search(pattern, words): return answer
    return "Sorry, try fee, exam or bye."                              # fallback
while (r := reply(input("You: "))) is not None: print("Bot:", r)      # loop until exit

Answer frame. Definition: NLP, NLU and NLG, applications, then challenges. Ethics: risks, remedies, oversight, frameworks. Chatbot: architecture, preprocessing, rules, code.

Asked: [7 marks] (Jun 2023) Give an overview of applications of Natural Language Processing Asked: [7 marks] (Dec 2023) Define NLP and its significance in today's technological landscape Asked: [7 marks] (Jun 2024) Evaluate the ethical implications of using NLP in surveillance and monitoring systems and how they can be addressed responsibly Asked: [7 marks] (Jun 2025) Develop a simple AI-based chatbot using rule-based NLP

Components of NLP

Definition. <mark>The two components of NLP are Natural Language Understanding (NLU) and Natural Language Generation (NLG), and understanding passes through four analysis levels.</mark>

Key points.

Morphological (lexical) analysis splits words into stems and affixes, for example "unhappiness" into un + happy + ness.
Syntactic analysis (parsing) checks grammar and builds a parse tree.
Semantic analysis assigns meaning to the parse, for example rejecting "colourless green ideas".
Pragmatic analysis reads context and intent ("Can you pass the salt?" is a request); discourse analysis links sentences ("Ravi came. He sat": He = Ravi).
NLG passes through content planning, sentence planning and surface realisation: from "rain, 30 mm, Bhopal" it realises "Bhopal received 30 mm of rain today."
Ambiguity is the core difficulty: lexical ("bank"), syntactic ("I saw the man with a telescope") and referential ("it" with two antecedents).

Application of NLP to design expert systems

Definition. <mark>NLP gives an expert system a natural-language interface so that users and experts can talk to it in ordinary language instead of formal commands.</mark>

Key points.

Query understanding: NLP analysis turns a plain-language question into facts for the inference engine.
Knowledge acquisition uses NLP to extract rules and facts from manuals and expert interviews into the knowledge base.
Explanation generation uses NLG to present the "why" and "how" of the reasoning in readable sentences.
Together these ease use and cut training; LUNAR (1972) answered geologists' English questions on Apollo moon rocks by translating them into database queries.

Asked: [7 marks] (Nov 2022) Write about Natural Language Processing and explain applications of NLP to design expert systems

Last-minute revision

Minimax: MAX takes the maximum, MIN the minimum; time $O(b^m)$, space $O(bm)$.
$\alpha$ (best for MAX, starts $-\infty$), $\beta$ (best for MIN, starts $+\infty$); prune when $\alpha \ge \beta$; root value unchanged.
Alpha-beta time: worst $O(b^d)$, random $O(b^{3d/4})$, best $O(b^{d/2})$.
Dec 2023 tree: pruned leaf 14, leaves (8, 9) and (15, 18); root value 3.
Block world predicates ON, ONTABLE, CLEAR, HOLDING, ARMEMPTY; STRIPS = preconditions + add + delete.
NLP = NLU + NLG; levels morphological, syntactic, semantic, pragmatic.

Memory hooks

"Me Max, Enemy Min"; alpha is Ahead for MAX, beta for MIN.
STRIPS = Pre, Add, Delete (PAD); NLP levels MSSP.

Coverage checklist

Game playing techniques like minimax procedure: minimax, tic-tac-toe, short notes.
alpha-beta cut-offs etc: explanation, Dec 2023 tree, Dec 2024 variation.
planning: STRIPS operators, forward and backward planning.
Study of the block world problem in robotics: discussion, what and why, Dec 2024 advances.
Introduction to understanding: definition, stages, ambiguity.
natural language processing (NLP): applications, definition, ethics, chatbot.
Components of NLP: NLU, NLG, four analysis levels.
application of NLP to design expert systems: Nov 2022.

Account

Artificial Intelligence (AL-304) - Unit 4 Short Notes

How unit 4 is examined

Game playing techniques like minimax procedure

Alpha-beta cut-offs

Planning

Study of the block world problem in robotics

Introduction to understanding

Natural language processing (NLP)

Components of NLP

Application of NLP to design expert systems

Last-minute revision

Memory hooks

Coverage checklist