1. Consider the Water Jugs problem described in class (see www.creighton.edu/~davereed/csc550/Code/jugs.pro). In Assignment 3, you used various uninformed search strategies to solve this problem and compared their behavior using the built-in time predicate. For this assignment, you will compare informed approaches using the following heuristic: take the sum of the differences in jug contents in the current state versus the goals state, then negate it and divide by 2. For example, suppose the contents of the large and small jugs in a given state are 4 and 1, respectively. Assuming the goal state specifies 2 and 0, the differences in volumes in the large and small jugs are |4-2| = 2 and |1-0| = 1, respectively. Adding these two values and dividing by two yields the heuristic value -1.5.
   1. Since a heuristic value is intended to quantify how "close" a given state is to the goal, it follows that a goal state should have the highest possible heuristic value. Is this true here? Justify your answer.
   2. Using this heuristic, would hill-climbing be able to solve the Water Jug problem? That is, starting with both jugs empty, would hill-climbing be able to find a sequence of moves that led to 2 gallons in the large jug and 0 gallons in the small jug? Justify your answer.
   3. Make a copy of the jugs.pro file and implement the described heuristic predicate in that file. Be sure to test your predicate on numerous states to ensure that it works as decribed. For example,
      ?- heuristic(jugs(0,0), jugs(2,0), Val). ?- heuristic(jugs(4,1), jugs(2,0), Val). Val = -1 Val = -1.5 Yes Yes
   4. Using your implementation of the heuristic function, determine whether a best first search leads to improved performance relative to an uninformed breadth first search. Do both searches produce the same answer? Does best first search require more or fewer inferences (as reported by the time predicate)?
   5. Is the performance advantage/disadvantage of best first search with your heuristic consistent across all goals? That is, if best first search required fewer inferences to solve the Water Jug problem (Part D), can you find a different goal state for which breadth first search is actually better? Or, likewise, if best first search required more inferences, is there a goal state for which it is better than breadth first search?
   
   
   
2. Consider a variant of the Water Jugs Problem in which we are interested in minimizing the amount of water that must be poured. Filling the large jug when it is empty requires pouring 4 gallons into it. Likewise, transferring water from a full large jug into an empty small jug requires pouring 3 gallons. A lazy person might not mind a longer solution to the problem if it in fact reduced the amount of water they had to heft and pour.
   1. Make a copy of jugs.pro called jugscost.pro and modify the move predicate to have an additional argument, specifying the cost (number of gallons poured) for each move.
   2. Consider a heuristic cost estimate h that is simply the negation of the heuristic from Problem 1. Is this heuristic admissible? Justify your answer.
   3. Replace the heuristic predicate in your jugscost.pro file with an h predicate that implements the new heuristic cost estimate. Be sure to test your predicate on numerous states to ensure that it works as decribed. For example,
      ?- h(jugs(0,0), jugs(2,0), Val). ?- h(jugs(4,1), jugs(2,0), Val). Val = 1 Val = 1.5 Yes Yes
   4. Is the least cost solution to the Water Jugs Problem the same as the shortest solution? Is it always true that a shorter solution will have a lower cost (number of gallons poured) than a longer solution? If so, explain why. If not, give a counter-example.
   
   
   
3. Consider the game Connect-4 (by Milton-Bradley). In this game, players take turns placing checkers in a 2-dimensional grid, with the goal of arranging a sequence of four consecutive checkers (either in a row, column, or diagonal), as in tic-tac-toe. Unlike tic-tac-toe, however, the player cannot select a specific cell, but can only select a column. You may think of each column as a slot in which the player places the checker, and the checker then falls as far as it can. For example, consider the following board, representing a game in progress. If it is white's turn and she places her checker in the second column, it will rest in the third row for a diagonal win.

   W
   B
   W	B	W				W
   B	B	B	W		W	B

   1. Does this game meet the criteria for applying John von Neumann's minimax theorem? That is, for each position in the game is there a "rational" move for the player to make? Justify your answer.
   2. Estimate the size of the game tree for a game of Connect-4 (starting with an empty board). Is expanding the entire tree and determining the "rational" move (if one exists) feasible?
   3. Describe a heuristic function that could be used to evaluate game positions. You should assume that the player placing black checkers is MAX, while the player placing white checkers is MIN. Your heuristic function should thus assign high values to positions that favor black, and low values to positions that favor white.
   4. Demonstrate your heuristic function on a simplified game board. Assume that there are only four rows and columns on the board, and that the goal is to place three consecutive checkers. On paper, perform a minimax search starting from the following game position, with a lookahead of 2 moves: black moves first, then white. Show the game tree two moves deep, along with the value of each position as minimax computes it. Be sure to clearly mark the move chosen.

      B
      W
      W
      B	W	B	W

   5. Indicate in your minimax search where alpha-beta would prune the search. Do this by marking a line through any edge at which alpha-beta would cut off the search.
   6. Is there a best move for black to make from this position? Did the minimax algorithm using your heuristic function select this best move? Explain.

ADDITIONAL QUESTION FOR GRADUATE STUDENTS:

4. Consider the Flashlight Problem (see www.creighton.edu/~davereed/csc550/Code/flashlight.pro). In our solution to this problem, we defined a heuristic cost estimate to a state based on the number of people out of position. Thus, if the starting state has all four people on the left side of the bridge, and the goal state has them all on the right, then the h value for that state would be 4. Assuming there are not two people that can cross the bridge in one minute, this is in fact an admissible heuristic. However, it fails to take the speed of the individuals into account. Consider, instead, the following Prolog code for a heuristic cost estimate:

   %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% h(STate, Goal, Value) : Value is the sum of the minutes required by individuals or pairs out of position h(bridge(Left, Right, _), bridge(GoalLeft, GoalRight, _), Value) :- diff_list(Left, GoalLeft, D1), high_vals(D1, V1), diff_list(Right, GoalRight, D2), high_vals(D2, V2), Value is V1 + V2. diff_list([], _, []). diff_list([H|T], L, Diff) :- diff_list(T, L, TDiff), (member(H,L), !, Diff = TDiff ; Diff = [H|TDiff]). high_vals([], 0). high_vals([N], N). high_vals([N1,N2|T], N) :- length(T, L), high_vals(T, NT), (L mod 2 =:= 0, !, N is NT+N2 ; N is NT+N1).

   This heuristic looks at all of the people who are out of position, pairs them up (slowest with next slowest, and so on), then sums the times needed for each pair to cross. For example,

   ?- h(bridge([1,2,5,10],[],left), bridge([],[1,2,5,10],right, Val). Val = 12 Yes ?- h(bridge([1,5,10],[2],left), bridge([],[1,2,5,10],right, Val). Val = 11 Yes
   1. Is this heuristic admissible? Justify your answer.
   2. Does Algorithm A using these two heuristics yield the same answer? If not, which produces the better answer? If so, which heuristic better guides the search (i.e., minimizes the number of inferences required to find the answer). Justify your answer.