Perfect Bitboard Piece Encoding

[dangi12012]

Maybe someone has differing thoughts on this:
A simple but very effective extended encoding scheme for bitboards is this:

Each of the 64 squares are encoded in a Quadboard: (64 vertically encoded nibbles in 256bit)

Code: Select all

0000 : empty_0  | 1000 : wpawn
0001 : empty_1  | 1001 : wknight
0010 : bpawn    | 1010 : wbishop
0011 : bknight  | 1011 : wrook
0100 : bbishop  | 1100 : wqueen
0101 : brook    | 1101 : wking
0110 : bqueen   | 1110 : wking_wmove
0111 : bking    | 1111 : special

wking_wmove = wking but its whites turn.
special on the corners of the board: Rook of the corresponding color - and equivalent to castling in that direction
special elsewhere: this is a pawn that just pushed (enpassant target)

This stores:
All pieces, color to move, castling rights, enpassant

Additional twist:
A chess position in any game must have at least 16 empty squares
The first 16 empty_0/1 squares: Empty + store 16 bits of extra data.

These 16bits can be picked freely and may be (repetition, eval, 50 move counter or anything else).

Comparing this to QBBEngine for example means that all the information below (with change) can be packed into a single Quadboard.

Code: Select all

/*
Board structure definition
PM,P0,P1,P2 are the 4 bitboards that contain the whole board
PM is the bitboard with the side to move pieces
P0,P1 and P2: with these bitboards you can obtain every type of pieces and every pieces combinations.
*/
typedef struct
{
   TBB PM;
   TBB P0;
   TBB P1;
   TBB P2;
   uint8_t CastleFlags; /* ..sl..SL  short long opponent SHORT LONG side to move */
   uint8_t EnPassant; /* enpassant column, =8 if not set */
   uint8_t Count50; /* 50 move rule counter */
   uint8_t Rep; /* 0 if it's not a repetition, 1 if it is */
   uint8_t STM; /* side to move */
} TBoard;

Quad boards need to be packed and unpacked which can be expensive.
Now a question: What board structure do you use - and why?

[dangi12012]

Better encoding:

Contains all of the above but in
192 bits

Now encoding pawns as having bit 0/1 and empty squares 0/1 garuantees 16 extra bits of data. (even with promotion as enemies have to die for pawns to promote and thus freeing up empty squares)

Code: Select all

/*
0000 : bp_data0 | 1000 : wp_data0
0001 : bp_data1 | 1001 : wp_data1
0010 : bknight  | 1010 : wknight
0011 : bbishop  | 1011 : wbishop
0100 : brook    | 1100 : wrook
0101 : bqueen   | 1101 : wqueen
0110 : bking    | 1110 : wking	  
0111 : empty_0  | 1111 : empty_1  //This garuantees 16 extra bits of data. - (c:1, castling: 4, ep: 4)
*/
struct NibblePosition
{
	uint64_t Occ; 
	uint64_t d1;
	uint64_t d2;
};

Here 32 nibbles are stored in d1 and d2.

This is a fast middleground between actual compression where many steps are needed: http://www.talkchess.com/forum3/viewtop ... =7&t=76892
And uncompressed Bitboards as compression/uncompression takes just a single loop.

I might do a comparison of Bitboards and Mailslots in terms of Compression/Decompression nodes per second. Its an interesting topic - and being able to pick a structure in the optimal memory/compute curve for your project seems a good step to take.

[pedrojdm2021]

My thoughts on QuadBoards is that they for sure save ram memory, but ( as everything ) has it's bad side: it requires couple more operations to get the actual pieces bitboards,

to me the best approarch for bitboards are denser boards