CMPUT 325 - Assignment #4

Due Date:    11:59pm, Wednesday  8 Dec 04   via the try program.

You should submit one file containing all your programs along with documentation. (Include answers to dry-lab questions as comments.) Your programs will be run against our solutions to provide feedback to your work. You may submit many versions; the last one before the deadline will be retained as your submission. (If you submit prior to the deadline, but plan to use one or two of your excused late days, you must tell the TAs to disregard your pre-deadline submission... or risk their wrath.) Questions about the try command can be directed to

Assignment Marks: This assignment is worth 12 assignment marks wrt entire course; the total score is 80 marks.
(2/Dec: RG corrected)

Your programs must be readable and understandable as well as correct. You could lose up to 1/2 of the marks for bad style even if your programs are correct. See DocumentationGuidelines, TA'sGuidelines and programming style and marking guideline for an overview of the documentation, testing examples, etc. that we expect.

Your PROLOG code should NOT use cut (!), not (\+), if (->).
(26/Nov: RG added)

In general, each of your Prolog functions may involve more than one clause, and may also involve new predicates.
You should also make sure you code is reasonably efficient -- or at least not incredibly inefficient.
As always, no line should be longer than 80 characters.

No knowledge of Harry Potter is required...

#1 (40 marks)   Cop and Robber; A SECD Machine Problem [Lisp]

Wormtail has been spotted! Due to budget cuts, you are the only remaining paid Minister-of-Magic officer on the force. It is your job to track him down.

For this question we will be simulating a two-player pursuer/prey situation in Lisp. Your job is to write code for the pursuer. This code will be written in SECD instructions, and executed on an SECD interpreter kindly provided by Bob Price and hacked to pieces by Kevin Andrusky.

To begin, please download the following files:
secd.lsp The SECD machine interpreter. Nothing really to see here assignment-wise, but this is essential for running and testing this assignment.
bots.lsp Contains the code for running the simulation. Loads the file secd.lsp automatically - as long as it is in the same directory as bots.lsp.

The SECD machine responds to the following primitive instructions:

nil          - places a nil on the stack
ldf          - loads a function
ldc          - loads a constant
ld (i . j)   - loads element from stack frame (whitespace is important)
ap           - applies a function
rtn          - returns from a function
sel          - branch on test
join         - rejoin main program
dum          - create dummy cell
rap          - fill in dummy with self loop
stop         - halt execution

And the following library functions:

null         - test if something is null
numberp      - test if something is a number
listp        - test if something is a list
atom         - test if something is an atom
eq           - test if two things are eq (by Lisp standards)
car          - take the car
cdr          - take the cdr
cons         - cons two things
eqnum        - test equality pf numbers
gt           - test greater than
lt           - test less than
add          - add _two_ numbers
sub          - subtract _two_ numbers
mul          - multiply _two_ numbers
div          - divide _two_ numbers
rnd          - generate a random number between 1 and the number on the
               top of the stack
out          - output the top of the stack (useful for debugging)

Finally, you may use the primitives brk and cnt to turn on and off (respectively) the debugger. These primitives do not count as an instruction for purposes of parallelizing the agents. However, you should take them out of your code before submitting.

Included in the bots.lsp file is a simple pursuer and a simple prey (they, in fact, do the same thing - just run around the border of the nxn grid that makes up the simulation). You may leave the prey alone (unless you want to make additional work for yourself). The code you should fool around with is that for the pursuer. It is your job to create as intelligent a pursuer as possible. One that will catch the prey in the fewest possible moves.

This pursuer must be written entirely in SECD machine code, using the functions and primitives given above. This code will be executed every time your agent needs to make a decision. You are guaranteed to have three pieces of information:

slot 1 . 1 : what you see in front of you: ('man or 'wall).
slot 1 . 2 : the distance to what you see.
slot 1 . 3 : your saved information from the last step

What goes into the final slot is your own choosing - you may store whatever information you see fit there. It will be saved for you from the last time your code was executed on the SECD machine. More on this below.

Upon reaching stop, your SECD machine should be primed to return one of the following instructions to the simulator (in the form (action . data)).

action      result
------      ------
nop         nothing happens (visiting the donut shop)
left        you turn to the left 90 degrees
right       you turn to the right 90 degrees
step        you move 1 step in the direction you are facing
            [If you are at wall (and facing wall), you will stay where you are]

