Almost every IT job exam with an AI question starts here: definitions of AI, the Turing test, AI vs ML vs DL, agent types, PEAS, and above all search — BFS/DFS complexity tables and A* with f = g + h. BSCS AP 17.01.2026 asked a full 10-mark question on A* vs BFS (§1.8). MCQs on McCarthy, admissible heuristics, forward/backward chaining and fuzzy operators are quick marks. Learn the tables in this chapter by heart.
1.1What is AI? — Definitions and the Turing Test
Artificial Intelligence (AI) is the branch of computer science that builds machines and programs able to do tasks that normally need human intelligence — perceiving, reasoning, learning, understanding language, planning and acting. John McCarthy, who coined the term "Artificial Intelligence" (Dartmouth proposal, 1955–56), defined it as "the science and engineering of making intelligent machines".
The standard textbook (Russell & Norvig, Artificial Intelligence: A Modern Approach) groups definitions along two axes: thinking vs acting, and measuring success against humans vs rationality (an ideal standard of "doing the right thing").
| Human-like | Rational | |
|---|---|---|
| Thinking | Thinking humanly — cognitive modelling: build programs that think the way humans do (cognitive science, psychology experiments, brain imaging) | Thinking rationally — "laws of thought": correct reasoning with formal logic (Aristotle's syllogisms → logic programming) |
| Acting | Acting humanly — the Turing test approach: behave so that a human cannot tell it from a person | Acting rationally — the rational agent approach: act to achieve the best (expected) outcome. Used by the textbook and by modern AI |
The Turing Test
Proposed by Alan Turing in his 1950 paper "Computing Machinery and Intelligence" as the Imitation Game. A human interrogator chats by text with a hidden human and a hidden machine. If the interrogator cannot reliably tell which is the machine, the machine passes. To pass, a computer needs: natural language processing, knowledge representation, automated reasoning and machine learning. The Total Turing Test adds a video signal and physical objects, so it also needs computer vision and robotics.
Chinese Room (John Searle, 1980) — argues that passing the test by symbol manipulation is not real understanding. Basis of the weak AI (simulates intelligence) vs strong AI (really has a mind) debate.
• "Rational" means maximising the expected performance measure, not being perfect or all-knowing (omniscient).
• Father of AI (term) = McCarthy; Turing = father of theoretical computer science and of the test.
1.2Types of AI: Narrow, General, Super
| Type (by capability) | Meaning | Status / example |
|---|---|---|
| Narrow AI (ANI, weak AI) | Good at one specific task or a limited set of tasks; cannot transfer to unrelated tasks | All AI in use today: face unlock, spam filter, fraud detection, chess engine, LLM chat assistants |
| General AI (AGI, strong AI) | Human-level ability to understand, learn and apply knowledge across any intellectual task | Not achieved; research goal (⚠ whether today's large models are "steps toward AGI" is debated) |
| Super AI (ASI) | Surpasses the best humans in every field, including creativity and social skills | Hypothetical; discussed in AI safety and ethics |
A second popular classification (by functionality): Reactive machines (no memory, e.g. Deep Blue) → Limited memory (uses recent data, e.g. self-driving cars, most ML models) → Theory of mind (understands emotions and beliefs — research stage) → Self-aware (hypothetical).
1.3AI vs ML vs DL vs Generative AI
| Term | Definition | Key point |
|---|---|---|
| AI | Any technique that makes machines behave intelligently | Includes hand-written rules and search — no learning needed |
| ML | Systems that learn patterns from data instead of being explicitly programmed. Tom Mitchell: a program learns from experience E for task T and performance measure P if its performance on T, measured by P, improves with E | Supervised, unsupervised, reinforcement learning; features often hand-engineered |
| DL | ML using artificial neural networks with many hidden layers | Learns features automatically from raw data; needs large data and GPUs |
| Generative AI | DL models that create new content (text, image, audio, code) similar to their training data | LLMs (GPT, Claude, Gemini, Llama) are built on the Transformer; contrast with discriminative models that classify/predict |
1.4Short History of AI
| Year | Milestone |
|---|---|
| 1943 | McCulloch & Pitts — first mathematical model of an artificial neuron |
| 1950 | Turing — "Computing Machinery and Intelligence", the Imitation Game (Turing test) |
| 1956 | Dartmouth workshop (McCarthy, Minsky, Shannon, Rochester) — birth of AI as a field; the term "Artificial Intelligence" |
| 1957–58 | Rosenblatt's Perceptron; McCarthy creates LISP (1958) |
| 1960s | ELIZA chatbot (Weizenbaum); DENDRAL expert system (chemistry) |
| 1969 | Minsky & Papert's book Perceptrons shows limits of single-layer perceptrons (e.g. XOR) |
| 1970s | Prolog (1972); MYCIN medical expert system; first "AI winter" — funding cuts after over-promising |
| 1980s | Commercial expert systems boom (e.g. XCON/R1); 1986 backpropagation popularised (Rumelhart, Hinton, Williams); second AI winter late 1980s–early 1990s |
| 1997 | IBM Deep Blue defeats world chess champion Garry Kasparov |
| 2011 | IBM Watson wins the quiz show Jeopardy! |
| 2012 | AlexNet (deep CNN on GPUs) wins ImageNet by a large margin — start of the deep-learning boom |
| 2016 | DeepMind's AlphaGo defeats Go champion Lee Sedol |
| 2017 | "Attention Is All You Need" — the Transformer architecture (basis of LLMs) |
| 2022 | ChatGPT released publicly — generative AI goes mainstream |
| 2024 | Nobel Prize in Physics to Hopfield and Hinton (neural networks); Chemistry shared by Hassabis and Jumper (AlphaFold protein-structure prediction) with Baker |
1.5Intelligent Agents
An agent is anything that perceives its environment through sensors and acts on it through actuators. The agent function maps every percept sequence to an action; the agent program implements it on a physical architecture (Agent = Architecture + Program).
Rational agent: for each possible percept sequence, selects the action expected to maximise its performance measure, given the evidence from the percept sequence and its built-in knowledge. Rationality depends on (1) the performance measure, (2) prior knowledge of the environment, (3) available actions, (4) the percept sequence to date.
PEAS — specifying the task environment
| Agent | Performance measure | Environment | Actuators | Sensors |
|---|---|---|---|---|
| Automated taxi | Safe, fast, legal, comfortable trip; profit | Roads, traffic, pedestrians, customers | Steering, accelerator, brake, horn, display | Cameras, LiDAR/radar, GPS, speedometer |
| Medical diagnosis system | Healthy patient, lower cost | Patient, hospital, staff | Display of questions, tests, diagnoses, treatments | Keyboard entry of symptoms, test results |
| Bank fraud-detection agent | Frauds caught, few false alarms, low customer friction | Card/mobile/internet-banking transactions, customers, fraudsters | Approve, decline, hold, send OTP/alert, raise case | Transaction stream, device/location data, customer history |
| Bank customer-service chatbot | Correct answers, resolution rate, satisfaction | Customers, core-banking data, FAQ base | Text/voice replies, ticket creation, hand-off to human | Typed/spoken messages, account data |
Properties of task environments
| Dimension | Meaning |
|---|---|
| Fully vs partially observable | Do sensors give the complete relevant state at each moment? (Poker: opponents' cards hidden → partial) |
| Deterministic vs stochastic | Is the next state completely fixed by the current state and action? (Dice, traffic → stochastic) |
| Episodic vs sequential | Episodic: each decision is independent (classify each image). Sequential: current action affects future ones (chess, driving) |
| Static vs dynamic | Does the world change while the agent is thinking? Semi-dynamic: world fixed but score changes with time (chess with a clock) |
| Discrete vs continuous | Finite distinct states/actions (chess) vs real-valued ones (steering angle, speed) |
| Single vs multi-agent; known vs unknown | Other agents competing/cooperating? Does the agent know the rules (outcomes of actions)? |
| Environment | Observable | Agents | Deterministic | Episodic | Static | Discrete |
|---|---|---|---|---|---|---|
| Crossword puzzle | Fully | Single | Deterministic | Sequential | Static | Discrete |
| Chess with a clock | Fully | Multi | Deterministic | Sequential | Semi | Discrete |
| Poker | Partially | Multi | Stochastic | Sequential | Static | Discrete |
| Taxi driving | Partially | Multi | Stochastic | Sequential | Dynamic | Continuous |
| Image classification | Fully | Single | Deterministic | Episodic | Semi | Continuous |
The hardest case is partially observable, multi-agent, stochastic, sequential, dynamic, continuous and unknown — e.g. real-world driving.
Types of agents (from simplest to most capable)
| Agent type | How it chooses an action | Example |
|---|---|---|
| Simple reflex | Condition–action (if–then) rules on the current percept only; no memory. Works only if the environment is fully observable; can loop forever otherwise | Thermostat; automatic door; vacuum: "if dirty then suck" |
| Model-based reflex | Keeps an internal state updated with a model of how the world changes and how actions affect it; handles partial observability | Car that remembers a vehicle now in its blind spot |
| Goal-based | Has a goal; asks "will this action sequence reach the goal?" — uses search and planning | GPS route finder; puzzle solver |
| Utility-based | A utility function scores how good a state is; picks the action with maximum expected utility; handles trade-offs and uncertainty | Route that balances time, toll and safety; loan-pricing system |
| Learning | Improves with experience. Four parts: performance element (chooses actions), learning element (makes improvements), critic (feedback against a performance standard), problem generator (suggests exploratory actions) | Spam filter that learns from "mark as spam"; fraud model retrained on new cases |
1.6Problem Solving as Search
A goal-based agent solves a problem by searching for a sequence of actions that leads from the start to a goal. A well-defined problem has five parts:
- Initial state — where the agent starts (e.g. in Dhaka).
- Actions — what can be done in a state (drive to a neighbouring city).
- Transition model — the state that results from an action.
- Goal test — is this a goal state? (in Chattogram?)
- Path cost — sum of step costs (km, time, money).
The initial state, actions and transition model together define the state space — a graph whose nodes are states and edges are actions. A solution is a path from the initial state to a goal; an optimal solution has the lowest path cost. Search algorithms build a search tree: the frontier (open list) holds generated but unexpanded nodes; the explored set (closed list) avoids revisiting states (graph search).
Measures of a search strategy: Completeness (always finds a solution if one exists?), Optimality (finds the lowest-cost solution?), Time complexity (nodes generated), Space complexity (nodes stored in memory). Expressed with b = branching factor, d = depth of the shallowest goal, m = maximum depth of the state space.
1.7Uninformed (Blind) Search
Uninformed strategies use only the problem definition — no knowledge of how close a state is to the goal.
| Strategy | Idea | Frontier data structure |
|---|---|---|
| Breadth-First (BFS) | Expand the shallowest node first, level by level | FIFO queue |
| Uniform-Cost (UCS) | Expand the node with the lowest path cost g(n) (Dijkstra-like) | Priority queue on g(n) |
| Depth-First (DFS) | Expand the deepest node first; backtrack at dead ends | LIFO stack (or recursion) |
| Depth-Limited (DLS) | DFS with a depth limit l; nodes at depth l are treated as leaves | LIFO stack |
| Iterative Deepening (IDS) | Run DLS with l = 0, 1, 2, … until a goal is found | LIFO stack |
| Bidirectional | Search forward from start and backward from goal; stop when they meet | Two frontiers |
| Criterion | BFS | UCS | DFS | DLS | IDS | Bidirectional |
|---|---|---|---|---|---|---|
| Complete? | Yes¹ | Yes¹,² | No | No (if l < d) | Yes¹ | Yes¹,⁴ |
| Optimal? | Yes³ | Yes | No | No | Yes³ | Yes³,⁴ |
| Time | O(bd) | O(b1+⌊C*/ε⌋) | O(bm) | O(bl) | O(bd) | O(bd/2) |
| Space | O(bd) | O(b1+⌊C*/ε⌋) | O(bm) | O(bl) | O(bd) | O(bd/2) |
¹ if b is finite; ² if every step cost ≥ some ε > 0; ³ if all step costs are equal; ⁴ if both directions use BFS. C* = cost of the optimal solution. DFS is complete in finite state spaces when it avoids repeated states (graph search), but never optimal.
IDS regenerates upper levels in each iteration: d·b + (d−1)·b² + … + 1·bd = 50 + 400 + 3,000 + 20,000 + 100,000 = 123,450 nodes — only about 11% more time, but memory is just O(bd) ≈ 50 nodes.
Conclusion: IDS is the preferred uninformed method when the state space is large and the solution depth is unknown.
• DFS has small memory (O(bm)) but may run forever in an infinite or cyclic space.
• UCS with all step costs equal behaves like BFS.
1.8Informed (Heuristic) Search and A*
Informed search uses a heuristic function h(n) = estimated cost of the cheapest path from node n to a goal (h(goal) = 0). It picks nodes using an evaluation function f(n).
| Algorithm | f(n) | Complete? | Optimal? | Note |
|---|---|---|---|---|
| Uniform-cost (for comparison) | g(n) | Yes | Yes | Ignores the goal direction |
| Greedy best-first | h(n) | No (yes in finite spaces with graph search) | No | Fast, heads straight for the goal; can be misled |
| A* | g(n) + h(n) | Yes¹ | Yes if h is admissible (tree search) / consistent (graph search) | Expands fewest nodes among optimal algorithms with the same h; main drawback is memory (exponential) |
¹ with finite branching factor and step costs ≥ ε > 0. Memory-saving variants: IDA* (iterative-deepening A*), SMA* (simplified memory-bounded A*).
Admissible: h(n) ≤ h*(n) for every n (never overestimates the true cost h*). Example: straight-line distance on a map.
Consistent (monotone): h(n) ≤ c(n, n′) + h(n′) for every successor n′ (triangle inequality). Consistent ⇒ admissible (not the reverse).
Special cases: h = 0 ⇒ A* = UCS; f = h only ⇒ greedy; f = g + w·h with w > 1 ⇒ weighted A* (faster, may lose optimality).
h₁ = misplaced tiles: 5, 1, 2 are out of place → h₁ = 3.
h₂ = Manhattan distance (sum of row + column moves of each tile): 5 → 2, 1 → 1, 2 → 1 → h₂ = 4.
Both are admissible (each misplaced tile needs at least one move, and at least its Manhattan distance). h₂ ≥ h₁ for every state, so h₂ dominates h₁ — A* with h₂ never expands more nodes. Rule: prefer the largest admissible heuristic.
Worked A* trace
▶ Step-by-step animation: A* vs greedy best-first on this graph
True cheapest costs to G: C = 3, B = 5, A = 7, S = 8, so every h ≤ true cost (admissible); every edge also satisfies h(n) ≤ c + h(n′) (consistent).
| Step | Expand (lowest f) | New / updated nodes: g + h = f | Frontier after the step |
|---|---|---|---|
| 0 | — | S: 0 + 7 = 7 | S(7) |
| 1 | S | A: 1 + 6 = 7; B: 4 + 4 = 8 | A(7), B(8) |
| 2 | A | B via A: 3 + 4 = 7 (better than 8, update); C: 6 + 2 = 8; G: 13 + 0 = 13 | B(7), C(8), G(13) |
| 3 | B | C via B: 5 + 2 = 7 (better than 8, update) | C(7), G(13) |
| 4 | C | G via C: 8 + 0 = 8 (better than 13, update) | G(8) |
| 5 | G — goal selected, stop | Path S → A → B → C → G, cost 1 + 2 + 2 + 3 = 8 (optimal) | |
BFS (fewest edges): finds G at depth 2 through A: S → A → G, cost 1 + 12 = 13 — fewest steps, highest cost.
UCS (f = g): also returns cost 8. On this tiny graph it expands the same nodes as A*; on large maps a good h lets A* skip most of the nodes UCS would expand.
Rule: the goal test is applied when a node is selected for expansion, not when it is generated — that is why G(13) is not accepted at step 2.
Compact answer:
- BFS is blind: it ignores where the goal is and spreads level by level in all directions; it examines and stores O(bd) nodes. It is optimal only when all edge costs are equal.
- A* is directed: it expands the node with the lowest f(n) = g(n) + h(n). Paths that move away from the goal get a large h, so they are expanded late or never — the search space is pruned and the search follows a narrow "corridor" toward the goal. The more accurate h is, the fewer nodes are expanded.
- Why the perfect path may not be guaranteed: A* is optimal only if h is admissible (and consistent for graph search). For speed, practical systems often use an inadmissible or weighted heuristic (f = g + w·h, w > 1) or greedy search (f = h). These rush toward the goal and may return a slightly longer path — a trade-off of time and memory against optimality. (Figure 1.2: greedy finds cost 9 instead of 8.)
- Example: Dhaka → Chattogram with straight-line distance as h: BFS also explores Rajshahi, Mymensingh and Khulna; A* goes mainly through the Cumilla–Feni direction and visits far fewer cities.
1.9Adversarial Search: Minimax and Alpha-Beta Pruning
In two-player, zero-sum games with perfect information (chess, tic-tac-toe), one player (MAX) tries to maximise the utility and the opponent (MIN) tries to minimise it. A game tree alternates MAX and MIN levels; leaves are terminal states with utility values.
Minimax: the value of a node = utility (if terminal); max of children (MAX node); min of children (MIN node). Computed by depth-first recursion. Time O(bm), space O(bm). It assumes the opponent plays optimally.
Alpha-beta pruning returns the same move as minimax but skips branches that cannot affect the decision. α = best (highest) value MAX can guarantee so far on the path; β = best (lowest) value MIN can guarantee so far. Prune when α ≥ β.
Second MIN node: first leaf is 2, so this node's value ≤ 2. MAX already has 3, so it will never choose this branch (β = 2 ≤ α = 3) → leaves 4 and 6 are pruned.
Third MIN node: 14, 5, 2 must all be checked (14 and 5 are above 3; only the last leaf 2 shows it is worse) → value 2.
Root = max(3, ≤2, 2) = 3 — same as plain minimax.
With perfect move ordering alpha-beta examines about O(bm/2) nodes instead of O(bm) — it can search roughly twice as deep in the same time. Real game programs also cut off at a fixed depth and use an evaluation function (e.g. material count in chess) instead of true utilities.
1.10Knowledge Representation and Reasoning; Expert Systems
A knowledge-based agent keeps a knowledge base (KB) of sentences in a formal language and uses an inference procedure to derive new sentences (TELL and ASK).
Propositional logic
Atomic propositions (P, Q) that are either true or false, combined with connectives: ¬ (NOT), ∧ (AND), ∨ (OR), ⇒ (implies), ⇔ (if and only if).
| P | Q | P ⇒ Q | P ⇔ Q |
|---|---|---|---|
| T | T | T | T |
| T | F | F | F |
| F | T | T | F |
| F | F | T | T |
De Morgan: ¬(P ∧ Q) ≡ ¬P ∨ ¬Q; ¬(P ∨ Q) ≡ ¬P ∧ ¬Q
Modus Ponens: P ⇒ Q, P ⊢ Q
Modus Tollens: P ⇒ Q, ¬Q ⊢ ¬P
Resolution: P ∨ Q, ¬Q ∨ R ⊢ P ∨ R
Tautology = always true; contradiction = always false; satisfiable = true in at least one model.
First-order (predicate) logic
Adds objects (constants: Rahim, Sonali), predicates (Customer(x), Owns(x, y)), functions (BranchOf(x)), variables and quantifiers: ∀ (for all) and ∃ (there exists). It can say things about all objects that propositional logic cannot express compactly.
| English | First-order logic |
|---|---|
| Every customer who has a loan pays interest. | ∀x (Customer(x) ∧ HasLoan(x) ⇒ PaysInterest(x)) |
| Some loans are in default. | ∃x (Loan(x) ∧ Defaulted(x)) |
| No customer is a fraudster. | ∀x (Customer(x) ⇒ ¬Fraudster(x)) ≡ ¬∃x (Customer(x) ∧ Fraudster(x)) |
Other representations: production rules (IF condition THEN action), semantic networks (nodes and labelled links such as is-a, with inheritance), frames (objects with slots and fillers, like classes), ontologies (shared vocabularies of concepts and relations).
Expert systems
An expert system is a program that captures the knowledge of human experts in a narrow domain and gives advice or decisions at expert level. Classic examples: DENDRAL (chemistry), MYCIN (diagnosing bacterial infections), XCON/R1 (configuring computer orders).
| Component | Role |
|---|---|
| Knowledge base | Domain facts and IF–THEN rules from experts |
| Inference engine | Applies rules to facts to derive conclusions (forward or backward chaining); resolves rule conflicts |
| Working memory | Facts of the current case |
| User interface | Takes questions/facts from the user, shows advice |
| Explanation facility | Answers "why?" and "how?" — shows the rules used |
| Knowledge acquisition | Helps the knowledge engineer add and update rules |
| Basis | Forward chaining | Backward chaining |
|---|---|---|
| Direction | Facts → conclusions (data-driven) | Goal/hypothesis → supporting facts (goal-driven) |
| Starts with | Known facts; fires every rule whose IF part is satisfied | A goal; finds rules whose THEN part matches it and tries to prove their IF parts |
| Suited for | Monitoring, control, planning, alert generation | Diagnosis, answering a specific question |
| Examples | Production systems (e.g. CLIPS, Rete-based engines) | Prolog; MYCIN |
R2: IF GoodCredit AND HasCollateral THEN ApproveLoan
Facts: Salary = 60,000; NoDefaultHistory; HasCollateral.
Forward: R1's IF part is true → add GoodCredit → R2's IF part is true → add ApproveLoan.
Backward: Goal ApproveLoan? → R2 needs GoodCredit and HasCollateral. HasCollateral is a fact; GoodCredit? → R1 needs Salary ≥ 50,000 (fact) and NoDefaultHistory (fact) → proved → ApproveLoan.
1.11Fuzzy Logic in Brief
Introduced by Lotfi Zadeh (1965). Classical (crisp) logic says a statement is 0 or 1; fuzzy logic allows a degree of truth / membership μ ∈ [0, 1]. Useful for vague concepts such as "high income", "warm", "risky".
OR: μA∨B = max(μA, μB)
NOT: μ¬A = 1 − μA
Rule: IF HighIncome AND GoodHistory THEN LowRisk → strength = min(0.6, 0.8) = 0.6.
HighIncome OR GoodHistory = max = 0.8; NOT HighIncome = 0.4.
Fuzzy inference system: Fuzzification (crisp input → membership degrees using membership functions, e.g. triangular) → rule evaluation (IF–THEN rules with min/max) → aggregation → defuzzification (fuzzy output → one crisp number, commonly the centroid method). Common models: Mamdani and Sugeno. Uses: appliance and industrial controllers (washing machines, air conditioners), decision support, risk scoring.
1.12AI Applications in Bangladesh Banking and Government
| Area | AI technique | Typical use |
|---|---|---|
| Fraud detection and AML | Supervised ML, anomaly detection, rules + scores | Real-time scoring of card, MFS and internet-banking transactions; flagging suspicious patterns for compliance review |
| Credit scoring | ML classification, sometimes rule-based expert systems | Loan/SME credit decisions, including alternative data for customers without credit history |
| e-KYC and onboarding | Computer vision (face matching, liveness), OCR | Matching a selfie with the NID photo; reading NID/forms automatically |
| Customer service | NLP chatbots, LLM assistants, speech recognition (Bangla and English) | 24/7 answers on balance, card blocking, FAQs; hand-off to a human agent |
| Document processing | OCR, NLP classification and extraction | Cheque processing, trade-finance documents, government file and application handling |
| Cybersecurity and IT operations | Anomaly detection, log analytics | Detecting unusual logins and network traffic; predicting ATM/server failures |
| Public services | Chatbots, NLP, analytics, optimisation | Citizen helpdesks, service-request routing, planning and forecasting |
⚠ Specific bank deployments, national AI policy versions and statistics change often; quote them only from an official, dated source.
1.13Written practice
Model answer: A rational agent selects, for each percept sequence, the action expected to maximise its performance measure, given its percepts and built-in knowledge (rational ≠ omniscient). PEAS: P — frauds caught, low false-positive rate, low customer friction, fast decision; E — transaction streams (card, MFS, internet banking), customers, fraudsters; A — approve, decline, hold, send OTP/alert, open case; S — transaction details, device ID, location, customer history. Environment: partially observable (fraudster's intent hidden), multi-agent (fraudsters adapt), stochastic, sequential (past patterns affect decisions), dynamic (transactions keep arriving), and practically continuous (amounts, times). Best design: a learning, utility-based agent that balances loss from fraud against the cost of blocking genuine customers.
Model answer: Draw the table of §1.7. BFS: complete, optimal for equal step costs, O(bd) time and space — memory is the problem. DFS: O(bm) space but incomplete in infinite/cyclic spaces and not optimal. UCS: complete and optimal for any positive step costs, expands by g(n), O(b1+⌊C*/ε⌋). IDS: repeats DLS with increasing limits — complete and optimal (equal costs) like BFS, with O(bd) memory like DFS; overhead is small (b = 10, d = 5: 123,450 vs 111,110 nodes). Choose IDS when the search space is large, the solution depth is unknown and step costs are equal.
Model answer: Definitions of MAX/MIN and minimax values (§1.9), then Figure 1.3: MIN values 3, 2, 2 → root 3. With α-β: after the first branch α = 3; in the second branch the first leaf 2 makes that MIN node ≤ 2 ≤ α, so leaves 4 and 6 are pruned. Pruning is safe because a pruned branch can only give MAX a value that MAX would never choose (or MIN would never allow) — the minimax value of the root is unchanged. With good move ordering the cost falls from O(bm) to about O(bm/2), so the program can search about twice as deep.
Model answer: Definition and examples (MYCIN, DENDRAL, XCON). Components: knowledge base, inference engine, working memory, user interface, explanation facility, knowledge-acquisition module (knowledge engineer). Forward chaining is data-driven (facts → conclusions; monitoring, alerts); backward chaining is goal-driven (goal → facts; diagnosis, Prolog, MYCIN). Use the loan-approval example of §1.10 and show both traces. Limitations: knowledge-acquisition bottleneck, brittle outside its domain, rules need maintenance, no learning unless combined with ML.