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 tommy@cs.ualberta.ca
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...
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:
(setq agent '(
;SECD code
)
)
Additional Notes
#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
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 ---
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
Finally, Dumbledore has managed to put together the following additional facts:
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,[X|_],1).
position(X,[Y|Ys],K) :-
X \== Y,
position(X,Ys,K1),
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),
write(Es),nl,nl,
X1 is X + 1,
printresults(X1,[A,B,C,D,E]).
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!
Cauldron (aka "water jug") A has capacity of 5 liters, and cauldron B has a capacity of 2 liters. We have 4 operators:
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
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,
| ?- bestOpSeq([5,0],[X,2],OpSeq). X = 3, OpSeq = [pourAB] ? ; X = 0, OpSeq = [empA,pourAB] ? ; X = 1, OpSeq = [pourAB,empB,pourAB] ? ; no | ?- bestOpSeq([5,0],X,OpSeq). X = [5,0], OpSeq = [] ? ; X = [3,2], OpSeq = [pourAB] ? ; X = [0,0], OpSeq = [empA] ? ; X = [0,2], OpSeq = [empA,pourAB] ? ; X = [3,0], OpSeq = [empB,pourAB] ? ; X = [2,0], OpSeq = [pourBA,empA,pourAB] ? ; X = [1,2], OpSeq = [pourAB,empB,pourAB] ? ; X = [1,0], OpSeq = [empB,pourAB,empB,pourAB] ? ; X = [0,1], OpSeq = [pourAB,empB,pourAB,empB,pourAB] ? ; noIn 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).
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.)