Bitboards for beginners

[lucasart]

Hello everyone,

Bitboards representation and move generation are typically the first step that discourages most beginners. So for those of you who are interested in writing a chess program, and have not yet managed to write all the bitboard code efficiently, I thought I would share my own code. Hope it helps, suggestions are also welcome, of course.

Code follows below (3 files).

[lucasart]

1/ defs.h

Code: Select all

#pragma once
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include <assert.h>

typedef unsigned long long U64;

static inline int min(int x, int y) { return x < y ? x : y;  }
static inline int max(int x, int y) { return x > y ? x : y;  }

#define NB_SQUARE 64
enum {
	A1, B1, C1, D1, E1, F1, G1, H1,
	A2, B2, C2, D2, E2, F2, G2, H2,
	A3, B3, C3, D3, E3, F3, G3, H3,
	A4, B4, C4, D4, E4, F4, G4, H4,
	A5, B5, C5, D5, E5, F5, G5, H5,
	A6, B6, C6, D6, E6, F6, G6, H6,
	A7, B7, C7, D7, E7, F7, G7, H7,
	A8, B8, C8, D8, E8, F8, G8, H8,
	NoSquare
};

#define NB_RANK_FILE 8
enum { Rank1, Rank2, Rank3, Rank4, Rank5, Rank6, Rank7, Rank8 };
enum { FileA, FileB, FileC, FileD, FileE, FileF, FileG, FileH };

#define NB_PIECE 6
enum { Pawn, Knight, Bishop, Rook, Queen, King, NoPiece };

#define NB_COLOR 2
enum { White, Black, NoColor };

#define NB_PHASE 2
enum { MiddleGame, EndGame };

static inline int rank_file_ok(int r, int f) { return 0 <= r && r < NB_RANK_FILE && 0 <= f && f < NB_RANK_FILE; }
static inline int square_ok(int sq)		{ return A1 <= sq && sq <= H8; }
static inline int color_ok(int color)	{ return color == White || color == Black; }
static inline int piece_ok(int piece)	{ return Pawn <= piece && piece < NoPiece; }

static inline int square(int r, int f) {
	assert(rank_file_ok(r, f));
	return 8 * r + f;
}
static inline int rank(int sq) {
	assert(square_ok(sq));
	return sq / 8;
}
static inline int file(int sq) {
	assert(square_ok(sq));
	return sq % 8;
}
static inline int opp_color(int color) {
	assert(color_ok(color));
	return color ^ 1;
}
static inline int is_slider(int piece) {
	assert(piece_ok(piece)); return Bishop <= piece && piece <= Queen;
}

[lucasart]

2/ bitboard.h

Code: Select all

#pragma once
#include "defs.h"

void init_bitboard();

extern U64 Bit[NB_SQUARE],
	Rank[NB_RANK_FILE], File[NB_RANK_FILE],
	Between[NB_SQUARE][NB_SQUARE],
    Direction[NB_SQUARE][NB_SQUARE],
	KAttacks[NB_SQUARE], NAttacks[NB_SQUARE],
    PAttacks[NB_COLOR][NB_SQUARE],
	PInitialRank[NB_COLOR], PPromotionRank[NB_COLOR];

extern U64 BPseudoAttacks[NB_SQUARE], RPseudoAttacks[NB_SQUARE];
	
void print_bitboard(U64 b);

static inline void set_bit(U64 *b, int i)	{ assert(square_ok(i)); *b |= Bit[i]; }
static inline void clear_bit(U64 *b, int i)	{ assert(square_ok(i)); *b &= ~Bit[i]; }
static inline U64 test_bit(U64 b, int i)	{ assert(square_ok(i)); return b & Bit[i]; }
static inline U64 shift_bit(U64 b, int i)	{ return i > 0 ? b << i : b >> -i;  }

int count_bit(U64 b);
int count_bit_max15(U64 b);

extern const int BitTable[NB_SQUARE];

static inline int first_bit(U64 b) {
	return BitTable[((b & -b) * 0x218a392cd3d5dbfULL) >> 58];
}
static inline int next_bit(U64 *b) {
	U64 _b = *b;
	*b &= *b - 1;
	return BitTable[((_b & -_b) * 0x218a392cd3d5dbfULL) >> 58];
}

