CSC 550: Introduction to Artificial Intelligence
CSC 650: Advanced Artificial Intelligence
Spring 2003
HW4: Algorithm A & Game Trees
 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.
 Make a copy of jugs.scm called jugscost.scm and modify the
GETMOVES 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).
 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.
 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
 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
counterexample.
 Consider the game Connect4 (by MiltonBradley). In this game, players
take turns placing checkers in a 2dimensional grid, with the goal of arranging a
sequence of four consecutive checkers (either in a row, column, or diagonal), as in
tictactoe. Unlike tictactoe, 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.
 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.
 Estimate the size of the game tree for a game of Connect4 (starting with an
empty board). Is expanding the entire tree and determining the "rational" move (if
one exists) feasible?
 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.
 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.
 Indicate in your minimax search where alphabeta would prune the search. Do
this by marking a line through any edge at which alphabeta would cut off the search.
 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:

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.