General Game Playing

Problem 7.2 - Fixed-Depth Heuristic Search

Consider the two-player game tree shown below. The values on the max nodes are actual goal values for the associated states as given in the game description, not state utilities determined by game tree search.

1. What is the state utility of the top of the tree (as determined, for example, by Minimax)?  
2. Now consider a player using fixed-depth heuristic search with depth limit 1. How many max nodes are searched in evaluating the top node in this tree (i.e. how many times is maxscore called)?  
3. Suppose the player uses a goal proximity heuristic with state reward as the heuristic value for non-terminal states. What is the minimum final reward for this player in this game?