typedef struct {
	U64 all, all_sym, all_a1h8, all_a8h1;
} occ_t;

void set_occ(occ_t *occ, int sq);
void clear_occ(occ_t *occ, int sq);
U64 rook_attack(const occ_t *occ, int sq);
U64 bishop_attack(const occ_t *occ, int sq);

static inline U64 piece_attack(const occ_t *occ, int piece, int sq)
{
	assert(Knight <= piece && piece <= King && square_ok(sq));
	
	if (piece == Knight)
		return NAttacks[sq];
	else if (piece == Bishop)
		return bishop_attack(occ, sq);
	else if (piece == Rook)
		return rook_attack(occ, sq);
	else if (piece == Queen)
		return bishop_attack(occ, sq) | rook_attack(occ, sq);
	else	// if (piece == King)
		return KAttacks[sq];
}

[lucasart]

3/ bitboard.c

NB: I use rotated bitboards here.

Code: Select all

#include "bitboard.h"

U64 Bit[NB_SQUARE],
	Rank[NB_RANK_FILE], File[NB_RANK_FILE],
	Between[NB_SQUARE][NB_SQUARE],
    Direction[NB_SQUARE][NB_SQUARE],
	KAttacks[NB_SQUARE], NAttacks[NB_SQUARE],
    PAttacks[NB_COLOR][NB_SQUARE],
	PInitialRank[NB_COLOR], PPromotionRank[NB_COLOR];

static void init_bit();
static void init_rank_file();
static void init_KNP_attacks();
static void init_rays();

U64 BPseudoAttacks[NB_SQUARE], RPseudoAttacks[NB_SQUARE];

static U64 symetric(U64 b);
static U64 rotate_a1h8(U64 b);
static U64 rotate_a8h1(U64 b);
static void init_rank_file_slides();
static void init_diag_slides();
static void init_BR_pseudo_attacks();

void init_bitboard()
{
	static int done = 0;
	if (done) return; else done = 1;
	
	init_bit();
	init_rank_file();
	init_KNP_attacks();
	init_rays();
	
	init_rank_file_slides();
	init_diag_slides();
	init_BR_pseudo_attacks();
}

static void init_bit()
{
	int i;
	for (i = A1; i <= H8; i++)
		Bit[i] = 1ULL << i;
}

static void init_rank_file()
{
	int i;
	for (i = 0; i < NB_RANK_FILE; i++) {
		Rank[i] = 0xFFULL << (8*i);
		File[i] = 0x0101010101010101ULL << i;
	}
	
	PInitialRank[White] = Rank[Rank2];
	PInitialRank[Black] = Rank[Rank7];
	
	PPromotionRank[White] = Rank[Rank8];
	PPromotionRank[Black] = Rank[Rank1];
}

