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
BitBoard representations of the board
Moderators: hgm, Rebel, chrisw
-
Uri Blass
- Posts: 10282
- Joined: Thu Mar 09, 2006 12:37 am
- Location: Tel-Aviv Israel
-
Gerd Isenberg
- Posts: 2250
- Joined: Wed Mar 08, 2006 8:47 pm
- Location: Hattingen, Germany
Re: BitBoard representations of the board
Hi Uri,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
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
}
Code: Select all
blackFrontSpans = blackPawnAttacks | blackPawnStop;
blackFrontSpans |= blackFrontSpan >> 8;
blackFrontSpans |= blackFrontSpan >> 16;
blackFrontSpans |= blackFrontSpan >> 32;
whitePassers = whitePawns & ~blackFrontSpans;
Gerd
-
Chan Rasjid
- Posts: 588
- Joined: Thu Mar 09, 2006 4:47 pm
- Location: Singapore
Re: BitBoard representations of the board
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.
Rasjid
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 {
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
};
/* bitboard of squares */
#define bbA1 (((u64)1) << A1)
#define bbB1 (((u64)1) << B1)
#define bbC1 (((u64)1) << C1)
#define bbD1 (((u64)1) << D1)
#define bbE1 (((u64)1) << E1)
#define bbF1 (((u64)1) << F1)
#define bbG1 (((u64)1) << G1)
#define bbH1 (((u64)1) << H1)
#define bbA2 (((u64)1) << A2)
#define bbB2 (((u64)1) << B2)
#define bbC2 (((u64)1) << C2)
#define bbD2 (((u64)1) << D2)
#define bbE2 (((u64)1) << E2)
#define bbF2 (((u64)1) << F2)
#define bbG2 (((u64)1) << G2)
#define bbH2 (((u64)1) << H2)
#define bbA3 (((u64)1) << A3)
#define bbB3 (((u64)1) << B3)
#define bbC3 (((u64)1) << C3)
#define bbD3 (((u64)1) << D3)
#define bbE3 (((u64)1) << E3)
#define bbF3 (((u64)1) << F3)
#define bbG3 (((u64)1) << G3)
#define bbH3 (((u64)1) << H3)
#define bbA4 (((u64)1) << A4)
#define bbB4 (((u64)1) << B4)
#define bbC4 (((u64)1) << C4)
#define bbD4 (((u64)1) << D4)
#define bbE4 (((u64)1) << E4)
#define bbF4 (((u64)1) << F4)
#define bbG4 (((u64)1) << G4)
#define bbH4 (((u64)1) << H4)
#define bbA5 (((u64)1) << A5)
#define bbB5 (((u64)1) << B5)
#define bbC5 (((u64)1) << C5)
#define bbD5 (((u64)1) << D5)
#define bbE5 (((u64)1) << E5)
#define bbF5 (((u64)1) << F5)
#define bbG5 (((u64)1) << G5)
#define bbH5 (((u64)1) << H5)
#define bbA6 (((u64)1) << A6)
#define bbB6 (((u64)1) << B6)
#define bbC6 (((u64)1) << C6)
#define bbD6 (((u64)1) << D6)
#define bbE6 (((u64)1) << E6)
#define bbF6 (((u64)1) << F6)
#define bbG6 (((u64)1) << G6)
#define bbH6 (((u64)1) << H6)
#define bbA7 (((u64)1) << A7)
#define bbB7 (((u64)1) << B7)
#define bbC7 (((u64)1) << C7)
#define bbD7 (((u64)1) << D7)
#define bbE7 (((u64)1) << E7)
#define bbF7 (((u64)1) << F7)
#define bbG7 (((u64)1) << G7)
#define bbH7 (((u64)1) << H7)
#define bbA8 (((u64)1) << A8)
#define bbB8 (((u64)1) << B8)
#define bbC8 (((u64)1) << C8)
#define bbD8 (((u64)1) << D8)
#define bbE8 (((u64)1) << E8)
#define bbF8 (((u64)1) << F8)
#define bbG8 (((u64)1) << G8)
#define bbH8 (((u64)1) << H8)
#define File1 (FILE_1)
#define File2 (FILE_1 << 1)
#define File3 (FILE_1 << 2)
#define File4 (FILE_1 << 3)
#define File5 (FILE_1 << 4)
#define File6 (FILE_1 << 5)
#define File7 (FILE_1 << 6)
#define File8 (FILE_1 << 7)
#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 (RANK_1)
#define Rank2 (RANK_1 << 8)
#define Rank3 (RANK_1 << 16)
#define Rank4 (RANK_1 << 24)
#define Rank5 (RANK_1 << 32)
#define Rank6 (RANK_1 << 40)
#define Rank7 (RANK_1 << 48)
#define Rank8 (RANK_1 << 56)
-
Uri Blass
- Posts: 10282
- Joined: Thu Mar 09, 2006 12:37 am
- Location: Tel-Aviv Israel
Re: BitBoard representations of the board
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.Gerd Isenberg wrote:Hi Uri,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
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.
The setwise approach is to do it with all pawns in parallel:Code: Select all
if ( (blockersAndGuards[black][squareOfwhitePawn] & blackPawns) == 0 ) { // is a passer }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.Code: Select all
blackFrontSpans = blackPawnAttacks | blackPawnStop; blackFrontSpans |= blackFrontSpan >> 8; blackFrontSpans |= blackFrontSpan >> 16; blackFrontSpans |= blackFrontSpan >> 32; whitePassers = whitePawns & ~blackFrontSpans;
Gerd
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: 2250
- Joined: Wed Mar 08, 2006 8:47 pm
- Location: Hattingen, Germany
Re: BitBoard representations of the board
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.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 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.
-
hgm
- Posts: 27796
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: BitBoard representations of the board
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...
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: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: BitBoard representations of the board
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.
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: 10282
- Joined: Thu Mar 09, 2006 12:37 am
- Location: Tel-Aviv Israel
Re: BitBoard representations of the board
I do not understand what was your target.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...
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: 2250
- Joined: Wed Mar 08, 2006 8:47 pm
- Location: Hattingen, Germany
Re: BitBoard representations of the board
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 63bob 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.
lzc even leaves deterministic 64 for empty sets.
-
hgm
- Posts: 27796
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: BitBoard representations of the board
The symmetry was only of importance in the magic-multiplication method for getting slider attacks. All sliders in Chess have full8-fold symmetry.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 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.