Question

In this question, we will investigate shallow search, also known as depth-limited search. Depth-limited search is not guaranteed to find the optimal solution to the original problem. The point of this question is to explore some of the (potentially undesirable) behavior of depth-limited search, and to illustrate that the quality of the evaluation function can play a big role in how well depth-limited search performs. Consider the following Pacman configuration, in the board below. At each time step, Pacman can move either West (left) or East (right) and is using limited-depth minimax search (where the minimizing agent does not really do anything) to choose his next move. Pacman is 3 East moves away from the food. We will consider the following state evaluation functions: • F1(state) = – (Number of food pellets left) • F2(state) = – (Number of food pellets left) + 0.5/(distance to closest food pellet + 1); distance to closest food pellet is taken as O when no food remains. The search depth referred to in this question corresponds to the depth in a search tree that only considers the maximizer's actions. For example, if the search considers sequences of up to 2 actions by the maximizer, it'd have a search depth of 2. Note that there can be ties (in which case both East or West could be returned by the search). Also, note that a search does not finish when the dots are eaten

For what search depths could East be returned by the search?

1
2
3
4
None of the above

Answer 1

For evaluation function F1, East is returned at any search depth because moving East reduces the number of food pellets. For F2, East is returned for depths 1, 2, and 3 as it will always increase the heuristic value, potentially also at depth 4. The search depth does not affect the return of East in the context of F1.

Step-by-step explanation:

We need to calculate which search depths would allow Pacman, using a limited-depth minimax search, to return East as a move choice with the given evaluation functions (F1 and F2). The question specifies Pacman is 3 moves away from the food going East.

For F1(state), the evaluation is simple: it's the negative of the number of food pellets left. Since the search depth here only considers Pacman's (maximizer's) moves and doesn't end when food is eaten, the depth of the search doesn't affect the decision at each step. If Pacman can make at least one move, going East will always bring him closer to his goal. Therefore, for a search depth of 1 or greater, East would be returned.

With F2(state), the evaluation function adds an incentive to move closer to food. At search depth 1, Pacman would look one move ahead and see that moving East gets him closer to food, thus giving a higher value to the move because the distance to the nearest food pellet would decrease from 3 to 2, changing the evaluation from -3 + 0.5/4 to -3 + 0.5/3. Similar calculations for search depths 2 and 3 would show that moving East also results in a higher value. At a search depth of 4, however, Pacman would reach the food, and the term involving distance would become 0.5/1, as it's added to a negative number, the total evaluation would be less negative than if only one food pellet were left with more distance to cover. This means, theoretically, that at a search depth of 4, a tie might occur between the choice of East or West since the value would remain the same. Yet, because the search does not finish when the food is eaten and since moving East is still preferable in terms of getting closer to the goal, we can assume that East would still be returned by the search.

Considering both F1 and F2, the correct answer to the question 'For what search depths could East be returned by the search?' would be 1, 2, and 3. At depth 4, it is uncertain without specific implementation details about how ties are broken, but given no end when dots are eaten, we could still consider East being returned.