Code

(defconstant player-tokens '(x o x o x o x o x))
(defconstant move-numbers  '(1 2 3 4 5 6 7 8 9))
(defconstant all-runs '((0 1 2)
                        (3 4 5)
                        (6 7 8)
                        (0 3 6)
                        (1 4 7)
                        (2 5 8)
                        (0 4 8)
                        (2 4 6)))

(defclass player ()
  ((name :accessor player-name :initarg :name :initform 'emanon)))

(defclass random-machine-player (player) ())
(defclass human-player (player) ())

(defmethod display ((p random-machine-player))
  (format t "RANDOM MACHINE PLAYER ...~%")
  (format t "name = ~A~%" (player-name p))
  (terpri)
  nil)

(defmethod display ((p human-player))
  (format t "HUMAN PLAYER ...~%")
  (format t "name = ~A~%" (player-name p))
  (terpri)
  nil)

(defmethod make-move ((p random-machine-player) (report t))
  (let ((move (select *avail*)))
    (when report
      (format t "BEGIN RANDOM PLAYER MOVE ...~%")
      (format t "randomly selecting ~A for my move ~%" move)
      (format t "END RANDOM PLAYER MOVE ...~%"))
    (setf *avail* (remove move *avail*))
    move))

(defmethod make-move ((p human-player) (report t))
  (when report
    (format t "BEGIN HUMAN PLAYER MOVE ...~%"))
  (format t "Please select a move from ~A~%" *avail*)
  (let ((move (read)))
    (if (not (member move *avail*))
      (make-move p)
      (setf *avail* (remove move *avail*)))
    (when report
      (format t "END HUMAN PLAYER MOVE~%"))
    move))

(defmethod generic-play ((x player) (o player) (report t) &aux move)
  (setf *avail*       '(nw n ne w c e sw s se))
  (setf *play-so-far* ())
  (dolist (player '(x o x o x o x o x))
    (when (or report (equal (type-of o) 'human-player-machine))
      (visualize *play-so-far*))
    (cond
     ((eq player 'x) (setf move (make-move x report)))
     ((eq player 'o) (setf move (make-move o report))))
    (setf *play-so-far* (snoc move *play-so-far*))
    (when (game-over-p *play-so-far*)
      (return nil)))
  *play-so-far*)

(defmethod game-over-p ((play list))
  (cond
   ((line-p (odd play))  'w)
   ((line-p (even play)) 'l)
   ((= (length play) 9)  'd)))

(defmethod odd ((l list))
  (cond
   ((null l) ())
   ((null (cdr l)) (list (car l)))
   (t (cons (car l)
            (odd (cddr l))))))

(defmethod even ((l list))
  (cond
   ((null l) ())
   ((null (cdr l)) ())
   (t (cons (cadr l)
            (even (cddr l))))))

(defun line (&rest line)
  (or (subsetp '(nw n ne) line)
      (subsetp '( w c  e) line)
      (subsetp '(sw s se) line)
      (subsetp '(nw w sw) line)
      (subsetp '(n  c s ) line)
      (subsetp '(ne e se) line)
      (subsetp '(nw c se) line)
      (subsetp '(ne c sw) line)))

(defmethod line-p ((l list))
  (cond
   ((< (length l) 3)
    nil)

   ((= (length l) 3)
    (line (first  l)
          (second l)
          (third  l)))

   ((= (length l) 4)
    (or
     (line (first l)  (second l) (third l))
     (line (first l)  (second l) (fourth l))
     (line (first l)  (third l)  (fourth l))
     (line (second l) (third l)  (fourth l))))

   ((= (length l) 5)
    (or
     (line (first l)  (second l) (third l))
     (line (first l)  (second l) (fourth l))
     (line (first l)  (second l) (fifth l))
     (line (first l)  (third l)  (fourth l))
     (line (first l)  (third l)  (fifth l))
     (line (second l) (third l)  (fourth l))
     (line (second l) (third l) (fifth l))
     (line (second l) (fourth l) (fifth l))
     (line (third l) (fourth l) (fifth l))))))

(defmethod demo-random-random ()
  (let* ((x (make-instance 'random-machine-player))
         (o (make-instance 'random-machine-player))
         (p (generic-play x o t)))
    (format t "~A~%" p)
    (visualize p)
    (format t "~A~%" (game-over-p p))
    nil))

(defmethod demo-random-human ()
  (let* ((x (make-instance 'random-machine-player))
         (o (make-instance 'human-player))
         (p (generic-play x o t)))
    (format t "~A~%" p)
    (visualize p)
    (format t "~A~%" (game-over-p p))
    nil))

(defmethod demo-human-random ()
  (let* ((x (make-instance 'human-player))
         (o (make-instance 'random-machine-player))
         (p (generic-play x o t)))
    (format t "~A~%" p)
    (visualize p)
    (format t "~A~%" (game-over-p p))
    nil))


(defmethod multi-nth ((ns list) (the-list list))
  (mapcar (lambda (n) (nth n the-list))
          ns))

(defmethod get-all-runs ((play list))
  (mapcar (lambda (ns) (multi-nth ns play))
          all-runs))

(defmethod take ((n integer) (the-list list))
  (if (or (= n 0)
          (null the-list))
    nil
    (cons (car the-list)
          (take (1- n)
                (cdr the-list)))))

(defmethod sort-by-nth ((list-of-lists list) (n integer) (predicate function))
  (sort list-of-lists
        (lambda (x y) (funcall predicate (nth n x) (nth n y)))))

(defmethod select ((the-list list))
  (let ((n (random (length the-list))))
    (nth n the-list)))

(defmethod snoc (element (the-list list))
  (append the-list
          (list element)))

(defmethod play ()
  (let* ((play  ())
         (avail '(nw n ne w c e sw s se)))
    (dolist (player player-tokens)
      (cond
       ((eq player 'x)
        (setf move (select avail))
        (setf avail (remove move avail))
        (setf play (snoc move play)))

       ((eq player 'o)
        (setf move (select avail))
        (setf avail (remove move avail))
        (setf play (snoc move play)))))
    play))

(defmethod print-row ((row list))
  (format t "~{~{~A~D~}~^║~}~%" row))

(defmethod print-row-sep ()
  (format t "══╬══╬══~%"))

(defmethod outcome-move ((tokens-moves list))
  (let ((tokens (mapcar #'first  tokens-moves))
        (moves  (mapcar #'second tokens-moves)))
    (list (apply   #'max moves)
          (outcome tokens))))

(defmethod outcome ((tokens list))
  (cond
   ((equal tokens '(x x x)) 'w)
   ((equal tokens '(o o o)) 'l)
   (T                       nil)))

(defmethod sort-by-position ((play list))
  (let ((location-token-move (mapcar #'list play
                                            player-tokens
                                            move-numbers)))
    (mapcar #'cdr
            (mapcar (lambda (location)
                      (assoc location location-token-move))
                    '(nw n ne
                       w c  e
                      sw s se)))))

(defmethod sort-by-position* ((play list))
  (let ((location-token-move (mapcar #'list play
                                            player-tokens
                                            move-numbers)))
    (mapcar #'cdr
            (mapcar (lambda (location)
                      (or (assoc location location-token-move)
                          (list location " " " ")))
                    '(nw n ne
                       w c  e
                      sw s se)))))

(defmethod visualize ((play list))
  (let ((positions (sort-by-position* play)))
    (print-row (subseq positions 0 3))
    (print-row-sep)
    (print-row (subseq positions 3 6))
    (print-row-sep)
    (print-row (subseq positions 6 9)))
  nil)

(defmethod analyze ((play list))
  (let* ((positions      (sort-by-position play))
         (tokens-moves   (get-all-runs positions))
         (outcomes-moves (mapcar #'outcome-move tokens-moves))
         (winning-moves  (remove-if (lambda (x) (null (second x)))
                                    outcomes-moves)))
    (if winning-moves
      (second (first (sort-by-nth winning-moves 0 #'<)))
      'D)))

(defmethod demo-va ()
  (let ((p (play)))
    (format t "~A~%" p)
    (visualize p)
    (format t "~A~%" (analyze p)))
  nil)

(defmethod stats ((n integer) (demo t))
  (when demo
    (format t "BEGIN GATHERING STATISTICS ...~%"))
  (let ((w 0)
        (l 0)
        (d 0))
    (dotimes (i n)
      (let* ((p (play))
             (result (analyze p)))
        (when demo
          (format t "~A~%" p)
          (visualize p)
          (format t "~A~%" result))
        (cond
         ((eq result 'w) (setf w (1+ w)))
         ((eq result 'l) (setf l (1+ l)))
         ((eq result 'd) (setf d (1+ d))))))
    (let ((results (mapcar #'probability
                           (list w l d)
                           (list n n n))))
      (when demo
        (format t "END GATHERING STATISTICS~%"))
      (mapcar #'list
              '(w l d)
              results))))

(defmethod probability ((special integer) (total integer))
  (float (/ special
            total)))

Demo

[1]> (load "ttt3.l")
;; Loading file ttt3.l ...
;; Loaded file ttt3.l
T
[2]> (demo-random-random)
      
══╬══╬══
      
══╬══╬══
      
BEGIN RANDOM PLAYER MOVE ...
randomly selecting NE for my move 
END RANDOM PLAYER MOVE ...
    X1
══╬══╬══
      
══╬══╬══
      
BEGIN RANDOM PLAYER MOVE ...
randomly selecting S for my move 
END RANDOM PLAYER MOVE ...
    X1
══╬══╬══
      
══╬══╬══
  O2  
BEGIN RANDOM PLAYER MOVE ...
randomly selecting W for my move 
END RANDOM PLAYER MOVE ...
    X1
══╬══╬══
X3    
══╬══╬══
  O2  
BEGIN RANDOM PLAYER MOVE ...
randomly selecting E for my move 
END RANDOM PLAYER MOVE ...
    X1
══╬══╬══
X3  O4
══╬══╬══
  O2  
BEGIN RANDOM PLAYER MOVE ...
randomly selecting NW for my move 
END RANDOM PLAYER MOVE ...
X5  X1
══╬══╬══
X3  O4
══╬══╬══
  O2  
BEGIN RANDOM PLAYER MOVE ...
randomly selecting N for my move 
END RANDOM PLAYER MOVE ...
X5O6X1
══╬══╬══
X3  O4
══╬══╬══
  O2  
BEGIN RANDOM PLAYER MOVE ...
randomly selecting SE for my move 
END RANDOM PLAYER MOVE ...
X5O6X1
══╬══╬══
X3  O4
══╬══╬══
  O2X7
BEGIN RANDOM PLAYER MOVE ...
randomly selecting C for my move 
END RANDOM PLAYER MOVE ...
(NE S W E NW N SE C)
X5O6X1
══╬══╬══
X3O8O4
══╬══╬══
  O2X7
L
NIL
[3]> (demo-random-random)
      
══╬══╬══
      
══╬══╬══
      
BEGIN RANDOM PLAYER MOVE ...
randomly selecting E for my move 
END RANDOM PLAYER MOVE ...
      
══╬══╬══
    X1
══╬══╬══
      
BEGIN RANDOM PLAYER MOVE ...
randomly selecting C for my move 
END RANDOM PLAYER MOVE ...
      
══╬══╬══
  O2X1
══╬══╬══
      
BEGIN RANDOM PLAYER MOVE ...
randomly selecting S for my move 
END RANDOM PLAYER MOVE ...
      
══╬══╬══
  O2X1
══╬══╬══
  X3  
BEGIN RANDOM PLAYER MOVE ...
randomly selecting W for my move 
END RANDOM PLAYER MOVE ...
      
══╬══╬══
O4O2X1
══╬══╬══
  X3  
BEGIN RANDOM PLAYER MOVE ...
randomly selecting SW for my move 
END RANDOM PLAYER MOVE ...
      
══╬══╬══
O4O2X1
══╬══╬══
X5X3  
BEGIN RANDOM PLAYER MOVE ...
randomly selecting NW for my move 
END RANDOM PLAYER MOVE ...
O6    
══╬══╬══
O4O2X1
══╬══╬══
X5X3  
BEGIN RANDOM PLAYER MOVE ...
randomly selecting SE for my move 
END RANDOM PLAYER MOVE ...
(E C S W SW NW SE)
O6    
══╬══╬══
O4O2X1
══╬══╬══
X5X3X7
W
NIL
[4]> (demo-random-random)
      
══╬══╬══
      
══╬══╬══
      
BEGIN RANDOM PLAYER MOVE ...
randomly selecting S for my move 
END RANDOM PLAYER MOVE ...
      
══╬══╬══
      
══╬══╬══
  X1  
BEGIN RANDOM PLAYER MOVE ...
randomly selecting NE for my move 
END RANDOM PLAYER MOVE ...
    O2
══╬══╬══
      
══╬══╬══
  X1  
BEGIN RANDOM PLAYER MOVE ...
randomly selecting C for my move 
END RANDOM PLAYER MOVE ...
    O2
══╬══╬══
  X3  
══╬══╬══
  X1  
BEGIN RANDOM PLAYER MOVE ...
randomly selecting NW for my move 
END RANDOM PLAYER MOVE ...
O4  O2
══╬══╬══
  X3  
══╬══╬══
  X1  
BEGIN RANDOM PLAYER MOVE ...
randomly selecting SW for my move 
END RANDOM PLAYER MOVE ...
O4  O2
══╬══╬══
  X3  
══╬══╬══
X5X1  
BEGIN RANDOM PLAYER MOVE ...
randomly selecting N for my move 
END RANDOM PLAYER MOVE ...
(S NE C NW SW N)
O4O6O2
══╬══╬══
  X3  
══╬══╬══
X5X1  
L
NIL
[5]> (demo-random-random)
      
══╬══╬══
      
══╬══╬══
      
BEGIN RANDOM PLAYER MOVE ...
randomly selecting W for my move 
END RANDOM PLAYER MOVE ...
      
══╬══╬══
X1    
══╬══╬══
      
BEGIN RANDOM PLAYER MOVE ...
randomly selecting E for my move 
END RANDOM PLAYER MOVE ...
      
══╬══╬══
X1  O2
══╬══╬══
      
BEGIN RANDOM PLAYER MOVE ...
randomly selecting NW for my move 
END RANDOM PLAYER MOVE ...
X3    
══╬══╬══
X1  O2
══╬══╬══
      
BEGIN RANDOM PLAYER MOVE ...
randomly selecting NE for my move 
END RANDOM PLAYER MOVE ...
X3  O4
══╬══╬══
X1  O2
══╬══╬══
      
BEGIN RANDOM PLAYER MOVE ...
randomly selecting N for my move 
END RANDOM PLAYER MOVE ...
X3X5O4
══╬══╬══
X1  O2
══╬══╬══
      
BEGIN RANDOM PLAYER MOVE ...
randomly selecting C for my move 
END RANDOM PLAYER MOVE ...
X3X5O4
══╬══╬══
X1O6O2
══╬══╬══
      
BEGIN RANDOM PLAYER MOVE ...
randomly selecting SE for my move 
END RANDOM PLAYER MOVE ...
X3X5O4
══╬══╬══
X1O6O2
══╬══╬══
    X7
BEGIN RANDOM PLAYER MOVE ...
randomly selecting SW for my move 
END RANDOM PLAYER MOVE ...
(W E NW NE N C SE SW)
X3X5O4
══╬══╬══
X1O6O2
══╬══╬══
O8  X7
L
NIL
[6]> (demo-random-random)
      
══╬══╬══
      
══╬══╬══
      
BEGIN RANDOM PLAYER MOVE ...
randomly selecting E for my move 
END RANDOM PLAYER MOVE ...
      
══╬══╬══
    X1
══╬══╬══
      
BEGIN RANDOM PLAYER MOVE ...
randomly selecting W for my move 
END RANDOM PLAYER MOVE ...
      
══╬══╬══
O2  X1
══╬══╬══
      
BEGIN RANDOM PLAYER MOVE ...
randomly selecting NW for my move 
END RANDOM PLAYER MOVE ...
X3    
══╬══╬══
O2  X1
══╬══╬══
      
BEGIN RANDOM PLAYER MOVE ...
randomly selecting NE for my move 
END RANDOM PLAYER MOVE ...
X3  O4
══╬══╬══
O2  X1
══╬══╬══
      
BEGIN RANDOM PLAYER MOVE ...
randomly selecting S for my move 
END RANDOM PLAYER MOVE ...
X3  O4
══╬══╬══
O2  X1
══╬══╬══
  X5  
BEGIN RANDOM PLAYER MOVE ...
randomly selecting SE for my move 
END RANDOM PLAYER MOVE ...
X3  O4
══╬══╬══
O2  X1
══╬══╬══
  X5O6
BEGIN RANDOM PLAYER MOVE ...
randomly selecting SW for my move 
END RANDOM PLAYER MOVE ...
X3  O4
══╬══╬══
O2  X1
══╬══╬══
X7X5O6
BEGIN RANDOM PLAYER MOVE ...
randomly selecting C for my move 
END RANDOM PLAYER MOVE ...
X3  O4
══╬══╬══
O2O8X1
══╬══╬══
X7X5O6
BEGIN RANDOM PLAYER MOVE ...
randomly selecting N for my move 
END RANDOM PLAYER MOVE ...
(E W NW NE S SE SW C N)
X3X9O4
══╬══╬══
O2O8X1
══╬══╬══
X7X5O6
D
NIL
[7]> (demo-random-random)
      
══╬══╬══
      
══╬══╬══
      
BEGIN RANDOM PLAYER MOVE ...
randomly selecting SW for my move 
END RANDOM PLAYER MOVE ...
      
══╬══╬══
      
══╬══╬══
X1    
BEGIN RANDOM PLAYER MOVE ...
randomly selecting S for my move 
END RANDOM PLAYER MOVE ...
      
══╬══╬══
      
══╬══╬══
X1O2  
BEGIN RANDOM PLAYER MOVE ...
randomly selecting E for my move 
END RANDOM PLAYER MOVE ...
      
══╬══╬══
    X3
══╬══╬══
X1O2  
BEGIN RANDOM PLAYER MOVE ...
randomly selecting NW for my move 
END RANDOM PLAYER MOVE ...
O4    
══╬══╬══
    X3
══╬══╬══
X1O2  
BEGIN RANDOM PLAYER MOVE ...
randomly selecting NE for my move 
END RANDOM PLAYER MOVE ...
O4  X5
══╬══╬══
    X3
══╬══╬══
X1O2  
BEGIN RANDOM PLAYER MOVE ...
randomly selecting SE for my move 
END RANDOM PLAYER MOVE ...
O4  X5
══╬══╬══
    X3
══╬══╬══
X1O2O6
BEGIN RANDOM PLAYER MOVE ...
randomly selecting W for my move 
END RANDOM PLAYER MOVE ...
O4  X5
══╬══╬══
X7  X3
══╬══╬══
X1O2O6
BEGIN RANDOM PLAYER MOVE ...
randomly selecting C for my move 
END RANDOM PLAYER MOVE ...
(SW S E NW NE SE W C)
O4  X5
══╬══╬══
X7O8X3
══╬══╬══
X1O2O6
L
NIL
[8]> (demo-random-human)
      
══╬══╬══
      
══╬══╬══
      
BEGIN RANDOM PLAYER MOVE ...
randomly selecting SE for my move 
END RANDOM PLAYER MOVE ...
      
══╬══╬══
      
══╬══╬══
    X1
BEGIN HUMAN PLAYER MOVE ...
Please select a move from (NW N NE W C E SW S)
nw
END HUMAN PLAYER MOVE
O2    
══╬══╬══
      
══╬══╬══
    X1
BEGIN RANDOM PLAYER MOVE ...
randomly selecting E for my move 
END RANDOM PLAYER MOVE ...
O2    
══╬══╬══
    X3
══╬══╬══
    X1
BEGIN HUMAN PLAYER MOVE ...
Please select a move from (N NE W C SW S)
c
END HUMAN PLAYER MOVE
O2    
══╬══╬══
  O4X3
══╬══╬══
    X1
BEGIN RANDOM PLAYER MOVE ...
randomly selecting SW for my move 
END RANDOM PLAYER MOVE ...
O2    
══╬══╬══
  O4X3
══╬══╬══
X5  X1
BEGIN HUMAN PLAYER MOVE ...
Please select a move from (N NE W S)
w
END HUMAN PLAYER MOVE
O2    
══╬══╬══
O6O4X3
══╬══╬══
X5  X1
BEGIN RANDOM PLAYER MOVE ...
randomly selecting N for my move 
END RANDOM PLAYER MOVE ...
O2X7  
══╬══╬══
O6O4X3
══╬══╬══
X5  X1
BEGIN HUMAN PLAYER MOVE ...
Please select a move from (NE S)
s
END HUMAN PLAYER MOVE
O2X7  
══╬══╬══
O6O4X3
══╬══╬══
X5O8X1
BEGIN RANDOM PLAYER MOVE ...
randomly selecting NE for my move 
END RANDOM PLAYER MOVE ...
(SE NW E C SW W N S NE)
O2X7X9
══╬══╬══
O6O4X3
══╬══╬══
X5O8X1
W
NIL
[9]> (demo-random-human)
      
══╬══╬══
      
══╬══╬══
      
BEGIN RANDOM PLAYER MOVE ...
randomly selecting SE for my move 
END RANDOM PLAYER MOVE ...
      
══╬══╬══
      
══╬══╬══
    X1
BEGIN HUMAN PLAYER MOVE ...
Please select a move from (NW N NE W C E SW S)
nw
END HUMAN PLAYER MOVE
O2    
══╬══╬══
      
══╬══╬══
    X1
BEGIN RANDOM PLAYER MOVE ...
randomly selecting N for my move 
END RANDOM PLAYER MOVE ...
O2X3  
══╬══╬══
      
══╬══╬══
    X1
BEGIN HUMAN PLAYER MOVE ...
Please select a move from (NE W C E SW S)
w
END HUMAN PLAYER MOVE
O2X3  
══╬══╬══
O4    
══╬══╬══
    X1
BEGIN RANDOM PLAYER MOVE ...
randomly selecting E for my move 
END RANDOM PLAYER MOVE ...
O2X3  
══╬══╬══
O4  X5
══╬══╬══
    X1
BEGIN HUMAN PLAYER MOVE ...
Please select a move from (NE C SW S)
sw
END HUMAN PLAYER MOVE
(SE NW N W E SW)
O2X3  
══╬══╬══
O4  X5
══╬══╬══
O6  X1
L
NIL
[10]> (demo-random-human)
      
══╬══╬══
      
══╬══╬══
      
BEGIN RANDOM PLAYER MOVE ...
randomly selecting SE for my move 
END RANDOM PLAYER MOVE ...
      
══╬══╬══
      
══╬══╬══
    X1
BEGIN HUMAN PLAYER MOVE ...
Please select a move from (NW N NE W C E SW S)
n
END HUMAN PLAYER MOVE
  O2  
══╬══╬══
      
══╬══╬══
    X1
BEGIN RANDOM PLAYER MOVE ...
randomly selecting NE for my move 
END RANDOM PLAYER MOVE ...
  O2X3
══╬══╬══
      
══╬══╬══
    X1
BEGIN HUMAN PLAYER MOVE ...
Please select a move from (NW W C E SW S)
e
END HUMAN PLAYER MOVE
  O2X3
══╬══╬══
    O4
══╬══╬══
    X1
BEGIN RANDOM PLAYER MOVE ...
randomly selecting S for my move 
END RANDOM PLAYER MOVE ...
  O2X3
══╬══╬══
    O4
══╬══╬══
  X5X1
BEGIN HUMAN PLAYER MOVE ...
Please select a move from (NW W C SW)
sw
END HUMAN PLAYER MOVE
  O2X3
══╬══╬══
    O4
══╬══╬══
O6X5X1
BEGIN RANDOM PLAYER MOVE ...
randomly selecting NW for my move 
END RANDOM PLAYER MOVE ...
X7O2X3
══╬══╬══
    O4
══╬══╬══
O6X5X1
BEGIN HUMAN PLAYER MOVE ...
Please select a move from (W C)
c
END HUMAN PLAYER MOVE
X7O2X3
══╬══╬══
  O8O4
══╬══╬══
O6X5X1
BEGIN RANDOM PLAYER MOVE ...
randomly selecting W for my move 
END RANDOM PLAYER MOVE ...
(SE N NE E S SW NW C W)
X7O2X3
══╬══╬══
X9O8O4
══╬══╬══
O6X5X1
D
NIL
[11]> (bye)
Bye.