CSC 550: Introduction to Artificial Intelligence
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
- 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?
- 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?
- 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?
- 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:
- 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?
- 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.
- 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.
- 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.