CSC 550: Introduction to Artificial Intelligence
Fall 2004

HW4: Algorithm A & Game Trees

  1. In class, we studied a Scheme implementation of the Flashlight puzzle. In particular, we defined a state space that captured a state (positions of the people and flashlight), a GET-MOVES function to generate legal moves and their associated costs (in minutes), and a simple heuristic estimate of remaining cost (in minutes) for a given state (see flashlight.scm). Given this implementation, Algorithm A (atree.scm), was able to find the minimum cost (in elapsed minutes) solution to the puzzle.

    The heuristic used in this implementation is rather simplistic: it merely counts the number of people out of their goal position. A better heuristic would take into account the actual time required for the people to get into their goal positions. For this problem, you will consider a "more informed" heuristic and compare Algorithm A's performance using this new heuristic.

    1. Similar to exercises in HW2, use the time function to time a solution to the Flashlight puzzle using Algorithm A (the a-tree function from atree.scm). Recall that the initial state is when all four people are on the left side with the flashlight, and the goal state is when all four are on the right side: > (a-tree '((1 2 5 10) left ()) '(() right (1 2 5 10))) How many milliseconds does it take to solve the problem?
    2. Now add an additional person to the puzzle, whose walking time to cross the bridge is 15 minutes. How many milliseconds does it take to solve the puzzle with this additional person?
    3. Does the speed of the additional walker affect the performance of Algorithm A in solving the puzzle? For example, if the additional walker required 100 minutes instead of 15, would that affect the running time of the algorithm? Explain your reasoning and provide timings to back up your claim.
    4. Now consider the following heuristic cost estimate function, which determines which people on each side are out of place, pairs them up, and adds the longer times from each pair. (define(H state goalState) (define (sum-odd-indices numlist) (cond ((null? numlist) 0) ((null? (cdr numlist)) (car numlist)) (else (+ (car numlist) (sum-odd-indices (cddr numlist)))))) (+ (sum-odd-indices (reverse (remove-all (car goalState) (car state)))) (sum-odd-indices (reverse (remove-all (caddr goalState) (caddr state)))))) For example, > (H '((1 2 5 10) left ()) '(() right (1 2 5 10))) 12 > (H '((1 2 10) left (5)) '(() right (1 2 5 10))) 11

      Is this new heuristic admissible? Justify your answer.

    5. Is this new heuristic "better informed" than the old one? That is, for any state, is this heuristic guaranteed to return a cost estimate that is at least as large as the original one? Justify your answer.
    6. Compare the performance of Algorithm using this new heuristic. That is, replace the current H function with this one, and time how long it takes to solve both the original problem and the extended problem (with additional walker). In general, would you always expect a "better informed" heuristic to lead to a faster search? Explain.

      > (H '(0 0) '(2 0)) > (H '(4 1) '(2 0)) 1 1.5

  2. Consider the game Connect-4 (by Milton-Bradley). In this game, players take turns placing checkers in a 6x7 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       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 smaller 5x5 game board. 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 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.