CSC 550: Introduction to Artificial Intelligence
HW2: AI programming and Search
PART 1: Eliza
Copy the Eliza program from eliza.scm
and make the following modifications:
- The Eliza rules currently include a rule that looks for the word "computer", and
However, this rule will not catch the plural "computers". Add a rule to the database
that simiarly responds to
user input containing "computers".
- Add a rule to the Eliza rule database that recognizes the phrase "I hate ___" in
the user's input. When this
phrase is found anywhere in the user input, Eliza should respond with either "Hate is
such an intense emotion" or
else a response of the form "What is it that you hate about ___".
- Add at least three more rules to the Eliza rule database of your own design.
- As it is currently written, the only way to terminate the Eliza program is to
issue a break (by clicking on
Break button). Augment the program so that any user input that contains the word
result in the response "Have a nice day." and will terminate the program.
PART 2: State Spaces & Search
Scheme provides a utility function, time, that can be
useful in profiling
code. The time function, when given an expression as
that expression and reports the number of milliseconds of CPU time
the evaluation. It even identifies the amount of CPU time taken by
collection, so that number can be subtracted out to determine the
amount of time spent doing actual computation.
For example, the call
(time (bfs '(0 0) '(2 0)))
would report how long it took to solve the Jugs Puzzle using breadth-first search.
Note, however, that the shortest time reportable by the time function is 10
ms. If a search
finding a solution in less than 10 ms, then it will register as no time at all. If
multiple calls to the function and divide by the number of repetitions to get a more
example, the following call would time how long it takes for breadth-first search to
solve the Jugs Puzzle five times.
(time (begin (bfs '(0 0) '(2 0))
(bfs '(0 0) '(2 0))
(bfs '(0 0) '(2 0))
(bfs '(0 0) '(2 0))
(bfs '(0 0) '(2 0))))
- Consider each of the three state space problems discussed in class:
- travel.scm: 'Omaha --> 'LosAngeles
- jugs.scm: '(0 0) --> '(2 0)
- tiles.scm: '(1 2 3 8 6 space 7 5 4) --> '(1 2 3 8 space 4 7 6 5)
Using the time function and the implementations in
of DFS, DFS-nocycles,
BFS, BFS-nocycles, and DFS-deepening on each of these
problems. That is, when
the strategy produces an answer, report the execution time (not
garbage collection). Comment on the apparent tradeoffs between the
- Consider the problem of traversing a maze, from one opening (identified as the
(identified as the Exit). For example, the diagram on the left shows an 8x9 maze,
Start is at the
upper-left corner, the Exit is at the lower-right corner, and walls are shown as black
rectangles. To the
right is a Scheme list structure that represents this maze.
"* ** * *"
"* ** *"
"* * *****"
"* * *"
"* * ** E"
For maze traversals, a state space can be defined in which a state is defined by
coordinates of the
person in the maze. For the above maze, we might identify the Start state as (1
row at index 1 and the column at index 0. Likewise, the goal (Exit) state for this
maze would be identified as (6 8).
The file maze.scm contains a Scheme definition of
the state space for this problem. Using this implementation, compare the performances
of the uninformed search
this maze and comment on the apparent tradeoffs.
- Similarly, compare the performances of the uninformed strategies on the following
- The maze.scm file defines a heuristic for
rating possible moves when searching a maze. A state is assigned a heuristic
value based on its row/column distance from the goal state. For example, if the
goal state is at (6 5), then the state (3 3) would have heuristic
value -5 (since it is off by and 3 rows and 2 columns) and
the state (7 3) would have heuristic value -3 (since it is off by 1 row and 2
Using this hueristic function, attempt to solve the mazes from the last two problems
using hill-climbing and best-first search (defined in heuristics.scm).
If a strategy is unable to solve the
problem, explain why. If it is successful, time its execution and compare its
efficiency with the uninformed strategies.