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

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
Steve Maughan
Posts: 1055
Joined: Wed Mar 08, 2006 7:28 pm
Location: Florida, USA
Contact:

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

Post by Steve Maughan » Wed Mar 27, 2013 12:21 pm

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

User avatar
hgm
Posts: 23149
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

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

Post by hgm » Wed Mar 27, 2013 12:56 pm

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
Posts: 567
Joined: Thu Mar 09, 2006 3:47 pm
Location: Singapore

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

Post by Chan Rasjid » Wed Mar 27, 2013 12:57 pm

Steve Maughan wrote: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.
Don't believe when you're told "There's no free lunch!" There is Linux.

tpetzke
Posts: 686
Joined: Thu Mar 03, 2011 3:57 pm
Location: Germany
Contact:

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

Post by tpetzke » Wed Mar 27, 2013 1:16 pm

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
Posts: 567
Joined: Thu Mar 09, 2006 3:47 pm
Location: Singapore

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

Post by Chan Rasjid » Wed Mar 27, 2013 1:27 pm

Hello,
tpetzke wrote: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.
Don't believe when you're told "There's no free lunch!" There is Linux.

User avatar
Steve Maughan
Posts: 1055
Joined: Wed Mar 08, 2006 7:28 pm
Location: Florida, USA
Contact:

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

Post by Steve Maughan » Wed Mar 27, 2013 2:13 pm

Hi H.G,
hgm wrote: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

User avatar
Steve Maughan
Posts: 1055
Joined: Wed Mar 08, 2006 7:28 pm
Location: Florida, USA
Contact:

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

Post by Steve Maughan » Wed Mar 27, 2013 2:21 pm

Hi Thomas,
tpetzke wrote:[...] 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
Posts: 916
Joined: Tue Mar 09, 2010 2:46 pm
Location: New York
Full name: Álvaro Begué (RuyDos)

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

Post by AlvaroBegue » Wed Mar 27, 2013 2:44 pm

Chan Rasjid wrote: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
Posts: 916
Joined: Tue Mar 09, 2010 2:46 pm
Location: New York
Full name: Álvaro Begué (RuyDos)

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

Post by AlvaroBegue » Wed Mar 27, 2013 2:48 pm

Steve Maughan wrote: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
Posts: 20362
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

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

Post by bob » Wed Mar 27, 2013 2:52 pm

Steve Maughan wrote: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...

Post Reply