18 01 2023

Pagina 1

Politecnico di Milano School of Industrial and Information Engineering Foundations of Artificial Intelligence January 18, 2023 Prof. Francesco Amigoni & Prof. Pierluca Lanzi GENERAL INSTRUCTIONS • This is a closed-book/closed-notes exam. • 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. • Notes/books/mobile phones are not 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 11 N08 14 N01 11 N09 2 N02 7 N10 11 N03 14 N11 3 N04 11 N12 7 N05 7 N13 11 N06 11 N14 4 N07 1 Question 2: Now, apply the alpha-beta pruning algorithm and, for each node, specify whether the node has been pruned. Assume that children are generated and explored from left to right. Node Was it pruned? Node Was it pruned? N00 No N08 No N01 No N09 No N02 No N10 No N03 No N11 No N04 No N12 No N05 No N13 Yes N06 Yes N14 Yes N07 No Leaves listed left to right 1 16 18 14 2 10 15 11 6 3 18 7 12 11 4 11 Was…