I'm Puzzled - Storing Piece Info & Magic Move Gen...

[Steve Maughan]

In my latest engine (Maverick), I'm intending to use the (oh-so-cool) Magic move generation technique for sliding pieces.

My first thought was to go completely bitboard based and store the bitboards for each piece type in an array such as:

Code: Select all

board->piece[color][type]

But then I realized I'd like to quickly know which piece is on a particular square. No problem, I'll just have a simple array:

Code: Select all

board->square[64]

Using this structure generating moves for pawns will be quick. I can see the clear advantage. But I cannot see the advantage for other pieces. What am I missing?

Wouldn't it be better (i.e. faster) to have a simple stack for the pieces (much like Fruit). Even the sliding pieces (e.g. the rook) don't need a specific bitboard as long as I know where they are and the location of friendly (or more specifically ~friendly) pieces. So I'll just keep an "all_pieces" and a "pieces[color]" bitboard up to date (as well as the pawn bitboard).

I'd appreciate any comments - especially if I'm missing anything,

Best,

Steve

[hgm]

You need bitboards for slider types to efficiently answer questions like "am I in check on this square?", "which of my pieces is pinned?" or "can I deliver a discovered check?" You would do this by intersecting the Rook set for the King with the bitboard of opponent orthogonal movers, and the Bishop set with the bitboard of opponent diagonal movers, etc.

[Chan Rasjid]

In my latest engine (Maverick), I'm intending to use the (oh-so-cool) Magic move generation technique for sliding pieces.

My first thought was to go completely bitboard based and store the bitboards for each piece type in an array such as:

Code: Select all

board->piece[color][type]

But then I realized I'd like to quickly know which piece is on a particular square. No problem, I'll just have a simple array:

Code: Select all

board->square[64]

Using this structure generating moves for pawns will be quick. I can see the clear advantage. But I cannot see the advantage for other pieces. What am I missing?

Wouldn't it be better (i.e. faster) to have a simple stack for the pieces (much like Fruit). Even the sliding pieces (e.g. the rook) don't need a specific bitboard as long as I know where they are and the location of friendly (or more specifically ~friendly) pieces. So I'll just keep an "all_pieces" and a "pieces[color]" bitboard up to date (as well as the pawn bitboard).

I'd appreciate any comments - especially if I'm missing anything,

Best,

Steve

I think there is no 'shorter' cut - you have to have pieceList[color][type, not king][16/index]. For the kings, just update the squares king[2] in makemove(). Very probably, all top bitboard programs have them. You scan the piece list for the pieces instead of 64 squares.

The real benefit of bitboards should be more with evaluation and not so much for move generations. My program has two phases for move generations - QS captures/promotions/ep and for the quiet moves. I only use bitboard for captures. For generating the quiet moves, I use mailbox.

Best Regards,
Rasjid.

[tpetzke]

Hi Steve,

I have a squares[64] structure in addition to the bit boards of each type and I maintain the position of the kings.

I don't have a piece list for the other pieces. I once had, but removed it later.

For move generation bit boards are very efficient to generate captures, for quiet moves it probably doesn't matter.

In evaluation they rule, especially if you have a rather big eval.

Thomas...

[Chan Rasjid]

Hello,

Hi Steve,

I have a squares[64] structure in addition to the bit boards of each type and I maintain the position of the kings.

I don't have a piece list for the other pieces. I once had, but removed it later.

For move generation bit boards are very efficient to generate captures, for quiet moves it probably doesn't matter.

In evaluation they rule, especially if you have a rather big eval.

Thomas...

I think there is some appreciable cost to update piece lists within makemove(). But I would be surprise if it speed things up without piece lists.

I could think of scanning the bits of bits[0][Rook] for white rooks and use bitscan to get the squares for the rooks. Is this way faster. I use to dislike bitScanForward as it is said to be expensive.

I may need to take away my piece lists.

Best Regards,
Rasjid.

[Steve Maughan]

Hi H.G,

You need bitboards for slider types to efficiently answer questions like "am I in check on this square?", "which of my pieces is pinned?" or "can I deliver a discovered check?" You would do this by intersecting the Rook set for the King with the bitboard of opponent orthogonal movers, and the Bishop set with the bitboard of opponent diagonal movers, etc.

OK - maybe pinned pieces and is-king-in-check (although I'm not 100% sure).

Thanks for the thoughts,

Steve

[Steve Maughan]

Hi Thomas,

[...] In evaluation they rule, especially if you have a rather big eval.[...]

I can see that bitboards in general are good in the evaluation, but can you give me an example where a bitboard of all white knights or all white rooks would be useful?

I still plan to do things like:

Code: Select all

center_control += popcount(knight_move[square] & center_squares);

Where square is the location of the knight.

Thanks,

Steve

[AlvaroBegue]

I could think of scanning the bits of bits[0][Rook] for white rooks and use bitscan to get the squares for the rooks. Is this way faster. I use to dislike bitScanForward as it is said to be expensive.

"It is said to be expensive" is not much of an argument for anything. Measure it!

Modern CPUs (the ones that support SSE 4.2) have hardware implementations for population count and finding the least-significant bit set (accessible through __builtin_popcountl and __builtin_ctzl, if you are using gcc).

[AlvaroBegue]

I can see that bitboards in general are good in the evaluation, but can you give me an example where a bitboard of all white knights or all white rooks would be useful?

I am not sure it's a good example, but I have something like this in my evaluation code:

Code: Select all

  // ROOKS ON OPEN COLUMNS
  u64 all_pawns = b.bb[WhitePawn] | b.bb[BlackPawn];
  u64 open_columns = ~saturate_vertically(all_pawns);
  int rooks_on_open_columns_score = rook_on_open_column_bonus * (popcount(b.bb[WhiteRook] & open_columns) - popcount(b.bb[BlackRook] & open_columns));

[bob]

In my latest engine (Maverick), I'm intending to use the (oh-so-cool) Magic move generation technique for sliding pieces.

My first thought was to go completely bitboard based and store the bitboards for each piece type in an array such as:

Code: Select all

board->piece[color][type]

But then I realized I'd like to quickly know which piece is on a particular square. No problem, I'll just have a simple array:

Code: Select all

board->square[64]

Using this structure generating moves for pawns will be quick. I can see the clear advantage. But I cannot see the advantage for other pieces. What am I missing?

Wouldn't it be better (i.e. faster) to have a simple stack for the pieces (much like Fruit). Even the sliding pieces (e.g. the rook) don't need a specific bitboard as long as I know where they are and the location of friendly (or more specifically ~friendly) pieces. So I'll just keep an "all_pieces" and a "pieces[color]" bitboard up to date (as well as the pawn bitboard).

I'd appreciate any comments - especially if I'm missing anything,

Best,

Steve

If you are going to use magic, how can you do so without bitboards?

In any case, you need to know where the bishops/rooks/queens are, you need to know the occupied squares on the board (as they block sliders). And you will want those bitboards in your eval as well to recognize patterns...