CSC 550: Introduction to Artificial Intelligence
Fall 2008

HW3: Game Trees & Expert Systems

PART 1: Connect-4

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. 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?

  2. Suppose you limited the search to 4 levels deep, applying a heuristic after looking ahead four moves (2 moves for each player). How large would this truncated game tree be? How about 6 levels deep?

  3. The file connect4.scm implements an interactive Connect-4 game in Scheme. It allows for two people to play against each other (alternating between B and W) or for a person to play against the computer (which simply picks moves at random). Review this code and play a few games to familiarize yourself with the game.

    At the bottom of connect4.scm, the file alpha-beta.scm is loaded. This file implements a generic alpha-beta search, relying on some of the Connect-4 specific functions from connect4.scm. There are two heuristic functions defined at the bottom of connect4.scm: the random-eval function assigns a random heuristic value while the dumb-eval inspects the board and assign a value based on a simple patterns. Review this code and play a few games against the computer using alpha-beta search and the dumb-eval heuristic function. How easy is it to beat the computer when it has a lookahead of 2 moves? 4 moves? 6 moves? How does the speed of the alpha-beta search degrade as the depth increases?

  4. Design and implement your own heuristic function for evaluating Connect-4 boards. Your function should be more sophisticated than the sample dumb-eval and should therefore produce better performance under an alpha-beta search. As a true test of your strategy, we will hold a tournament between all student strategies and crown a class champion.

PART 2: Rule-based Diagnosis

In class, we studied a simple expert system, auto.html, which was used to diagnose problems with automobiles. Using this Web-based expert system, answer the following questions:

  1. Suppose you have a car that won't run. When you try to start the car, the engine cranks slowly and the headlights dim. Assuming you are willing to pay any amount to fix the car, what would the expert system recommend?

  2. When dealing with concepts such as "slow" and "normal", it can often be difficult to commit with absolute certainty. Suppose you try to start the car and it seems like it cranks slowly, but you are only 90% sure. Assuming the other symptoms are unchanged (lights dim and unlimited cash), will this uncertainty affect the answer you receive from the expert system? Explain.

  3. Now that doubt is creeping into your mind, suppose you further doubt whether the headlights really are dimming. Does a 90% certainty that the lights dim change the result (assuming the 90% certainty of slow cranking and unlimited funds still hold)? How about an 80% certainty of dim lights? Explain.

  4. Would the order in which the rules are written in the knowledge base affect the answers you might obtain? Explain why or why not. If the system is sensitive to rule ordering, give an example where the same symptoms would yield a different result, simply because the rules have been swapped around. You can view the knowledge base for the expert system in auto.kb.