Where the index index into the value array

; This is code to implement the Tic-Tac-Toe example in Chapter 1 of the ; book "Learning by Interacting". Read that chapter before trying to ; understand this code.

; States are lists of two lists and an index, e.g., ((1 2 3) (4 5 6) index), ; where the first list is the location of the X's and the second list is ; the location of the O's. The index is into a large array holding the value ; of the states. There is a one-to-one mapping from index to the lists.

(defun show-state (state)
(let ((X-moves (first state))
(O-moves (second state)))
(format t "~%")
(loop for location in magic-square
for i from 0
do
(format t (cond ((member location X-moves)
" X")
((member location O-moves)
" O")
(t " -")))
(when (= i 5) (format t " ~,3F" (value state))) (when (= 2 (mod i 3)) (format t "~%"))))
(values))

; The value function will be implemented as a big, mostly empty array. Remember ; that a state is of the form (X-locations O-locations index), where the index ; is an index into the value array. The index is computed from the locations. ; Basically, each side gets a bit for each position. The bit is 1 is that side ; has played there. The index is the integer with those bits on. X gets the ; first (low-order) nine bits, O the second nine. Here is the function that ; computes the indices:

(defun init ()
(setq value-table (make-array (* 512 512) :initial-element nil)) (setq initial-state '(nil nil 0))
(set-value initial-state 0.5)
(values))

(defun value (state)
(aref value-table (third state)))

(defun possible-moves (state)
"Returns a list of unplayed locations"
(loop for i from 1 to 9
unless (or (member i (first state)) (member i (second state))) collect i))

(defun random-move (state)
"Returns one of the unplayed locations, selected at random" (let ((possible-moves (possible-moves state)))
(if (null possible-moves)
nil
(nth (random (length possible-moves))
possible-moves))))