Functional Tic-Tac-Toe

Recently in the #Clojure channel on Freenode I heard someone say that you could write a tic-tac-toe game without any mutable variables. I had trouble conceiving how that could be possible. I decided to write one to find out.

The full running code is on github. This post will just look at a few of the functions that show how what seems like such an imperative problem can be solved in a functional way.

When I first created the project, I called it stateless-tic-tac-toe, but this was a misnomer. There is state everywhere. Each of the functions get passed the state they need to operate on, and usually the return is an updated version of the state.

Writing individual functions was pretty straight forward. I knew I was going to need a function that took no parameters and returned an empty board. It didn't take me long to realize that I would need to keep track of who's turn it was also.

(defn new-game [] 
  [(into [] (map str (range 1 10))) "X"])

The first big difference between a functional implementation and an imperative one is in the move function. In an imperative version, the board would be stored in a variable or property, and move would be a method that accepted a move as a parameter and modified the board variable.

In the functional version, move will not modify anything. The state of the game is passed in to move, along with the move to be applied. If the move legal, move returns a new version of the board. If the move was illegal then the calling function will get an unmodified board returned.

(defn move [[board player :as game] move]
  (if (legal-input? move)
    (let [board-index (- (Integer/parseInt move) 1)]
      (if (= (nth board board-index) move)
        [(assoc board board-index player)
         (if (= player "X") "O" "X")] 
        game)) game))

Functions like check-winner again show the different style of functional verses imperative. check-winner is passed in the current game state. It passes the current board configuration to functions that check for horizontal, vertical and diagonal lines. Finally, it returns the winner if there is one, or nil, which is evaluated to false, if there is no winner.

(defn check-winner [[board _]]
  (first (concat (check-horizontal board)
                 (check-vertical board) 
                 (check-diaganal board))))

I used a text based UI, which is pretty straight forward. Drawing the board is done with a function that takes in the board vector and returns strings that can be printed out to show the board. Everything was going great until I was ready for the actual event loop.

Using a while loop seemed like such a natural way to structure the game. While the game is not over, redraw the board and ask for a new move. I couldn't find a good way to write that without mutation. Instead of a while loop, I needed to use recursion.

Once I realized that I needed recursion, the function came pretty quickly. I have a function that takes in the game state and draws the board. After that, it checks to see if the game is over. If someone has won the game, or there are no more legal moves, the function prints out a message, and then exits. If the game is not over yet, the play-game function calls the move function and recursively calls itself with the result.

(defn play-game [the-game]
  (loop [game the-game]
    (println (render-board game))
    (if (game-over? game)
          (if-let [winner (check-winner game)]
            (println (str "Congrats to " winner))
            (println "tie game"))
          (recur (move game (get-move))))))