BitBoard representations of the board

Discussion of chess software programming and technical issues.

Moderators: Harvey Williamson, bob, hgm

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Uri Blass
Posts: 8794
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

BitBoard representations of the board

Post by Uri Blass » Sun Oct 14, 2007 9:16 am

BitBoard chess program are based on an injective function from squares of the board to 64 integers (0-63) in other words

f:{A1,B1,...H1,...H8}:->{0-63) that has the property f(sq1)!=f(sq2) for
sq1!=sq2

Every square has a file('a'-'h') and a rank 1-8
define
fil_number(sq)=fil(sq)-'a'
rank_number(sq)=rank(sq)-1

f(sq)=fil_number(sq)+8*rank_number(sq) is a possible function to start from it a bitboard chess program.

I wonder what other functions are practiclly used as a basis for bitboard chess programs(there are 64! possible functions)

Some simple alternatives are:
f(sq)=(7-fil_number(sq))+8*rank_number(sq)
f(sq)=(7-fil_number(sq))+8*(7-rank_number(sq))
f(sq)=fil_number(sq)+8*(7-rank_number(sq))


Uri

Gerd Isenberg
Posts: 2200
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: BitBoard representations of the board

Post by Gerd Isenberg » Sun Oct 14, 2007 4:09 pm

Uri Blass wrote:BitBoard chess program are based on an injective function from squares of the board to 64 integers (0-63) in other words

f:{A1,B1,...H1,...H8}:->{0-63) that has the property f(sq1)!=f(sq2) for
sq1!=sq2

Every square has a file('a'-'h') and a rank 1-8
define
fil_number(sq)=fil(sq)-'a'
rank_number(sq)=rank(sq)-1

f(sq)=fil_number(sq)+8*rank_number(sq) is a possible function to start from it a bitboard chess program.

I wonder what other functions are practiclly used as a basis for bitboard chess programs(there are 64! possible functions)

Some simple alternatives are:
f(sq)=(7-fil_number(sq))+8*rank_number(sq)
f(sq)=(7-fil_number(sq))+8*(7-rank_number(sq))
f(sq)=fil_number(sq)+8*(7-rank_number(sq))


Uri
Hi Uri,

I don't understand your question. What does your f(sq) have to do with bitboards? It seems about mapping a number to a square or a mirrored and flipped square.

Bitboards implement a set (or list) of up to 64 distinct squares.
bitboard = 2^sq1 | 2^sq2 | ... | 2^sqN

The union of two sets is done by bitwise or (or if the sets are disjoint by add, xor), intersection by and, different elements by bitwise xor, complement set by bitwise not. Movement, aka +- 1,7,8,9 is done with all members of the squares by shift left, right. Where you need wrap-conditions you simply need pre- or post-and masks before or after shifting one file left or right (+-1,7,9). Flipping the ranks, aka scalarwise xor 56, can be done setwise by bytewise little-big endian conversion, swapping byte 0 with 7, 1 with 6 etc., aka x86 bswap. Mirroring files (xor 7) is a bit harder setwise, swapping one,two and four bits by consecutive shifts, and, or.

If you have a square of a white pawn, and you look whether the pawn is a passer, you may use an expression like this, whith a precalculated sets[{white,black}][square], which contains all squares of the file and adjacent files in front of the pawn.

Code: Select all

   if ( (blockersAndGuards[black][squareOfwhitePawn] & blackPawns) == 0 )
   {
       // is a passer
   }
The setwise approach is to do it with all pawns in parallel:

Code: Select all

blackFrontSpans  = blackPawnAttacks | blackPawnStop;
blackFrontSpans |= blackFrontSpan >>  8;
blackFrontSpans |= blackFrontSpan >> 16;
blackFrontSpans |= blackFrontSpan >> 32;
whitePassers     = whitePawns & ~blackFrontSpans;
While the setwise approach looks more expensive, it has no lookups and hoist conditional loop bodies over all pawns. Also most intermediate sets, such as disjoint front- and rear span-sets are re-used for a lot of other purposes. Working in the bitboard centric, setwise world allows computing independent sets in parallel.

