25 01 2022

Pagina 1

Politecnico di Milano School of Industrial and Information Engineering Foundations of Artificial Intelligence January 25, 2022 Prof. Francesco Amigoni & Pierluca Lanzi NAME CODICE PERSONA/ID GENERAL INSTRUCTIONS • This is a closed-book/closed-notes exam. • Answers must be written inside the answer box designated for each problem. • Answers must be legible and adequately motivated. • Pencils are not allowed. • The exam must be returned with all its original sheets. • No any other sheet can be added nor removed. • Only non-programmable calculators are allowed. • Notes/books/mobile phones are not allowed. • If you are caught using forbidden material, the exam will immediately end and an RP grade will be recorded; then, your exam will consist of an oral examination from then on. SCORING • A problem left unsolved will amount to zero points. • Incorrect answers or statements assign negative points. A completely wrong solution will amount to -3 points. STUDENTS HAVE 1:15h TO SOLVE ALL THE PROBLEMS GRADES Search (8 points). The Criss-Cross Solitaire consists of a board with 17 square cells. Initially, the 8 cells on the left side are occupied by white tokens, the 8 cells on the right side are occupied by black tokens; the central cell is empty. The objective is to exchange the positions of the two sets of tokens with the minimum number of moves. Tokens can move either to an adjacent empty cell (cells are adjacent if they share an edge, they are not adjacent if they share only a corner) or by jumping over an adjacent token (of any color) into an empty cell. Tokens cannot be removed from the board. Start configuration. Goal configuration. The gray token moves to the free adjacent cell. The gray token jumps the adjacent token to reach the empty cell. Question 1: Define a search…