Note: this assignment is structured on the excellent material prepared by Andrew Blair, from UNSW, for the cs3411 subject "Artifical Intelligence". But where as Dr. Blair uses JAVA, we will use LISP.
For this project you will be implementing an agent to play a simple text-based adventure game. The agent is required to move around a rectangular environment, collecting tools and avoiding (or removing) obstacles along the way. The obstacles and tools within the environment are represented as follows:
Obstacles Tools
| B | big bad bush | a | axe |
| - | door | k | key |
| * | wall | d | dynamite |
| ~ | water | g | gold |
Note: bushes are impassible (big, bad, thorns, posionious).
The agent will be represented by one of the characters
^, v, < or >,
depending on which direction it is pointing.
The agent is capable of the following instructions:
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
When it executes an L or R instruction, the agent remains in the same location and only its direction changes. When it executes an F instruction, the agent attempts to move a single step in whichever direction it is pointing. The F instruction will fail (have no effect) if there is a wall, bush or door directly in front of the agent; if the agent moves forward into the water, it will fall in and drown.
When the agent moves to a location occupied by a tool, it automatically picks up the tool. The agent may use a C, O or B instruction to remove an obstacle immediately in front of it, if it is carrying the appropriate tool. A bush may be removed with a C (chop) instruction, if an axe is held. A door may be removed with an O (open) instruction, if a key is held. A wall, bush or door may be removed with a B (blast) instruction, if dynamite is held.
Note:
To win the game, the agent must pick up the gold and then return to its initial location.
Running
(load "iccle") (make 'game) ; the game loads
Then, to test the game, use
(test-stagger)
at which point, 10 times the agent walks to a random place. You should then see something like this:
~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~ ~~ B B k ~~ ~~ *** *** ~~ ~~*-* v *-*~~ ~~ ** ** ~~ ~~ g ** d ** a ~~ ~~ BB BB ~~ ~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~ ~~ B B k ~~ ~~ *** v *** ~~ ~~*-* *-*~~ ~~ ** ** ~~ ~~ g ** d ** a ~~ ~~ BB BB ~~ ~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~ ~~ B B k ~~ ~~ *** v *** ~~ ~~*-* *-*~~ ~~ ** ** ~~ ~~ g ** d ** a ~~ ~~ BB BB ~~ ~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~ ~~ B B k ~~ ~~ *** v *** ~~ ~~*-* *-*~~ ~~ ** ** ~~ ~~ g ** d ** a ~~ ~~ BB BB ~~ ~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~ ~~ B B k ~~ ~~ *** *** ~~ ~~*-* v *-*~~ ~~ ** ** ~~ ~~ g ** d ** a ~~ ~~ BB BB ~~ ~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~ ~~ B B k ~~ ~~ *** *** ~~ ~~*-* v *-*~~ ~~ ** ** ~~ ~~ g ** d ** a ~~ ~~ BB BB ~~ ~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~ ~~ B B k ~~ ~~ *** v *** ~~ ~~*-* *-*~~ ~~ ** ** ~~ ~~ g ** d ** a ~~ ~~ BB BB ~~ ~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~ ~~ B B k ~~ ~~ *** v*** ~~ ~~*-* *-*~~ ~~ ** ** ~~ ~~ g ** d ** a ~~ ~~ BB BB ~~ ~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~ ~~ B B k ~~ ~~ *** v *** ~~ ~~*-* *-*~~ ~~ ** ** ~~ ~~ g ** d ** a ~~ ~~ BB BB ~~ ~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~ ~~ B v B k ~~ ~~ *** *** ~~ ~~*-* *-*~~ ~~ ** ** ~~ ~~ g ** d ** a ~~ ~~ BB BB ~~ ~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~v~~~~~~~~~ ~~ B ~ B k ~~ ~~ *** *** ~~ ~~*-* *-*~~ ~~ ** ** ~~ ~~ g ** d ** a ~~ ~~ BB BB ~~ ~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~
(Note that I've just drowned- that's a bug you need to fix.)
The code should run in two modes:
Enter Action:At this prompt, one of L,R,F,C,O,B is a valid entry.
Under the hood, the two modes share the same code. If you look at lib/game/stagger.lisp we see that the actual move function is
(defun stagger1 (board) (move-to (any (empty-neighbors board)) board))
Breaking that down, we can guess that
So if we replace any with a function (say) what2do-batch or what2do-interactive, then you've implemented the two modes (so both modes just look at the list of current neighbors, and returns on them).
Now how that is done is up to you but here are some "might be good ideas" that you could try:
We'll call this explore, not stagger cause one day soon, this will stop roaming around drunkedly:
(defun explore (board &optional (what2do #'what2do=any))
(move-to (funcall what2do (empty-neighbors board) board)
board))
(defun what2do=any (options board)
(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
)))
(defun what2do=batch (options board)
....
)
Writing an Agent
You may assume that the environment is no larger than 80 by 80, and that it is totally surrounded by water, so there is no confusion about where the environment begins and ends.
Additional examples of input and output files will be provided in the directory lib/game/eg.
Here, we explore the code offered in http://unbox.org/wisp/var/timm/10/ai/src/.
Two useful idioms is to store constants in one box and things that change in another.
The working memory is stuff you zap before the next run. And by resetting the working memory, everything goes back to some initial useful initial state.
(defstruct wm "runtime working memory" (toolong 1000) board) (defparameter *w* (make-wm)) (defun zap () (setf *w* (make-wm)))
Working memory should be kept separate to the things that never change. For GAMELAND, these are the size of infinity and a bunch of characters that map to types in our system:
(defstruct fixed
"fixed stuff"
(inf most-positive-fixnum)
(ninf (* -1 most-positive-fixnum))
(version 0.01)
(width 21) ; counting from zero
(height 10) ; counting from zero
(chars '((#\a . axe)
(#\k . key)
(#\d . dynamite)
(#\g . gold)
(#\B . bush)
(#\- . door)
(#\. . blank)
(#\* . wall)
(#\ . blank)
(#\~ . water)
(#\^ . player)
(#\> . player)
(#\v . player)
(#\< . player )))
(steps '( ;deltax deltay
(#\^ 0 -1)
(#\> 1 0)
(#\v 0 1)
(#\< -1 0))))
(defparameter *f* (make-fixed))
Note the "steps". This shows how we can more from the current position.
After the glabls, the next best thing to look at are the data types.
A "point" has slots "x" and "y".
(defstruct point "why isn't this a listp build in?" (x 0) (y 0))
A "board" contains the state of the board, where we can find the current player and the the gold.
(defstruct board g h gold ; position of gold at ; position of player width height (contents (make-grid)) ; an array height * width )
"Make-grid" is short-hand for "return an array of the height and width of the board".
(defun make-grid () (make-array (list (fixed-height *f*) (fixed-width *f*))))
thing
player #\^ #\< #\> #\v has direction, holding
piece has cost=0
blanks #\. #\
blocks has cost=inf, fixedp
bush #\B
door #\-
wall #\*
water #\~ has fixedp=t
tool
axe #\a
key #\k
dynamite #\d
gold #\g
Note that the characters make to types via the "chars" of "*f". There are two use functions for chars:
Contains code to read strings like:
~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~ ~~ B B k ~~ ~~ *** *** ~~ ~~*-* v *-*~~ ~~ ** ** ~~ ~~ g ** d ** a ~~ ~~ BB BB ~~ ~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~
and output "board"s:
(read1)
#S(BOARD
:G NIL
:H NIL
:WIDTH 20
:HEIGHT 9
:GOLD #S(POINT :X 3 :Y 6)
:AT #S(POINT :X 10 :Y 4)
:CONTENTS #2A((#S(WATER :COST 536870911 :FIXEDP T)
#S(WATER :COST 536870911 :FIXEDP T)
#S(WATER :COST 536870911 :FIXEDP T)
...
#S(WATER :COST 536870911 :FIXEDP T))
(#S(WATER :COST 536870911 :FIXEDP T)
#S(WATER :COST 536870911 :FIXEDP T)
...
S(WATER :COST 536870911 :FIXEDP T))
(#S(WATER :COST 536870911 :FIXEDP T)
#S(WATER :COST 536870911 :FIXEDP T)
#S(BLANK :COST 0)
#S(BLANK :COST 0)
#S(BLANK :COST 0)
#S(BLANK :COST 0)
#S(BLANK :COST 0)
#S(BUSH :COST 536870911 :FIXEDP NIL)
#S(BLANK :COST 0)
#S(BLANK :COST 0)
#S(BLANK :COST 0)
#S(BLANK :COST 0)
#S(BLANK :COST 0)
#S(BUSH :COST 536870911 :FIXEDP NIL)
#S(BLANK :COST 0)
#S(BLANK :COST 0)
#S(BLANK :COST 0)
#S(KEY :COST 0)
#S(BLANK :COST 0)
#S(WATER :COST 536870911 :FIXEDP T)
#S(WATER :COST 536870911 :FIXEDP T))
...
)
This file also contains a "board-ok-p" function that checks that the generated board makes sense.
A recally common task is walk around the board. This is simplified by the "walk" macro
(walk (i k cell endp board)
...
)
which calls the body for each "cell" at position "i" and "j" in "board".
The boolean "endp" is true if "cell" is the last cell in the row.
The code in this file pretty-prints a board. It is a nice example of polymorphism in LISP so we show it in its entirity.
(defun onstring (x)
(with-output-to-string (str)
(onstream x str)))
(defmethod onstream ((x blank) &optional (str *standard-output*))
(princ " " str))
(defmethod onstream ((x piece) &optional (str *standard-output*))
(princ (piece->char x) str))
(defmethod onstream ((x board) &optional (str *standard-output*))
(let (sep
(max (1- (fixed-width *f*))))
(format str "~%")
(walk (i j cell endrowp x)
(princ (or sep "") str)
(onstream cell str)
(if endrowp (princ #\Newline str)))))
(defmethod onstream ((x player) &optional (str *standard-output*))
(princ (player-direction x) str))
Shows code for finding the neighbors and empty neighbors of a cell on the board.
Stagger shows code for picking empty neighbors at random, then moving to them. Note that, at each step, "onstream" is called to pretty print the currrent state of the board.