ACI — question bank with collapsible answers.

Questions extracted directly from the CS1–CS8 lecture slides, now with collapsible answers in easy words. Try the question first, then open the answer to check the core idea. Quick recall questions are grouped by lecture, followed by long / descriptive exercises for big-mark subjective practice.

CS1 — AI & intelligent agents

1. State the four views of AI on the think/act × human/rational grid, and say which one this course adopts.
2. Define a rational agent. Is a rational agent necessarily omniscient? Justify.
3. Write the agent function f : P* → A and explain why it maps the whole percept history rather than the current percept.
4. Expand PEAS and give a complete PEAS description for an automated taxi driver.
5. Distinguish "agent = architecture + program" with an example of each part.

CS2 — Environments, agent types & problem solving

1. List the six axes used to classify a task environment and classify "chess with a clock" on each.
2. Name the five agent types in order of increasing capability and state what each adds over the previous.
3. Draw the block structure of a learning agent (performance element, learning element, critic, problem generator) and explain the role of each.
4. Define the five components of a search problem and identify each for the 8-puzzle.
5. Differentiate "solution" from "optimal solution". On what four criteria do we judge a search algorithm?

CS3 — Uninformed & informed search

1. Compare BFS, DFS, UCS and IDS on completeness, optimality, time and space complexity.
2. Why is the goal test applied at expansion (not generation) in UCS? What goes wrong otherwise?
3. Write the evaluation functions for Greedy Best-First search and A*.
4. Define admissibility and consistency of a heuristic. Prove that consistency implies admissibility.
5. Show that h = 0 reduces A* to UCS. What does it mean for one admissible heuristic to dominate another?

CS4 — Heuristic design & local search

1. Explain how relaxing a problem yields an admissible heuristic. Derive h₁ and h₂ for the 8-puzzle and state which dominates.
2. What is the effective branching factor b* and why is a value near 1 desirable?
3. List pattern databases, landmarks and learned heuristics as sources of heuristics; give one line on each.
4. Why does local search use so little memory? Name three problems where the path is irrelevant.
5. Describe the failure modes of hill climbing (local maxima, plateaus, ridges) and three fixes.
6. Write the simulated-annealing acceptance probability and explain the role of temperature T and its cooling schedule.

CS5 — Beam search, GA, online search & ACO

1. How does local beam search differ from running k independent hill climbers? What does the stochastic variant add?
2. List the components of a genetic algorithm and explain the complementary roles of crossover and mutation.
3. Distinguish offline from online search and give one algorithm and one scenario for each.
4. Write the ACO transition probability and the pheromone update rule, defining every symbol (τ, η, α, β, ρ, Q).
5. In ACO, which term provides exploration and which provides exploitation? What happens if α is large and β small?

CS6 — ACO worked example + Neural Architecture Search

1. For the 5-city TSP (start node 4, α=0.5, β=0.75, ρ=0.1, Q=100), describe how one ant builds a complete tour step by step.
2. Why does a shorter tour deposit more pheromone, and how does that drive convergence?
3. Explain NAS as bilevel optimization — what evolves at the high level and what is learned at the low level?
4. What problem do innovation numbers solve in NEAT, and what does speciation protect?
5. State the limitation of NEAT that DeepNEAT fixes, and the limitation of DeepNEAT that CoDeepNEAT fixes.
6. In CoDeepNEAT, what is a blueprint vs a module, and how is the phenotype assembled from them?

CS7 — Adversarial search & minimax

1. Contrast normal search with adversarial search on number of agents, goal, environment and what the next state depends on.
2. List the six components used to formally define a game and identify each for tic-tac-toe.
3. Define MAX and MIN and explain what "two-player zero-sum" means.
4. State the minimax back-up rule for MAX and MIN nodes. Apply it to a tree with leaves (4,7) and (2,6).
5. Why can't MAX simply pick the branch containing the largest leaf value? Explain with the opponent's reply.
6. What are the properties of a good static evaluation function? Give a chess example and a simple piece-count example.

CS8 — Alpha-beta pruning & MCTS