Gerd

Chan Rasjid
Posts: 567
Joined: Thu Mar 09, 2006 3:47 pm
Location: Singapore

Re: BitBoard representations of the board

Post by Chan Rasjid » Sun Oct 14, 2007 4:49 pm

Hello Uri,

I have just finished a basic revision of my codes as I have moved development from Windows-XP+Visual C++ to Fedora7 and KDevelop IDE and gcc.BTW KDevelop IDE is great! debugs easily with GDB.

Currently I still only manage to play matches with WindowsXP. Without bugs, OK.

My bitboard basics are these. If anyone sees anything silly, please let me know.

Code: Select all

//config.h
#if	defined(MS_VISUAL_C)
typedef int bool;
enum{ false, true };

typedef unsigned _int64		u64;
typedef signed _int64			i64;
typedef unsigned _int32		u32;
typedef signed _int32			i32;
typedef unsigned _int16		u16;
typedef signed _int16			i16;
typedef unsigned _int8		u8;
typedef signed _int8			i8;

#define FILE_1				(u64)0x0101010101010101
#define RANK_1  			(u64)0xff

#define  BoardAll	        (u64)0xffffffffffffffff
#define  BoardBlack  		(u64)0x55aa55aa55aa55aa
#define  BoardWhite 		~BoardBlack

#else
/* assume GCC + linux / MINGW + windows_xp */
#include <stdint.h>
#include <stdbool.h>
/*has bool, true,  false */

typedef uint64_t		u64;
typedef int64_t		i64;
typedef uint32_t		u32;
typedef int32_t		i32;
typedef uint16_t		u16;
typedef int16_t		i16;
typedef uint8_t		u8;
typedef int8_t		    i8;


#define FILE_1  				0x0101010101010101ULL
#define RANK_1  		0xffULL

#define  BoardAll	        0xffffffffffffffffULL
#define  BoardBlack  		0x55aa55aa55aa55aaULL
#define  BoardWhite 		~BoardBlack

#endif

//bitboard.h ...
#include "config.h"
enum &#123;
    A8, B8, C8, D8, E8, F8, G8, H8,
    A7, B7, C7, D7, E7, F7, G7, H7,
    A6, B6, C6, D6, E6, F6, G6, H6,
    A5, B5, C5, D5, E5, F5, G5, H5,
    A4, B4, C4, D4, E4, F4, G4, H4,
    A3, B3, C3, D3, E3, F3, G3, H3,
    A2, B2, C2, D2, E2, F2, G2, H2,
    A1, B1, C1, D1, E1, F1, G1, H1
&#125;;
/*  bitboard of squares */
#define  bbA1  ((&#40;u64&#41;1&#41; << A1&#41;
#define  bbB1  ((&#40;u64&#41;1&#41; << B1&#41;
#define  bbC1  ((&#40;u64&#41;1&#41; << C1&#41;
#define  bbD1  ((&#40;u64&#41;1&#41; << D1&#41;
#define  bbE1  ((&#40;u64&#41;1&#41; << E1&#41;
#define  bbF1  ((&#40;u64&#41;1&#41; << F1&#41;
#define  bbG1  ((&#40;u64&#41;1&#41; << G1&#41;
#define  bbH1  ((&#40;u64&#41;1&#41; << H1&#41;

#define  bbA2  ((&#40;u64&#41;1&#41; << A2&#41;
#define  bbB2  ((&#40;u64&#41;1&#41; << B2&#41;
#define  bbC2  ((&#40;u64&#41;1&#41; << C2&#41;
#define  bbD2  ((&#40;u64&#41;1&#41; << D2&#41;
#define  bbE2  ((&#40;u64&#41;1&#41; << E2&#41;
#define  bbF2  ((&#40;u64&#41;1&#41; << F2&#41;
#define  bbG2  ((&#40;u64&#41;1&#41; << G2&#41;
#define  bbH2  ((&#40;u64&#41;1&#41; << H2&#41;

