Diagonal bitmaps

Code, algorithms, languages, construction...
Post Reply
MDV
Posts: 1
Joined: Mon Nov 16, 2020 2:55 am

Diagonal bitmaps

Post by MDV » Mon Nov 16, 2020 10:50 am

I have just ( last 2 weeks) started coding a chess-engine - thought it would be a fun spare-time project, from scratch.. and I discovered this site!
- I have a question about the way I am storing the state of the board.

I'm successfully enumerating all moves from a given position, ( including castling and en-passant). Data structures ? each colour has an AttackedBy bitmap per square and I also find that an AttackedBySliding is useful (sliding pieces - a subset of AttackedBy ) - An 'Attacking' bitmap is also needed, etc. There's a few other bits of data of course.

For occupancy (1 bit per square) I use 4 bitmaps for the board - ( one column-major, one row-major, and 2 for diagonals needed for Bishop/Queen).

The diagonals are the interesting one, and I wanted to check if this is the best way: 1 diagonal map (A) represents a 'low right to high left' diagonal, the other map (B) represents the opposite ( low left to high right). I define 2 arrays (below) -
for a given (x,y) board coordinate, the low diagonal bit of 'A' is given by BitIdx[x + y] + y , of 'B' by BitIdx[(7-x) + y] + y
and the corresponding mask of bits is given by BitMaskDiagonal[x + y], and BitMaskDiagonal[ (7-x) + y]

u8 Board::BitIdxl[] =
{
0,1,3,6,10,15,21,28,35,41,46,50,53,55,56
};

u64 Board::BitMaskDiagonal[] =
{
0b1Ui64,
0b11v << 1,
0b111Ui64 << 3,
0b1111Ui64 << 6,
0b11111Ui64 << 10,
0b111111Ui64 << 15,
0b1111111Ui64 << 21,
0b11111111Ui64 << 28,
0b1111111Ui64 << 36,
0b111111Ui64 << 43,
0b11111Ui64 << 49,
0b1111Ui64 << 54,
0b111Ui64 << 58,
0b11Ui64 << 61,
0b1Ui64 << 63,
};


I use the bitmask for sliding pieces to evaluate extents of threats ( basically, I split into L and R halves around the piece and use _BitScanForward64 and _BitScanReverse64 with some bitwise jiggery to efficiently create the threats from a sliding piece. It seems really fast
BUT as this is my first attempt at a chess engine, then there may be much faster ways than this.... any pointers or hints would be welcome,
particularly with the process of updating / restoring a position... since 'undoing' a position takes a bunch of bit-vector operations, not slow BUT ... faster is better... and the alternative would be to push/pop data... which would be probably around1.5k - even a fast copying would likely be slow, compared to the bunch of bit vector ALU operations...

Thanks for any hints here...

BrianR
Posts: 17
Joined: Thu Jun 10, 2010 4:48 am

Re: Diagonal bitmaps

Post by BrianR » Mon Nov 16, 2020 9:54 pm

If you have not looked here yet, there is a huge amount of info

https://www.chessprogramming.org/Main_Page

Post Reply