Starting a Clojure Chess Engine

Question

In my journey to learn Clojure I recently decided that I would like to write a chess engine, which is kind of funny because I don't really know chess either. ;-) My goals are to learn Clojure and chess, and write something that is fairly easy to understand.

Currently I'm working on board representation and basic movement. There are many ways to represent a chess board, but I decided to represent the board as a list of game pieces because I would like to see how that choice affects the implementation in a Lisp dialect.

Everything is still early in the development, but I'd like to get some feedback on what I've started.

Here is my board representation.

(ns chess.state)

(defn make-board
  "Creates a chess board in the initial configuration."
  []
  '({:type :rook   :color :black :rank 8 :file 1 }
    {:type :knight :color :black :rank 8 :file 2 }
    {:type :bishop :color :black :rank 8 :file 3 }
    {:type :queen  :color :black :rank 8 :file 4 }
    {:type :king   :color :black :rank 8 :file 5 }
    {:type :bishop :color :black :rank 8 :file 6 }
    {:type :knight :color :black :rank 8 :file 7 }
    {:type :rook   :color :black :rank 8 :file 8 }

    {:type :pawn   :color :black :rank 7 :file 1 }
    {:type :pawn   :color :black :rank 7 :file 2 }
    {:type :pawn   :color :black :rank 7 :file 3 }
    {:type :pawn   :color :black :rank 7 :file 4 }
    {:type :pawn   :color :black :rank 7 :file 5 }
    {:type :pawn   :color :black :rank 7 :file 6 }
    {:type :pawn   :color :black :rank 7 :file 7 }
    {:type :pawn   :color :black :rank 7 :file 8 }

    {:type :pawn   :color :white :rank 2 :file 1 }
    {:type :pawn   :color :white :rank 2 :file 2 }
    {:type :pawn   :color :white :rank 2 :file 3 }
    {:type :pawn   :color :white :rank 2 :file 4 }
    {:type :pawn   :color :white :rank 2 :file 5 }
    {:type :pawn   :color :white :rank 2 :file 6 }
    {:type :pawn   :color :white :rank 2 :file 7 }
    {:type :pawn   :color :white :rank 2 :file 8 }

    {:type :rook   :color :white :rank 1 :file 1 }
    {:type :knight :color :white :rank 1 :file 2 }
    {:type :bishop :color :white :rank 1 :file 3 }
    {:type :queen  :color :white :rank 1 :file 4 }
    {:type :king   :color :white :rank 1 :file 5 }
    {:type :bishop :color :white :rank 1 :file 6 }
    {:type :knight :color :white :rank 1 :file 7 }
    {:type :rook   :color :white :rank 1 :file 8 }))

Here are some common movement functions that I'm using for calculating the movement of each piece.

(ns chess.movement
  (:require [chess.state :refer :all]
            [clojure.math.numeric-tower :as math]))

(defn on-board?
  "Determines if a position is on the board."
  [[rank file :as position]]
  (and (>= rank 1)
       (<= rank 8)
       (>= file 1)
       (<= file 8)))

(defn same-rank?
  "Determines if two positions are in the same rank."
  [[start-rank start-file :as position] [dest-rank dest-file :as destination]]
  (and (= dest-rank start-rank) (not= dest-file start-file)))

(defn same-file?
  "Determines if two positions are in the same file."
  [[start-rank start-file :as position] [dest-rank dest-file :as destination]]
  (and (= dest-file start-file) (not= dest-rank start-rank)))

(defn diagonal?
  "Determines if two positions are diagonal from each other. We need this for things like determining whether a pawn movement is a capture, etc."
  [[start-rank start-file :as position] [dest-rank dest-file :as destination]]
  (= (math/abs (- start-rank dest-rank))
     (math/abs (- start-file dest-file))))

