General Game Playing

Problem 7.1 - Depth-Limited Search

Consider the single-player game tree shown below. and answer the questions that follow.


1. What is the minimax value of the tree?  
2. What is the value returned by depth-limited search with a depth limit of 3?  
3. How many nodes are examined by depth-first search with a depth-limit of 3, i.e. how many times is maxscore called?  
4. How many nodes are examined by breadth-first search with a depth-limit of 3, i.e. how many times is maxscore called?  
5. How many nodes are examined by iterative-deepening search with a depth-limit of 3 and a depth increment of 1, i.e. how many times is maxscore called?