A simple Tic Tac Toe game

Question

I am trying to learn some Common Lisp, except basically all of my computing background is the C family of languages. So, I'm starting small. I have made a Tic-Tac-Toe game, and I am looking for some constructive criticism.

In particular, is this idiomatic Lisp? Is it styled normally? What would an experienced lisper improve about this?

Some concerns I have about this code are:

• The win checking seems repetitive. Can it be simplified?
• The get-player-move is very long. Should it be broken up?

;;;; A simple tic-tac-toe game

(defvar p1 88) ; char code for 'X'
(defvar p2 79) ; char code for 'O'
(defvar tie 49) ; arbitrary constant to represent ties

(defun is-move-free (move board)
  (let ((player (elt board move)))
    (not (or (= player p1) (= player p2)))))

(defun is-same (a b c)
  (and (= a b) (= b c)))

(defun win-on-rows (board)
  (defun check-a-row (offset)
    (or (is-same (elt board offset) (elt board (+ offset 1)) (elt board (+ offset 2)))))
  (or (check-a-row 0) (check-a-row 3) (check-a-row 6)))

(defun win-on-columns (board)
  (defun check-a-column (offset)
    (or (is-same (elt board offset) (elt board (+ offset 3)) (elt board (+ offset 6)))))
  (or (check-a-column 0) (check-a-column 1) (check-a-column 2)))

(defun win-on-diagonals (board)
  (or (is-same (elt board 0) (elt board 4) (elt board 8)) (is-same (elt board 2) (elt board 4) (elt board 6))))

