50
\$\begingroup\$

I wrote a Connect Four game including a AI in Clojure and since I'm rather new to Clojure, some review would be highly appreciated. It can include everything, coding style, simplifications, etc. But keep in mind the AI is not finished yet, other heuristics will be added in the near future. Currently it only cares about connected coins (not e.g. whether those 3 connected coins can actually result into 4).

The whole source code can be found on GitHub.

I'm asking specifically for the AI, but if you have suggestions regarding the board.clj, check_board.clj or core.clj I am happy to hear them too.

ai_minimax.clj:

(ns clj-connect-four.ai-minimax
  (:require [clj-connect-four.board       :as board]
            [clj-connect-four.check-board :as check]))

;;; HEURISTIC FUNCTIONS ;;;

;; consider connected coins
; define score points for 2, 3 and 4 connected coins
(def CC4  1048576)
(def CC3  32)
(def CC2  4)

(defn bit-count
  "Checks how many bits are set on given bitboard."
  [board]
  (map #(bit-test board %) board/board-bits))

(defn get-score
  "Determines score of a bitboard manipulated by check-board-*."
  [check points]
  (* points
     (apply + (map #(count (filter true? (bit-count %))) check))))

(defn heuristic
  "Calculates the main heuristic value of given bitboards for a player."
  [boards player-num]
  (apply +
    (map (fn [[c p]] (get-score c p))
         [[(check/check-board-4 (boards player-num)) CC4]
          [(check/check-board-3 (boards player-num)) CC3]
          [(check/check-board-2 (boards player-num)) CC2]
          [(check/check-board-4 (boards (- 3 player-num))) (- 1 CC4)]
          [(check/check-board-3 (boards (- 3 player-num))) (- 1 CC3)]
          [(check/check-board-2 (boards (- 3 player-num))) (- 1 CC2)]])))

;; consider possible winning combinations
;; (only when first heuristic returns equal values)
(defn get-diags
  "Generates diagonals of given starting position using given step-f."
  [step-fn start-pos]
  (for [pos start-pos]
    (take 4 (iterate step-fn pos))))

(def win-combos
  "All 69 possible winning combinations."
  (let [rows (for [y (range 6), j (range 4)]
               (for [i (range 4)]
                 [y (+ i j)]))
        columns (for [x (range 7), j (range 3)]
                  (for [i (range 4)]
                    [(+ i j) x]))
        diagonals (concat
                   ; descending diagonals \
                   (get-diags (partial mapv inc)
                              (for [y (range 3), x (range 4)]
                                [y x]))
                   ; ascending diagonals /
                   (get-diags (fn [[y x]] [(inc y) (dec x)])
                              (for [y (range 3), x (range 3 7)]
                                [y x])))]
    (concat rows columns diagonals)))

(defn filter-current-move [y x coll]
  "Filter win-combos for coords including given [y x]."
  (if (nil? y)
    (some #{[0 x]} coll)
    (some #{[(inc y) x]} coll)))

(defn filter-open-combos [player-num boards coll]
  "Filter for combos which are still open."
  (some (fn [[y x]] (or (not (bit-test (boards 0) (+ y (* 7 x))))
                        (bit-test (boards player-num) (+ y (* 7 x)))))
        coll))

(defn heuristic2
  "Calculate second heuristic value."
  [boards player-num x]
  (count (filter
          #(and
            (filter-current-move (board/get-y (boards 0) x) x %)
            (filter-open-combos player-num boards %))
          win-combos)))

;;; MINIMAX ALGORITHM ;;;

(defn not-nil? [x]
  (not (nil? x)))

(defn get-max [coll]
  (if (empty? coll) 0
    (apply max coll)))

(defn minimax
  "Minimax algorithm using only main heuristic."
  [boards player-num x depth]
  (if (or (nil? boards)
          (nil? (board/insert boards x player-num))) nil
    (if (= depth 0)
      (heuristic (board/insert boards x player-num) player-num)
      (- (heuristic (board/insert boards x player-num) player-num)
         (get-max (filter not-nil?
                          (map #(minimax
                                 (board/insert boards x player-num)
                                 (- 3 player-num)
                                 %
                                 (- depth 1))
                               [0 1 2 3 4 5 6])))))))

(defn get-highest-index [coll]
  (apply max-key second
         (filter #(not-nil? (second %)) coll)))

(defn make-move
  "Generate next move using minimax
  and second heuristic if needed."
  [boards player-num depth]
  (let [heuristics (map #(minimax boards player-num % depth)
                        [0 1 2 3 4 5 6])
        highest (get-highest-index (map-indexed vector heuristics))]
    (println heuristics)
    (if (> (count (filter #{(second highest)} heuristics)) 1)
      ; equal values from first heuristics - look at second
      (first (get-highest-index
              (map #(vector (first %) (heuristic2 boards player-num (first %)))
                   ; only consider the highest and equal values
                   (filter #(= (second highest) (second %))
                           (map-indexed vector heuristics)))))
      (first highest))))

The algorithm used to check the board is a slightly modified version of the algorithm explained in the paragraph "Algorithm 2: Bitboard" here.

\$\endgroup\$

1 Answer 1

Reset to default
16
+100
\$\begingroup\$

This is two and a half years old, but for the sake of future viewers:

Overall your coding style looks pretty good, especially for someone new to Clojure. I don't have any comments on the AI engine itself, but here are a few structural notes:

not-nil? already exists in clojure.core as some?.

Docstrings are usually phrased actively: e.g. "Returns the result of.." or "Generates y based on..."

There are some places where the -> or ->> macros could be used instead of deeply nested forms. How extensively you do this is largely up to personal taste. I like reading functions as pipelines so, for example, get-score could be written as:

(defn get-score
  [check points]
  (let [count-true-bits #(count (filter true? (bit-count %)))]
    (->> check
         (map count-true-bits)
         (apply +)
         (* points))))

minimax could benefit from a let to avoid repeating (board/insert boards x player-num) four times, and could use when-let with and instead of explicitly returning nil:

(defn minimax
  "Minimax algorithm using only main heuristic."
  [boards player-num x depth]
  (when-let [boards' (and boards (board/insert boards x player-num))]
    (let [heuristic-val (heuristic boards' player-num)]
      (if (zero? depth)
        heuristic-val
        (- heuristic-val
           (->> (range 7)
                (map #(minimax boards' (- 3 player-num) % (dec depth)))
                (filter some?)
                get-max))))))

I would rename the functions filter-current-move and filter-open-combos, since they seem to be more like predicates than filters -- some will return the first logical true value of (pred item-in-coll) or else nil. Also, their docstrings should come before their parameter lists.

make-move could be flattened a bit, again depending on your preference for nesting-vs-threading (->>), and could use keep-indexed if you want to get fancy:

(defn make-move
  "Generates next move using minimax and second heuristic if needed."
  [boards player-num depth]
  (let [heuristics (map #(minimax boards player-num % depth)
                        (range 7))
        [highest-index highest] (get-highest-index (map-indexed vector heuristics))]
    (println heuristics)
    (if (> (count (filter #{highest} heuristics)) 1)
      ; equal values from first heuristics - look at second
      (->> heuristics
           (keep-indexed (fn [index x]
                           (when (= highest x)
                             [index (heuristic2 boards player-num index)]))
           get-highest-index
           first)
      highest-index)))
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.