(defn occupied?
  "Determines if a location on the board is occupied by a piece. If the color actual
  parameter is provided then the piece at that location must be that color. We need to know this
  to help determine the ability to move, capture, etc."
  ([board [rank file :as position]]
   (some #(and (= rank (% :rank)) (= file (% :file))) board))
  ([board [rank file :as position] color]
   (some #(and (= rank (% :rank)) (= file (% :file)) (= color (% :color))) board)))

(defn opponent-color
  "Returns the opponent's color."
  [color]
  (cond
   (= color :black) :white
   (= color :white) :black))

(defn remove-pieces
  "Removes pieces from the board at the specified locations."
  [board position & remaining-positions]
  (let [positions (into #{position} remaining-positions)
        matching-position? #(positions [(% :rank) (% :file)])]
    (remove matching-position? board)))

(defn positions-between
  "Generates a list of the positions between start and end. If the
   start and end positions aren't in the same rank, file, or diagonal
   from each other then returns an empty list."
  [[start-rank start-file :as start] [end-rank end-file :as end]]
  (if (or (same-rank? start end)
          (same-file? start end)
          (diagonal? start end))
    (let [next-rank (cond (= start-rank end-rank) identity
                          (< start-rank end-rank) inc
                          (> start-rank end-rank) dec)
          next-file (cond (= start-file end-file) identity
                          (< start-file end-file) inc
                          (> start-file end-file) dec)]
      (loop [positions '()
             [current-rank current-file :as current-position] [(next-rank start-rank) (next-file start-file)]]
        (if (= current-position end)
          positions
          (recur (conj positions current-position) [(next-rank current-rank) (next-file current-file)]))))
    '()))

(defn movement-blocked?
  "Move is blocked if the destination is occupied by the player's own piece, or
   if any position between the start and destination contains a piece. Note that
   this function does not work for Pawns (yet) because a pawn is blocked when
   moving forward if the destination is occupied by any piece."
  [board [rank file :as position] [dest-rank dest-file :as destination] color]
  (or (occupied? board destination color)
      (some (into #{} (positions-between position destination))
            (map (fn [p] [(p :rank) (p :file)]) board))))

Here is my code for deciding which positions a rook can move to on the board.

(ns chess.rook-movement
  (:require [chess.movement :refer :all]
            [chess.state :refer :all]))

(defn valid-rook-move?
  "Determines if a rook can make a move from one position to another on a board."
  [board [start-rank start-file :as position] [dest-rank dest-file :as destination] color]
  (and (on-board? destination)
       (or (same-rank? position destination)
           (same-file? position destination))
       (not (movement-blocked? board position destination color))))

(defn rook-destinations
  "Returns a lazy sequence of positions (tuples containing rank and file) that a rook can move to."
  [board [rank file :as position] color]
  (let [possible-dests (concat (map (fn [f] [rank f]) (range 1 9))
                               (map (fn [r] [r file]) (range 1 9)))]
    (filter #(valid-rook-move? board position % color) possible-dests)))

Please comment! I'm looking for ways to make the code more idiomatic, readable, organized better, more efficient, etc.

Answer 1

Funnily enough, although Clojure is a Lisp, Clojure programmers rarely use lists to store data. Typically we use vectors. I think a lot of this is because vectors have their own syntax that's easier to read and type than a quoted list, and you don't have to worry about quoting because vectors never try to do function application.

But vectors and lists do have different performance characteristics. A list resembles its counterparts in Common Lisp or Scheme: it's singly-linked, so lookups are linear time. Vectors, on the other hand, are giant flat trees; looking something up in a vector with \$n\$ items is \$O(\log_{32}n)\$, which you can typically think of as effectively constant. (E.g. \$log_{32}(10^{30}) = 20.6\$, rounded off.) For both of these reasons, I think a vector might have been a better choice for your representation of the board. A map from occupied spaces to the piece occupying it might have been even better; you could more quickly check if a space is already occupied, and if you do need to iterate over all the elements, maps support the sequence abstraction too:

(def m {:a 1, :b 2, :c 3})
(keep #(when (< 2 (% 1)) (% 0)) m)
;; Returns (:c)

When you use map on a map, each key and value get passed to the function you provide as a two-element vector. That snippet makes a list of all the keys whose values are greater than 2. (keep is just map, except it doesn't include nil values in the list; it's equivalent to (remove nil? (map f-that-is-sometimes-nil some-seq)).)

Note that unlike Python, since almost all types in Clojure are immutable, you can use almost anything as the key to a map. So if you wanted to do a map from occupied spaces to pieces, you could do this:

(def board {[2 1] {:type :pawn, :color :white}, 
            [2 2] {:type :pawn, :color :white}
            ...

or this:

(def board {{:rank 2, :file 1} {:type :pawn, :color :white}, 
            {:rank 2, :file 2} {:type :pawn, :color :white}
            ...

You might also programmatically generate your initial board configuration, instead of writing it all out.

---

Based on your code for determining if a move is a valid move for a rook, I'm guessing you have a bunch of functions like valid-queen-move?, queen-destinations, valid-knight-move?, knight-destinations, etc. floating around in a namespace somewhere. That seems a little messy. I think a cleaner way would be to use one of Clojure's pseudo object-oriented features, either records and protocols or multimethods.

With records and protocols, you could make each piece type a record, like this:

(defrecord Rook [color rank file])
(defrecord Knight [color rank file])
(defrecord Queen [color rank file])
;; etc.

There's probably some metaprogramming or macro tricks you could do to generate these declarations for you; I played around with some approaches I thought would work, but none did.

EDIT: I posted a Stack Overflow question about how to generate the record definitions programmatically, and got some great answers. Stack Overflow users Arthur Ulfeldt and galdre both gave macros that can give you record definitions for all the pieces in a couple lines of code, so go check out their answers if you're interested in that.

Anyway, you could then have a protocol, like the following, for different move types:

(defprotocol move
    (move-legal? [this source dest])
    (spaces-limited? [this]))

Then you have each piece implement the protocol. For a rook, it would look like this:

(extend-type Rook
    move
    (move-legal? [_ source dest]
      (or (same-rank? source dest) (same-file? source dest)))
    (space-limit [_] 5000))  ; Larger than board size, i.e. infinite

For a king, it would look like this:

(extend-type King
    move
    (move-legal? [this source dest]
      (< (move-distance source dest) (space-limit this)))
    (space-limit [this] (if (castling? this) 2 1))

For a pawn:

(extend-type Pawn
  move
  (move-legal? [this source dest]
    (and (< (move-distance source dest) (space-limit this))
      (or (same-file? source dest)
        (and (diagonal? source dest) (occupied? dest)))))
  (space-limit [this]
    (if (at-start this)
      2
      1)))

Then I would have a helper function, can-make-move?, that checks if the movement is blocked or off the board as well as calling move-legal? on the piece. Call this to check if a move is valid before making it.

(defn can-make-move?
  [piece source dest]
  (and (not (movement-blocked? board source dest (:color piece)))
       (on-board? dest)
       (move-legal? piece source dest)))

(defn make-move
  [piece source dest]
  (if (can-make-move? piece source dest)
     (move piece dest)
     (throw (java.lang.IllegalArgumentException. "Move invalid."))))

There's a lot more polish to be put on this, but that would be the basic approach to using protocols and records. The main advantage here over the approach with maps and separate functions is code organization. Rather than having separate valid-rook-move?, valid-queen-move?, etc. functions, you just have a single move-legal? that works for any piece. In the future, if you need some other behavior from all pieces, add a function to the protocol and implement it. This is Clojure's version of object-oriented programming, and you can use just as much of it as you need whenever OO is advantageous, without becoming an Inheritance Hierarchy Morlock.

The multimethod version would be similar; you could use the same map representation you have now, and define multimethods instead of the protocol functions. The multimethods would dispatch on the type of the piece. Multimethods are great, but all their power is not needed here. I think protocols and records are a better fit here, since you have an obvious single type (which piece you're working with) to dispatch on. Protocols and records also have good performance, since they turn straight into Java classes and method calls behind the scenes.