Author: Bas Hamstra
Date: 15:09:12 01/13/03
Go up one level in this thread
If I understand correctly, you
a) Shift the Occupied-mask so that "From" is in position 0
b) AND with a ray-mask such as RANK0
c) Apply the X ^ (X-2) trick
d) Shift the result back
In case of a queen this has to be done for
- rank
- file
- diag left
- diag right
and this in twofold, normal and reversed. So in fact we are talking about 8
operations (for each direction). Although this probably works (I have to test it
yet) compare this to rotated bitboards. Suppose I want to generate rookattacks.
First I want to generate the RANK attacks:
a) Shift the Occupied bitboard so many ranks that From is at RANK0
b) AND this with RANKMASK_0
This isolates the first rank and gives me a number from 0-255, because 8 bits
have 256 possible states. Now from a pre-computed lookuptable BB
Table[Square][State] I can read the places the rook can move to along the rank
it is on.
For files it is different, because file-bits are not "aligned" and won't give me
a number in the range 0-255. Therefore I keep a 90 degress rotated bitboard, so
that the filebits are aligned as ranks. And then I can do the same trick.
For diags it is even more complicated, because you have to fold non
uniform-length diagonals in a 8x8 square. But basically that's the same trick.
I would not be surprised if despite it's memory references, rotated biboards is
faster, at least at 32 bits cpu's. One shift, one AND and a memory lookup and
you're done for the entire ray. Four operations for a queen, not 8...
Toedeledokie!
Bas.
Shift the from square to 0
b)
On January 13, 2003 at 16:16:11, Sander de Zoete wrote:
>Does anyone use reverse bitboards? I'm writing a new chess program "Preatorian",
>which uses reverse bitboards. Up till now it looks good, but is still 10% slower
>on capture generation than my 0x88 program "Shark". And Shark is slow, it must
>say.
>
>I add some code to see if i'm doing it correct? What could be improved?
>
>//---------------------------------------------------------------------------
>// Generate Rook Moves for Move List
>// Bit Manipulation Trick for REVERSE Bitboard use
>// BITBOARD x, y;
>// y = x ^ (x - 4);
>// Starting from bit 3 (4 = 0100) up, all bits are set to 1 until the
>// first bit of x, which is 1. Also including this bit.
>// eg. x = 0101 0011, y will be 0011 1100.
>// Steps to use bit manipulation x ^ (x -2)
>// 1. Shift allpieces bitboard to the right until the bit with the attacking
>// piece is bit zero
>// 2. Mask the rank/file (for offboard problems)
>// (BITBOARD rank_mask = 0xFF; BITBOARD file_mask = 0x0101010101010101;)
>// 3.1 Perform the bit manipulation
>// 3.2 If file or diagonal: use file_mask/diagonal_mask again!
>// 4.1 Shift back to the left
>// 4.2 Use clear_right half of diagonal if bit 3 (int 4) is set to remove
>// redundant/wrong squares in upper right corner
>// 5 Result is attacks by piece without piece itself
>// 6. Use same steps 1 - 5 for reverse bitboard
>//---------------------------------------------------------------------------
>void RookRankMoves(TBoard *pos, BITBOARD rooksqueen_bitboard, BITBOARD
>all_pieces,
> int reverse, BITBOARD capture_board, int capture )
>{
>BITBOARD h1_bitboard, h2_bitboard;
>int sq_to, sq_fr;
>
>h1_bitboard = rq_bitboard;
>while(h1_bitboard)
>{ sq_fr = LSB(h1_bitboard);
> h2_bitboard = all_pieces;
> h2_bitboard = h2_bitboard>>sq_fr;
> h2_bitboard = h2_bitboard ^ (h2_bitboard - 2);
> h2_bitboard = h2_bitboard<<sq_fr;
> h2_bitboard = h2_bitboard & (mask_rank_1<<(8*(sq_fr>>3))) ;
> //h1_bitboard = Clear_LSB(h1_bitboard);
> h1_bitboard ^= bit_mask[sq_fr];
> // remove captures/own pieces from non capture board
> if (capture)
> h2_bitboard &= capture_board;
> else
> h2_bitboard &= ~all_pieces;
> while(h2_bitboard)
> { sq_to = LSB(h2_bitboard);
> //h2_bitboard = Clear_LSB(h2_bitboard);
> h2_bitboard ^= bit_mask[sq_to];
> if (reverse)
> AddMoveToList((63-sq_fr), (63-sq_to),
> (pos->piece_on_square[(63-sq_fr)]>>2),
> (pos->piece_on_square[(63-sq_to)]>>2), 0, 0, 0);
> else
> AddMoveToList(sq_fr, sq_to,
> (pos->piece_on_square[sq_fr]>>2),
> (pos->piece_on_square[sq_to]>>2), 0, 0, 0);
> g_move_list_counter++;
> }// while h2_board
>}// while h1_board
>}
>
>Thanks for any input,
>Sander de Zoete
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.