Artificial Intelligence MCQs - Adversarial Search and Constraint Satisfaction (Set 4)

Q1. What minimax value is backed up to the MAX root of the game tree below?

MAX root with three MIN children (left to right):
MIN1 leaves: 4, 9, 7
MIN2 leaves: 6, 2, 10
MIN3 leaves: 8, 5, 11

a) 4

b) 2

c) 5

d) 11

Q2. Alpha-beta pruning is applied to the same tree, evaluating leaves left to right. Which leaves are pruned?

MAX root with three MIN children (left to right):
MIN1 leaves: 4, 9, 7
MIN2 leaves: 6, 2, 10
MIN3 leaves: 8, 5, 11

a) Only the leaf with value 10

b) The leaves with values 2 and 10

c) The leaves with values 5 and 11

d) No leaves are pruned

Q3. With perfect move ordering, what is the time complexity of alpha-beta search for a tree of depth m and branching factor b?

a) O(b^m)

b) O(b^(m/2))

c) O(bm)

d) O(b^(3m/4))

Q4. How does alpha-beta pruning affect the value computed at the root compared with plain minimax?

a) It gives an approximate value that is usually close

b) It gives a higher value for MAX

c) It changes the value only when move ordering is poor

d) It gives exactly the same value

Q5. Which algorithm extends minimax for games such as backgammon that include dice rolls?

a) Expectiminimax

b) Alpha-beta with iterative deepening

c) Monte Carlo tree search without chance

d) Negamax

Q6. A depth-limited game search fails to see that an unavoidable loss is only delayed beyond its search depth by stalling moves. This problem is called:

a) the frame problem

b) quiescence

c) the horizon effect

d) the credit assignment problem

Q7. A constraint satisfaction problem is formally defined by which three components?

a) States, actions and goal test

b) Variables, domains and constraints

c) Nodes, edges and costs

d) Percepts, actions and rewards

Q8. The minimum-remaining-values (MRV) heuristic in backtracking search chooses:

a) the value that rules out the fewest options for neighbours

b) the variable involved in the most constraints

c) the variable assigned most recently

d) the unassigned variable with the fewest legal values left

Q9. When MRV produces a tie, which heuristic is commonly used to break it by choosing the variable involved in the most constraints on other unassigned variables?

a) Degree heuristic

b) Least-constraining-value heuristic

c) Min-conflicts heuristic

d) Manhattan distance heuristic

Q10. Once a variable has been chosen, the least-constraining-value heuristic orders its values by preferring the value that:

a) appears first in the domain

b) was successful in a previous run

c) rules out the fewest values in the domains of neighbouring variables

d) has the largest number of conflicts

Q11. What does forward checking do immediately after a variable X is assigned a value?

a) It checks every arc in the CSP for consistency

b) It removes values inconsistent with X's assignment from the domains of unassigned variables connected to X

c) It backtracks to the most recent conflicting variable

d) It assigns values to all neighbours of X

Q12. What is the worst-case time complexity of AC-3 for a binary CSP with c constraints (arcs) and maximum domain size d?

a) O(cd)

b) O(c^2 d)

c) O(d^c)

d) O(cd^3)

Q13. Variables X and Y both have domain {1, 2, 3} and the constraint is X < Y. After enforcing arc consistency in both directions, what are the domains?

a) X = {1, 2}, Y = {2, 3}

b) X = {1}, Y = {3}

c) X = {1, 2, 3}, Y = {2, 3}

d) X = {2, 3}, Y = {1, 2}

Q14. Five regions are arranged in a ring so that each region borders exactly its two neighbours. What is the minimum number of colours needed so that no two bordering regions share a colour?

a) 2

b) 4

c) 3

d) 5

Q15. A CSP whose constraint graph is a tree with n variables and domain size d can be solved in what time?

a) O(d^n)

b) O(nd^2)

c) O(n^2 d^2)

d) O(n!)

Q16. In a cryptarithmetic puzzle, the requirement that all letters stand for different digits is an example of which kind of constraint?

a) Unary constraint

b) Preference (soft) constraint

c) Binary constraint only

d) Global (Alldiff) constraint

Q17. Which local search method for CSPs repeatedly picks a conflicted variable and gives it the value that violates the fewest constraints, and is very effective for large n-queens problems?

a) Min-conflicts

b) Forward checking

c) Conflict-directed backjumping

d) Arc consistency

Q18. What does the minimax algorithm assume about the opponent in a two-player zero-sum game?

a) The opponent plays randomly

b) The opponent plays optimally to minimise MAX's utility

c) The opponent always copies MAX's previous move

d) The opponent cooperates with MAX