09 02 2023

Page 1

Politecnico di Milano School of Industrial and Information Engineering Foundations of Artificial Intelligence February 9, 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. 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 Monte Carlo Tree Search (MCTS) (8 points). Consider a simplified abstract game with two players: the white player and the black player. Each player can perform two actions, either 0 or 1; the players alternate; the game can be either won (utility is 1) or lost (utility is 0). The game works like the one we used in class to discuss Monte Carlo Tree Search. Consider the MCTS tree below for the white player. The tree follows the same convention used for the example discussed in class; thus, all the nodes contain statistics about the player at the root (in this case, the white player). Recall that the UCB1 value is computed as: where log is the natural logarithm. Question 1: Compute the UCB1 values for all the following nodes using C=1.4. Node UBC1 Value N00 Not possible and not…