Board representation : Purely bitboard ?

[mathmoi]

Hi,

My last engine used an hybrid board representation. It has the twelve usual bitboard (One for every piece type of each sides) and a board[64] array. This last one was used to answer the question : wich piece is on square X. For example this was extensively used in the capture generations functions to get the type of the captured piece.

Is this how you all do this? Or do you use a Purely bitboard board representation?

Also is a piece list usefull, to generates moves without scanning bitboards looking for pieces?

Mathieu Pag

[Reinhard Scharnagl]

Hi mathmoi,

program Smirf does not use bitboards. But it has two implicite piece lists.

Reinhard.

[Leen Ammeraal]

Hi Mathieu,
In Queen, I do it in the same way as you, using bitboards as
well as an array, which I have declared as

Code: Select all

unsigned char a[64];

Leen Ammeraal

[Pradu]

Same as Leen.

[mathmoi]

Hi Mathieu,
In Queen, I do it in the same way as you, using bitboards as
well as an array, declared as
unsigned char a[64];
Leen Ammeraal

Hi Leen,

It's probably the right things to do then. Thanks you for the answer.

Mathieu Pag

[Peter Fendrich]

Is this how you all do this? Or do you use a Purely bitboard board representation?

I believe that most programs are not bitboard based at all and that goes for commercial programs as well. In the the end it all comes down to personal taste. Choose the representation you like most and think is fun to work with!

Also is a piece list usefull, to generates moves without scanning bitboards looking for pieces?

I think that a piece list is useful for both biboard and other representations but in a bitboard program the piece list are the bitboards together!
I've tried to combine bitboards with other piece lists but it is costly to keep track of them both simutaneously.
/Peter

[Pradu]

Bitboard's don't have enough data density (for instance when generating captures) so it is necesary to have an array of piece types. Here is my board structure:

Code: Select all

//the board structure (found in defs.h in Witz)
typedef struct _brd
{
   U8    PieceTypes[64];        //All the piece types according to squares
   U64   AllPieces;             //All the pieces on the board
   U64   R45;                   //All the pieces rotated 45 degrees right
   U64   L45;                   //All the pieces rotated 45 degrees left
   U64   L90;                   //All the pieces rotated 90 degress left
   U64   PiecesSide[2];         //All the pieces belonging to each side
   U64   Pieces[NUMPIECETYPES]; //Specific pieces on the board
   U64   EP;                    //All enpassant squares
   U8    castling;              //Castling privilages - format defined below
   U8    fifty;                 //Fifty move count
   bool  side;                  //the side to play
   bool  xside;                 //the side opposite to play
   U64   hashkey;               //the hash key for the transposition table
}brd;

You can the (somewhat) current source for my program here.

I believe crafty has something similar to this, but the source is too complex so you can never tell .

I use 7 for NUMPIECETYPES by the way (one for null piece which you will see the need for in my source).

[Peter Fendrich]

Bitboard's don't have enough data density (for instance when generating captures) so it is necesary to have an array of piece types.

If it's necesary or not is debatle. My program Terra is a pure bitboard without any piece list similar to your "PieceTypes[64]". I'm quite convinced that Crafty doesn't have such lists either. It is at least as pure bitboard as Terra...
/Peter

[Pradu]

How do you generate captures Peter?

Yes, I do understand that you can and your bitboard with each piece to generate captures almost as efficiently as using a piece list but say for example you use a SEE. You must test the target square what kind of piece it is (Rook or Queen, or Queen or Bishops for ray casting) and it makes the code much more complex. I don't believe there is an efficient way of doing these tasks without using expensive testing.

And on the topic of crafty not using some sort of piece lists, if you check movegen.c and look at function GenerateCaptures you see this in every move generation loop:

*move++ = temp | (to << 6) | ((-PcOnSq(to)) << 15);

PcOnSq is a marco and you can check in the source. It looks like an incrementally updated piece list (correct me if I am wrong--Crafty code is very complex).

And also written by Hyatt on his website in the bitboard section (http://www.cis.uab.edu/hyatt/boardrep.html):

...One note is that we will likely decide to use an offset board representation to complement a bitmap approach. One reason for this is move generation. When we generate a target square for a piece, and discover this piece is occupied by an opponent's piece, we might want to store the captured piece as part of the move. Unfortunately, figuring out what we are capturing is not exactly trivial, because we have to create a bitmap with the target square bit set, and then AND this with each of the bitmaps for the opponent's pieces until we get a non-zero result. Not very efficient. It would be much better if we had a board[] offset representation as well, where board[square] contains a piece code for the piece that occupies that square. It seems redundant, and it really is, but it turns out to be more efficient to do this, ...

Although piecelists may not be the best for these tasks, it is the best I know so far so enlighten me on how you do it .

[Uri Blass]

Hi,

My last engine used an hybrid board representation. It has the twelve usual bitboard (One for every piece type of each sides) and a board[64] array. This last one was used to answer the question : wich piece is on square X. For example this was extensively used in the capture generations functions to get the type of the captured piece.

Is this how you all do this? Or do you use a Purely bitboard board representation?

Also is a piece list usefull, to generates moves without scanning bitboards looking for pieces?

Mathieu Pag?

No

This is not how all do it.
There are people who do not use bitboard.

Personally I have info[64] that give the piece type for every square but I do not use bitboards for move generation because I have also piece list.

I have no bitboards for most type of pieces but only bitboard for pawns.

Uri

[Roman Hartmann]

Hi,
I'm not using bitboards at all currently (I'm using a 10x12 array to represent the board and store integer values for the different pieces in that array).
Neither am I using a piece list. I tried an incremental updated piece list once but it didn't pay out for me as the overhead to keep the piece list up to date actually even slowed down my move generator quite a bit. So I'm back again looping through the whole board to find the pieces (keep only track of the kings). Just recently I had some ideas for another data structure to update a piece list with less work but I would have to rewrite big parts (parts that are working) of my engine and postponed that idea meanwhile. Maybe I will pick that idea up again if I find some time.

I'm planning to add bitboards for the pawn evaluation though. Seems to me that evaluation for pawn structures is relatively easy with some bitboard masks but I didn't actually try that yet.

Roman

[Peter Fendrich]

Maybe it's all about language and definitions...

How do you generate captures Peter?

I have two bitboards with white and black pieces. BBwhite and BBblack.
So generating white knight captures is:

Code: Select all

while (BBwn){
    from = getone(BBwn);
    BBto = Knightattacks(from) & BBblack;
    ...
}

Right? Maybe your question is how do I know what piece I captured? I have an 'int board[64]' which is the current board position right now. I never associated piece list with my board position but I suppose that was what you were talking about. For me piece list is something more than that.
I'm thinking bout piece lists in my non bitboard program these days...

Yes, I do understand that you can and your bitboard with each piece to generate captures almost as efficiently as using a piece list but say for example you use a SEE. You must test the target square what kind of piece it is (Rook or Queen, or Queen or Bishops for ray casting) and it makes the code much more complex. I don't believe there is an efficient way of doing these tasks without using expensive testing.

yeah, the same thing here...

Although piecelists may not be the best for these tasks, it is the best I know so far so enlighten me on how you do it .

Enlighten? Listen to me and I will lead you into darkness.
/Peter