Chess: the chess piece

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

The Chess Piece

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

Donald Knuth is credited with the statement:

…We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%.

Chess programming is most assuredly in the 3%! Our challenge in this series will be to strike a reasonable balance between efficiency and clarity. Our first opportunity to that end is the chess piece.

Here is the source for piece.rkt

The data structure we’ll use to model a chess piece is a byte. The first 3 bits will indicate the type of piece:

  • 000 Empty square
  • 001 Pawn
  • 010 Knight
  • 011 Bishop
  • 100 Rook
  • 101 Queen
  • 110 King
  • 111 Not used

We’ll use the 4th bit to indicate the piece is black, and the 5th bit to indicate the piece is white. We’ll see later that having one bit per color is more efficient than a single bit where 0 and 1 values indicate different colors.

There are two optimizations in this file. We require racket/performance-hint on line 36, so that we can use define-inline to encourance the compiler to inline the simple functions such as:

1
2
 
(define-inline (is-knight? piece)
  (fx= (fxand piece piece-type-bits) knight-bits))

The second (prelude to) optimization is requiring racket/fixnum on line 35, so we can use fixnum functions such as fx=, fx>, fxand, etc. As explained in 4.3.4 Fixnums, the safe operations, such as fx+, may not be faster than simply using +; however, later, we can easily switch from safe operations to unsafe operations, with a single require change, and then we will gain speed. For now, we’ll stick with safe operations for development & testing.

The majority of this file contains predicates for various aspects of pieces, and they use bit manipulations to extract the information. Here’s an example for determining if a piece is a bishop:

1
2
 
(define-inline (is-bishop? piece)
  (fx= (fxand piece piece-type-bits) bishop-bits))

Here we extract the low order bits of the piece where the type information is stored and test whether they’re equal to the bishop type bits.

The only other noteworthy item is the pair of functions to translate a piece to its symbol and vice versa (piece-symbol and symbol-piece). These will be used in the human interaction functionality.