18 01 2024

Pagina 1

Politecnico di Milano School of Industrial and Information Engineering Foundations of Artificial Intelligence January 18, 2024 Prof. Francesco Amigoni & Prof. Pierluca Lanzi GENERAL INSTRUCTIONS • This is a closed-book/closed-notes exam. Notes, books, and mobile phones are not allowed. Pencils are not allowed. Answers must be written inside the answer boxes designated for each problem. Answers must be legible and adequately motivated. • The exam must be returned with all its original sheets. No sheet can be added. None of the sheets can be removed. • Only non-programmable calculators are allowed. • If a student is caught using forbidden material, the exam will immediately end, and the disciplinary committee will be notified. • Exam receiving 5 points or less will be graded as REPEAT. SCORING • A problem left unsolved will amount to zero points. • Completely wrong answers assign negative points. STUDENTS HAVE 1:30h TO SOLVE ALL THE PROBLEMS SIGN THIS BOX TO WITHDRAW FROM THE EXAM FAMILY NAME FIRSTNAME CODICE PERSONA/ID Problem Scores /8 /8 /8 /8 Adversarial Search. Consider the game tree depicted below. Question 1: Apply the minimax algorithm and report the minimax value of each node. Assume that children are generated and explored left to right. Node Value Node Value N00 13 N16 18 N01 13 N17 18 N02 11 N18 14 N03 14 N19 15 N04 13 N20 7 N05 12 N21 15 N06 11 N22 13 N07 13 N23 18 N08 14 N24 12 N09 7 N25 8 N10 13 N26 16 N11 12 N27 18 N12 8 N28 11 N13 11 N29 16 N14 11 N30 11 N15 13 Question 2: Now, apply the alpha-beta pruning algorithm and for each node, specify whether the node has been pruned or evaluated. Assume that children are generated and explored from left to right. Node Was it pruned? Node Was it pruned? N00 No N16 No N01 No N17 No N02 No N18 No N03 No N19 No N04…