#define  bbA3  ((&#40;u64&#41;1&#41; << A3&#41;
#define  bbB3  ((&#40;u64&#41;1&#41; << B3&#41;
#define  bbC3  ((&#40;u64&#41;1&#41; << C3&#41;
#define  bbD3  ((&#40;u64&#41;1&#41; << D3&#41;
#define  bbE3  ((&#40;u64&#41;1&#41; << E3&#41;
#define  bbF3  ((&#40;u64&#41;1&#41; << F3&#41;
#define  bbG3  ((&#40;u64&#41;1&#41; << G3&#41;
#define  bbH3  ((&#40;u64&#41;1&#41; << H3&#41;

#define  bbA4  ((&#40;u64&#41;1&#41; << A4&#41;
#define  bbB4  ((&#40;u64&#41;1&#41; << B4&#41;
#define  bbC4  ((&#40;u64&#41;1&#41; << C4&#41;
#define  bbD4  ((&#40;u64&#41;1&#41; << D4&#41;
#define  bbE4  ((&#40;u64&#41;1&#41; << E4&#41;
#define  bbF4  ((&#40;u64&#41;1&#41; << F4&#41;
#define  bbG4  ((&#40;u64&#41;1&#41; << G4&#41;
#define  bbH4  ((&#40;u64&#41;1&#41; << H4&#41;

#define  bbA5  ((&#40;u64&#41;1&#41; << A5&#41;
#define  bbB5  ((&#40;u64&#41;1&#41; << B5&#41;
#define  bbC5  ((&#40;u64&#41;1&#41; << C5&#41;
#define  bbD5  ((&#40;u64&#41;1&#41; << D5&#41;
#define  bbE5  ((&#40;u64&#41;1&#41; << E5&#41;
#define  bbF5  ((&#40;u64&#41;1&#41; << F5&#41;
#define  bbG5  ((&#40;u64&#41;1&#41; << G5&#41;
#define  bbH5  ((&#40;u64&#41;1&#41; << H5&#41;

#define  bbA6  ((&#40;u64&#41;1&#41; << A6&#41;
#define  bbB6  ((&#40;u64&#41;1&#41; << B6&#41;
#define  bbC6  ((&#40;u64&#41;1&#41; << C6&#41;
#define  bbD6  ((&#40;u64&#41;1&#41; << D6&#41;
#define  bbE6  ((&#40;u64&#41;1&#41; << E6&#41;
#define  bbF6  ((&#40;u64&#41;1&#41; << F6&#41;
#define  bbG6  ((&#40;u64&#41;1&#41; << G6&#41;
#define  bbH6  ((&#40;u64&#41;1&#41; << H6&#41;

#define  bbA7  ((&#40;u64&#41;1&#41; << A7&#41;
#define  bbB7  ((&#40;u64&#41;1&#41; << B7&#41;
#define  bbC7  ((&#40;u64&#41;1&#41; << C7&#41;
#define  bbD7  ((&#40;u64&#41;1&#41; << D7&#41;
#define  bbE7  ((&#40;u64&#41;1&#41; << E7&#41;
#define  bbF7  ((&#40;u64&#41;1&#41; << F7&#41;
#define  bbG7  ((&#40;u64&#41;1&#41; << G7&#41;
#define  bbH7  ((&#40;u64&#41;1&#41; << H7&#41;

#define  bbA8  ((&#40;u64&#41;1&#41; << A8&#41;
#define  bbB8  ((&#40;u64&#41;1&#41; << B8&#41;
#define  bbC8  ((&#40;u64&#41;1&#41; << C8&#41;
#define  bbD8  ((&#40;u64&#41;1&#41; << D8&#41;
#define  bbE8  ((&#40;u64&#41;1&#41; << E8&#41;
#define  bbF8  ((&#40;u64&#41;1&#41; << F8&#41;
#define  bbG8  ((&#40;u64&#41;1&#41; << G8&#41;
#define  bbH8  ((&#40;u64&#41;1&#41; << H8&#41;

