CS 440: Intro to AI
Midterm Exam 2 (Spring 2026)
Version A
• This exam covers multi-agent search, constraint satisfaction problem, and Bayesian
network (not including sampling).
• Please write the answers ONLY in the space provided, and write your name on every page.
• You have 75 minutes to complete this exam (no grace period). The exam will start at 5:45pm.
Please arrive on time and bring a photo ID.
• If you would like to submit your exam early, please do so before 6:50pm. Otherwise, we kindly
ask that you remain seated until all exams have been collected.
• You may use a two-sided cheat sheet. No electronic device is allowed.
• You may detach the scratch paper provided at the end from the stapled exam for convenience,
but it is your responsibility to ensure all exam pages remain in the correct order.
• For “Select all that apply” questions, you will lose one point for each incorrect selection and each
missed correct answer.
• The exam includes 6 bonus points (≈ 10%) of your own choice, i.e., X − 6 is considered 100%,
where X is the total score of all questions. Prioritize questions you are most confident in.
PRINT your name:
PRINT your NetID:
PRINT your seat number:
Your work may not be graded without signing. I certify that answers to this exam represent my
own work and I have read the cover page and RU academic integrity policies
www.cs.rutgers.edu/academics/undergraduate/academic-integrity-policy.
Sign here:
,CS 440: Intro to AI (Version A) Name:
Problem 1: Multi-agent Search (14 points)
Hunt for Freedom: A hero (H) is trying to escape a dungeon. A dragon (D) guards the exit
and will try to prevent the hero from escaping. The hero is the maximizer and the dragon is the
minimizer. The hero first chooses Sneak Past (SN) or Charge Through (CH). The dragon then
responds with Breathe Fire (BF) or Tail Swipe (T). Finally, the hero decides to Dodge (DO) or
Block (BL).
The adversarial search tree is shown below. Leaf values represent the hero’s (maximizer’s)
utility.
H (MAX)
SN CH
D (MIN) D (MIN)
BF T BF T
H (MAX) H (MAX) H (MAX) H (MAX)
DO BL DO BL DO BL DO BL
4 −1 7 2 −8 −3 1 6
Figure 1: Adversarial search tree. Solid boxes = hero (MAX). Dashed boxes = dragon (MIN). Leaf
values = hero’s utility.
(a) (2pts) Use the minimax search algorithm to determine the hero’s optimal sequence of actions.
(A) Sneak Past, Dodge
(B) Sneak Past, Block
(C) Charge Through, Dodge
(D) Charge Through, Block
Your answer:
Page 1 of 11
, CS 440: Intro to AI (Version A) Name:
(b) Pruning (6pts). What branch(es) would be pruned when using α-β pruning from left to
right (i.e., you start with the leaf node of utility 4)?
Draw an “X” on the corresponding pruned branch, or indicate “None of the branches”.
Your Answer:
H (MAX)
SN CH
D (MIN) D (MIN)
BF T BF T
H (MAX) H (MAX) H (MAX) H (MAX)
DO BL DO BL DO BL DO BL
4 −1 7 2 −8 −3 1 6
What branch(es) would be pruned when using α-β pruning from right to left (i.e., you
start with the leaf node of utility 6)?
Draw an “X” on the corresponding pruned branch, or indicate “None of the branches”.
Your Answer:
H (MAX)
SN CH
D (MIN) D (MIN)
BF T BF T
H (MAX) H (MAX) H (MAX) H (MAX)
DO BL DO BL DO BL DO BL
4 −1 7 2 −8 −3 1 6
(c) (2pts) Based on your observations from part (b), select all statements that are TRUE.
(A) The ordering of leaf nodes can affect the efficiency of the α-β pruning algorithm.
(B) The ordering of leaf nodes can affect the optimal action of a player.
(C) For the MAX player, ordering child nodes of higher utility early can increase the likeli-
hood of pruning.
(D) The minimax value calculated at the root using α-β pruning may differ from the value
obtained without pruning.
Your answer:
Page 2 of 11
Midterm Exam 2 (Spring 2026)
Version A
• This exam covers multi-agent search, constraint satisfaction problem, and Bayesian
network (not including sampling).
• Please write the answers ONLY in the space provided, and write your name on every page.
• You have 75 minutes to complete this exam (no grace period). The exam will start at 5:45pm.
Please arrive on time and bring a photo ID.
• If you would like to submit your exam early, please do so before 6:50pm. Otherwise, we kindly
ask that you remain seated until all exams have been collected.
• You may use a two-sided cheat sheet. No electronic device is allowed.
• You may detach the scratch paper provided at the end from the stapled exam for convenience,
but it is your responsibility to ensure all exam pages remain in the correct order.
• For “Select all that apply” questions, you will lose one point for each incorrect selection and each
missed correct answer.
• The exam includes 6 bonus points (≈ 10%) of your own choice, i.e., X − 6 is considered 100%,
where X is the total score of all questions. Prioritize questions you are most confident in.
PRINT your name:
PRINT your NetID:
PRINT your seat number:
Your work may not be graded without signing. I certify that answers to this exam represent my
own work and I have read the cover page and RU academic integrity policies
www.cs.rutgers.edu/academics/undergraduate/academic-integrity-policy.
Sign here:
,CS 440: Intro to AI (Version A) Name:
Problem 1: Multi-agent Search (14 points)
Hunt for Freedom: A hero (H) is trying to escape a dungeon. A dragon (D) guards the exit
and will try to prevent the hero from escaping. The hero is the maximizer and the dragon is the
minimizer. The hero first chooses Sneak Past (SN) or Charge Through (CH). The dragon then
responds with Breathe Fire (BF) or Tail Swipe (T). Finally, the hero decides to Dodge (DO) or
Block (BL).
The adversarial search tree is shown below. Leaf values represent the hero’s (maximizer’s)
utility.
H (MAX)
SN CH
D (MIN) D (MIN)
BF T BF T
H (MAX) H (MAX) H (MAX) H (MAX)
DO BL DO BL DO BL DO BL
4 −1 7 2 −8 −3 1 6
Figure 1: Adversarial search tree. Solid boxes = hero (MAX). Dashed boxes = dragon (MIN). Leaf
values = hero’s utility.
(a) (2pts) Use the minimax search algorithm to determine the hero’s optimal sequence of actions.
(A) Sneak Past, Dodge
(B) Sneak Past, Block
(C) Charge Through, Dodge
(D) Charge Through, Block
Your answer:
Page 1 of 11
, CS 440: Intro to AI (Version A) Name:
(b) Pruning (6pts). What branch(es) would be pruned when using α-β pruning from left to
right (i.e., you start with the leaf node of utility 4)?
Draw an “X” on the corresponding pruned branch, or indicate “None of the branches”.
Your Answer:
H (MAX)
SN CH
D (MIN) D (MIN)
BF T BF T
H (MAX) H (MAX) H (MAX) H (MAX)
DO BL DO BL DO BL DO BL
4 −1 7 2 −8 −3 1 6
What branch(es) would be pruned when using α-β pruning from right to left (i.e., you
start with the leaf node of utility 6)?
Draw an “X” on the corresponding pruned branch, or indicate “None of the branches”.
Your Answer:
H (MAX)
SN CH
D (MIN) D (MIN)
BF T BF T
H (MAX) H (MAX) H (MAX) H (MAX)
DO BL DO BL DO BL DO BL
4 −1 7 2 −8 −3 1 6
(c) (2pts) Based on your observations from part (b), select all statements that are TRUE.
(A) The ordering of leaf nodes can affect the efficiency of the α-β pruning algorithm.
(B) The ordering of leaf nodes can affect the optimal action of a player.
(C) For the MAX player, ordering child nodes of higher utility early can increase the likeli-
hood of pruning.
(D) The minimax value calculated at the root using α-β pruning may differ from the value
obtained without pruning.
Your answer:
Page 2 of 11