static void init_KNP_attacks()
{
	const int K_dir[8][2] = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
	const int N_dir[8][2] = {{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};
	const int P_dir[NB_COLOR][2][2] = { {{1,-1},{1,1}}, {{-1,-1},{-1,1}} };

	int sq, i, c;
	for (sq = A1; sq <= H8; sq++) {
		int r = rank(sq), f = file(sq);
		KAttacks[sq] = NAttacks[sq] = 0ULL;

		for (i = 0; i < 8; i++) {
			int dr = K_dir[i][0], df = K_dir[i][1];
			if (rank_file_ok(r+dr,f+df))
				set_bit(&KAttacks[sq], square(r+dr,f+df));

			dr = N_dir[i][0], df = N_dir[i][1];
			if (rank_file_ok(r+dr,f+df))
				set_bit(&NAttacks[sq], square(r+dr,f+df));
		}

		PAttacks[White][sq] = PAttacks[Black][sq] = 0ULL;
		for (i = 0; i < 2; i++)
			for (c = White; c <= Black; c++) {
				int dr = P_dir[c][i][0], df = P_dir[c][i][1];
				if (rank_file_ok(r+dr,f+df))
					set_bit(&PAttacks[c][sq], square(r+dr,f+df));
			}
	}
}

static void init_rays()
{
	const int dir[8][2] = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
	memset(Between, 0, sizeof(Between));
	memset(Direction, 0, sizeof(Direction));

	int sq, i;
	for (sq = A1; sq <= H8; sq++) {
		int r = rank(sq), f = file(sq);

		for (i = 0; i < 8; i++) {
			int dr = dir[i][0], df = dir[i][1];
			int _r, _f, _sq;
			U64 mask;

			for (_r=r+dr,_f=f+df,mask=0ULL; rank_file_ok(_r,_f); _r+=dr,_f+=df) {
				_sq = square(_r,_f);
				set_bit(&mask, _sq);
				Between[sq][_sq] = mask;
			}

			U64 direction = mask;

			while (mask) {
				_sq = next_bit(&mask);
				Direction[sq][_sq] = direction;
			}
		}
	}
}

/* Bitboard primitives */

int count_bit(U64 b)
{
	b -= ((b>>1) & 0x5555555555555555ULL);
	b = ((b>>2) & 0x3333333333333333ULL) + (b & 0x3333333333333333ULL);
	b = ((b>>4) + b) & 0x0F0F0F0F0F0F0F0FULL;
	b *= 0x0101010101010101ULL;
	return b >> 56;
}

int count_bit_max15(U64 b)
{
	b -= (b>>1) & 0x5555555555555555ULL;
	b = ((b>>2) & 0x3333333333333333ULL) + (b & 0x3333333333333333ULL);
	b *= 0x1111111111111111ULL;
	return b >> 60;
}

const int BitTable[NB_SQUARE] = {
	0, 1, 2, 7, 3, 13, 8, 19, 4, 25, 14, 28, 9, 34, 20, 40, 5, 17, 26, 38, 15,
	46, 29, 48, 10, 31, 35, 54, 21, 50, 41, 57, 63, 6, 12, 18, 24, 27, 33, 39,
	16, 37, 45, 47, 30, 53, 49, 56, 62, 11, 23, 32, 36, 44, 52, 55, 61, 22, 43,
	51, 60, 42, 59, 58
};

/* Symetric and Rotated Bitboard code */

static const int diag_shift[] = {0, 1, 3, 6, 10, 15, 21, 28, 36, 43, 49, 54, 58, 61, 63};
static const U64 diag_mask[] = {1, 3, 7, 15, 31, 63, 127, 255, 127, 63, 31, 15, 7, 3, 1};

static const int rot_a1h8[NB_SQUARE] = {
	A1, C1, F1, B2, G2, E3, D4, D5,
	B1, E1, A2, F2, D3, C4, C5, C6,
	D1, H1, E2, C3, B4, B5, B6, A7,
	G1, D2, B3, A4, A5, A6, H6, F7,
	C2, A3, H3, H4, H5, G6, E7, B8,
	H2, G3, G4, G5, F6, D7, A8, E8,
	F3, F4, F5, E6, C7, H7, D8, G8,
	E4, E5, D6, B7, G7, C8, F8, H8
};

static const int rot_a8h1[NB_SQUARE] = {
	D5, C6, A7, F7, B8, E8, G8, H8,
	D4, C5, B6, H6, E7, A8, D8, F8,
	E3, C4, B5, A6, G6, D7, H7, C8,
	G2, D3, B4, A5, H5, F6, C7, G7,
	B2, F2, C3, A4, H4, G5, E6, B7,
	F1, A2, E2, B3, H3, G4, F5, D6,
	C1, E1, H1, D2, A3, G3, F4, E5,
	A1, B1, D1, G1, C2, H2, F3, E4
};

static U64 symetric(U64 b)
// returns the symetric of b with respect to a1h8
{
	static const int sym[] = {
		A1, A2, A3, A4, A5, A6, A7, A8,
		B1, B2, B3, B4, B5, B6, B7, B8,
		C1, C2, C3, C4, C5, C6, C7, C8,
		D1, D2, D3, D4, D5, D6, D7, D8,
		E1, E2, E3, E4, E5, E6, E7, E8,
		F1, F2, F3, F4, F5, F6, F7, F8,
		G1, G2, G3, G4, G5, G6, G7, G8,
		H1, H2, H3, H4, H5, H6, H7, H8
	};
	int i;
	U64 result = 0;

	for (i = 0; i < 64; i++)
		if (test_bit(b, sym[i]))
			set_bit(&result, i);

	return result;
}

static U64 rotate_a1h8(U64 b)
{	
	int i;
	U64 result = 0;

	for (i = 0; i < 64; i++)
		if (test_bit(b, i)) set_bit(&result, rot_a1h8[i]);

	return result;
}

static U64 rotate_a8h1(U64 b)
{	
	int i;
	U64 result = 0;

	for (i = 0; i < 64; i++)
		if (test_bit(b, i)) set_bit(&result, rot_a8h1[i]);

	return result;
}

static U64 rank_slides[NB_RANK_FILE][0x100], file_slides[NB_RANK_FILE][0x100],
    diag_a1h8_slides[NB_SQUARE][0x100], diag_a8h1_slides[NB_SQUARE][0x100];

static void init_rank_file_slides()
{
	memset(rank_slides, 0, sizeof(rank_slides));
	memset(file_slides, 0, sizeof(file_slides));

	int i, occ;
	for (i = 0; i < NB_RANK_FILE; i++)
		for (occ = 0; occ < 0x100; occ++) {
			U64 mask = 0;
			int f;

			// calculate rank_slides
			for (f = i-1; f >= 0; f--) {
				set_bit(&mask, f);
				if (test_bit(occ, f)) break;
			}
			for (f = i+1; f < 8; f++) {
				set_bit(&mask, f);
				if (test_bit(occ, f)) break;
			}
			rank_slides[i][occ] = mask;

			// calculate file_slides (just symetric)
			file_slides[i][occ] = symetric(mask);
		}
}

static void init_diag_slides()
{
	memset(diag_a1h8_slides, 0, sizeof(diag_a1h8_slides));
	memset(diag_a8h1_slides, 0, sizeof(diag_a8h1_slides));

	int sq, occ, i;
	for (sq = A1; sq <= H8; sq++) {
		int f = file(sq), r = rank(sq);

		// calculate diag_a1h8_slides
		for (occ = 0; occ <= diag_mask[f + r]; occ++) {
			int _sq = r + f < 8				// first square of the diag a1h8 containing sq
			? square(r + f, 0)
			: square(7, f + r - 7);
			int pos = r + f < 8 ? f : 7 - r;	// pos on the diag: top left -> bottom right
			U64 mask = rank_slides[pos][occ] & diag_mask[f + r];	// copy this onto the diag

			for (i = 0; i < 8; i++, _sq -= 7)
				if (test_bit(mask, i))
					set_bit(&diag_a1h8_slides[sq][occ], _sq);
		}

		// calculate diag_a8h1_slides
		for (occ = 0; occ <= diag_mask[f + 7-r]; occ++) {
			int _sq = 7-r + f < 8			// first square of the diag a8h1 containing sq
			? square(7, f + 7-r)
			: square(r + 7-f, 7);
			int pos = 7-r + f < 8 ? 7-r : 7-f;	// pos on the diag: top right -> bottom left
			U64 mask = rank_slides[pos][occ] & diag_mask[f + 7-r];	// copy this onto the diag

			for (i = 0; i < 8; i++, _sq -= 9)
				if (test_bit(mask, i))
					set_bit(&diag_a8h1_slides[sq][occ], _sq);
		}
	}
}

static void init_BR_pseudo_attacks()
{
	occ_t occ;
	memset(&occ, 0, sizeof(occ_t));

	int sq;
	for (sq = A1; sq <= H8; sq++) {
		BPseudoAttacks[sq] = bishop_attack(&occ, sq);
		RPseudoAttacks[sq] = rook_attack(&occ, sq);
	}
}

/* Occupancy primitives */

void clear_occ(occ_t *occ, int sq)
{
	assert(square_ok(sq));
	clear_bit(&occ->all, sq);
	clear_bit(&occ->all_sym, square(file(sq), rank(sq)));
	clear_bit(&occ->all_a1h8, rot_a1h8[sq]);
	clear_bit(&occ->all_a8h1, rot_a8h1[sq]);
}

void set_occ(occ_t *occ, int sq)
{
	assert(square_ok(sq));
	set_bit(&occ->all, sq);
	set_bit(&occ->all_sym, square(file(sq), rank(sq)));
	set_bit(&occ->all_a1h8, rot_a1h8[sq]);
	set_bit(&occ->all_a8h1, rot_a8h1[sq]);
}

U64 rook_attack(const occ_t *occ, int sq)
{
	assert(square_ok(sq));
	int r = rank(sq), f = file(sq);

	return (rank_slides[f][(occ->all >> (r * 8)) & 0xFF] << (r * 8))
	       | (file_slides[r][(occ->all_sym >> (f * 8)) & 0xFF] << f);
}

U64 bishop_attack(const occ_t *occ, int sq)
{
	assert(square_ok(sq));
	int r = rank(sq), f = file(sq),
	    diagno_a1h8 = r + f,
	    diagno_a8h1 = 7-r + f;

	U64 occ_a1h8 = (occ->all_a1h8 >> diag_shift[diagno_a1h8]) & diag_mask[diagno_a1h8],
	    occ_a8h1 = (occ->all_a8h1 >> diag_shift[diagno_a8h1]) & diag_mask[diagno_a8h1];

	return diag_a1h8_slides[sq][occ_a1h8] | diag_a8h1_slides[sq][occ_a8h1];
}

[lucasart]

4/ Post Scriptum

Here's how I display a bitboard (essential for debugging)

Code: Select all

void print_bitboard(U64 b)
{
	int r, f;
	for (r = Rank8; r >= Rank1; r--) {
		for (f = FileA; f <= FileH; f++) {
			int sq = square(r, f);
			char c = test_bit(b, sq)
				? 'X'
				: '.';
			printf(" %c", c);
		}
		printf("\n");
	}
}

Credits
The only code I took is the count_bit and first_bit functions. My implementation of those is basically a verbatim copy of StockFish's one.
All the rest I wrote from scratch, including rotated bitboards, which I heard about in an article from Beowulf explaining how they work. You can also look at the chess programming wiki for that, but it wasn't available at the time I wrote this code. I reused my code from my previous program BibiChess 0.5 on the rotated BB stuff.

Hope it helps !

[hgm]

Bitboards representation and move generation are typically the first step that discourages most beginners.

Yes, well, that is of course exactly why beginners should never use bitboards...

[lucasart]

Bitboards representation and move generation are typically the first step that discourages most beginners.

Yes, well, that is of course exactly why beginners should never use bitboards...

I don't agree. When I started, I did a non bitboard representation. It looks easier, and you think you've gained a lot of effort by avoiding bitboards. But when you start writing the move generation code, your life becomes hell very quickly! And same for the evaluation and, in fact, every part of your chess program that manipulates the chess board. So what you think you've saved in the first place, you end up paying for afterwards.

By beginners, I don't mean people who are just copying a "hello world" program fro a manual and compiling it. These people shouldn't even dream about chess programming, and they shouldn't even be coding in C in the first place.

[hgm]

What is so hellish about mailbox move-generation code? Mine is only 30 lines, or so...

Code: Select all

    // GENERATE MOVES, put them on back-to-back capture and non-capt stacks
    bestMove = capts = lastMove = nonCapts = moveSP += 256;   // reserve space for move list

    protected = 0;
    for(piece = stm + 15; piece >= stm; piece--) { // loop over our pieces
        if((from = pos[piece]) == 0xFF) continue;  // is captured
        dir = firstDirTab[ firstDir[piece]+from ];
        while(step = steps[dir]) { // loop over directions
            to = from + step;
            do{ // scan along ray (ends after one iteration for leapers)
#ifdef XQ
                if(block[dir] && board[block[dir]+from] != EMPTY)
                    break; // lame leaper is blocked, next direction
#endif
                victim = board[to];
                if(victim != EMPTY) {              // capture
#ifdef XQ
                    if(dir >= 92) {                // Cannon
                        // displace toSqr to first obstacle after platform
                        while((victim = board[to+=step]) == EMPTY);
                    }
#endif
                    if((victim & ~COLOR) == 0) {  // King capture
                        bestScore = INF; //nodeCnt-=depth==0;
                        goto KingCapt;
                    }
                    moveStack[--capts].u.from = from;
                    moveStack[capts].u.to = to;
                    moveStack[capts].u.key = (PST[victim][to]+0x400000>>17) - (PST[piece][from]>>21);
                } else {                           // non-capture
                    moveStack[lastMove].u.key  = (PST[piece][to] - PST[piece][from] >> 16) + 128;
                    moveStack[lastMove].u.from = from;
                    moveStack[lastMove++].u.to = to;
                }

                to += step;
            } while(!(victim-EMPTY | dir<75));     // end if leaper or capt
            dir++;                                 // try new direction
        }
    }

[lucasart]

What is so hellish about mailbox move-generation code? Mine is only 30 lines, or so...

Code: Select all

    // GENERATE MOVES, put them on back-to-back capture and non-capt stacks
    bestMove = capts = lastMove = nonCapts = moveSP += 256;   // reserve space for move list

    protected = 0;
    for(piece = stm + 15; piece >= stm; piece--) { // loop over our pieces
        if((from = pos[piece]) == 0xFF) continue;  // is captured
        dir = firstDirTab[ firstDir[piece]+from ];
        while(step = steps[dir]) { // loop over directions
            to = from + step;
            do{ // scan along ray (ends after one iteration for leapers)
#ifdef XQ
                if(block[dir] && board[block[dir]+from] != EMPTY)
                    break; // lame leaper is blocked, next direction
#endif
                victim = board[to];
                if(victim != EMPTY) {              // capture
#ifdef XQ
                    if(dir >= 92) {                // Cannon
                        // displace toSqr to first obstacle after platform
                        while((victim = board[to+=step]) == EMPTY);
                    }
#endif
                    if((victim & ~COLOR) == 0) {  // King capture
                        bestScore = INF; //nodeCnt-=depth==0;
                        goto KingCapt;
                    }
                    moveStack[--capts].u.from = from;
                    moveStack[capts].u.to = to;
                    moveStack[capts].u.key = (PST[victim][to]+0x400000>>17) - (PST[piece][from]>>21);
                } else {                           // non-capture
                    moveStack[lastMove].u.key  = (PST[piece][to] - PST[piece][from] >> 16) + 128;
                    moveStack[lastMove].u.from = from;
                    moveStack[lastMove++].u.to = to;
                }

                to += step;
            } while(!(victim-EMPTY | dir<75));     // end if leaper or capt
            dir++;                                 // try new direction
        }
    }

OK here's my version of generating all legal moves for pieces, when the current position isn't a check. And I insist on *legal* moves, not *pseudo-legal*. With all due respect, I find it more readable and easier to write than your mailbox hell

Code: Select all

move_t *gen_piece_moves(const Board *B, U64 targets, move_t *mlist, int king_moves)
/* Generates piece moves, when the board is not in check. Uses targets to filter the tss, eg.
 * targets = ~friends (all moves), empty (quiet moves only), enemies (captures only). */
{
	assert(!king_moves || !board_is_check(B));
	const int us = B->turn, them = opp_color(us);
	const int last_piece = king_moves ? King : Queen;
	assert(!(targets & B->all[us]));
	U64 fss, tss;
	
	for (int piece = Bishop; piece <= last_piece; piece++) {
		fss = B->b[us][piece];

		while (fss) {
			int fsq = next_bit(&fss);
			U64 tss = piece_attack(&B->occ, piece, fsq) & targets;

			if (piece == King)	// filter direct self checks
				tss &= ~B->st->attacks;

			while (tss) {
				int tsq = next_bit(&tss);
				mlist = serialize_moves(B, fsq, tsq, mlist);
			}
		}
	}

	return mlist;
}

[hgm]

Except of course that the code you show does not really do anything at all. All the work is done by the routines next_bit, serialize_moves, piece_attack... Note that there is not a single function call in the code I showed. That code is not just a facade, but the real thing.

If I would show my code at the same level as yours, it would look like

Code: Select all

GenMoves(stm);

Which code is simpler now?