#define File1   &#40;FILE_1&#41;
#define File2   &#40;FILE_1 << 1&#41;
#define File3   &#40;FILE_1 << 2&#41;
#define File4   &#40;FILE_1 << 3&#41;
#define File5   &#40;FILE_1 << 4&#41;
#define File6   &#40;FILE_1 << 5&#41;
#define File7   &#40;FILE_1 << 6&#41;
#define File8   &#40;FILE_1 << 7&#41;

#define FileA   File1
#define FileB   File2
#define FileC   File3
#define FileD   File4
#define FileE   File5
#define FileF   File6
#define FileG   File7
#define FileH   File8


#define Rank1   &#40;RANK_1&#41;
#define Rank2   &#40;RANK_1 << 8&#41;
#define Rank3   &#40;RANK_1 << 16&#41;
#define Rank4   &#40;RANK_1 << 24&#41;
#define Rank5   &#40;RANK_1 << 32&#41;
#define Rank6   &#40;RANK_1 << 40&#41;
#define Rank7   &#40;RANK_1 << 48&#41;
#define Rank8   &#40;RANK_1 << 56&#41;
Rasjid
Don't believe when you're told "There's no free lunch!" There is Linux.

Uri Blass
Posts: 8794
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: BitBoard representations of the board

Post by Uri Blass » Sun Oct 14, 2007 5:43 pm

Gerd Isenberg wrote:
Uri Blass wrote:BitBoard chess program are based on an injective function from squares of the board to 64 integers (0-63) in other words

f:{A1,B1,...H1,...H8}:->{0-63) that has the property f(sq1)!=f(sq2) for
sq1!=sq2

Every square has a file('a'-'h') and a rank 1-8
define
fil_number(sq)=fil(sq)-'a'
rank_number(sq)=rank(sq)-1

f(sq)=fil_number(sq)+8*rank_number(sq) is a possible function to start from it a bitboard chess program.

I wonder what other functions are practiclly used as a basis for bitboard chess programs(there are 64! possible functions)

Some simple alternatives are:
f(sq)=(7-fil_number(sq))+8*rank_number(sq)
f(sq)=(7-fil_number(sq))+8*(7-rank_number(sq))
f(sq)=fil_number(sq)+8*(7-rank_number(sq))


Uri
Hi Uri,

I don't understand your question. What does your f(sq) have to do with bitboards? It seems about mapping a number to a square or a mirrored and flipped square.

Bitboards implement a set (or list) of up to 64 distinct squares.
bitboard = 2^sq1 | 2^sq2 | ... | 2^sqN

The union of two sets is done by bitwise or (or if the sets are disjoint by add, xor), intersection by and, different elements by bitwise xor, complement set by bitwise not. Movement, aka +- 1,7,8,9 is done with all members of the squares by shift left, right. Where you need wrap-conditions you simply need pre- or post-and masks before or after shifting one file left or right (+-1,7,9). Flipping the ranks, aka scalarwise xor 56, can be done setwise by bytewise little-big endian conversion, swapping byte 0 with 7, 1 with 6 etc., aka x86 bswap. Mirroring files (xor 7) is a bit harder setwise, swapping one,two and four bits by consecutive shifts, and, or.

If you have a square of a white pawn, and you look whether the pawn is a passer, you may use an expression like this, whith a precalculated sets[{white,black}][square], which contains all squares of the file and adjacent files in front of the pawn.

