For this assignment you will need the ID number printed on your MIT ID card. Be sure to have it with you when you do the problems.
To warm up, load the code for problem set 7 and start the simulation by typing (setup <your name>). Play with the world a bit. One simple thing to do is to stay where you are and run the clock for a while with (run-clock <ticks>). Since the characters in our simulated building NE43 have a certain amount of restlessness, people should come walking by and say hi to you. Try running the clock with *deity-mode* set to both true and false. When it is set to true, you see everything that happens everywhere in the simulation. When it is set to false, you see only what happen in the room you are in. You'll probably want to set *deity-mode* it false most of the time.
Walk the avatar to a room that has a thing called the-goal in it. Have the avatar take the-goal, and lose it somewhere else. Show a transcript of this session.
Check the 6.001 discussion forum for computer-ex-01
|
Look here
for information about the forum.
| |
To solve the previous problem you did not really have to search for the goal: You had a map (from tutorial exercise 3) and you knew where the goal was, so you could plan a route and follow it directly. But suppose that you are in a world with no map, as in the World Wide Web. As you saw in problem set 6, you can search such a graph if you can keep track of where you have already been. You also need a bit more-see tutorial exercise 5. Hint: You may want to look at the procedure reverse-exit in the file search-rooms.scm.
Rather than searching the humdrum world of building NE43, you are to explore a magic labyrinth. If you enter the labyrinth unprepared, you are very likely to get very lost, because all the rooms have the same name and the same description.
You can explore the labyrinth using the same method you learned about in problem set 6. Namely, you can do a graph traversal, marking where you've been. Recall that exercise 6 implemented the marking by means of make-mark-procedures, which we used to construct two procedures, one for testing whether we've already visited a place, and one to mark the place as visited:
(define mark-procedures (make-mark-procedures)) (define deja-vu? (car mark-procedures)) (define note-visited! (cadr mark-procedures))
You'll find make-mark-procedures supplied for you in the file search-rooms.scm. By applying deja-vu? and note-visited! to your location as you walk around, you should be able to search the labyrinth without getting terribly lost.
Reinitialize the world for this exercise by running (start-exercise-2 <your name>). It makes the same NE43 world, with the addition of a randomly constructed labyrinth of twisty little passages, all alike. This labyrinth is accessible through an exit, constructed at the location of the avatar, called Dis. Somewhere in the labyrinth there is a thing named diamond. You should be able to use your mark procedures to help you find the diamond and bring it back into the world of NE43. In point of fact, the maze we construct here is very small. We don't want you to get lost--yet! So it is likely you'll quickly stumble across the diamond, even without a search strategy. But use the marks anyway, because you'll need to understand how this works for the rest of this problem set. Turn in a transcript showing a record of your activity in exploring the labyrinth.
Check the 6.001 discussion forum for computer-ex-02
|
Look here
for information about the forum.
| |
The mark procedures we provided for you in exercise 2 maintain a list of (pointers to) the rooms you've visited. But this is unrealistic, even in our fantasy magic world: What is the physical interpretation of carrying around a list of rooms to compare with your current location? (Does eq? make sense in the ``real world''?) To be more realistic, we should mark the rooms in some other way. For example, when we enter a room, we can drop some object that we can later recognize if we ever return to the room.
Define a new class of object called a pebble, and define a new version of make-mark-procedures such that note-visited! works by constructing a pebble and dropping it at the place being visited. The associated procedure deja-vu? checks to see if a pebble is present in the room visited. The pebble should be a new subclass of thing.
Notice that two searches will be confused if we cannot distinguish the pebbles used in the first search from the pebbles used in the second search. A simple way to deal with this is to name all the pebbles used in a given search with a fixed number, but to use different numbers for different searches (like using different colored pebbles for each search). The number must be incremented each time a search is begun (when make-mark-procedures allocates the name). Walk the avatar around NE43, dropping pebbles and recognizing them when you encounter them. (Hint: Look through objtypes.scm to see how new classes of objects are defined. Observe that for each class there is a make procedure, and an associated construct procedure, which is the procedure you call to actually construct the object. Also note that you should make your objects respond to a PEBBLE? message, so that you can use is-a to identify these as pebbles.)
Check the 6.001 discussion forum for computer-ex-03
|
Look here
for information about the forum.
| |
You can now use your pebbles to search the labyrinth. But you do not want to do this for large labyrinth. Instead, you can program your robot to do the searching for you. Of course, you have to construct a robot before you can use it. Look at the definition of the robot object in objtypes.scm, to see how robots are constructed in general. Then, look at the procedure start-robot-searching! in search-rooms.scm to see how to the robot's program gets coupled to the search strategy.
Look at the procedure setup-robot at the end of the file search-rooms.scm to see how to construct a robot and start it up. The existing setup-robot program will find the object called the-goal, just as you did in computer exercise 1.
Play with the robot a bit. Reinitialize the simulation with (setup <your name>) and run the robot until it finds the-goal. Do this with *deity-mode* true and also false so you can see how the robot is working. Now try (start-exercise-4 <your name>), set up the robot to find the diamond (which is somewhere in the labyrinth) than the-goal) and observe how this works. There is nothing to turn in for this exercise.
Check the 6.001 discussion forum for computer-ex-04
|
Look here
for information about the forum.
| |
For the next part of your adventure, you will search the maze for a
truly valuable object: a magic scroll. If you can get your hands on
the scroll, you can learn a magic word that you can use to get extra
points on Quiz 2. (We're not kidding!) This magic word is
personalized to you: Each student will get a different magic
word.
The magic scroll will be hidden inside a new labyrinth, which is a lot larger than the one for exercises 3 and 4. There are also a few characters that wander aimlessly through the labyrinth, and do nothing in particular. You might be able to search this labyrinth by hand, but we don't recommend trying. Instead, you should use a robot to perform the search.
There is, however, a catch. The magic scroll will work only in Jill's office. So it's not
enough to just send the robot searching for the scroll. You'll have
to modify the robot's program so that it not only finds the scroll,
but brings it back to you so you can take it to Jill's office to read
it.
Reinitialize the the world for this exercise by running (start-exercise-5 <your name>). This creates a large labyrinth with the magic scroll hidden in it. The magic scroll is a new kind of object of class scroll (so that it responds to the SCROLL? message), and whose name is magic-scroll. Reprogram the robot to venture into the labyrinth and retrieve the scroll for you. Take the scroll to Jill's office and ask the scroll to read, and follow the instructions. If all works well, you'll obtain the magic word. You'll need to have your MIT ID number handy. Caution: You can read the scroll only once. After that, its magic will be used up. Keep your magic word for the quiz, but turn in your modified robot program for this exercise.
Warning: Like all things magical, the scroll must be handled with great care. It is content to be handled by a robot or an avatar. But if you try to ``cheat'' by ordering the scroll to move directly, the scroll's magic will be destroyed and you will have to restart the problem.
Check the 6.001 discussion forum for computer-ex-05
|
Look here
for information about the forum.
| |
Suppose we had a poltergeist, who randomly wanders around the labyrinth. The poltergeist picks up objects that are not owned and drops them in other places. Would your search robot work if the world included a poltergeist? If you think it would, explain. If you think it would not, explain. Does it make a difference to your answer whether pebbles are constructed as a subclass of thing vs. as a subclass of named-object? You need not provide a running example to back up your explanation.
Check the 6.001 discussion forum for computer-ex-06
|
Look here
for information about the forum.
| |
Having read through to code for this problem set, you've seen that there are lots of possibilities to extend the world with new kinds of objects. (See, for example, the troll implementation in objtypes.scm.) Create a world of your own, with some novel characters and an interesting story line. Include a short narrative description of your work. We will award prizes for the most interesting stories combined with the cleverest technical ideas. Note that it is more impressive to implement a simple, elegant idea than to amass a pile of characters and places.
Turn in answers to the following questions along with your answers to the questions in the problem set: