Two out of three – TicTacToe

After a mention of TicTacToe in the newLISP forums, I thought I’d take a look at writing a version of what we used to call Noughts and Crosses for myself. Peter posted a link to his excellent version, which plays a perfect game from the command line. So, to be different, I decided to start from the other end and write a GUI version using newLISP-GS.

There are basically three tasks to do: do the basic game mechanics, implement a user interface, and add a dash or two of intelligent strategy.

The game mechanics are simple enough. You need a board:

(set '*grid* (dup nil 9))

and a list of winning positions:

(set '*winning-positions*
   '((0 1 2) (3 4 5) (6 7 8) (0 3 6) (1 4 7) (2 5 8) (0 4 8) (2 4 6)))

Each move places a ‘X or ‘O symbol in the grid, using set-nth or nth-set:

(set-nth (*grid* a-move) 'X)

There’s also a function to find the moves still available:

(define (available-moves)
  (index nil? *grid*))

and a function to check whether a proposed move is valid:

(define (check-move move)
  (and (<= 0 move 8) (find move (available-moves))))

Here’s a function to see if a player has won:

(define (won? player)
   (letn ((player-squares (index (fn (x) (= x player)) *grid*))
          (wins-for-player
             (map (fn (win) (= win (intersect win player-squares))) *winning-positions*)))
      (if (exists true? wins-for-player)
          (set '*winner* (list player (find true wins-for-player))))))

This uses the intersect function, which I haven’t used much before. The idea is that the set of grid squares occupied by a player might equal or contain the set of numbers which constitute a winning position:

(set 'win '(2 5 8))
(intersect '(2 5 8) '(2 3 5 7 8))
;-> (2 5 8)
(= win (intersect win '(2 3 5 7 8)))
;-> true

I wonder if there’s a simpler way to see whether ‘(2 3 5 7 8) contains ‘(2 5 8)?

Add a game-over? function:

(define (game-over?)
  (or (won? 'X) (won? 'O) (empty? (available-moves))))

and the mechanics are mostly done.

I found the user interface task a bit harder. The problem is that you have to use an event-driven model, but the only event that’s going to happen is the user clicking a square to place a ‘X. So inside the main loop:

(do-until (game-over?) (gs:check-event 1000000))

everything has to be driven by mouse clicks. I ended up with something like this:

(define (do-human-move move)
  (and (not (game-over?) (= *turn* "human"))
       (check-move move)
       (set-nth (*grid* move) 'X)
       (display)
       (set '*turn* "computer")
       (do-computer-move)
       (display)))

which kind of works – and you can see now why I used set-nth. You might think that nth-set would do the job perfectly, and it does, but it returns the value of the replaced element, which, being nil, finished the and clause too early.

And what about the third task, adding the intelligent strategy? This is certainly the most interesting part of the job, but I haven’t had the time to start it yet. I’ve been testing with the simplest possible strategy:

(define (generate-computer-move)
  (apply amb (available-moves)))

Here, amb has to be applyed to a list; unlike randomize, it takes single arguments rather than a single list.

Perhaps one day I’ll get round to starting the third task. If you want to help me, get the file from the downloads page and get coding!