;;; This function gets the players move, plays it if possible
;;; then gets the next move. The game will play out in it's
;;; entirety through recursively calling this function.
(defun get-player-move (player board move-num)
  (apply #'format t " ~C | ~C | ~C ~%-----------~% ~C | ~C | ~C ~%-----------~% ~C | ~C | ~C~%" (map 'list #'code-char board)) ; Print the board
  (if (>= move-num 9) ; if all the moves have been played, and there is no winner
    tie               ; return the tie constant
    (let ((move (- (parse-integer (read-line)) 1))) ; get the move from input, and convert it to list location
      (if (is-move-free move board)
        (let ((board (substitute player (elt board move) board))) ; apply the move, and get the new board
          (if (or (win-on-columns board) (win-on-rows board) (win-on-diagonals board)) ; check if this was the winning move
            (elt board move) ; return the winner
            (get-player-move (if (= player p1) p2 p1) board (+ move-num 1)))) ; continue the game
        (get-player-move player board move-num))))) ; move again, if the move was taken

(let ((result (get-player-move p1 '(49 50 51 52 53 54 55 56 57) 0)))
  (if (= result tie)
    (format t "It's a tie!")
    (format t "The winner is ~C" (code-char result))))

Answer 1

Here are a few considerations.

DEFPARAMETER vs. DEFVAR

The first three definitions should be given with defparameter instead of defvar. The first operator is used for values that do not change, unless they are modified in the source file and then recompiled. The second for variables that can be modified at run time but, when reloaded and recompiled, does not modify the current run-time value (i.e. are not re-initialized).

Comparison operators on more than one value

In Common Lisp is very handy the possibility of using all the comparison operators with more then one argument. For instance if you want to check if the numbers a, b and c are all equal, you can simply write (= a b c); if you want to check that they are all different among them (that is that the are no two values equal), you can write (\= a b c). This can simplify the function is-move-free as well as make non necessary the function is-same.

Semplification of the win functions

In effect they have all the same pattern: you compare three value starting with a certain index and then incrementing that index with the same value two times. For this reason I suggest a more simple function that includes all the three:

(defun win (board)
  (flet ((check (start increment)
                (= (elt board start) (elt board (incf start increment)) (elt board (incf start increment)))))
    (some #'check '(0 3 6 0 1 2 0 2) '(1 1 1 3 3 3 4 2))))

Note:

1. The use of the flet to define an internal function: defun should be used only for top level functions. In case of internal recursive functions you should use labels instead of flet.

2. The use of incf which performs a side-effect incrementing the value of a variable (which is safe in this case since in Common Lisp parameters are passed by value).

3. The use of some which is a functional that returns a true value if some predicate is at least once true when applied to one (or more) lists. In this case the predicate is check and it is applied to the list of starting indexes, and the list of the increments.

The final code

Here is the entire code with my modifications:

(defparameter p1 88) ; char code for 'X'
(defparameter p2 79) ; char code for 'O'
(defparameter tie 49) ; arbitrary constant to represent ties

(defun is-move-free (move board)
  (let ((player (elt board move)))
    (/= p1 p2 player)))

(defun win (board)
  (flet ((check (start increment)
                (= (elt board start) (elt board (incf start increment)) (elt board (incf start increment)))))
    (some #'check '(0 3 6 0 1 2 0 2) '(1 1 1 3 3 3 4 2))))

;;; This function gets the players move, plays it if possible
;;; then gets the next move. The game will play out in it's
;;; entirety through recursively calling this function.
(defun get-player-move (player board move-num)
  (apply #'format t " ~C | ~C | ~C ~%-----------~% ~C | ~C | ~C ~%-----------~% ~C | ~C | ~C~%" (mapcar #'code-char board)) ; Print the board
  (if (>= move-num 9) ; if all the moves have been played, and there is no winner
      tie               ; return the tie constant
      (let ((move (- (parse-integer (read-line)) 1))) ; get the move from input, and convert it to list location
        (if (is-move-free move board)
            (let ((board (substitute player (elt board move) board))) ; apply the move, and get the new board
              (if (win board) ; check if this was the winning move
                  (elt board move) ; return the winner
                  (get-player-move (if (= player p1) p2 p1) board (+ move-num 1)))) ; continue the game
            (get-player-move player board move-num))))) ; move again, if the move was taken

(let ((result (get-player-move p1 '(49 50 51 52 53 54 55 56 57) 0)))
  (if (= result tie)
      (format t "It's a tie!")
      (format t "The winner is ~C" (code-char result))))

Note the use of the more common indentention convention for the if, as well as the semplification of the format.

An iterative version

Common Lisp has been designed to be used both with applicative (i.e. functional) style, as well as imperative (i.e. with side-effect) style. So, instead of using the applicative style of creating each time a new board with substitute and passing it to a recursive call of the function get-player-move, an alternative could be a simple iterative style, like for instance:

(defun get-player-move (player board move-num)
  (loop
    (apply #'format t " ~C | ~C | ~C ~%-----------~% ~C | ~C | ~C ~%-----------~% ~C | ~C | ~C~%" (mapcar #'code-char board)) ; Print the board
    (let ((move (- (parse-integer (read-line)) 1)))
      (when (is-move-free move board)
        (setf (elt board move) player)
        (when (win board) (return player))
        (incf move-num)
        (when (= move-num 9) (return tie))
        (setf player (if (= player p1) p2 p1))))))

Note that in this case, since the board is modified, one should create it initially with (list 49 50 51 52 53 54 55 56 57), instead of using a constant like '(49 50 51 52 53 54 55 56 57).

Answer 2

Some other improvements:

• more functions with useful names make code better documented. optionally use documentation strings.
• global variables are written as *name*
• DEFUN replaced with FLET for local functions
• use ? or -p for predicates
• don't use character values, use symbols and numbers directly
• after printing make sure the output is done, before reading -> finish-output
• sectionize your code to improve visual navigation

Code:

(defparameter *p1*  'X   "Player 1")    
(defparameter *p2*  'O   "Player 2")    
(defparameter *tie* 'tie "Tie") 

(defun is-move-free? (move board)
  (let ((player (elt board move)))
    (not (or (eql player *p1*)
             (eql player *p2*)))))

(defun is-same? (a b c)
  (and (eql a b) (eql b c)))

Winning?

(defun win-on-rows? (board)
  (flet ((check-a-row? (offset)
           (or (is-same? (elt board offset)
                         (elt board (+ offset 1))
                         (elt board (+ offset 2))))))
    (or (check-a-row? 0)
        (check-a-row? 3)
        (check-a-row? 6))))

(defun win-on-columns? (board)
  (flet ((check-a-column? (offset)
           (is-same? (elt board offset)
                     (elt board (+ offset 3))
                     (elt board (+ offset 6)))))
    (or (check-a-column? 0)
        (check-a-column? 1)
        (check-a-column? 2))))

(defun win-on-diagonals? (board)
  (or (is-same? (elt board 0)
                (elt board 4)
                (elt board 8))
      (is-same? (elt board 2)
                (elt board 4)
                (elt board 6))))

(defun win? (board)
  (or (win-on-columns?   board)
      (win-on-rows?      board)
      (win-on-diagonals? board)))

Game Logic:

(defun next-player (player)
  (if (eql player *p1*) *p2* *p1*))

(defun get-move ()
  (- (parse-integer (read-line)) 1))

(defun print-board (board)
  (apply #'format t
         " ~A | ~A | ~A ~%-----------~% ~A | ~A | ~A ~%-----------~% ~A | ~A | ~A~%"
         board)
  (finish-output))

;;; This function gets the players move, plays it if possible
;;; then gets the next move. The game will play out in it's
;;; entirety through recursively calling this function.
(defun get-player-move (player board move-num)
  (print-board board)
  (if (>= move-num 9)
      *tie*
    (let ((move (get-move)))
      (if (is-move-free? move board)
          (let ((board (substitute player (elt board move) board)))
            (if (win? board)
                (elt board move)
              (get-player-move (next-player player)
                               board
                               (+ move-num 1))))
        (get-player-move player board move-num)))))


(defun game ()
  (let ((result (get-player-move *p1* (list 1 2 3 4 5 6 7 8 9) 0)))
    (if (eql result *tie*)
        (format t "It's a tie!")
      (format t "The winner is ~C" result))))