DouKaku?

(defconstant +diff-alist+ '((1 1) (3 3) (4 1 2 3 4) (5 3) (7 1)))
(defun wonp (ps)
  (loop for (m . ds) in +diff-alist+
    if (member m ps)
    do (loop for d in ds
         if (and (member (- m d) ps) (member (+ m d) ps))
         do (return-from wonp t))))

(defun execute-game (player-O player-X)
  (do ((vacant (list 0 1 2 3 4 5 6 7 8))
       (turn :O (if (eq turn :O) :X :O))
       (pl1 player-O pl2)
       (pl2 player-X pl1)
       (ps1 () ps2)
       (ps2 () ps1))
      ((null vacant) :draw)
    (multiple-value-setq (ps1 vacant) (funcall pl1 ps1 ps2 vacant))
    (if (wonp ps1) (return turn))))

(let ((state (make-random-state t)))
  (defun random-player (ps-player ps-opponent vacant)
    (declare (ignore ps-opponent))
    (let ((r (random (length vacant) state)))
      (if (zerop r)
          (values (cons (car vacant) ps-player) (cdr vacant))
        (let ((p (pop (cdr (nthcdr (1- r) vacant)))))
          (values (cons p ps-player) vacant))))))

;;; test
(let ((a 0) (b 0) (c 0))
  (dotimes (i 10000)
    (case (execute-game #'random-player #'random-player)
      (:O (incf a))
      (:X (incf b))
      (:draw (incf c))))
  (format t "O win: ~A~%X win: ~A~%draw: ~A" a b c))