Author: Gerd Isenberg
Date: 12:43:24 01/14/03
Go up one level in this thread
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
Hi Sander,
the x^x-2 trick is absolutely great. But IMHO the reversed bitboard idea has one
drawback. If you want to do further processing with the bitboards like anding,
oring, xoring, shifting, comparing etc. you have to do it twice 64 bit wise -
and if you finally traverse or serialize the bitboards, you need two loops
instead of one. More code, more data, lower data density. The other option, to
mirror the reversed bitboard to get them compatible, is too expensive, with
respect to KoggeStone fill.
I use the x^x-2 trick only for (multiple) rooks right-direction attacks. On
future 64-bit processors KoggeStone fill attack generation is an attractive
option. It may even combined with rotated to have routines that generate
fill-attacks for multiple virtual pieces, eg. from a set of safe target squares
of a bishop, to get some progressive mobility.
Regards,
Gerd
This page took 0.02 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.