1. Define α and β and state the pruning condition. Why does alpha-beta give the same result as minimax?
2. Trace alpha-beta on leaves 6, 5, 8, 10, 2, 1, 9, 12 (MAX root) and list the nodes pruned.
3. Explain why move ordering affects alpha-beta's efficiency, and state the best-case node count.
4. Name the four phases of MCTS and describe what happens in each.
5. What does the UCB rule balance, and why does MCTS suit games like Go where a static evaluation is hard to write?
6. List the preconditions for a combinatorial game suitable for MCTS.

Long / descriptive questions (slide exercises)

The full multi-part exercises exactly as set in the lecture decks — with their given data — plus the worked problems. These carry the big marks in a subjective paper: draw the trees, design the functions, and show every step.

1. L1 · PEAS for an interactive English tutor (CS2 — Exercise 1). Write the full PEAS specification for an interactive English tutor such as Grammarly: Performance measure, Environment, Actuators, Sensors.
2. L2 · Path-finding robot (CS2 — Exercise 2). For a path-finding robot, characterise the task environment — Observability? Number of agents? Determinism? Dynamicity? Episodic or sequential? Number of states? — and then write the PEAS for the problem.
3. L3 · Identify the environment (CS2 — Exercise 3). Classify each of these on all six environment axes: 15-puzzle game, Poker, Medical Diagnosis, Taxi Driving.
4. L4 · Problem formulation (CS3 — Exercise 1). For each task — (1) planning a trip with a delivery drone, (2) solving a maze, (3) scheduling patient appointments in a clinic — formulate the problem by specifying initial state, possible actions, transition model, goal test, and (optional) path cost. Note any missing components and assess whether each is a well-formed problem.
5. L5 · A* on a graph (CS3 — Exercise 2). Apply the A* algorithm on the graph below (start S, goal G) with heuristics h(S)=5, h(A)=3, h(B)=4, h(C)=2, h(D)=6, h(G)=0 and edge costs S–A=1, S–B=2, A–C=1, A–D=5, B–D=3, C–D=2, C–G=4, D–G=10 (use the edge weights as drawn on the slide). Show the f = g + h value of every expanded node and give the final path.
6. L6 · Heuristics activity (CS4 — Activity). For the 8-puzzle define h₁ = number of misplaced tiles and h₂ = sum of Manhattan distances. Verify on the given start state that h₁(S) = 8 and h₂(S) = 3+1+2+2+2+3+3+2 = 18, argue both are admissible, and state which dominates. Then provide at least two admissible heuristics for a second puzzle of your choice.
7. L7 · GBFS vs A* on a weighted graph (CS4 — Exercise 1). For a weighted graph whose nodes carry heuristic values h(n) estimating cost to goal G (start = B, goal = G): apply Greedy Best-First Search, then apply A*, compare your findings, and check whether the heuristic is admissible and consistent.
8. L8 · Warehouse-robot heuristics (CS4 — Exercise 2). A robot must collect three packages (at C, F, G) and reach exit X. Rooms S,A,B,C,D,E,F,G,X are joined by corridors (cost 1 per move); some doors are locked and need a matching key — K1 at B, K2 at E. Corridors/costs/conditions: S–A 1 open · A–B 1 open · A–C 2 open · B–D 2 needs K1 · C–D 2 open · D–E 1 open · E–F 2 needs K2 · D–G 3 open · G–X 2 open · F–X 2 open.
   • Part A: Define a state representation (current room, packages collected, keys collected); write the initial state and one goal state.
   • Part B: For each relaxation — (1) ignore locked doors, (2) ignore collection order and use only shortest distance to exit, (3) collect any package instantly once in the same connected component but still move to exit, (4) ignore current location and estimate only the min cost to connect all uncollected packages + exit — say which constraint was dropped; which gives the weakest and which the strongest heuristic; why a relaxed-problem solution cost is admissible; and construct a few heuristics from these relaxations.
