confused about recursion/scope

[fuzzylogic]

Hi there
I'm writing some simple AI algorithms for a simple game (something like tic-tac-toe but with numbers).
I'm trying to use recursion to travel down a tree of potential moves in order to do determine the best route.

I'm getting really jammed up though because each time I step into the next level of recursion, any variable changes I make manipulate previous levels, even if not passed in, I guess because of CLISP's "dynamic scope".

Is there a way to limit the visibility of variables? I've tried using LET blocks, but that doesn't seem to make any difference.

Thanks very much for any assistance

[nuntius]

An ounce of code is worth hours of our guessing... Use the "Code" button over the comment box to insert

Code: Select all

 blocks for better formatting.

Standard beginning: Have you read a book like [url=http://www.gigamonkeys.com/book/]Practical Common Lisp[/url]?

[smithzv]

I'll hazard some guessing.

Dynamic scope could in fact be causing this, but you would have had to go out of your way to declare certain variables as special (either with DEFVAR or DEFPARAMETER or with (DECLARE (SPECIAL MY-VAR)) ). A much more probable reason is that you are using an array (or list or whatever) to express your tic-tac-toe like board, and you are mutating the state of that data structure in your recursion.

Code: Select all

(defun my-func (arr)
  (setf (aref arr 0) nil) )

(let ((array (make-array '(3) :initial-element t)))
  (my-func array)
  (print array) )
==> #(NIL T T)

This is because the symbols ARRAY and ARR both point to the same data structure because of the way Lisp passes arguments to functions; Common Lisp passes arrays (and any data type other than numbers and symbols (are there more?)) by reference. When MY-FUNC changes the data pointed to by ARR, it is also changing the data pointed to by ARRAY, because it is the same data. Other languages handle this differently. NewLisp, for instance, performs implicit copying of all arguments on function calls so ARR and ARRAY point to different data. In more functional languages like Clojure, you have data structures that cannot be mutated, so while they point to the same data, you can't change it. Both of these approaches have associated overhead. In Common Lisp, and most languages, the choice is to pass by reference roughly whenever data isn't costly to copy, and pass by value when it isn't (of course 'costly' is open to interpretation, bignums being an interesting gray area, see the FSet motivation page for an in depth discussion of this: http://common-lisp.net/project/fset/Site/index.html).

If my guess is correct, you can fix your code by the placement of a few COPY-TIC-TAC-TOE-BOARD functions calls in order to explicitly copy your arguments. Of course this is not the prescribed efficient way to do this... If I guess incorrectly, sorry.

[fuzzylogic]

Thanks both for responding, and I'm sorry that I'm responding a few days late. I found a work around to the problem I was having, although I never figured out what was wrong initially.

@nuntius: I'll include my recursive function at the end of this point, although it is lengthy and messy, as I'm not a great programmer and still learning CLISP. I've been slowly reading that book you posted (I found it a couple weeks ago just through searching), but have also been constantly referencing later chapters for extra info.

@smithzv: I didn't declare any special variables as such, so I guess that wasn't the problem. I wasn't having trouble with my board, but I think the problem you brought up was probably the issue.

I'll post the recursive function just below. The function AI sets up a 'route' variable with two symbols, board and score. The board symbol contains a value with whatever the current state of the board is, and the score symbol is defaulted to 0, since no score for that particular route has been calculated.

AI then places a call to a "choose" method (the recursive method), which chooses the best possible route to take, and therefor the next move (or it should anyway, lol).

The problem I WAS having is that I also had a depth symbol attached to the route, which would be incremented every time I called "choose". Choose would then generate all possible moves of that board. If the depth is less than 4, it would loop through each newly generated move, calling "choose" for each one. If the depth has reached 4, choose would then call another function, which calculates the score of that board (or move). That route (with current board and new score) are then passed back to the previous level.

Once all of the scores of those moves are found, choose would calculate which one is the best, and then return to the previous level, and so on. My problem was that each time I went back to the previous level, the depth wouldn't be the right number. It just kept incrementing, no matter what depth I was really at.

I solved the problem by getting rid of depth as a separate symbol for route. Instead, I just pass in an incremented depth each time I call choose. I tried to make it as clear as possible, so sorry if it's hard to understand what I mean. Here's the code:

Code: Select all

(defun ai (board)
	(let
		()
		(princ "I'm thinking...")(terpri)
		(putprop 'route 'board board)
		(putprop 'route 'score 0)
		(if (equal board '(nil nil nil nil nil nil nil nil nil))
			'(nil nil nil nil nil nil 5 nil nil)
			(get (choose 'route 0) 'board))))
		
(defun choose (route depth)
	(let
		()
		(if (equal depth depthlength)
			(putprop route 'score (determine-score (get route 'board)))
			(progn
				(setf child-scores '(-1))
				(setf child-boards (gen-next (get route 'board)))
				(if (equal depth 0)
					(progn
						(setf end nil)
						(loop for i in child-boards
							do (if (check-end i)
								(progn
									(putprop 'route 'board i)
									(setf end t))))))
				(setf child-boards (gen-next (get route 'board)))
				(if (and (not (null child-boards)) (not end))
					(progn
						(loop for i in child-boards
							do (putprop 'temp-route 'board i)
							do (putprop 'temp-route 'score 0)
							do (cond
								((equal (car child-scores) -1) (setf child-scores (list (get (choose 'temp-route (+ depth 1)) 'score))))
								(t (setf child-scores (concatenate 'list child-scores (list (get (choose 'temp-route (+ depth 1)) 'score)))))))
						(setf goal (car child-scores))
						(setf index 0)
						(setf goal-index 0)
							(loop for j in child-scores
								do (if (> j goal)
									(progn
										(setf goal j)
										(setf goal-index index)))
								do (setf index (+ index 1)));))
						(setf child-boards (gen-next (get route 'board)))
						(putprop route 'board (car (nth-cdr goal-index child-boards)))
						(putprop route 'score (car (nth-cdr goal-index child-scores))))
					(putprop route 'score (determine-score (get route 'board))))))
		route))

[ramarren]

still learning CLISP

Common Lisp, which is a specific language in the Lisp family, is usually abbreviated CL. CLISP is a specific implementation of Common Lisp. CL does not contain PUTPROP and it is not a CLISP extension. Posting incomplete code referring to unknown operators is not usually very helpful, and it creates a doubt if you are using a similar, but different Lisp dialects, since they are quite many.

From what I can tell it typically does the equivalent of (setf (get ...)). This is a global property list associated with a symbol, which means that everywhere you are using PUTPROP you are in effect modifying a global variable. Rather than using symbol property lists one would normally use property lists, or alists, or hash-tables, or objects, or something else which is a first class datum, and hence fully local.

Also, you use several variables without declaring them (like CHILD-SCORES and CHILD-BOARDS), which means on most implementations they would be automatically made either globally special or global lexicals. Or you are declaring them as globals in the unshown part of the code, but you said you did not. In any case, they are global.

From the look of this function you have been learning from material either thirty years old (predating Common Lisp ANSI standard) or based on that (professors who learnt Lisp when they were young, maybe?). You should probably focus on PCL to relearn some basics.

[nuntius]

I don't think Ramarran meant that to sound so harsh, but his points are generally accurate.

[Warren Wilkinson]

This problem sounded like fun, so I went ahead and wrote skeleton code for how I would solve it. I hope it will give you some good ideas.

Code: Select all

(defpackage :tictac
  (:use :common-lisp))

(in-package :tictac)

;; Using a vector to represent the board makes access
;; easier and faster e.g. (elt *board* (+ (* 3 x) y))
(defun make-board () (make-array 9 :initial-element nil))
(defun empty-board-p (board) (every #'null board))

;; +search-depth+ controls recursion depth.
(defconstant +search-depth+ 4)

;; Gen-next takes a current board position, and must generate
;; all valid positions that can be made from it. Because its
;; NIL, the game will assume there are never any valid
;; positions, and will be over very soon.
(defun gen-next (board our-turn-p) (declare (ignore board our-turn-p)) nil)

;; A board-score of 0 is neutral. Use negative numbers to communicate
;; a board is BAD, and positive to communicate a board is good.
(defun board-score (board) (declare (ignore board)) 0)
;; Score calculates the boards score then adds the score for the
;;  boards children (upto +search-depth+ deep)  to produce the
;; branches total score.
(defun score (board depth)
  (let ((score (board-score board)))
    (if (= depth +search-depth+)
	score
	(loop for child in (gen-next board (evenp depth)) ;; Even-p means its our move, odd means theirs.
	      do (incf score (score child (1- depth)))
	      finally (return score)))))

;; Choose computes the children for a board and runs SCORE on each
;; one. It returns the board with the highest score, or NIL if
;; there where no boards.
(defun choose (board)
  (caar (sort (loop for child in (gen-next board t) collecting (cons child (score child 0))) #'> :key #'cdr)))
  	
;; AI will return the next board or NIL if the game is over.
(defun ai (board) (format t "~%I'm thinking...") (choose board))

So to use you just have to replace board-score and gen-next with the appropriate functions... I went ahead and made it play tic-tac-toe with this code...

Code: Select all

;; Compute is 5's,
;; Player is 0's.

(flet ((copy-set (board our-turn-p pos)
	 (setf board (copy-seq board))
	 (setf (elt board pos) (if our-turn-p 5 0))
	 board))
  (defun tic-tac-gen-next (board our-turn-p)
    (let ((results nil))
      (loop for i from 0 to (1- 9)
	    unless (elt board i)
	    do (push (copy-set board our-turn-p i) results))
      results)))

(defun line-score-friend (a b c)
  (cond ((and a       b       c       (= 5 a b c)) 100)
	((and a       b       (not c) (= 5 a b))   25)
	((and a       (not b) c       (= 5 a c))   25)
	((and (not a) b       c       (= 5 b c))   25)
	((and a       (not b) (not c) (= 5 a))     10)
	((and (not a) b       (not c) (= 5 b))     10)
	((and (not a) (not b) c       (= 5 c))     10)
	(t 0)))

(defun line-score-foe (a b c)
  (cond ((and a       b       c       (= 0 a b c)) -100)
	((and a       b       (not c) (= 0 a b))   -25)
	((and a       (not b) c       (= 0 a c))   -25)
	((and (not a) b       c       (= 0 b c))   -25)
	((and a       (not b) (not c) (= 0 a))     -10)
	((and (not a) b       (not c) (= 0 b))     -10)
	((and (not a) (not b) c       (= 0 c))     -10)
	(t 0)))
(defun line-score (a b c) (+ (line-score-friend a b c) (line-score-foe a b c)))

(defun tic-tac-board-score (board)
  (+ (line-score-friend (elt board 0) (elt board 1) (elt board 2))
     (line-score-friend (elt board 3) (elt board 4) (elt board 5))
     (line-score-friend (elt board 6) (elt board 7) (elt board 8))

     (line-score-friend (elt board 0) (elt board 3) (elt board 6))
     (line-score-friend (elt board 1) (elt board 4) (elt board 7))
     (line-score-friend (elt board 2) (elt board 5) (elt board 8))

     (line-score-friend (elt board 0) (elt board 4) (elt board 8))
     (line-score-friend (elt board 2) (elt board 4) (elt board 6))))

(defun gen-next (board our-turn-p) (tic-tac-gen-next board our-turn-p))
(defun boad-score (board) (tic-tac-board-score board))

(defun display (board)
  (format t "~%Display: ~a" board)
  (if (null board)
      (format t "~%The game is over.")
      (format t "~%~a    ~a    ~a~%~a    ~a    ~a~%~a    ~a    ~a" 
	      (elt board 0) (elt board 1) (elt board 2) (elt board 3) (elt board 4)
	      (elt board 5) (elt board 6) (elt board 7) (elt board 8))))
	  
(defun run () 
  (format t "~%Would you like to go first?")
  (let ((board (make-board)))
    (unless (eq (read-char) #\y) (setf board (ai board)))
    (loop until (null board)
	  do (display board)
	  do (format t "~%Where would you like to move (0 - 8, q to quit.)?")
	  do (case (read-char)
	       (#\0 (setf (elt board 0) 0) (setf board (ai board)))
	       (#\1 (setf (elt board 1) 0) (setf board (ai board)))
	       (#\2 (setf (elt board 2) 0) (setf board (ai board)))
	       (#\3 (setf (elt board 3) 0) (setf board (ai board)))
	       (#\4 (setf (elt board 4) 0) (setf board (ai board)))
	       (#\5 (setf (elt board 5) 0) (setf board (ai board)))
	       (#\6 (setf (elt board 6) 0) (setf board (ai board)))
	       (#\7 (setf (elt board 7) 0) (setf board (ai board)))
	       (#\8 (setf (elt board 8) 0) (setf board (ai board)))
	       (#\q (return-from run board))))))      

Its not the nicest interface, and you can cheat by playing over the computers moves. It also can't identify when the game has been won. The AI plays to win, but doesn't seem smart enough to block its opponents moves. Perhaps the weight scales are wrong, or my board score calculations suck. In anycase, take a look.