14 06 2022

Page 1

Politecnico di Milano School of Industrial and Information Engineering Foundations of Artificial Intelligence June 14, 2022 Prof. Francesco Amigoni & 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. 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 SURNAME FIRSTNAME CODICE PERSONA/ID SIGN BELOW TO WITHDRAW GRADES Adversarial Search (8 points). Close-the-box is a game of dice for two players. Each player has a counting box with 11 tiles (from 2 to 12). Each tile can be open (showing its number) or closed (hiding its number). At the start of the game, all tiles are open, showing the numerals 2 to 12. Each player plays in turn. A player begins her turn by throwing two dice. After throwing, the player can close the tiles using either the sum of the dice or both dice separately to close one or two tiles. For example, if the player rolled a 6 and a 2, she can either close the tile 8 (if still open) or the tiles 6 and 2 (if they are both open). If the player cannot close any tile, the turn ends, and the other player rolls. The player that closes all the tiles first wins. The image below shows an example of a game. It is the turn of player #2 who…