Writing a chess program in 99 steps

11  The move generator

This section is probably going to be the steepest part of your chess programming learning curve.  Take your time, you might have to read this (and other articles on the internet) many times, before the ideas sink in and before you come to appreciate how bitboard move generation works; I did too.  The basic idea for bitboard move generation is that moves are not calculated, but looked up in a table.  There are many variations, but all methods are trying to hit some optimum between speed and memory, depending on the intended use of the chess engine.  Engines that are meant for handheld devices will have an implementation with very compact tables, at the cost of more computations to calculate the table lookup address. Winglet is at the other end of the scale. Computations are kept to a minimum, making the code readable, at the cost of a significant memory footprint (total memory allocation for winglet's sliding attack tables is 128kB).

Before we can write a move generator, we need to define the internal representation of a chess move.  Let's see if we can use a 32-bit unsigned integer to store a move.  Why 32-bit? because using less than 32 bits would probably not give significant speed benefits, most computers today are based on a 32-bit or 64-bit architecture. More than 32 bits could lead to some speed penalties on 32-bit systems (not on 64-bit systems).

The move structure

A chess move can be represented by the from (from) and to (tosq) field (two positive integers, from 0..63, so 6 bits each. Since we also need to be able to unmake (reverse) a move, captured pieces need to be stored as part of the move. Our piece identifiers are numbers between 0..15, for this we need (2⁴=16) 4 bits (stored in a 4-bit bitfield: capt).
In case of a pawn promotion (a white pawn reaches rank 8, or black pawn reaches rank 1), we also need to store the promotion piece (queen, rook , bishop, or knight). One more 4-bit bitfield is added: prom. 
Our total is 20 bits, which is still less than 32. We might as well store the moving piece, it's only taking 4 additional bits and could prove useful later, let's call this bitfield piec.
So, we use 24 bits of a 32-bit unsigned integer to store a move.
We already talked about pawn promotions, how about other 'special' moves, like en-passant captures, and castling? In order to make the move reversible, we need to flag an en-passant move, or else a captured opponent's pawn would be misplaced when reversing the move. We'll use the existing 4-bit prom field to identify an en-passant capture: if the promotion bit-field equals WHITE_PAWN, it will mean that this is en-passant capture by a white pawn. 
There really is no need to do anything special for castlings. If the king moves more than one field, it must be a castling move. However, just for ease of identifying castlings, we'll use the Prom field again: if it equals WHITE_KING, or BLACK_KING, then it means this was a castling move involving one of the rooks.

The move structure and member functions are defined below. I kept the header (.h) and actual implementation coding (.cpp) separate, even if the functions are very short. This will make it easier  to test different methods of storing a move, in terms of computational speed.

step 24: move.h

---

#ifndef WINGLET_MOVE_H_

#define WINGLET_MOVE_H_

 

#include "defines.h"

 

//  There are at least 3 different ways to store a move in max 32 bits

//  1) using shift & rank in an unsigned int                

//  2) using 4 unsigned chars, union-ed with an unsigned int

//  3) using C++ bitfields, union-ed with an unsigned int   

 

//  this is 1) using shift & rank in an unsigned int (32 bit):

struct Move                                  

{

       // from (6 bits)

       // tosq (6 bits)

       // piec (4 bits)

       // capt (4 bits)

       // prom (4 bits)

       unsigned int moveInt;

 

       void clear();

       void setFrom(unsigned int from);  

       void setTosq(unsigned int tosq);  

       void setPiec(unsigned int piec);  

       void setCapt(unsigned int capt);  

       void setProm(unsigned int prom); 

       unsigned int getFrom();  

       unsigned int getTosq();  

       unsigned int getPiec();  

       unsigned int getCapt();

       unsigned int getProm();  

       BOOLTYPE isWhitemove();

       BOOLTYPE isBlackmove();

       BOOLTYPE isCapture();

       BOOLTYPE isKingcaptured();

       BOOLTYPE isRookmove();

       BOOLTYPE isRookcaptured();

       BOOLTYPE isKingmove();

       BOOLTYPE isPawnmove();

       BOOLTYPE isPawnDoublemove();

       BOOLTYPE isEnpassant();

       BOOLTYPE isPromotion();

       BOOLTYPE isCastle();

       BOOLTYPE isCastleOO();

       BOOLTYPE isCastleOOO();

};

 

#endif

---

 The implementation of the member functions below looks quite long, for just a single chess move. I'll explain:

step 25: move.cpp

---

#include "move.h"

 

void Move::clear()

{

       moveInt = 0;

}

 

void Move::setFrom(unsigned int from)  

{   // bits  0.. 5

       moveInt &= 0xffffffc0; moveInt |= (from & 0x0000003f);

}

 

void Move::setTosq(unsigned int tosq)  

{   // bits  6..11      

       moveInt &= 0xfffff03f; moveInt |= (tosq & 0x0000003f) << 6;

}

 

void Move::setPiec(unsigned int piec)  

{   // bits 12..15

       moveInt &= 0xffff0fff; moveInt |= (piec & 0x0000000f) << 12;

} 

 

void Move::setCapt(unsigned int capt)  

{   // bits 16..19

       moveInt &= 0xfff0ffff; moveInt |= (capt & 0x0000000f) << 16;

} 

 

void Move::setProm(unsigned int prom)  

{   // bits 20..23

       moveInt &= 0xff0fffff; moveInt |= (prom & 0x0000000f) << 20;

} 

      

// read move information:

// first shift right, then mask to get the info

 

unsigned int Move::getFrom()  

{   // 6 bits (value 0..63), position  0.. 5

       return (moveInt        & 0x0000003f);

}  

 

unsigned int Move::getTosq()  

{   // 6 bits (value 0..63), position  6..11

       return (moveInt >>  6) & 0x0000003f; 

}   

 

unsigned int Move::getPiec()  

{   // 4 bits (value 0..15), position 12..15

       return (moveInt >> 12) & 0x0000000f; 

}   

 

unsigned int Move::getCapt()  

{   // 4 bits (value 0..15), position 16..19

       return (moveInt >> 16) & 0x0000000f; 

}   

 

unsigned int Move::getProm()  

{   // 4 bits (value 0..15), position 20..23

       return (moveInt >> 20) & 0x0000000f; 

}   

 

// boolean checks for some types of moves.

// first mask, then compare

// Note that we are using the bit-wise properties of piece identifiers, so we cannot just change them anymore !

 

BOOLTYPE Move::isWhitemove()  

{   // piec is white: bit 15 must be 0

       return (~moveInt & 0x00008000) == 0x00008000;

} 

 

BOOLTYPE Move::isBlackmove()  

{   // piec is black: bit 15 must be 1

       return ( moveInt & 0x00008000) == 0x00008000;

} 

 

BOOLTYPE Move::isCapture()    

{   // capt is nonzero, bits 16 to 19 must be nonzero

       return ( moveInt & 0x000f0000) != 0x00000000;

} 

 

BOOLTYPE Move::isKingcaptured()

{   // bits 17 to 19 must be 010

       return ( moveInt & 0x00070000) == 0x00020000;

} 

 

BOOLTYPE Move::isRookmove()

{   // bits 13 to 15 must be 110

       return ( moveInt & 0x00007000) == 0x00006000;

} 

 

BOOLTYPE Move::isRookcaptured()

{   // bits 17 to 19 must be 110

       return ( moveInt & 0x00070000) == 0x00060000;

} 

 

BOOLTYPE Move::isKingmove()

{   // bits 13 to 15 must be 010

       return ( moveInt & 0x00007000) == 0x00002000;

} 

 

BOOLTYPE Move::isPawnmove()

{   // bits 13 to 15 must be 001

       return ( moveInt & 0x00007000) == 0x00001000;

} 

 

BOOLTYPE Move::isPawnDoublemove()

{   // bits 13 to 15 must be 001 &

       //     bits 4 to 6 must be 001 (from rank 2) & bits 10 to 12 must be 011 (to rank 4)

    // OR: bits 4 to 6 must be 110 (from rank 7) & bits 10 to 12 must be 100 (to rank 5)

 

       return ((( moveInt & 0x00007000) == 0x00001000) && (((( moveInt & 0x00000038) == 0x00000008) && ((( moveInt & 0x00000e00) == 0x00000600))) || 

                                                          ((( moveInt & 0x00000038) == 0x00000030) && ((( moveInt & 0x00000e00) == 0x00000800)))));

} 

 

BOOLTYPE Move::isEnpassant()  

{   // prom is a pawn, bits 21 to 23 must be 001

       return ( moveInt & 0x00700000) == 0x00100000;

} 

 

BOOLTYPE Move::isPromotion()  

{   // prom (with color bit removed), .xxx > 2 (not king or pawn)

       return ( moveInt & 0x00700000) >  0x00200000;

} 

 

BOOLTYPE Move::isCastle()     

{   // prom is a king, bits 21 to 23 must be 010

       return ( moveInt & 0x00700000) == 0x00200000;

} 

 

BOOLTYPE Move::isCastleOO()   

{   // prom is a king and tosq is on the g-file

       return ( moveInt & 0x007001c0) == 0x00200180;

} 

 

BOOLTYPE Move::isCastleOOO()  

{   // prom is a king and tosq is on the c-file

       return ( moveInt & 0x007001c0) == 0x00200080;

} 

---

What's all that 0xfffff03f about? These are numbers, constants, in this case using the hexadecimal system (using digits from 0 to f). A hexadecimal number in C++ starts with 0x , to signal the compiler that what follows is to be interpreted as a hexadecimal number. Using hexadecimals is a compact way of writing binary numbers, because 4 bits can be replaced by 1 hexadecimal digit (see table below), and a 32-bit number can be written as a hexadecimal number using just 8 digits (a bitboard is 16 hexadecimal digits).
 

decimal	binary	hexadecimal
0	0000	0
1	0001	1
2	0010	2
3	0011	3
4	0100	4
5	0101	5
6	0110	6
7	0111	7
8	1000	8
9	1001	9
10	1010	a
11	1011	b
12	1100	c
13	1101	d
14	1110	e
15	1111	f

Let's look how a move like 'pawn from e2 to e4' is going to be stored in a 32-bit word:
We start by calling move.clear(), to clear any garbage from a previous use of this memory location, then we call move.setFrom(E2), move.setTosq(E4) and finally move.setPiec(WHITE_PAWN).
The numerical values are: E2=12, E4=28 and WHITEPAWN=1.

move.setFrom(E2) will be executed as folllows (with the hexadecimal constants written as 32 bits):  
moveInt &=         11111111111111111111111111000000;   // this will clear the rightmost 6 bits, the 'from' bitfield
moveInt != (from & 00000000000000000000000000111111);  // this will set the rightmost 6 'from' bits to the value of
                                                       // 'from': e2 (which is equal to 12), binary 001100

move.setTosq(E4) will be executed as folllows:  
moveInt &=         11111111111111111111000000111111;         // this will clear the 'to' bitfield
moveInt != (tosq & 00000000000000000000000000111111) << 6 ;  // this will set the 'to' bitfield to the value of
                                                             // 'tosq': e4 (which is equal to 24), binary 011000

move.setPiec(WHITE_PAWN) will be executed as folllows:  
moveInt &=         11111111111111110000111111111111;         // this will clear the 'piec' bitfield
moveInt != (piec & 00000000000000000000000000001111) << 12;  // this will set the 'piece' bitfield to the value of
                                                             // 'piec': WHITE_PAWN (which is equal to 1), binary 0001

So we end up with the following 32-bit word for e2-e4 (the bitfields are separated for clarity):
00000000 0000 0000 0001 011000 001100
         prom capt piec  tosq   from

Phew, not sure if I'm going to do much more examples like that, don't want my keyboard 1's and 0's to drop out.  I suppose you get the idea.

Next we introduce a move buffer, this is just an array of type Move, sufficiently long to store the generated moves (complete code snippets will follow later, no need to copy & paste now)

last update: Friday 10 June 2011