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 ...
X5║O6║X1
══╬══╬══
X3║ ║O4
══╬══╬══
║O2║
BEGIN RANDOM PLAYER MOVE ...
randomly selecting SE for my move
END RANDOM PLAYER MOVE ...
X5║O6║X1
══╬══╬══
X3║ ║O4
══╬══╬══
║O2║X7
BEGIN RANDOM PLAYER MOVE ...
randomly selecting C for my move
END RANDOM PLAYER MOVE ...
(NE S W E NW N SE C)
X5║O6║X1
══╬══╬══
X3║O8║O4
══╬══╬══
║O2║X7
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 ...
║ ║
══╬══╬══
║O2║X1
══╬══╬══
║ ║
BEGIN RANDOM PLAYER MOVE ...
randomly selecting S for my move
END RANDOM PLAYER MOVE ...
║ ║
══╬══╬══
║O2║X1
══╬══╬══
║X3║
BEGIN RANDOM PLAYER MOVE ...
randomly selecting W for my move
END RANDOM PLAYER MOVE ...
║ ║
══╬══╬══
O4║O2║X1
══╬══╬══
║X3║
BEGIN RANDOM PLAYER MOVE ...
randomly selecting SW for my move
END RANDOM PLAYER MOVE ...
║ ║
══╬══╬══
O4║O2║X1
══╬══╬══
X5║X3║
BEGIN RANDOM PLAYER MOVE ...
randomly selecting NW for my move
END RANDOM PLAYER MOVE ...
O6║ ║
══╬══╬══
O4║O2║X1
══╬══╬══
X5║X3║
BEGIN RANDOM PLAYER MOVE ...
randomly selecting SE for my move
END RANDOM PLAYER MOVE ...
(E C S W SW NW SE)
O6║ ║
══╬══╬══
O4║O2║X1
══╬══╬══
X5║X3║X7
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║
══╬══╬══
X5║X1║
BEGIN RANDOM PLAYER MOVE ...
randomly selecting N for my move
END RANDOM PLAYER MOVE ...
(S NE C NW SW N)
O4║O6║O2
══╬══╬══
║X3║
══╬══╬══
X5║X1║
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 ...
X3║X5║O4
══╬══╬══
X1║ ║O2
══╬══╬══
║ ║
BEGIN RANDOM PLAYER MOVE ...
randomly selecting C for my move
END RANDOM PLAYER MOVE ...
X3║X5║O4
══╬══╬══
X1║O6║O2
══╬══╬══
║ ║
BEGIN RANDOM PLAYER MOVE ...
randomly selecting SE for my move
END RANDOM PLAYER MOVE ...
X3║X5║O4
══╬══╬══
X1║O6║O2
══╬══╬══
║ ║X7
BEGIN RANDOM PLAYER MOVE ...
randomly selecting SW for my move
END RANDOM PLAYER MOVE ...
(W E NW NE N C SE SW)
X3║X5║O4
══╬══╬══
X1║O6║O2
══╬══╬══
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
══╬══╬══
║X5║O6
BEGIN RANDOM PLAYER MOVE ...
randomly selecting SW for my move
END RANDOM PLAYER MOVE ...
X3║ ║O4
══╬══╬══
O2║ ║X1
══╬══╬══
X7║X5║O6
BEGIN RANDOM PLAYER MOVE ...
randomly selecting C for my move
END RANDOM PLAYER MOVE ...
X3║ ║O4
══╬══╬══
O2║O8║X1
══╬══╬══
X7║X5║O6
BEGIN RANDOM PLAYER MOVE ...
randomly selecting N for my move
END RANDOM PLAYER MOVE ...
(E W NW NE S SE SW C N)
X3║X9║O4
══╬══╬══
O2║O8║X1
══╬══╬══
X7║X5║O6
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 ...
║ ║
══╬══╬══
║ ║
══╬══╬══
X1║O2║
BEGIN RANDOM PLAYER MOVE ...
randomly selecting E for my move
END RANDOM PLAYER MOVE ...
║ ║
══╬══╬══
║ ║X3
══╬══╬══
X1║O2║
BEGIN RANDOM PLAYER MOVE ...
randomly selecting NW for my move
END RANDOM PLAYER MOVE ...
O4║ ║
══╬══╬══
║ ║X3
══╬══╬══
X1║O2║
BEGIN RANDOM PLAYER MOVE ...
randomly selecting NE for my move
END RANDOM PLAYER MOVE ...
O4║ ║X5
══╬══╬══
║ ║X3
══╬══╬══
X1║O2║
BEGIN RANDOM PLAYER MOVE ...
randomly selecting SE for my move
END RANDOM PLAYER MOVE ...
O4║ ║X5
══╬══╬══
║ ║X3
══╬══╬══
X1║O2║O6
BEGIN RANDOM PLAYER MOVE ...
randomly selecting W for my move
END RANDOM PLAYER MOVE ...
O4║ ║X5
══╬══╬══
X7║ ║X3
══╬══╬══
X1║O2║O6
BEGIN RANDOM PLAYER MOVE ...
randomly selecting C for my move
END RANDOM PLAYER MOVE ...
(SW S E NW NE SE W C)
O4║ ║X5
══╬══╬══
X7║O8║X3
══╬══╬══
X1║O2║O6
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║ ║
══╬══╬══
║O4║X3
══╬══╬══
║ ║X1
BEGIN RANDOM PLAYER MOVE ...
randomly selecting SW for my move
END RANDOM PLAYER MOVE ...
O2║ ║
══╬══╬══
║O4║X3
══╬══╬══
X5║ ║X1
BEGIN HUMAN PLAYER MOVE ...
Please select a move from (N NE W S)
w
END HUMAN PLAYER MOVE
O2║ ║
══╬══╬══
O6║O4║X3
══╬══╬══
X5║ ║X1
BEGIN RANDOM PLAYER MOVE ...
randomly selecting N for my move
END RANDOM PLAYER MOVE ...
O2║X7║
══╬══╬══
O6║O4║X3
══╬══╬══
X5║ ║X1
BEGIN HUMAN PLAYER MOVE ...
Please select a move from (NE S)
s
END HUMAN PLAYER MOVE
O2║X7║
══╬══╬══
O6║O4║X3
══╬══╬══
X5║O8║X1
BEGIN RANDOM PLAYER MOVE ...
randomly selecting NE for my move
END RANDOM PLAYER MOVE ...
(SE NW E C SW W N S NE)
O2║X7║X9
══╬══╬══
O6║O4║X3
══╬══╬══
X5║O8║X1
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 ...
O2║X3║
══╬══╬══
║ ║
══╬══╬══
║ ║X1
BEGIN HUMAN PLAYER MOVE ...
Please select a move from (NE W C E SW S)
w
END HUMAN PLAYER MOVE
O2║X3║
══╬══╬══
O4║ ║
══╬══╬══
║ ║X1
BEGIN RANDOM PLAYER MOVE ...
randomly selecting E for my move
END RANDOM PLAYER MOVE ...
O2║X3║
══╬══╬══
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)
O2║X3║
══╬══╬══
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 ...
║O2║X3
══╬══╬══
║ ║
══╬══╬══
║ ║X1
BEGIN HUMAN PLAYER MOVE ...
Please select a move from (NW W C E SW S)
e
END HUMAN PLAYER MOVE
║O2║X3
══╬══╬══
║ ║O4
══╬══╬══
║ ║X1
BEGIN RANDOM PLAYER MOVE ...
randomly selecting S for my move
END RANDOM PLAYER MOVE ...
║O2║X3
══╬══╬══
║ ║O4
══╬══╬══
║X5║X1
BEGIN HUMAN PLAYER MOVE ...
Please select a move from (NW W C SW)
sw
END HUMAN PLAYER MOVE
║O2║X3
══╬══╬══
║ ║O4
══╬══╬══
O6║X5║X1
BEGIN RANDOM PLAYER MOVE ...
randomly selecting NW for my move
END RANDOM PLAYER MOVE ...
X7║O2║X3
══╬══╬══
║ ║O4
══╬══╬══
O6║X5║X1
BEGIN HUMAN PLAYER MOVE ...
Please select a move from (W C)
c
END HUMAN PLAYER MOVE
X7║O2║X3
══╬══╬══
║O8║O4
══╬══╬══
O6║X5║X1
BEGIN RANDOM PLAYER MOVE ...
randomly selecting W for my move
END RANDOM PLAYER MOVE ...
(SE N NE E S SW NW C W)
X7║O2║X3
══╬══╬══
X9║O8║O4
══╬══╬══
O6║X5║X1
D
NIL
[11]> (bye)
Bye.