CSC 550: Introduction to Artificial Intelligence
CSC 650: Advanced Artificial Intelligence
Spring 2003

HW4: Algorithm A & Game Trees


  1. 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.scm called jugscost.scm and modify the GET-MOVES function so that the cost of each move, i.e., the number of gallons poured, is returned along with the move (as in the examples discussed in class).
    2. Consider a heuristic cost estimate h that is simply the negation of the heuristic from Assignment 3, i.e., the average difference between jugs in current and goal states. Is this heuristic admissible? Justify your answer.
    3. Replace the HEURISTIC function in your jugscost.scm file with an H function that implements the new heuristic cost estimate. Be sure to test your function on numerous states to ensure that it works as decribed. For example,

      > (H '(0 0) '(2 0)) > (H '(4 1) '(2 0)) 1 1.5
    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.


  2. 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:

  1. Consider the Flashlight Problem (see www.creighton.edu /~davereed/csc550/Code/flashlight.scm). 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. Devise and implement a better heuristic function for the Flashlight Problem. Compare the performance of Algorithm A using the two heuristics functions.