[Next] [Up] [Previous]

Exercises

1. Work out how to add the information that the Northern Line joins Embankment, Charing Cross, Leicester Square, and Tottenham Court Road to the database for the route finding program. What difference will this make to the routes that the program finds from Westminster to Tottenham Court Road and to Warren Street?
2. Could the order in which the map information is stored in the database ever make a difference to the output of the route finding program? If it could, would the difference ever be very important?
3. Work out how to change the route finding program to make more realistic assumptions about travel times. For instance, instead of assuming that it takes 2 minutes to travel between any pair of adjacent stations on any line, the program could use a specific time for each line, or even for each pair of stations. These times would, of course, have to be recorded in advance in the database. Work out suitable modifications of the data representation and of the program in order to use this more detailed information.
4. Suppose the database contains the London Underground map, represented as in section 4.5. What is the apparent purpose of the following procedure, and what might the call to it print out?

       define lines(stat);
   
           vars line;
   
           foreach [[?line ^^stat] connects =] do
   
               line =>
   
           endforeach;
   
           foreach [= connects [?line ^^stat]] do
   
               line =>
   
           endforeach;
   
       enddefine;
   
   
   
       lines([Green Park]);

   Why is the second half of this procedure necessary?

   Write a procedure that prints out all the names of the stations on a given line. Modify it so that instead of printing the information, the station names are returned in a list. Do not worry if a station name appears more than once in the list. (It is quite easy to write a procedure that will remove the extra occurrences.)

5. Draw out the complete game tree for quadripawn; it is not large. For each board state for white, calculate the static evaluation score (using the evaluation function given on page [*]) and the score for 2 move lookahead. If white starts, is there a strategy that guarantees it will never lose?
6. Take a game that you know how to play, perhaps draughts (checkers in the United States) or chess, and draw the game tree for two or three moves from a state in the end game, when there are very few pieces left. Devise a static evaluation function for the game and discover how a minimax program using it would behave in your example.
7. Imagine that you have to build a tower 20 centimetres high using a set of 8 blocks, with the following heights in centimetres: 8, 7, 7, 6, 3, 3, 2, and 1. Clearly this can be done using the blocks of heights 8, 7, 3, and 2 centimetres, but with a larger number of blocks and a higher tower the problem can take a very long time to solve. Try writing a POP-11 program that solves problems like this by computer search. You can assume that the block heights and the target height have been stored in some suitable format in the database.

   Your program will probably proceed by trying different combinations of blocks -- i.e., by effectively asking questions like ``What if the tower includes the block of height 7?'' The program might use the database to store information about which blocks are available and which ones have been tried. This program may be rather easier when you know more POP-11, so you may want to return to it when you have read further along in the book.

[Next] [Up] [Previous]