Project2a

For 400-level subjects only.

Goals

1. Familiarize yourself with Gameland.
2. Implement match-select-act for Gameland.

   (defun what2do=batch (options board)
     (let ((what-do-you-see    (feature-extraction     board))
           (what-can-you-do    (match what-do-you-see  board))
           (what-is-best-to-do (select what-can-you-do board)))
       (act what-is-best-to-do)))
   

   Hints:

   • This will all be based around the "*banana-ops*" structure seen in class.
   • The "board" will be extended to include a slot storing some working memory.
   • The above will be called by the "combiner" function of some function like "tree-search".
   • "Feature extraction" generates the symbols seen in the "preconds" list.
   • "Match" finds which members of "-ops*" are relevant so some working memory.
   • "Select" will handle the case where "match" finds more than one thing to do. Beam search could be implemented here (e.g. sort all the possibilities and prune the dull ones).
   • "Act" combines the actions proposed by "select" with the current state of the board. This might generate multiple boards which are the "what-ifs" explored by the search algorithm.
3. Collect baseline results on a simple search engine running over the above. These baselines will be used in the next project to compare your performance against other systems.

Coding Notes

File / Directory Standards

Recognize:

• What is specific to the game. These functions should be stored in a new directory called game which will need a game.asd file.
• What is useful in a more general sense to AI. These functions should be stored in a new directory called seeker which will need a seeker.asd file.
• What is useful in a more general sense to LISP programming. These functions should be extensions or changes to LISP101.

With the above, there should be .asd files that show the above separation. So "game.asd" will "depends-on" the "seeker" code and the "seeker" code will "depends-on" your lisp101 code.

A note on testing

I will test the following using a random selection of the boards shown in http://unbox.org/wisp/var/timm/09/ai/lib/game/eg/.

The text in those files should be converted to a board using the following code.

(deftest read1 (&optional (f "game/eg/1"))
   (init-board (file->linesOfChar f))

So you should test your code on all the board in that directory.

Nested Dependencies

Read the following very two paragraphs very carefully. It will save you days of debugging. Honest.

Beware nested dependencies. Because of the pointer forest inside LISP, it is possible that if you run two "what-ifs" then the changes made by the first "what-if" can pollute the reasoning of the second one. Somewhere in your code you will have to take care to copy dataand their contents when generating multiple what-ifs.

For simple lists, the magic call is "(copy-list l)". For structures, it is possible to define a special copier function for that structure (for details, see Destruct Options).

Tasks

Task0: Preliminaries

Read:

• GameLand introductory notes.
• Read GameCode introductory nodes.
• Read the section Problem Search Strategies in search lecture.

Testing Task0

To test task0, I will point to random parts of my Gameland code and ask you "what does this do?"

Task 1: Stop the water damage

cd trunk
make edit  # emacs starts
M-x slime ; slime starts
(load "iccle")
(make 'game) ; the game loads
(test-stagger)

You have to change test-stagger (see trunk/lib/game/stagger.lisp) such that when I stagger around, I do not fall into the water.

Testing Tasks1

Note: to test staggering, I will edit your stagger.lisp and change

(defun stagger (board &optional (n 10)) to
(defun stagger (board &optional (n 100)) 

Task2: Monkey's Banana

Using DFS, BFS, DFID, adapt the tree search algorithm i gave you in class to the monkey/banana problem shown in class (and yes, you to use the (op ...) syntax.

If you answer this question properly then your search engine should be very general and the only place we see domain details is in (op).

Testing Task2

I will run demo-task2 and expect to see a trace generating of the monekey getting the banana. Then, I will edit the "-op" list, run again, and expect a different behaviour.

Task 3: Interaction

The test-stagger function described above is a fully automatic staggerer without human interaction. Implement the following explore functionaility such that if I call

(defun demo-walk2 (&optional (file "game/eg/3"))
  (let ((board (read1 file)))
     (explore board  #'what2do=interactive)))

• L : turn left
• R : turn right
• F : (try to) move forward
• C : (try to) chop down a bush, using an axe
• O : (try to) open a door, using a key
• B : (try to) blast a wall, door or bush, using dynamite

To implememnt interaction, you need to code up the following:

(defun explore (board &optional (what2do #'what2do=any))
  (move-to (funcall what2do (empty-neighbors board) board) 
           board))

(defun what2do=any (options board)
   "this calls the stagger code you implemented above"
   (declare (ignore board)) ; smarter schemes would NOT ignore the board
    (any options))

(defun what2do=interactive (options board)
   (format t "Enter action: ")
   (let ((what2do (read)))
     (if (cando? what2do board)
         ; then return the right option
         ; else, print error and call this function recursively
    )))

Testing Task3

To test task3, I will run demo-walk3 with calls "explore" and try to run into the water or into a bush. You code should not let me do either. Also, if I type something that is not "L R F C O B", your code should just print "?".

Task4: Infer Legal Options

The above code accepts any of "L R F C O B" as an action. This is a mistake since (e.g.) if I am not standing next to a key I can't pick anything up.

The legal actions need to be position dependent. You need functions that query the local space and return only the legal operators. Since we need to do that anyway for the search stuff, we'll do that using the op notation shown in lectures.

In my Problem Search Strategies in search lecture there are some examples of how op structs are generated from a higher level representation (see the way *maze-ops* is generated. Write code that queries the local space and generates the appropriate operators.

Testing Task4

To test task4, I will run demo-walk4, a variant of the above demo-walk-4 which does the same as demo-walk1 but, at each move, it prints the available operator list at each move.

Task 5: Use Legal Options

Change the code of cando? shown above such that the list of legal options is inferred from the output of Task3.

Testing Task5

To test task5, I will run demo-walk5 and now the list of legal inputs "L R F C O B" actually shrinks depending on where I am on the board.

Task 6: Higher-Level Goals

The operators you have generated above are all simple actions like take 1 step, pick up 1 thing, etc. At a higher level there are other operators whose pre-conditions are queries to the board. e.g.

    (op 'sub-goal
        :preconds '(cant-get-to-gold (not goingforkey) (key-at  3 4) (cangetto 3 4))
        :add-list '(going-for-key (goal 3 4)) 
        :del-list '())
    (op 'arrive-at-key
        :preconds '(going-for-key (position 3 4) (goal 3 4))
        :add-list '(pick-up-key)
        :del-list '(going-for-key (goal 3 4)))

Note: these higher level "preconds" like "cant-get-to-gold" are discovered by the feature extractor function, shown above.

Testing Task6

To test task6, I will run demo-walk6 which does the same as the above, it prints the available operator list at each move. But this time, I am expecting to see some higher-level goals.

Task 7: Baseline result

This project is a set up for the next project where you apply different search engines to GameLand and report statistics on what method gets you to the gold and home again, fastest.

To generate a baseline result, implement a depth-first search to get to the gold and get home again.

Testing Task7

To test task7, I will run demo-walk7 which is a fully automatic system which, if we watch, the player will go for the gold and come home.

What's Next?

That's the end of this project. But if you want to get a jump start on the next project:

• Add in BFS, DFID, best, beam search (what heuristic could you impose to determine distance to goal?).
• Make GameLand more evil: open doors can shut; dynamited bushes can grow back, and the tide will ebb and flow so the water sometimes changes as well.
• Add in a home brew search engine of your own ideas that does something tricky that you are proud of.
• Write a report describing Gameland, your code, search, different search engines, and performance results on the different search engines. Comment on how the performance of different search engines change as Gameland goes from evil=0 to evil=lots.