Chess: the chess board

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

The Chess Board

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

One of the most significant design decisions for a chess engine is how to model the chess board. I think the most competitive engines use a bitboard representation; however, for our purposes, a mailbox representation is more intuitive and easy to visualize. In particular, we will use a 10 x 12 board.

Here is the source for board.rkt

Here’s a code comment to visualize the representation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
 
;; 10x12 Mailbox Board Representation
;; Index of upper left is 0. Index of lower right is 119
;; Numbers on the 8 x 8 board in the center are indices
;; into the byte string.
;;
;; FF  FF  FF  FF  FF  FF  FF  FF  FF FF
;; FF  FF  FF  FF  FF  FF  FF  FF  FF FF
;; FF  21  22  23  24  25  26  27  28 FF 8
;; FF  31  32  33  34  35  36  37  38 FF 7
;; FF  41  42  43  44  45  46  47  48 FF 6
;; FF  51  52  53  54  55  56  57  58 FF 5
;; FF  61  62  63  64  65  66  67  68 FF 4
;; FF  71  72  73  74  75  76  77  78 FF 3
;; FF  81  82  83  84  85  86  87  88 FF 2
;; FF  91  92  93  94  95  96  97  98 FF 1
;; FF  FF  FF  FF  FF  FF  FF  FF  FF FF
;; FF  FF  FF  FF  FF  FF  FF  FF  FF FF
;;      a   b   c   d   e   f   g   h

This 10 x 12 board will be stored in a byte string of length 120. In the center, you see an 8 x 8 chess board with files a through z and ranks 1 through 8. The numbers on that 8 x 8 board are the index into the byte string. While we could use an 8 x 8 representation, the 10 x 12 representation has the advantage that moves computed for any piece on the 8 x 8 board in the center will result in a valid index.

For example, consider a knight on a8 (index 21, line 6 of the comment). One invalid move would be “up 2, left 1”. This results in an index of 0 (the upper left FF on line 4), so the index is still within the valid byte string indices of 0 through 119. This saves us from having to do bounds checking.

This also works for knights on the left and right files away from the corners. For example, consider a knight on a3 (index 71) with an invalid move of “left 2, up 1”. Moving left simply subtracts 1 from the index, so moving left twice results in an index of 69 which corresponds to the FF guard square to the right of h4. Moving up subtracts the length of a row (10) resulting in 59 which corresponds to the FF guard square to the right of h5. The bottom line is that a knight can be on any of the 8 x 8 squares of the chess board, and a generated move will either produce an index of one of the valid 8 x 8 squares for a valid move, or an index of a guard square for an invalid move.

We’ve carefully chosen the guard squares to have values that will make our later computations easier - in particular, they have both the white color and black color bits set.

Here is the byte string for an empty board:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
 
(define empty-board
  (bytes->immutable-bytes
   (bytes
    #xFF #xFF #xFF #xFF #xFF #xFF #xFF #xFF #xFF #xFF
    #xFF #xFF #xFF #xFF #xFF #xFF #xFF #xFF #xFF #xFF
    #xFF #x00 #x00 #x00 #x00 #x00 #x00 #x00 #x00 #xFF
    #xFF #x00 #x00 #x00 #x00 #x00 #x00 #x00 #x00 #xFF
    #xFF #x00 #x00 #x00 #x00 #x00 #x00 #x00 #x00 #xFF
    #xFF #x00 #x00 #x00 #x00 #x00 #x00 #x00 #x00 #xFF
    #xFF #x00 #x00 #x00 #x00 #x00 #x00 #x00 #x00 #xFF
    #xFF #x00 #x00 #x00 #x00 #x00 #x00 #x00 #x00 #xFF
    #xFF #x00 #x00 #x00 #x00 #x00 #x00 #x00 #x00 #xFF
    #xFF #x00 #x00 #x00 #x00 #x00 #x00 #x00 #x00 #xFF
    #xFF #xFF #xFF #xFF #xFF #xFF #xFF #xFF #xFF #xFF
    #xFF #xFF #xFF #xFF #xFF #xFF #xFF #xFF #xFF #xFF)))

To allow us to easily compute an index into this byte string from a file/rank position (e.g. d6 or g5) we’ll use the following vector. This is only used in human interaction, so it’s not speed sensitive:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
 
(define positions
  (vector-immutable
   "  " "  " "  " "  " "  " "  " "  " "  " "  " "  "   ;   0 -   9
   "  " "  " "  " "  " "  " "  " "  " "  " "  " "  "   ;  10 -  19
   "  " "a8" "b8" "c8" "d8" "e8" "f8" "g8" "h8" "  "   ;  20 -  29
   "  " "a7" "b7" "c7" "d7" "e7" "f7" "g7" "h7" "  "   ;  30 -  39
   "  " "a6" "b6" "c6" "d6" "e6" "f6" "g6" "h6" "  "   ;  40 -  49
   "  " "a5" "b5" "c5" "d5" "e5" "f5" "g5" "h5" "  "   ;  50 -  59
   "  " "a4" "b4" "c4" "d4" "e4" "f4" "g4" "h4" "  "   ;  60 -  69
   "  " "a3" "b3" "c3" "d3" "e3" "f3" "g3" "h3" "  "   ;  70 -  79
   "  " "a2" "b2" "c2" "d2" "e2" "f2" "g2" "h2" "  "   ;  80 -  89
   "  " "a1" "b1" "c1" "d1" "e1" "f1" "g1" "h1" "  "   ;  90 -  99
   "  " "  " "  " "  " "  " "  " "  " "  " "  " "  "   ; 100 - 109
   "  " "  " "  " "  " "  " "  " "  " "  " "  " "  ")) ; 120 - 119

(define (idx->pos idx)
  (vector-ref positions idx))

(define (pos->idx pos)
  (vector-member pos positions))

The print-board utility function will output an ASCII chess board as below. Lower case letters represent black pieces, upper case letters represent white pieces:

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