ttt-gametree.clj

(ns ttt-gametree.core)

(def win-patterns [[0 1 2]   ; 1st row
                   [3 4 5]   ; 2nd row
                   [6 7 8]   ; 3rd row
                   [0 4 8]   ; diagonal
                   [2 4 6]   ; diagonal
                   [0 3 6]   ; 1st col
                   [1 4 7]   ; 2nd col
                   [2 5 8]]) ; 3rd col

(def empty-board (vec (repeat 9 nil)))

(def next-player {:x :o
                  :o :x})

(defn- extract-pattern [pattern board]
  (map #(nth board %) pattern))

(defn- pattern-player-win? [player pattern board]
  (every? #(= player %)
          (extract-pattern pattern board)))

(defn- player-win? [player board]
  (some true?
        (map #(pattern-player-win? player % board)
             win-patterns)))

(defn- winner [board]
  (cond (player-win? :x board) :x
        (player-win? :o board) :o
        :else nil))

(defn- possible-moves [board]
  (filter #(nil? (nth board %)) (range 9)))

(defn game-tree
  ([] (game-tree empty-board :x))
  ([board player]
   (let [moves (possible-moves board)
         win   (winner board)]
     (cond win win
           (empty? moves) :tie
           :else (apply merge
                  (for [move moves]
                    (let [next-board (assoc board move player)]
                      {move (game-tree
                             next-board
                             (next-player player))})))))))


(defmacro calc-game-macro []
  (game-tree))

;; Calculate game tree on compile time
(def tic-tac-toe-tree-compiletime (calc-game-macro))

;; Calculate game tree on run time
(def tic-tac-toe-tree-runtime (game-tree))

;;; ---------------------

;; [:x :x :x
;;  :_ :o :_
;;  :_ :o :_]
(get-in tic-tac-toe-tree-runtime [0 4, 1 7, 2])
;; => :x

;; [:o :x :x
;;  :x :o :_
;;  :_ :_ :o]
(get-in tic-tac-toe-tree-compiletime [1 4, 2 0, 3 8])
;; => :o

No tail recur, but couldn't be assed because of stack height