HW #4
Provide answers to the following questions. Your answers should be thoughtful, clearly stated, and grammatically correct. Submit your answers through blackboard in .txt, .pdf, .odt, or .doc(x) format.
- The Switching Sides Problem
Consider a chess board with the black pieces removed, and the white pieces in their normal starting positions. The Switching Sides Problem requires you to find the shortest sequence of moves that puts all of the white pieces in the corresponding starting positions of the black pieces: The white queen should be in the usual starting position of the black queen etc. The actions available in each state correspond to the allowable moves for each piece.
- Describe a heuristic function for this problem based on a relaxation.
- Line of Sight Distance Heuristic
Section 3.5 The textbook describes the straight line distance (SLD) heuristic for the problem of finding paths between cities in Romania. This is a nice heuristic, but what if we don't know all those straight line distances? Assume that we only know straight line distances for cities that are within 150 kilometers of the goal city. I propose the following heuristic based on this information:
h(s) = { 0, if the goal city is more than 150 kilometers from s. SLD otherwise. I claim that this heuristic admissible, but not consistent.
- Justify the claim that this heuristic is admissible.
- Provide an example that shows that this heuristic is not consistent.
- Given the information available to us, is there an easy way to modify our heuristic so that it is both admissible and consistent? If so what is it?
- Minimax
A Minimax search tree of three plys has a fan-out of three at each node. The utility values at the leaf nodes are:
[9,2,10, 3,5,1, 4,7,9, 2,10,9, 3,6,2, 5,5,6, 7,5,9, 6,2,11, 6,9,2]
- Draw the game tree, including the utility values at the leaf nodes. Show the minimax values for each state.
- Draw an X through any node in the tree above that would not be evaluated during an alpha-beta search.