Starting a Clojure Chess Engine

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 }

{:ty

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 functio

StackExchange Code Review Q#87325, answer score: 6