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

[tpetzke]

Hi Steve,

sure

BB_ROOKS[WHITE] & BB_RANKS[7]

to check whether you have a rook at the 7th.

popCount(BB_ROOKS[WHITE] & BB_RANKS[7]) to count the rooks at the 7th

WEAK_SQUARES[BLACK] & BB_KNIGHTS[WHITE]

to check whether white has a knight on a WEAK_SQUARE

Also the check for a rook behind / in front a passed pawn comes into mind.

Thomas...

PS.: I have a getLSB() method the uses a cpu instruction to get the least significant bit from a bit board. It is fairly fast.

[Steve Maughan]

Hi Bob,

[...]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...

I will be using bitboards. The question is should I maintain and incrementally update a bitboard for knights, bishops, queens, rooks and kings for each side? I will maintain a all_pieces bitboard and two bitboards will all pieces corresponding to each color - which as far as U can tell is all that is required for magic move generation.

It would seem there are some evaluation terms which may be easier with bitboards so I'll probably keep them in.

Thanks,

Steve

[Steve Maughan]

Hi Thomas,

OK - I'm convinced. I'll keep them in!

Thanks,

Steve

[Steve Maughan]

Hi Álvaro,

Thanks! I'm convinced - I'll keep them in.

Cheers,

Steve

[Chan Rasjid]

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).

I think yes - my piece list goes. I'll keep the current version, do the changes and compare.

I was thinking a little, that it should be better without the piece list. Updating them don't seem to come cheap. Less global array of pclist[2][8][16] means more cache friendly - just need u64 bits[2][8] all the time. Also not much need for pawn piece list in evaluation as pawn hash has hit rate of 95%.

Best Regards,
Rasjid.

[Steve Maughan]

Hi Chan,

[...]I think yes - my piece list goes. I'll keep the current version, do the changes and compare.[...]

I'll be interested to see your results.

Steve

[Evert]

The question is should I maintain and incrementally update a bitboard for knights, bishops, queens, rooks and kings for each side?

Yes because you can do something like this

Code: Select all

piece = get_piece_on_square(from);
piece_bitboard ^= square[from] | square[to];

to move a piece to its new position. If you don't maintain bitboards for all pieces you need to test the piece-type and update a bitboard (or not), which complicates the code (and adds a branch that will be mis-predicted often).

[Evert]

Code: Select all

uint8_t get_piece(const board_t *board, int where)
{
   assert&#40;where<=H8&#41;;
   assert&#40;where>=A1&#41;;
   assert&#40;board&#41;;
   assert&#40;board->occupied & square&#40;where&#41;);
   bitboard_t bb_where = square&#40;where&#41;;
   
   if &#40;board->bbp&#91;PAWN&#93; & bb_where&#41;
      return PAWN;
   if (&#40;board->bbp&#91;KNIGHT&#93; | board->bbp&#91;BISHOP&#93;) & bb_where&#41; &#123;
      if &#40;board->bbp&#91;BISHOP&#93; & bb_where&#41;
         return BISHOP;
      return KNIGHT;
   &#125;
   if (&#40;board->bbp&#91;ROOK&#93; | board->bbp&#91;QUEEN&#93;) & bb_where&#41; &#123;
      if &#40;board->bbp&#91;QUEEN&#93; & bb_where&#41;
         return QUEEN;
      return ROOK;
   &#125;

   /* Only one possibility left - this should be a king */
   assert&#40;board->bbp&#91;KING&#93; & bb_where&#41;
   return KING;
&#125;

This is (a slightly simplified version of) the function I use in Jazz to get the piece type on a particular square. It's fast enough.

In Sjaak and Leonidas I use a board[64] array to keep track of what piece is on what square, so there the code is much simpler (and presumably faster, but either of them is much slower than Jazz overall).

The reason I don't do that in Jazz is that I use "copy-make" rather than "make-unmake" to update the board: I have an array of board structs and copy the current one to the next entry, then update the "current board" pointer to point to the next entry in the array. When I "unmake" a move I simply decrement the "current board" pointer. It works well, but there is a down side: if you mess up the board during the search (due to a bug) you can't always tell because it's not propagated back to the root so the bug can stay hidden for a long time.

[Rein Halbersma]

This is (a slightly simplified version of) the function I use in Jazz to get the piece type on a particular square. It's fast enough.

In Sjaak and Leonidas I use a board[64] array to keep track of what piece is on what square, so there the code is much simpler (and presumably faster, but either of them is much slower than Jazz overall).

The reason I don't do that in Jazz is that I use "copy-make" rather than "make-unmake" to update the board: I have an array of board structs and copy the current one to the next entry, then update the "current board" pointer to point to the next entry in the array. When I "unmake" a move I simply decrement the "current board" pointer. It works well, but there is a down side: if you mess up the board during the search (due to a bug) you can't always tell because it's not propagated back to the root so the bug can stay hidden for a long time.

How big is your Position class? Would adding 64 bytes of board[64] make such a big difference? Just one cache line per copy. Note that in draughts/checkers you don't need the board array because finding out which piece is on a square is so much cheaper (only king or pawn).

[Evert]

How big is your Position class? Would adding 64 bytes of board[64] make such a big difference? Just one cache line per copy.

Six bitboards (one for each piece type) and two for each side, plus some extra data for a total of 96 bytes (some of which is padding added by the compiler). So adding 64 bytes to that is significant, but actually the perft results aren't that much worse if I add 64 (unused) bytes to the end of the struct, only about 10%. I'd recover some of that from a more efficient get_piece() function.

Still, I suspect a more sensible way to do it would be to use make/unmake for the board[64] array even if I use copy/make for the bitboards, but then it might make more sense to switch to make/unmake altogether (which would be a big hassle since parts of the code rely on being able to access previous positions directly).