final-search-games

CS 188 Spring 2023 Final Review: Search/Logic Q1. Power Pellets Consider a Pacman game where Pacman can eat 3 types of pellets: • Normal pellets (n-pellets), which are worth one point. • Decaying pellets (d-pellets), which are worth max (0 , 5 − t ) points, where t is time. • Growing pellets (g-pellets), which are worth t points, where t is time. The location and type of each pellet is fixed. The pellet’s point value stops changing once eaten. For example, if Pacman eats one g-pellet at t = 1 and one d-pellet at t = 2, Pacman will have won 1 + 3 = 4 points. Pacman needs to find a path to win at least 10 points but he wants to minimize distance travelled. The cost between states is equal to distance travelled. (a) Which of the following must be including for a minimum, sufficient state space? □ Pacman’s location □ Location and type of each pellet □ How far Pacman has travelled □ Current time □ How many pellets Pacman has eaten and the point value of each eaten pellet □ Total points Pacman has won □ Which pellets Pacman has eaten (b) Which of the following are admissible heuristics? Let x be the number of points won so far. □ Distance to closest pellet, except if in the goal state, in which case the heuristic value is 0. □ Distance needed to win 10 − x points, determining the value of all pellets as if they were n-pellets. □ Distance needed to win 10 − x points, determining the value of all pellets as if they were g-pellets (i.e. all pellet values will be t .) □ Distance needed to win 10 − x points, determining the value of all pellets as if they were d-pellets (i.e. all pellet values will be max (0 , 5 − t ). □ Distance needed to win 10 − x points assuming all pellets maintain current point value (g-pellets stop increasing in value and d-pellets stop decreasing in value) □ None of the above (c) Instead of finding a path which minimizes distance, Pacman would like to find a path which minimizes the following: C new = a ∗ t + b ∗ d where t is the amount of time elapsed, d is the distance travelled, and a and b are non-negative constants such that a + b = 1. Pacman knows an admissible heuristic when he is trying to minimize time (i.e. when a = 1 , b = 0), h t , and when he is trying to minimize distance, h d (i.e. when a = 0 , b = 1). Which of the following heuristics is guaranteed to be admissible when minimizing C new ? □ mean ( h t , h d ) □ min ( h t , h d ) □ max ( h t , h d ) □ a ∗ h t + b ∗ h d □ None of the above 1