Checking for a win in Tic-Tac-Toe

Question

Okay, so I'm about finished with my latest project, a (admittedly not very good) implementation of Tic Tac Toe in Common Lisp (the whole program available here), but I'm stuck on one last part; I can't figure out how to get my function that checks for a winner working. The function (and its subordinate function) look like this:

(defun check-for-win ()
    (cond ((is-line 1 2 3) t)
            ((is-line 1 4 7) t)
            ((is-line 1 5 9) t)
            ((is-line 2 5 8) t)
            ((is-line 3 6 9) t)
            ((is-line 3 5 7) t)
            ((is-line 4 5 6) t)
            ((is-line 7 8 9) t))
    nil)

(defun is-line (a b c)
    (let ((a (aref *board* (- a 1)))
              (b (aref *board* (- b 1)))
              (c (aref *board* (- c 1))))
        (if (and 
                  (eql a b)
                  (eql a c)
                  (eql b c))
            t
            nil)))

(albeit not indented so deeply), and in (is-line), a, b and c will be (in a winning scenario) set to a symbol (either :X or :O). How do I get the equality checks working?

Answer 1

There's implicit progn in defun statement, so it is evaluated in a such way:

1. statements are evaluated one after another;
2. value of last statement is returned as a function result.

In your check-for-win you have 2 statements: cond and nil. In accordance with progn evaluation rules, value of nil will be returned for any call, and result of cond will be just ignored.

Try this code:

(defun check-for-win ()
  (cond ((is-line 1 2 3) t)
          ((is-line 1 4 7) t)
          ((is-line 1 5 9) t)
          ((is-line 2 5 8) t)
          ((is-line 3 6 9) t)
          ((is-line 3 5 7) t)
          ((is-line 4 5 6) t)
          ((is-line 7 8 9) t)
          (:else nil)))

:else is just a keyword, and as any keyword it is evaluated to true. You can use any other keyword or just true. So, if no statement before gave true, the result of cond (and all the function) will be nil.

Answer 2

This also fixes a few other problem areas in tandem with Andrei's fix.

First, adjust logic flow in the play() functionality.

;;; Play the game
(defun play (&optional switch-p)
(when switch-p (switch-player))
(check-choice (read-choice))

;;; Check if we should continue playing.
(when (and 
          (not (check-for-win)) 
          (not (stalemate)))
  (play t))


;;; Check for win FIRST (last move in possible stalemate may be a win)
(when (check-for-win)
    (format t "~a has won! " *player*)
    (if (y-or-n-p "Play again? ")
        (play-again)
        (quit)))

;;; Check for stalemate.
(when (stalemate)
    (if (y-or-n-p "~%~%Stalemate! Play again? ")
        (play-again)
        (quit))))

Second, adjust the check-choice() function...

;;; Changed (> choice 1) to (> choice 0) otherwise square 1 is always invalid.
(defun check-choice (choice)
(if (and
          (numberp choice)
          (> choice 0)
          (< choice 10))
    (select choice)
    (progn
        (format t "~%Invalid choice.~%")
        (check-choice (read-choice)))))

The problem on the first section was that if the last move which was the only move left and a winning move the program would report a stalemate before a win.

The issue in the second section was that square 1 was always reporting an invalid selection because of it was not greater than itself.

Answer 3

In CHECK-FOR-WIN:

The COND is a bad choice for what it's meant to accomplish. Think about it: you want the function to return T if any of the IS-LINEs return T, and NIL otherwise. Well that's pretty much the definition of what OR does, so dump the COND and collect the IS-LINE calls in a single OR. You could use SOME to shorten it even more, but that might end up being too "clever."

In IS-LINE

Let's take this inside-out: first, EQL is transitive, so if you know (EQL A B) and (EQL A C), then it's redundant to test (EQL B C).

Now that IF, is absolutely unforgivable. It is, quite literally, the same as doing

if (x)
  return true;
else
  return false;

in a braces language. You already have the truth value you want to return so just return that.

Finally, it's bad style to shadow variables like you are doing with the LET. At any rate, I would argue that by tossing one EQL you reduce the necessity of precomputing array refs to almost nil anyway.

In general

The convention in Common Lisp for naming predicates (functions that return either T or NIL) is to come up with a noun phrase that describes what they're testing for, and tack on a "p". So I think WINNING-POSITION-P and CELLS-MATCH-P would be better names.

I think it might be a good idea to write a function to get the content of a board square as opposed to using AREF, since the latter exposes details of its implementation. Even if it's a relatively minor issue in this case, it's a good habit to get into.

Following these suggestions would result in this code:

(defun winning-position-p ()
  (or (cells-match-p 1 2 3)
      (cells-match-p 1 4 7)
      (cells-match-p 1 5 9)
      (cells-match-p 2 5 8)
      (cells-match-p 3 6 9)
      (cells-match-p 3 5 7)
      (cells-match-p 4 5 6)
      (cells-match-p 7 8 9)))

(defun cells-match-p (a b c)
  (and (eql (board-ref a)
            (board-ref b))
       (eql (board-ref a)
            (board-ref c)))

(defun board-ref (cell)
  ;; Could check for errors here.
  (aref *board* (1- cell)))

Answer 4

Take advantage of the power of first class functions and eliminate the code repetition (this has the side effect of fixing the original problem too :)

(defun check-for-win ()
  (some (lambda (x) (apply #'is-line x)
        '((1 2 3) (1 4 7) (1 5 9) (2 5 8) (3 6 9) (3 5 7) (4 5 6) (7 8 9))))

Regarding setfing board-ref, this common case is actually rather simple,

(defun (setf board-ref) (val cell)
  (setf (aref *board* (1- cell)) val))