Chess: the chess move

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

The Chess Move

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

This post will cover the following tasks, in preparation for generating chess moves:

  • A macro for conveniently encoding fields in a fixnum integer
  • An efficient encoding of a chess move
  • Basic game state

fixnum-fields macro

Jens Axel Søgaard was kind enough to provide a fixnum-fields macro to have struct-like convenience for efficiently storing bitfields in a single fixnum.

Here is the source for fixnum-fields

An example using it:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
#lang racket

(require "./fixnum-fields.rkt")

;; Declare a contact record with 3 numeric fields and 1 flag
(fixnum-fields contact ([ dob-month  4        ]
                        [ dob-day    5        ]
                        [ dob-year  12        ]
                        [ active     1 #:flag ]))

;; Create a contact instance
(define employee (make-contact 5 12 1976 1))

(printf "DOB = ~a/~a/~a\n"
        (contact-dob-month employee)
        (contact-dob-day   employee)
        (contact-dob-year  employee))

(println (if (contact-active? employee) "Active" "Inactive"))

;; Unset the "active" flag
(set! employee (unset-contact-active? employee))

(println (if (contact-active? employee) "Active" "Inactive"))

The chess move

We will be making and unmaking chess moves as we search for the best move, so we will store the following information to allow making and unmaking moves:

Here is the source for move.rkt

  • The type of the source piece
  • The board index of the source square
  • The board index of the destination square
  • The type of the captured piece (if any)
  • The type of the pawn-promoted piece (if any)
  • A flag indicating the move is a queenside castle
  • A flag indicating the move is a kingside castle
  • A flag indicating the move is an en passant capture

With our new fixnum-fields macro, we can no easily do this as follows:

1
2
3
4
5
6
7
8
 
(fixnum-fields move ([ src                 5        ]
                     [ src-idx             7        ]
                     [ dst-idx             7        ]
                     [ captured-piece      5        ]
                     [ promoted-piece      5        ]
                     [ is-castle-queenside 1 #:flag ]
                     [ is-castle-kingside  1 #:flag ]
                     [ is-ep-capture       1 #:flag ]))

Basic game state

I strongly prefer a functional approach to most programming tasks; however, when speed is a high priority, it’s important to allocate as little as possible, so our chess engine will make heavy use of mutation. In particular, when we generate moves for a certain depth of the search tree, we will simply store moves (i.e. fixnums) in a pre-allocated vector.

Many engines use global vectors/arrays for these move lists, but we’ll encapsulate them in a game struct, which may help give us a head start for parallelization later.

Here is the source for game.rkt

The game struct is as follows:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
 
;; --------------------------------------------------------------------------------------------
;; State information for a chess game:
;; --------------------------------------------------------------------------------------------
;; board           : The 10 x 12 mailbox representation of a chess board
;; depth           : The current depth of the search tree
;; quiet-length    : An fxvector (indexed by depth) containing lengths of quiet-moves vectors
;; quiet-moves     : A vector (indexed by depth) of fxvectors containing quiet moves
;; tactical-length : An fxvector (indexed by depth) containing the lengths of tactical-moves vectors
;; tactical-moves  : A vector (indexed by depth) of fxvectors containing tactical moves

(struct game (board
              depth
              quiet-length    ; Indexed by depth
              quiet-moves     ; Indexed by depth
              tactical-length ; Indexed by depth
              tactical-moves) ; Indexed by depth
  #:transparent #:mutable)

We will find it convenient to partition chess moves into two types. Quiet moves are moves that do not involve a capture, and tactical moves are moves that do involve a capture.

For each depth of the search tree, we will need a vector of moves and the length of that vector i.e. how many move fixnums are currently stored. So, for example, if we want information at depth N, then (using pseudocode) quiet-moves[N] would return the vector of moves stored at depth N, and quiet-length[N] would return the number of moves currently stored in the vector. Likewise for tactical moves.

We will need some more game state, but we will add that later when we need it.