Code: Select all

   if ( &#40;blockersAndGuards&#91;black&#93;&#91;squareOfwhitePawn&#93; & blackPawns&#41; == 0 )
   &#123;
       // is a passer
   &#125;
The setwise approach is to do it with all pawns in parallel:

Code: Select all

blackFrontSpans  = blackPawnAttacks | blackPawnStop;
blackFrontSpans |= blackFrontSpan >>  8;
blackFrontSpans |= blackFrontSpan >> 16;
blackFrontSpans |= blackFrontSpan >> 32;
whitePassers     = whitePawns & ~blackFrontSpans;
While the setwise approach looks more expensive, it has no lookups and hoist conditional loop bodies over all pawns. Also most intermediate sets, such as disjoint front- and rear span-sets are re-used for a lot of other purposes. Working in the bitboard centric, setwise world allows computing independent sets in parallel.

Gerd
I understand what bitboards do but the bitboards of white pawns can get different arithmetic values if you define the squares to be different numbers.

WhitePawns for example in the opening position is always
(2^A2)+(2^B2)+(2^C2)+(2^D2)+(2^E2)+(2^F2)+(2^G2)+(2^H2)

The point is that this 64 bit number may be different for different programs because of different values of A2-H2 and I asked what people use as values for the squares or in other words what function they use.

I do not know which values are better to make the program faster and I have no reason to assume that A1=0,B1=1,...H1=7,...H8=63 are best

These values can be expressed by
f(A1)=0
f(B1)=1
...
f(H1)=7
f(H8)=63

I did not like to write with ... that give other people to guess what I mean
and is not an exact definition
so I found the mathematical formula

f(sq)=fil_number(sq)+8*rank_number(sq) after defining fil_number and rank_number.

Edit:Note that A1=0 is not mathematically correct and is only a definition that is used by part of the BitBoard chess programs.

A1 is a square and 0 is a number so in order to be mathematically correct in my post I wrote f(A1)=0

program can also use fA1=0 fB1=1,...as constants but I think that it is more simple to use A1=0 B1=1 when the intention is clear.

Uri

Gerd Isenberg
Posts: 2200
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: BitBoard representations of the board

Post by Gerd Isenberg » Sun Oct 14, 2007 7:08 pm

Uri Blass wrote:I understand what bitboards do but the bitboards of white pawns can get different arithmetic values if you define the squares to be different numbers.

WhitePawns for example in the opening position is always
(2^A2)+(2^B2)+(2^C2)+(2^D2)+(2^E2)+(2^F2)+(2^G2)+(2^H2)

The point is that this 64 bit number may be different for different programs because of different values of A2-H2 and I asked what people use as values for the squares or in other words what function they use.

I do not know which values are better to make the program faster and I have no reason to assume that A1=0,B1=1,...H1=7,...H8=63 are best

These values can be expressed by
f(A1)=0
f(B1)=1
...
f(H1)=7
f(H8)=63

I did not like to write with ... that give other people to guess what I mean
and is not an exact definition
so I found the mathematical formula

f(sq)=fil_number(sq)+8*rank_number(sq) after defining fil_number and rank_number.

Edit:Note that A1=0 is not mathematically correct and is only a definition that is used by part of the BitBoard chess programs.

A1 is a square and 0 is a number so in order to be mathematically correct in my post I wrote f(A1)=0

program can also use fA1=0 fB1=1,...as constants but I think that it is more simple to use A1=0 B1=1 when the intention is clear.

Uri
I think any arbitrary mapping or enumeration along ranks or files is fine and a matter of taste and habituation. There are approaches with redundant occupancies with different mapping, like rotated or reversed bitboards.

I use fileNr(a) == 0, fileNr(h) == 7 and rankNr(1) == 0 rankNr(8) == 7,
f(sq) = filenr + 8*ranknr

which is somehow natural in the sense that a < h and 1 < 8.
The drawback is while debugging, inspecting bitboard variables - binary (aka hex) numbers, the least significant digit is the rightmost, while square a1 is left from white points of view.

Enumerating along the file
f(sq) = ranknr + 8*filenr
or
f(sq) = ranknr ^ 8*filenr ^ 56
has an advantage for pawn attack or push shifts, since you don't need to consider wraps since pawns can never be on the 1. or 8.rank.

User avatar
hgm
Posts: 24956
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: BitBoard representations of the board

Post by hgm » Sun Oct 14, 2007 7:53 pm

I once experimented a bit with mappings that transformed symmetry operations on the board into simple bit-shifts / rotates in the bitbord as much as possible. This in the hope that it would reduce the table-space requirement for magic-bitboard move generation, by allowing symmetry-related squares to use the same tables.

Problem is that the 12 squares on the diagnals belong to a higher symmetry group than the non-diagonal squares. Even if I reduced teh symmetry only to a C4 rotation group, not exploiting board reflections, mapping the bits such that a 90-degree rotation of the board would correspond to a rotate left by 16 bits of the bitboard, I could not easily map the squares to bits in such a way that no collisions in the high bits of the bitboard would occur.

So I abandoned the idea for now. Especially since my engines do not use bitbords anyway...

bob
Posts: 20918
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: BitBoard representations of the board

Post by bob » Sun Oct 14, 2007 8:08 pm

that question I can answer for me...

A1 = bit 0 (LSB), B1 = bit 1, ..., H1 = bit 7, ..., H8 = bit 63.

I chose this to make the bits line up with the BSF/BSR way of counting where LSB = 0, MSB = 63. For the rest, the property File(sq) = 0 for A1-A8 and File(sq) is defined simply as sq >> 3. Ditto for rank where Rank(A1) = 0, Rank(A8) = 7, where Rank(sq) is defined is sq & 7.

Any mapping can be made to work however as mine used to be backward because of the way the Cray does big scanning in the opposite way of Intel.

Uri Blass
Posts: 8794
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: BitBoard representations of the board

Post by Uri Blass » Sun Oct 14, 2007 8:16 pm

hgm wrote:I once experimented a bit with mappings that transformed symmetry operations on the board into simple bit-shifts / rotates in the bitbord as much as possible. This in the hope that it would reduce the table-space requirement for magic-bitboard move generation, by allowing symmetry-related squares to use the same tables.

Problem is that the 12 squares on the diagnals belong to a higher symmetry group than the non-diagonal squares. Even if I reduced teh symmetry only to a C4 rotation group, not exploiting board reflections, mapping the bits such that a 90-degree rotation of the board would correspond to a rotate left by 16 bits of the bitboard, I could not easily map the squares to bits in such a way that no collisions in the high bits of the bitboard would occur.

So I abandoned the idea for now. Especially since my engines do not use bitbords anyway...
I do not understand what was your target.
Did you try to use bitboards in order to change the board position to symmetric board position and how did you think to use bitboards?

Note that when you have pawns in the board B3 is not symmetric to C2 and the problem that you mention of higher symmetry group is only when there are no pawns and in this case B3 C2 G3 F2 B6 C7 G6 F7 can be considered as symmetric when B2 has only 3 symmetric squares.

Uri

Gerd Isenberg
Posts: 2200
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: BitBoard representations of the board

Post by Gerd Isenberg » Sun Oct 14, 2007 8:45 pm

bob wrote:that question I can answer for me...

A1 = bit 0 (LSB), B1 = bit 1, ..., H1 = bit 7, ..., H8 = bit 63.

I chose this to make the bits line up with the BSF/BSR way of counting where LSB = 0, MSB = 63. For the rest, the property File(sq) = 0 for A1-A8 and File(sq) is defined simply as sq >> 3. Ditto for rank where Rank(A1) = 0, Rank(A8) = 7, where Rank(sq) is defined is sq & 7.

Any mapping can be made to work however as mine used to be backward because of the way the Cray does big scanning in the opposite way of Intel.
The question whether a1, h1, a8 or h8 is least significant square is independent on how you count or scan bits from 0 to 63 in a 64-bit word. Since K10 and future intel (SSE5 something) will have leading zero count (even faster direct path instruction on K10), you may switch back again to save the xor 63 ;-)

lzc even leaves deterministic 64 for empty sets.

User avatar
hgm
Posts: 24956
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: BitBoard representations of the board

Post by hgm » Sun Oct 14, 2007 9:28 pm

Uri Blass wrote:I do not understand what was your target.
Did you try to use bitboards in order to change the board position to symmetric board position and how did you think to use bitboards?
The symmetry was only of importance in the magic-multiplication method for getting slider attacks. All sliders in Chess have full8-fold symmetry.

The idea was that if the occupancy set of, say, c2 was merely an 16-bit left-shifted version of the occupancy set of g3, I could multiply it with a 16-bit right-shifted magic constant (i.e. magic[C2] == magic[G3]>>16), to get the same product for equivalent occupancy. I could then use the same table to retrieve the move set for c2 and g3 (and f7 and b6). Except that I would have to rotate the move board by 90 degrees, which would then also be a simple rotate instruction.

Post Reply