Chess: generating moves

:: programming, racket, artificial intelligence, lisp, scheme

Generating Moves

Part of the How to Program a Chess Engine in Lisp series.

This post will cover basic game state and move generation.

Game State

In order to generate moves, we’ll need some more state information. In particular:

  • Index of the en passant square, if any
  • Indices of the white and black kings
  • Which side is to move
  • Indications of whether the four types of castle moves are permitted
    • White kingside
    • White queenside
    • Black kingside
    • Black queenside

En passant is a special chess rule that allows a pawn to capture an opponent’s pawn that has just moved two squares forward. To handle this rule, we keep track of the en passant square’s index, if applicable, in the game state when the pawn advances two squares.

With respect to castling, if a king has moved, it cannot castle. If a rook has moved, then castling cannot be performed with that rook.

Here is the game state represented with a fixnum-fields:

1
2
3
4
5
6
7
8
 
(fixnum-fields state ([ ep-idx          7        ]
                      [ black-king-idx  7        ]
                      [ white-king-idx  7        ]
                      [ whites-move     1 #:flag ]
                      [ w-queenside-ok  1 #:flag ]
                      [ w-kingside-ok   1 #:flag ]
                      [ b-queenside-ok  1 #:flag ]
                      [ b-kingside-ok   1 #:flag ]))

And the new game struct containing this new state field:

1
2
3
4
5
6
7
8
 
(struct game (board
              depth
              state
              quiet-length    ; Indexed by depth
              quiet-moves     ; Indexed by depth
              tactical-length ; Indexed by depth
              tactical-moves) ; Indexed by depth
  #:transparent #:mutable)

Here is the source for state.rkt

Move Generation

Move generation is very important for a chess engine. We need to generate every possible move for each depth of the search tree, and we need to do it quickly. Later in this series, we’ll cover an industry standard technique for testing our move generation, but for this post, we’ll just cover the move generation.

Here is the generate-moves! function:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
 
(define (generate-moves! g #:quiet-moves? [ quiet-moves? #t ])
  (define is-white? (is-whites-move? g))

  ;; Initialize the move vectors at the current depth
  (init-moves! g)

  (for* ([ rank (in-range 8) ]
         [ file (in-range 8) ])
    (let* ([ idx   (file-rank->idx file rank)      ]
           [ piece (get-square (game-board g) idx) ])
      (when (is-right-color-piece? piece is-white?)
        (match (piece-type piece)
          [ (== pawn-piece)   (generate-pawn-moves!   g idx piece #:quiet-moves? quiet-moves?) ]
          [ (== knight-piece) (generate-knight-moves! g idx piece #:quiet-moves? quiet-moves?) ]
          [ (== bishop-piece) (generate-bishop-moves! g idx piece #:quiet-moves? quiet-moves?) ]
          [ (== rook-piece)   (generate-rook-moves!   g idx piece #:quiet-moves? quiet-moves?) ]
          [ (== queen-piece)  (generate-queen-moves!  g idx piece #:quiet-moves? quiet-moves?) ]
          [ (== king-piece)   (generate-king-moves!   g idx piece is-white?
                                                 #:quiet-moves? quiet-moves?) ])))))

generate-moves! has two parameters, the game struct, g, and an optional keyword parameter, #:quiet-moves?. There will be times when we’ll only want to generate tactical moves - we’ll pass #f for #:quiet-moves? in those cases.

On line 5 we initialize the tactical and quiet moves vectors at the current depth. We preallocate these vectors at the start of the program for increased performance. We’ll be storing generated moves directly into these preallocated vectors.

We loop over every square on the board, and if the piece’s color matches the color of the side to move, we call a generate functions specific to the piece. We’ll cover each of the piece-specific generate functions next:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
(define (generate-bishop-moves! g idx piece #:quiet-moves? quiet-moves?)
  (generate-sliding-moves! g idx piece north-east quiet-moves?)
  (generate-sliding-moves! g idx piece south-east quiet-moves?)
  (generate-sliding-moves! g idx piece south-west quiet-moves?)
  (generate-sliding-moves! g idx piece north-west quiet-moves?))

(define (generate-rook-moves! g idx piece #:quiet-moves? quiet-moves?)
  (generate-sliding-moves! g idx piece north quiet-moves?)
  (generate-sliding-moves! g idx piece east quiet-moves?)
  (generate-sliding-moves! g idx piece south quiet-moves?)
  (generate-sliding-moves! g idx piece west quiet-moves?))

(define (generate-queen-moves! g idx piece #:quiet-moves? quiet-moves?)
  (generate-bishop-moves! g idx piece #:quiet-moves? quiet-moves?)
  (generate-rook-moves! g idx piece #:quiet-moves? quiet-moves?))

(define (generate-sliding-moves! g idx piece direction quiet-moves?)
  (define board (game-board g))

  (let loop ([ target-idx (fx+ idx direction) ])
    (let ([ target (get-square board target-idx) ])
      (cond [ (fx= target empty-square)
              (when quiet-moves?
                ;; Add quiet move and continue
                (push-quiet-move! g (create-move piece idx target-idx)))
              (loop (fx+ target-idx direction)) ]
            [ (is-other-piece? piece target)
              ;; Add tactical move for capture and exit
              (push-tactical-move! g
                                   (create-move piece idx target-idx #:captured-piece target)) ]))))

In the code above, generate-sliding-moves! is a helper used by bishops, rooks & queens. Queen moves are the union of bishop and rook moves.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
 
(define (generate-king-moves! g idx piece is-white? #:quiet-moves? quiet-moves?)
  (generate-offset-moves! g idx piece king-offsets quiet-moves?)
  (when (and quiet-moves? (may-castle? g is-white?))
    (generate-castle-moves! g idx piece is-white?)))

;; may-castle? resides in game.rkt, not generate-moves.rkt
(define-inline (may-castle? g white?)
  (let ([ s (game-state g) ])
    (if white?
        (or (state-w-kingside-ok? s) (state-w-queenside-ok? s))
        (or (state-b-kingside-ok? s) (state-b-queenside-ok? s)))))

(define (generate-castle-moves! g idx piece is-white?)
  (let ([ s       (game-state g) ]
        [ squares (game-board g) ])
    ;; King side
    (when (and (if is-white? (state-w-kingside-ok? s) (state-b-kingside-ok? s))
               (fx= empty-square (get-square squares (fx+ idx 1)))
               (fx= empty-square (get-square squares (fx+ idx 2))))
      (push-quiet-move! g
                       (create-move piece idx (fx+ idx 2) #:is-castle-kingside? #t)))
    ;; Queen side
    (when (and (if is-white? (state-w-queenside-ok? s) (state-b-queenside-ok? s))
               (fx= empty-square (get-square squares (fx- idx 1)))
               (fx= empty-square (get-square squares (fx- idx 2)))
               (fx= empty-square (get-square squares (fx- idx 3))))
      (push-quiet-move! g
                       (create-move piece idx (fx- idx 2) #:is-castle-queenside? #t)))))

(define (generate-knight-moves! g idx piece #:quiet-moves? quiet-moves?)
  (generate-offset-moves! g idx piece knight-offsets quiet-moves?))

(define (generate-offset-moves! b idx piece offsets quiet-moves?)
  (define board (game-board b))

  (let loop ([ lst offsets ])
    (when (not (null? lst))
      (let* ([ offset     (car lst)                     ]
             [ target-idx (fx+ idx offset)              ]
             [ target     (get-square board target-idx) ])
        (cond [ (fx= target empty-square)
                (when quiet-moves?
                  (push-quiet-move! b (create-move piece idx target-idx))) ]
              [ (is-other-piece? piece target)
                (push-tactical-move! b
                                    (create-move piece idx target-idx #:captured-piece target)) ]))
      (loop (cdr lst)))))

In the code above, generate-offset-moves! is a helper used by kings and knights. Kings, in addition to moving one space in every direction, can also castle, if the king and one rook have not been moved.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
 
(define (generate-pawn-moves! g idx piece #:quiet-moves? quiet-moves?)
  (let-values ([ (white? n1-idx n2-idx nw-idx w-idx ne-idx e-idx min8th max8th min2nd max2nd)
                 (if (is-white? piece)
                     (values #t
                             (fx+ idx north)
                             (fx+ idx north north)
                             (fx+ idx north-west)
                             (fx+ idx west)
                             (fx+ idx north-east)
                             (fx+ idx east)
                             21 28 81 88)
                     (values #f
                             (fx+ idx south)
                             (fx+ idx south south)
                             (fx+ idx south-west)
                             (fx+ idx west)
                             (fx+ idx south-east)
                             (fx+ idx east)
                             91 98 31 38)) ])
    (let* ([ squares    (game-board g)              ]
           [ n1         (get-square squares n1-idx) ]
           [ n2         (get-square squares n2-idx) ]
           [ nw         (get-square squares nw-idx) ]
           [ ne         (get-square squares ne-idx) ]
           [ last-rank? (<= min8th n1-idx max8th)   ])

      (when (and (fx= n1 empty-square) quiet-moves?)
        ;; Single push
        (if last-rank?
            ;; Quiet promotions
            (generate-quiet-promotions! g white? piece idx n1-idx)

            ;; Regular single push
            (push-quiet-move! g (create-move piece idx n1-idx)))

        ;; Double push (only if single push was allowed)
        (when (and (fx<= min2nd idx max2nd)
                   (fx= n2 empty-square))
          (push-quiet-move! g (create-move piece idx n2-idx))))


      ;; Capture north west
      (cond [ (is-other-piece? piece nw)
              (if last-rank?
                  (generate-capture-promotions! g white? piece idx nw-idx nw)
                  (push-tactical-move! g (create-move piece idx nw-idx #:captured-piece nw))) ]
            [ (fx= (get-ep-idx g) nw-idx)
              ;; En passant capture
              (push-tactical-move! g
                                 (create-move piece idx nw-idx
                                              #:captured-piece (get-square squares w-idx) #:is-ep-capture? #t)) ])

      ;; Capture north east
      (cond [ (is-other-piece? piece ne)
              (if last-rank?
                  (generate-capture-promotions! g white? piece idx ne-idx ne)
                  (push-tactical-move! g (create-move piece idx ne-idx #:captured-piece ne))) ]
            [ (fx= (get-ep-idx g) ne-idx)
              ;; En passant capture
              (push-tactical-move! g
                                 (create-move piece idx ne-idx
                                              #:captured-piece (get-square squares e-idx) #:is-ep-capture? #t)) ]))))

In the code above, pawn moves have the most special case logic. They can move two spaces, but only as their first move. They can be promoted to another piece, but only by reachin the 8th rank. They can capture a pawn that has advanced past the normal capture square, if this was done via a two-square first move. Lastly, they move only forward, and capture only diagonally!

Here is the source for generate-moves.rkt

As I mentioned above, we’ll use an industry standard method for testing move generation later, but for now, I created a simple unit test to display moves generated for an example board setup. We set up the board using fen-placement->board! (discussed earlier in the series). Here is the board placement:

---------------------------------
| r |   |   |   | k |   |   | r |  8
---------------------------------
|   | p |   |   | b |   | p |   |  7
---------------------------------
| b |   | n |   | p |   |   |   |  6
---------------------------------
|   |   | p | p |   |   | q | p |  5
---------------------------------
|   |   |   | P | P |   | B |   |  4
---------------------------------
|   | Q |   |   |   | p | P |   |  3
---------------------------------
| P | B |   | N |   |   |   |   |  2
---------------------------------
| R |   |   |   | K |   |   | R |  1
---------------------------------
| a | b | c | d | e | f | g | h |

It’s white’s move, and here are the generated tactical moves:

Pd4xc5
Pe4xd5
Bg4xh5
Bg4xf3
Bg4xe6
Qb3xd5
Qb3xb7
Qb3xf3
Nd2xf3
Rh1xh5

Here are the generated quiet moves:

Pe4-e5
Bg4-h3
Bg4-f5
Qb3-c4
Qb3-c2
Qb3-d1
Qb3-a4
Qb3-b4
Qb3-b5
Qb3-b6
Qb3-c3
Qb3-d3
Qb3-e3
Qb3-a3
Pa2-a3
Pa2-a4
Bb2-c3
Bb2-c1
Bb2-a3
Nd2-f1
Nd2-b1
Nd2-c4
Ra1-b1
Ra1-c1
Ra1-d1
Ke1-e2
Ke1-f2
Ke1-f1
Ke1-d1
Ke1-g1
Ke1-c1
Rh1-h2
Rh1-h3
Rh1-h4
Rh1-g1
Rh1-f1