# 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))))