1)      A knight moves on a chessboard two squares up, down, left, or right followed by one square in one of the two directions perpendicular to the first part of the move. (I.e., the move is L-shaped.) Suppose the knight is on an unbounded board at square (0,0) and we wish to move it to square (x,y) in the smallest number of moves. (For example, to move from (0,0) to (1,1) requires two moves.)

a)       Explain how to decide whether the required number of moves is even or odd without constructing a solution.

b)       Design an admissible heuristic function for estimating the minimum number of moves required; it should be as accurate as you can make it. Prove rigorously that your heuristic is admissible.

2)      Sometimes there is no good evaluation function for a problem, but there is a good comparison method: a way to tell whether one node is better than another without assignment numerical values to either.  Show that this is enough to do best first search.  Is there an analog of A*?

3)  AIMA Ex 5.9(all parts)