9. L9 · 8-queens via genetic algorithm (CS5 — worked steps). Initialise k = 4 states encoded as column strings 2 4 1 2, 1 3 4 1, 1 4 2 2, 1 4 2 3. Fitness = number of non-attacking pairs of queens (threshold = 6). Compute each state's fitness; if any reaches 6, stop. Otherwise calculate selection probabilities, apply the roulette wheel, perform single-point crossover on the selected pairs, mutate one gene, and show the next generation.
10. L10 · Local beam search selection (CS5 — Exercise 1). Local beam search has k = 3. Current states have heuristic values S1=12, S2=15, S3=10; their successors are A=16, B=11, C=14, D=18, E=13, F=17. If the goal is to maximise, which three states are selected for the next beam?
11. L11 · Crossover & selection (CS5 — Exercise 2). (1) Given Parent 1 = [1,2,3,4,5,6,7,8] and Parent 2 = [8,7,6,5,4,3,2,1], apply single-point crossover after the 4th position and generate both children. (2) Given individuals with fitness A=10, B=30, C=40, D=20, which has the highest chance of being selected by a roulette wheel, and why?
12. L12 · ACO on the TSP (CS6 — worked example). For the 5-city TSP with start node 4 and α=0.5, β=0.75, ρ=0.1, Q=100: write the next-node transition-probability formula, compute the scores from node 4 over the unvisited cities, justify the tour 4→2→3→5→1→4, then apply one full pheromone update (evaporation + deposit) and explain why shorter tours dominate over many iterations.
13. L13 · CoDeepNEAT pipeline (CS6). Explain the full CoDeepNEAT generational loop for evolving a CNN on a cat-vs-dog task: initialization (~100 minimal networks), fitness via brief training + validation accuracy, fitness-proportionate selection, crossover and mutation of architectures, speciation, and phenotype assembly from blueprints + modules. State why each step matters and how accuracy climbs (~50% → ~95%) across generations.
14. L14 · Castle Battle game (CS7 — Exercise 2). Two armies play a strategy game. MAX is the attacking army (wants to capture the castle); MIN is the defender. Search only 2 moves ahead, then apply a static evaluation. At the current position MAX has three moves — Attack Left Gate, Attack Main Gate, Attack Right Gate — and after each, MIN has two replies, giving leaves L1,L2 / M1,M2 / R1,R2.
    • (a) Draw the game tree to depth 2 (root = MAX, level 2 = MIN, leaves = positions after MIN replies).
    • (b) Using Evaluation = 2×Soldier Advantage + 3×Gate Damage + 2×MAX Safety + 4×Supply Control, compute the evaluation score at each leaf from the feature table below.
    • (c) Apply minimax to back the values up and state MAX's best opening move and its guaranteed value.

    Leaf	Soldier Adv.	Gate Damage	MAX Safety	Supply Control
    L1	2	3	2	0
    L2	1	4	0	1
    M1	3	2	3	0
    M2	1	3	1	2
    R1	2	2	2	1
    R2	0	5	0	1

15. L15 · Alpha-beta pruning trace (CS8 — Exercise 1). For a 3-ply tree (MAX root) with leaf values 8, 7, 3, 15, 9, 8, −10, 5, 1, 4, 8, 9, 9, 9, 12, −3 left to right (α = lower bound of the maximizer, β = upper bound of the minimizer): run alpha-beta left to right, list every node pruned by an alpha cutoff and every node pruned by a beta cutoff, and give the minimax value at the root.
16. L16 · Sliding-tile two-player game (CS8 — Sample Problem). A sliding-tile game has three "A" tiles, three "B" tiles and two empty spaces; a player wins when three of their own tiles are adjacent (same row or same column). Player A moves first; A and B alternate. Legal moves: (i) a tile slides into an adjacent empty cell; (ii) a tile hops over one tile in the same row into an empty cell.
    • (a) Expand the complete game tree (neat diagram) from the given state to exactly 3 levels.
    • (b) Compute leaf utilities with Utility = 3×(MAX win chance − MIN win chance) + 2×(MAX adjacent pairs − MIN adjacent pairs), where "win chance" counts a player's tiles adjacent to an empty cell (e.g. in the initial state 3 A-tiles adjacent to empty ⇒ MAX win chance = 3; 1 B-tile adjacent ⇒ MIN win chance = 1).
    • (c) Apply the minimax algorithm over the tree and give the value backed up to the root.