Before you stop the SECD machine you should ensure that you've stored something in the data field you are returning. This will be placed into slot 1 . 3 the next time your code is executed on the SECD machine. You may assume that, on the first iteration, the value nil will be stored in 1 . 3.

As an example, if I wish to return that I've decided to make the action step, and retain the information
((prey (last-seen-at 3 4) (moves-ago 10) ) (me (currently-at 3 4))), I would ensure that my stack contains only the cons
(step . ((prey (last-seen-at 3 4) (moves-ago 10) ) (me (currently-at 3 4))) when I hit stop.

There is an additional action _nop that you should not return. This is used to indicate steps where your agent has not completed the execution of his code. The agents are run in parallel, and each step corresponds to one clock cycle (or, more specifically, one executed instruction) on the SECD machine. Most of the time your code will still be in the process of executing, a _nop action is the simulator's way of telling you that your code has yet to execute stop and return its action.

As noted above, the simulator will run your code in parallel to the code of your prey (Wormtail). Moves will be made when you return them. Therefore SECD code that takes longer to evaluate (ie. contains more instructions) will result in your agent moving more slowly. In other words, you must carefully consider the tradeoffs between thinking and acting.

The code for your prey will be written by the course TAs. A few of these (more primitive) will be made available for you to test your own agents against. The rest will be held for testing upon submission. You may safely assume that your prey receives only the information you do, namely the nearest obstruction, its distance, and any information he has decided to save from the last execution of the SECD machine.

To start the simulator, invoke the function: (go-bots pur prey halt debug) where pur is the SECD code (embedded in a list) for the pursuer, prey is the SECD code for the prey, halt is one of {step,action,nil}, and debug is one of {t,nil}. See the function (test-bots) in bots.lsp for an example of this.

For halting purposes, "step" means that the simulation will halt after every step (press enter to resume it). "action" means that the simulator will stop when one (or both) of the agents has returned an action. "nil" will prevent the simulator from halting until agent 1 has caught agent 2. Agent 2 is considered caught when he is occupying the same space in the environment that Agent 1 is occupying.

The marks for this question will be awarded in three different areas:

  1. A correct, working agent. You must submit an agent that can move through his environment in a vaguely intelligent manner. For instance, he should not try to walk into walls. He also shouldn't spend too much time at Tim Horton's (ie, lots of NOPs).
  2. An agent capable of capturing our prey (within a certain, large, number of moves). Your agent should be able to capture the prey that we provide. The more you can capture, the better your mark here.
  3. An agent capable of skillfully capturing our prey. Marks here are based upon the technique your agent uses (which should be well-documented with your submission), the speed with which he captures our prey and, since you asked for it, your agent's performance compared to the performance of the agents submitted by your peers.
For submission purposes, we ask only that you provide the SECD code for your agent. This should be provided as:
(setq agent '(
     ;SECD code
Additional Notes
  1. This code is probably best run in Clisp over gcl.
  2. You must be using a VT100 terminal, or an emulator thereof. The screen updates rely on this.
  3. You may edit the code in bots.lsp and secd.lsp. Remember, however, that we will be using our own versions of these for testing.
  4. We may edit the code in bots.lsp and secd.lsp to add functionality. We will not break compatibility with older versions of either file. If these files are changed, it will be announced on the newsgroup.
  5. For this question we do not need test cases. However, we would like a fairly detailed description of the inner workings of your agent.

#2 (15 marks)   Saving the Weasleys (A Constraint Satisfaction Problem) [Prolog package]

While on a quiet visit to the Burrow, Harry Potter suddenly notices that five hands on Mrs. Weasley's famous clock (which tracks the location of her family members) have snapped into position pointing directly at "Mortal Peril". The hands tell the fate of

At this exact moment, an owl -- one regularly used by the Order of the Phoenix -- delivers to Harry a letter straight from Albus Dumbledore, the headmaster of Hogwarts.

It seems Voldemort has had enough of the Weasleys, and ordered their liquidation. Fortunately for Harry, despite having an army of Death Eaters, each of which is able to kill with a single incantation, Voldemort has decided to 'deal with' the Weasleys one at a time, so that he may gloat over their corpses in turn. This gives Harry the chance to heroically save each of the threatened Weasleys in succession.

Unfortunately for Harry, Dumbledore has spent too much of the last few weeks taunting young, aspiring witches and wizards by making them choose blindly between attending Hogwarts and partying with the Dursleys. As a result, his information and preparations for dealing with the possible "Weasley wiping" are somewhat less than complete.

Dumbledore has been able to ascertain the locations to which the five Weasleys have been taken ---

(2/Dec: RG tweaked name of "old house")
-- and has managed to make a portkey for each of these locations out of five distinct items that no muggle would ever pick up: (Note that a portkey will transport a person to a single specific location.) However, he cannot remember which portkey corresponds to which location -- too much butterbeer that evening! In addition, he has determined that, for each rescue, Harry will need one particular item:

Dumbledore's information is partly based upon where the five Weasleys were before being captured by the Death Eaters. However, he was not able to determine this fully, nor was Harry able to remember where exactly the hands of the clock were before snapping to mortal peril (quite a useful device, eh? you know they're in danger, but you no longer know where they are). Harry does remember that the hands were at different locations

for each of the five... but not which one was where.

Finally, Dumbledore has managed to put together the following additional facts:

  1. To rescue Ginny, Harry will need a Nimbus 2000.
  2. The rubber boot will take Harry to George.
  3. Harry will need a prophesy if he is to succeed in saving the Weasley endangered at the Ministry of Magic. Lucky for him that's where they're stored.
  4. Fred has been forced to pay a visit to Askaban prison.
  5. Immediately after saving a Weasley with the aid of Gillyweed, Harry will have to grab himself a Prophesy to save the next one.
  6. Harry will have to use an old tire to get to the Weasley who was at work before being captured by the Death Eaters.
  7. Harry will have to use a time tuner to save the Weasley who was taken from school.
  8. The Weasley held at Voldemort's old house will be killed third.
  9. Percy will be killed first. And rightly so.
  10. The broken rod will take Harry to the Weasley who will be killed either immediately before or immediately after the Weasley who was originally at home.
  11. The cardboard box will take Harry to the Weasley who is to be killed either immediately before or immediately after the Weasley who was taken from school.
  12. The Weasley who was travelling unexpectedly found himself on a Quiddich Pitch.
  13. Before this started, Ron (and Neville) were visiting Neville's parents at the hospital.
  14. Percy will be killed immediately before or immediately after the Weasley that Harry must save using the Gilderoy Lockheart books.

(2/Dec: RG added the immediatelys appearing above.)

For all the good that being able to transform animals into cups, and being able to fly really fast on a mode of transportation that would give Ralph Nader an aneurysm if he were to even comteplate it must be, magic is of no use to Harry here. So, in an act of sheer desperation, Harry turns to you for help.

Given the facts presented above, write a Prolog relation solve(X) that is true when X contains an assignment of death order (what a cheerful question) to name, original location, new location, portkey, and item matching the facts above. This relation must use the Constraint Logic Programming over Finite Domains package (SICS Doumentation, Old Lecture Notes (Dr. Mueller)).

The list X should be of the form:

X = [[_,_,_,_,_],[_,_,_,_,_],[_,_,_,_,_],[_,_,_,_,_],[_,_,_,_,_]].

where each element of X is a list, each element of which is a number corresponding to the order in which Voldemort is planning on killing the Weasleys.
(2/Dec: RG corrected wording above)
The position of this number in each element corresponds to the location where that death will occur, etc. The elements of X are in order of


X = [Name,OldLoc,NewLoc,Portkey,Item].

The values for these parameters can be given as Prolog facts:

name( [ginny, ron, fred, percy, george] ).
old_loc( [work, school, home, travelling, hospital] ).
new_loc( [ministry, askaban, toms_house, quidditch_pitch, dursleys] ).
portkey( [rubber_boot, old_tire, broken_rod, cardboard_box, bar_tab] ).
item( [prophesy, nimbus_2000, gillyweed, time_tuner, book_collection] ).
Please include these facts in your file, as they will not be included by try.

So, for instance, if the first element of X (Name) contained [3,2,5,4,1], this would mean that George will be killed first, followed by Ron, Ginny, Percy and Fred.

Since Harry would like to make use of the information, we would like to print it out in a readable form, not just return the list X. The markers of this assignment would prefer the list X so that we need not actually read your results. The following two predicates can be used to print out X in a readable manner for our favourite boy wizard.


position(X,[Y|Ys],K) :-
	X \== Y,
	K is K1 + 1.
printresults(X,_) :-
	X >= 6.

printresults(X,[A,B,C,D,E]) :-
	X < 6,
	write('#'), write(X), write(') name: '),
	position(X,A,Ap), name(N), position(As,N,Ap),
	write(As),nl,write('    was at: '),
	position(X,B,Bp), old_loc(O), position(Bs,O,Bp),
	write(Bs),nl,write('    now at: '),
	position(X,C,Cp), new_loc(P), position(Cs,P,Cp),
	write(Cs),nl,write('    portkey: '),
	position(X,D,Dp), portkey(Q), position(Ds,Q,Dp),
	write(Ds),nl,write('    item: '),
	position(X,E,Ep), item(R), position(Es,R,Ep),
	X1 is X + 1,

This can then be called as printresults(1,X) immediately after doing the labeling.

Help Harry fill in the gaps in Dumbledore's information and save the Weasleys -- yes, even Percy. And remember: where magic fails, Prolog succeeds!

#3 (15 marks)  Planning Problem [Prolog]

Cauldron (aka "water jug") A has capacity of 5 liters, and cauldron B has a capacity of 2 liters.  We have 4 operators:

In general, we want to find the shortest sequence of these operators that "transforms" one state to another -- perhaps changing from the state where cauldronA is filled and cauldronB is empty, to the state where cauldronB has exactly 1 liter (and cauldronA's contents is irrelevant).

You should define the bestOpSeq( Start, Finish, OpSeq ) predicate that is true when OpSeq is a shortest sequence of operators required to get from the state Start to the state Finish; eg, bestOpSeq( [5,0], [_,1], OpSeq ). You may assume the first two arguments are specified (note that the second argument may involve variables).

To do this, you may want to define the trajectory( States, Operators ) predicate, where

In general, the state represented by State_i is the result of applying the sequence of operations [op_i, ..., op_1] to the initial state, here [5,0]. Eg, applying [empA,pourAB] to [5,0] would pour cauldronA's contents into cauldronB, resulting in the [3,2] state, then emptying the contents of cauldronA, which yields [0,2], which is the value of state_2 shown above.

You will need clauses describing each of 4 operators. It will also help to define the "step" predicate, where step( NewState, NewOp, State ) holds when NewState is the state obtained by applying the operator NewOp to the state State.

Hint: Be care to avoid "looping" here -- ie, your system should avoid visiting the same state more than once. This means your code should avoid sequences like " ..., pourAB, pourBA, ..."; and should not apply "empA" when cauldronA is already empty, etc. For this reason, you may want to (instead) define step( NewState, NewOp, State, Op ), where Op was the operator used to produce this State.

(6/Dec: RG added following example -- taken from newgroup)
Your implementation should allow variables in the 2nd argument. For instance,

In each case, there may be more than one solution of the same length, so you need not match my OpSeq. In addition, any state of X with the same length, OpSeq can appear in any order (within the collection of Xs with equal length OpSeqs).
#4 (5 marks)  Bayes Rule [Dry Lab]
Suppose Cauldron#1 contains 10 frogs and 5 newts, and Cauldron#2 contains 7 frogs and 5 newts. One of the cauldrons is chosen at random (with equal probability) and an item is selected from the cauldron and found to be an frog. Find the probability that the frog came from Cauldron#1.
(Hint: Use Bayes' theorem!)

#5 (5 marks)  Conditioning Events [Dry Lab]
Dumbledore (a powerful wizard) shows you three sealed envelopes, and tells us exactly one contains an admission letter to Hogwarts (which is good), while the other two are invitations to a party with the Dursleys (which is very very bad). You select one; call it A. Before you open A, Dumbledore opens one of the unpicked envelopes (say B), and shows you that it is an invitation to the Dursley's party. He then gives you a choice: either keep your letter A, or exchange it for the other unopened letter, C.

What should you do --- open your original A or instead switch and open C? You may assume that Dumbledore always shows a Dursley letter and gives this option of switching.

(Hint: Feel free to implement a simulation, to verify your answer.)