bitboard move generation question

Stuart Cracraft

unread,

Sep 5, 1997, 3:00:00 AM9/5/97

to

Hi,

I understand how to generate moves using bitboards for non-sliding
pieces and pawns.

But I don't understand how to generates moves using bitboards for
sliding pieces.

The best I can think of is to take the ray and and it with the
compliment of the friendly pieces bitmboard. Then calculate the
first set bit in that bitboard, if any, which is furthest away from
the current piece and then retrieve the bitboard for all the square
between the two inclusive and that becomes the legal moves
available on that array. Iterate for all rays then combine to
produce pseudo-legals.

But all of that is a lot of calculation compared to calculating the
moves for non-sliding pieces. Anything faster available?

--Stuart

P.S. Also, what are rotated bitboards and what are they used for?

Marcel van Kervinck

unread,

Sep 5, 1997, 3:00:00 AM9/5/97

to

Stuart Cracraft (crac...@earthlink.net) wrote:
> But all of that is a lot of calculation compared to calculating the
> moves for non-sliding pieces. Anything faster available?

> P.S. Also, what are rotated bitboards and what are they used for?

The rotated bitboards are just designed to enable generating
sliding moves. In short:

Say you have a rook on e4 and want to generate the horizontal moves
for that. To do so you need to know where the other pieces on 4th
rank are, because they block the ray. With a bitboard containing
all pieces you can do a shift and an and-operation. This gives you
8 bits telling you what the 4th rank looks like. This is easy,
because in the bitmap all 4th rank bits are next to eachother.
This 'bitrank', together with the square e4, is used to do a table
lookup to get the horizontal moves. Something like:

/* declaration of some array of precomputed bitboards containing moves */
unsigned long long my_array[256][64];

/* and how to use it */
moves = my_array[rankbits][square];

Now we need to find the vertical moves. This is a bit more difficult,
because now we need the 8 bits that make up the e-file. These
are scattered all over the bitboard. The trick is to also have
a rotated bitboard. This one tells you where the pieces are,
but it is 90 degrees rotated. So we can take that one, shift and
and it, and use that to index the array.

Same idea also applies for diagonal moves. We keep two additional
bitboards, one rotated 45 degrees, and one rotated -45 degrees.
These have all bits that are on the same diagonal next to eachother,
so we can use them to index the table.

So, to generate queenmoves, you need to do 4 table lookups.
One for the horizontal moves, one for the vertical moves, and
two for the diagonal moves. Plus some shifting and masking.

Kind regards,

Marcel
-- _ _
_| |_|_|
|_ |_ Marcel van Kervinck
|_| mar...@stack.nl

Robert Hyatt

unread,

Sep 5, 1997, 3:00:00 AM9/5/97

to

Stuart Cracraft (crac...@earthlink.net) wrote:
: Hi,

: I understand how to generate moves using bitboards for non-sliding
: pieces and pawns.

: But I don't understand how to generates moves using bitboards for
: sliding pieces.

: The best I can think of is to take the ray and and it with the
: compliment of the friendly pieces bitmboard. Then calculate the
: first set bit in that bitboard, if any, which is furthest away from
: the current piece and then retrieve the bitboard for all the square
: between the two inclusive and that becomes the legal moves
: available on that array. Iterate for all rays then combine to
: produce pseudo-legals.

: But all of that is a lot of calculation compared to calculating the

: moves for non-sliding pieces. Anything faster available?

: --Stuart

: P.S. Also, what are rotated bitboards and what are they used for?

Rotated bitmaps are faster. To understand, take a rook. And try to
generate moves as it slides along the rank. There are only 256 unique
states for that rank of course, since there are exactly 8 squares. So
to generate rook moves, sliding along a rank, I create an array of
bitmaps "rank_attacks[64][256]". the 64 is for the 64 squares on the
board, the 256 is for the state of the particular rank I am generating
moves for. I simply take the rank in question, slide the bitmap to
make that rank's 8 bits the rightmost 8 bits in the word, then AND this
with 255. I now have the 8 bits representing the state of the rank the
rook is on. Call this "rank_stuff" I now fetch

rank_attacks[square][rank_stuff]

And with some careful pre-computation, that gives me the squares the rook
attacks along a rank occupied with pieces on "rank_stuff" squares. I
simply pre-compute all of these before starting the game. So sliding
along a rank takes one memory load and I am done. What about files?
I can't do the same trick since the bits for a file are not in adjacent
bits in the occupied-squares bitmap. But I keep a second occupied-squares
that is rotated 90 degrees right, so that the bits for files are adjacent.
And I the load

file_attacks[square][file_stuff]

and then OR the two results together to get the complete set of rook
attacks.

I also keep a rotated left 45 and rotated right 45, which lines up squares
on a diagonal into adjacent bits, and then do the same thing for diagonal
sliding pieces. And, of course, if you OR all 4 of the above together,
you get queen moves. With no loops. No heavy computations... just simple
memory loads...

*very* fast...

Bas Hamstra

unread,

Sep 6, 1997, 3:00:00 AM9/6/97

to

-=[ Quoting hy...@crafty.cis.uab.edu ]=-

hy> : I understand how to generate moves using bitboards for non-sliding
hy> : pieces and pawns.

hy> : But I don't understand how to generates moves using bitboards for
hy> : sliding pieces.

hy> : The best I can think of is to take the ray and and it with the
hy> : compliment of the friendly pieces bitmboard. Then calculate the
hy> : first set bit in that bitboard, if any, which is furthest away from
hy> : the current piece and then retrieve the bitboard for all the square
hy> : between the two inclusive and that becomes the legal moves
hy> : available on that array. Iterate for all rays then combine to
hy> : produce pseudo-legals.

hy> : But all of that is a lot of calculation compared to calculating the
hy> : moves for non-sliding pieces. Anything faster available?

hy> : --Stuart

hy> : P.S. Also, what are rotated bitboards and what are they used for?

hy> Rotated bitmaps are faster. To understand, take a rook. And try to
hy> generate moves as it slides along the rank. There are only 256 unique
hy> states for that rank of course, since there are exactly 8 squares. So
hy> to generate rook moves, sliding along a rank, I create an array of
hy> bitmaps "rank_attacks[64][256]". the 64 is for the 64 squares on the
hy> board, the 256 is for the state of the particular rank I am generating
hy> moves for. I simply take the rank in question, slide the bitmap to
hy> make that rank's 8 bits the rightmost 8 bits in the word, then AND
hy> this with 255. I now have the 8 bits representing the state of the
hy> rank the rook is on. Call this "rank_stuff" I now fetch

hy> rank_attacks[square][rank_stuff]

hy> And with some careful pre-computation, that gives me the squares the
hy> rook attacks along a rank occupied with pieces on "rank_stuff" squares.
hy> I simply pre-compute all of these before starting the game. So
hy> sliding along a rank takes one memory load and I am done. What about
hy> files? I can't do the same trick since the bits for a file are not in
hy> adjacent bits in the occupied-squares bitmap. But I keep a second
hy> occupied-squares that is rotated 90 degrees right, so that the bits
hy> for files are adjacent. And I the load

hy> file_attacks[square][file_stuff]

hy> and then OR the two results together to get the complete set of rook
hy> attacks.

hy> I also keep a rotated left 45 and rotated right 45, which lines up
hy> squares on a diagonal into adjacent bits, and then do the same thing
hy> for diagonal sliding pieces. And, of course, if you OR all 4 of the
hy> above together, you get queen moves. With no loops. No heavy
hy> computations... just simple memory loads...

hy> *very* fast...

Interesting. I'm very curious if this is faster than a table lookup like GNU
(I believe). So a table that contains all legal moves for all squares for
all pieces, with pointers *Continue en *Nextdir. Switch to *Nextdir if a
square is taken. So, what would you think generates moves faster, bitboards
or such a table?

Also I would like to hear your comment on the board representation as used
in (I believe) KnightCap. Every square is a 32 bit number. The bits indicate
which pieces attack the square. The author reported it to be very fast and
handy.

Regards,
Bas Hamstra.

Robert Hyatt

unread,

Sep 6, 1997, 3:00:00 AM9/6/97

to

Bas Hamstra (ham...@kb.xs4all.nl) wrote:
: -=[ Quoting hy...@crafty.cis.uab.edu ]=-

: hy> : --Stuart

: hy> rank_attacks[square][rank_stuff]

: hy> file_attacks[square][file_stuff]

: hy> *very* fast...

In terms of operations, it is much better, because when I want to generate
captures, I *only* generate valid captures. I don't have to scan down each
ray to see if I hit an opponent's piece first. However, on 32 bit machines,
it is not a clear win, because 64bit operations take more time than 32 bit
operations, and some of the needed instructions are not implemented on
all machines (IE the Cray has a FirstOneBit and PopCount instructions, which
are important for bitmap programs.

: Also I would like to hear your comment on the board representation as used

: in (I believe) KnightCap. Every square is a 32 bit number. The bits indicate
: which pieces attack the square. The author reported it to be very fast and
: handy.

It seems like an interesting approach. As to being better or worse,
however, it is like comparing octal to hex arithmetic. Two ways to
do the same thing.

However, I like the 64bit approach for evaluation purposes, because I can
ask some very complicated questions (can this pawn race and promote or will
it be caught by the enemy king?) with one simple AND operation. Ditto for
things like "is this pawn passed?" or "is this pawn isolated"? or "is this
pawn backward?" or "is this rook on an open file?" Things that used to take
loops in Cray Blitz now take the form of simple AND/OR operations, which is
quite useful and fast...

But as far as which is better, that's likely a religious question. :) I'm
a 64bitter, he's a 32bitter, others are no-bitters... :) But I'm not bitter
about the issue. :)

Marcel van Kervinck

unread,

Sep 7, 1997, 3:00:00 AM9/7/97

to

Robert Hyatt (hy...@crafty.cis.uab.edu) wrote:
> : Interesting. I'm very curious if this is faster than a table lookup like GNU
> : (I believe). So a table that contains all legal moves for all squares for
> : all pieces, with pointers *Continue en *Nextdir. Switch to *Nextdir if a
> : square is taken. So, what would you think generates moves faster, bitboards
> : or such a table?

> In terms of operations, it is much better, because when I want to generate
> captures, I *only* generate valid captures. I don't have to scan down each
> ray to see if I hit an opponent's piece first. However, on 32 bit machines,
> it is not a clear win, because 64bit operations take more time than 32 bit
> operations, and some of the needed instructions are not implemented on
> all machines (IE the Cray has a FirstOneBit and PopCount instructions, which
> are important for bitmap programs.

Another problem is that popcount and firstbit are no operators in
C at the moment. Bob, do you have nps numbers for alpha and
ultrasparc? Crafty is still significantly slower than mine on the
latter when I compile crafty. I haven't profiled yours, however.

Robert Hyatt

unread,

Sep 7, 1997, 3:00:00 AM9/7/97

to

Marcel van Kervinck (mar...@stack.nl) wrote:

No. There is one alpha/500mhz on ICC that I have seen run, and it seems
to hit around 150K nps, generally. No numbers for an ultrasparc as we
don't have any here...

My NPS is a good bit lower than "normal" also, because of some of the
pruning I do in the q-search. Throw out any captures and NPS drops,
because you do the work to generate 'em, but don't make 'em... I
have pretty well stopped comparing NPS, since it is so variable from
one program to another, and, instead, use time-to-solution for known
problems instead. That is a better speed metric. I use NPS when I
work on crafty, since I am sometimes only trying to make it faster
without changing the shape of the tree or the eval at all...

George R. Barrett

unread,

Sep 7, 1997, 3:00:00 AM9/7/97

to

Robert Hyatt wrote:
>
> No. There is one alpha/500mhz on ICC that I have seen run, and it seems
> to hit around 150K nps, generally. No numbers for an ultrasparc as we
> don't have any here...
>
> My NPS is a good bit lower than "normal" also, because of some of the
> pruning I do in the q-search. Throw out any captures and NPS drops,
> because you do the work to generate 'em, but don't make 'em... I
> have pretty well stopped comparing NPS, since it is so variable from
> one program to another, and, instead, use time-to-solution for known
> problems instead. That is a better speed metric. I use NPS when I
> work on crafty, since I am sometimes only trying to make it faster
> without changing the shape of the tree or the eval at all...

I see around 50K NPS for Crafty on Ultrasparcs - nothing to write home
about.

--
_____________________________________________________________________
George R. Barrett
Electrical Engineering : Systems `` Without insight, method is
University of Michigan, Ann Arbor largely useless. ''
_____________________________________________________________________

"We make our world significant by the courage of our questions and
the depth of our answers." -- Carl Sagan

Andrew Tridgell

unread,

Sep 8, 1997, 3:00:00 AM9/8/97

to

Robert Hyatt wrote:
> But as far as which is better, that's likely a religious question. :) I'm
> a 64bitter, he's a 32bitter, others are no-bitters... :) But I'm not bitter
> about the issue. :)

The ironic thing is that Bob is running on a 32 bit machine and
I'm using a 64 bit machine (a SGI with a R10k cpu)

:-)

Bas Hamstra

unread,

Sep 8, 1997, 3:00:00 AM9/8/97

to

-=[ Quoting hy...@crafty.cis.uab.edu ]=-

hy> @MSGID: 67:100/4 000040e9
hy> From: hy...@crafty.cis.uab.edu (Robert Hyatt)
hy> Subject: Re: bitboard move generation question
hy> Organization: CIS, University of Alabama at Birmingham

hy> Bas Hamstra (ham...@kb.xs4all.nl) wrote:
hy> : -=[ Quoting hy...@crafty.cis.uab.edu ]=-

: hy> : --Stuart

: hy> board, the 256 is for the state of the particular rank I am genera-

: hy> rank_attacks[square][rank_stuff]

: hy> file_attacks[square][file_stuff]

: hy> *very* fast...

hy> : Interesting. I'm very curious if this is faster than a table lookup
hy> like GNU : (I believe). So a table that contains all legal moves for
hy> all squares for : all pieces, with pointers *Continue en *Nextdir.
hy> Switch to *Nextdir if a : square is taken. So, what would you think
hy> generates moves faster, bitboards : or such a table?

hy> In terms of operations, it is much better, because when I want to
hy> generate captures, I *only* generate valid captures. I don't have to
hy> scan down each ray to see if I hit an opponent's piece first. However,
hy> on 32 bit machines, it is not a clear win, because 64bit operations
hy> take more time than 32 bit operations, and some of the needed
hy> instructions are not implemented on all machines (IE the Cray has a
hy> FirstOneBit and PopCount instructions, which are important for bitmap
hy> programs.

I just implemented such a legal moves table.

hy> : Also I would like to hear your comment on the board representation
hy> as used : in (I believe) KnightCap. Every square is a 32 bit number.
hy> The bits indicate : which pieces attack the square. The author reported
hy> it to be very fast and : handy.

hy> It seems like an interesting approach. As to being better or worse,
hy> however, it is like comparing octal to hex arithmetic. Two ways to
hy> do the same thing.

hy> However, I like the 64bit approach for evaluation purposes, because I
hy> can ask some very complicated questions (can this pawn race and promote
hy> or will it be caught by the enemy king?) with one simple AND operation.
hy> Ditto for things like "is this pawn passed?" or "is this pawn
hy> isolated"? or "is this pawn backward?" or "is this rook on an open
hy> file?" Things that used to take loops in Cray Blitz now take the form
hy> of simple AND/OR operations, which is quite useful and fast...

hy> But as far as which is better, that's likely a religious question. :)
hy> I'm a 64bitter, he's a 32bitter, others are no-bitters... :) But I'm
hy> not bitter about the issue. :)

hy> -!-
hy> ! Origin: Usenet:CIS, University of Alabama at Birmingham (67:100/4)

Robert Hyatt

unread,

Sep 8, 1997, 3:00:00 AM9/8/97

to

Bas Hamstra (ham...@kb.xs4all.nl) wrote:

: I'll remember this. As soon as I get to this type of evaluation questions I
: probably will try it. I guess it must be possible to use bitboards without
: using them for move generation.
:
:

Yes. In fact, I have a board[64] in crafty anyway, because I need to
know what piece is on what square since I store the captured piece in
the moves at present (I am looking at getting rid of this since things
are pretty well debugged) but I do need to know what I am capturing.
Without this board, it is a bit of a pain to see what piece is on a
square...

But, back to the subject. Yes, you can use bitmaps for some, many, or all
program features. In Cray Blitz I used 'em for attack detection only, because
it was so very fast (is this square attacked by the opponent, as it the
famous "InCheck()" sort of test...) In Crafty I use them for *everything*
of course. Somewhere between these two extremes there are interesting things
to try...

Bas Hamstra

unread,

Sep 8, 1997, 3:00:00 AM9/8/97

to

-=[ Quoting hy...@crafty.cis.uab.edu ]=-

: hy> : --Stuart

: hy> rank_attacks[square][rank_stuff]

: hy> file_attacks[square][file_stuff]

: hy> *very* fast...

Well, I have to start somewhere. I just made a precomputed table a la GNU
and it seems to work. From the starting position it can store 35.000 times a
second *all* legal moves in an array, and I believe a lot more is reachable
with some optimizing and a better compiler. This on a Cyrix P200+. Current-
ly, before I generate white moves I first see which squares are attacked by
black (not so efficient of course). Without doing that it would rather be
plm. 50.000 at the moment.

But for now I leave it, because maybe it turns out to be handy to have
InitMovGen() store for every square if it's attacked by white *and* if it's
attacked bij black. I don't know yet. It is even possible to store (during
InitMovGen) for every square by which piece the square is attacked, practi-
cally for free. Bitwise, like in KnightCap (which does it all different of
course).

hy> However, I like the 64bit approach for evaluation purposes, because I
hy> can ask some very complicated questions (can this pawn race and promote
hy> or will it be caught by the enemy king?) with one simple AND operation.
hy> Ditto for things like "is this pawn passed?" or "is this pawn
hy> isolated"? or "is this pawn backward?" or "is this rook on an open
hy> file?" Things that used to take loops in Cray Blitz now take the form
hy> of simple AND/OR operations, which is quite useful and fast...

I'll remember this. As soon as I get to this type of evaluation questions I

probably will try it. I guess it must be possible to use bitboards without
using them for move generation.

Regards,
Bas Hamstra.

Robert Hyatt

unread,

Sep 9, 1997, 3:00:00 AM9/9/97

to

Stuart Cracraft (crac...@earthlink.net) wrote:
: On 5 Sep 1997 16:33:00 GMT, hy...@crafty.cis.uab.edu (Robert Hyatt)
: wrote:

: >Stuart Cracraft (crac...@earthlink.net) wrote:
: >: Hi,
: >

: >: I understand how to generate moves using bitboards for non-sliding
: >: pieces and pawns.
: >
: >: But I don't understand how to generates moves using bitboards for
: >: sliding pieces.
: >
: >: The best I can think of is to take the ray and and it with the
: >: compliment of the friendly pieces bitmboard. Then calculate the
: >: first set bit in that bitboard, if any, which is furthest away from
: >: the current piece and then retrieve the bitboard for all the square
: >: between the two inclusive and that becomes the legal moves
: >: available on that array. Iterate for all rays then combine to
: >: produce pseudo-legals.
: >
: >: But all of that is a lot of calculation compared to calculating the
: >: moves for non-sliding pieces. Anything faster available?
: >
: >: --Stuart
: >
: >: P.S. Also, what are rotated bitboards and what are they used for?
: >
: >Rotated bitmaps are faster. To understand, take a rook. And try to
: >generate moves as it slides along the rank. There are only 256 unique
: >states for that rank of course, since there are exactly 8 squares. So

: I don't understand why there are 256 states. Could you elaborate?

Because a rank has 8 squares, and any of the 8 squares can be empty
or occupied. which gives 256 possible ways to organize a rank with
empty and occupied squares (since there are 2 states, and 8 squares,
we get 2^8 combinations or 256).

: >to generate rook moves, sliding along a rank, I create an array of
: >bitmaps "rank_attacks[64][256]". the 64 is for the 64 squares on the
: >board, the 256 is for the state of the particular rank I am generating
: >moves for. I simply take the rank in question, slide the bitmap to
: >make that rank's 8 bits the rightmost 8 bits in the word, then AND this

: Why do you slide the bitmap? This isn't clear to me either.

You nened the 8 bits for a rank,file or diagonal to be adjacent to
each other, and since they are going to be used as an array index,
they have to be in the right-end of a word. hence the shift right
and then then AND with 0xff.

: >with 255. I now have the 8 bits representing the state of the rank the

: >rook is on. Call this "rank_stuff" I now fetch
: >

: Can you describe the "state of the rank"? Conceptually what does this
: represent?

occupied/empty squares. if you know which squares are occupied and
which are empty, you can figure out where a sliding piece can move to.
You don't need to know what is on each square, just whether they are
empty or not.

: >rank_attacks[square][rank_stuff]
: >
: >And with some careful pre-computation, that gives me the squares the rook
: >attacks along a rank occupied with pieces on "rank_stuff" squares. I

: This leaves me a little unclear too. Sorry if it is just me or not my
: day.

: >simply pre-compute all of these before starting the game. So sliding
: >along a rank takes one memory load and I am done. What about files?
: >I can't do the same trick since the bits for a file are not in adjacent
: >bits in the occupied-squares bitmap. But I keep a second occupied-squares
: >that is rotated 90 degrees right, so that the bits for files are adjacent.
: >And I the load
: >
: >file_attacks[square][file_stuff]
: >
: >and then OR the two results together to get the complete set of rook
: >attacks.
: >
: >I also keep a rotated left 45 and rotated right 45, which lines up squares
: >on a diagonal into adjacent bits, and then do the same thing for diagonal
: >sliding pieces. And, of course, if you OR all 4 of the above together,
: >you get queen moves. With no loops. No heavy computations... just simple
: >memory loads...
: >
: >*very* fast...

Stuart Cracraft

unread,

Sep 9, 1997, 3:00:00 AM9/9/97

to

On 5 Sep 1997 16:33:00 GMT, hy...@crafty.cis.uab.edu (Robert Hyatt)
wrote:

>Stuart Cracraft (crac...@earthlink.net) wrote:
>: Hi,
>
>: I understand how to generate moves using bitboards for non-sliding
>: pieces and pawns.
>
>: But I don't understand how to generates moves using bitboards for
>: sliding pieces.
>
>: The best I can think of is to take the ray and and it with the
>: compliment of the friendly pieces bitmboard. Then calculate the
>: first set bit in that bitboard, if any, which is furthest away from
>: the current piece and then retrieve the bitboard for all the square
>: between the two inclusive and that becomes the legal moves
>: available on that array. Iterate for all rays then combine to
>: produce pseudo-legals.
>
>: But all of that is a lot of calculation compared to calculating the
>: moves for non-sliding pieces. Anything faster available?
>
>: --Stuart
>
>: P.S. Also, what are rotated bitboards and what are they used for?
>
>Rotated bitmaps are faster. To understand, take a rook. And try to
>generate moves as it slides along the rank. There are only 256 unique
>states for that rank of course, since there are exactly 8 squares. So

I don't understand why there are 256 states. Could you elaborate?

>to generate rook moves, sliding along a rank, I create an array of

>bitmaps "rank_attacks[64][256]". the 64 is for the 64 squares on the
>board, the 256 is for the state of the particular rank I am generating
>moves for. I simply take the rank in question, slide the bitmap to
>make that rank's 8 bits the rightmost 8 bits in the word, then AND this

Why do you slide the bitmap? This isn't clear to me either.

>with 255. I now have the 8 bits representing the state of the rank the

>rook is on. Call this "rank_stuff" I now fetch
>

Can you describe the "state of the rank"? Conceptually what does this
represent?

>rank_attacks[square][rank_stuff]

Stuart Cracraft

unread,

Sep 10, 1997, 3:00:00 AM9/10/97

to

Thanks. I now understand (better).

On 9 Sep 1997 03:48:22 GMT, hy...@crafty.cis.uab.edu (Robert Hyatt)
wrote:

>Stuart Cracraft (crac...@earthlink.net) wrote:
>: On 5 Sep 1997 16:33:00 GMT, hy...@crafty.cis.uab.edu (Robert Hyatt)

>: wrote:
>
>: >Stuart Cracraft (crac...@earthlink.net) wrote:
>: >: Hi,
>: >
>: >: I understand how to generate moves using bitboards for non-sliding
>: >: pieces and pawns.
>: >
>: >: But I don't understand how to generates moves using bitboards for
>: >: sliding pieces.
>: >
>: >: The best I can think of is to take the ray and and it with the
>: >: compliment of the friendly pieces bitmboard. Then calculate the
>: >: first set bit in that bitboard, if any, which is furthest away from
>: >: the current piece and then retrieve the bitboard for all the square
>: >: between the two inclusive and that becomes the legal moves
>: >: available on that array. Iterate for all rays then combine to
>: >: produce pseudo-legals.
>: >
>: >: But all of that is a lot of calculation compared to calculating the
>: >: moves for non-sliding pieces. Anything faster available?
>: >
>: >: --Stuart
>: >
>: >: P.S. Also, what are rotated bitboards and what are they used for?
>: >
>: >Rotated bitmaps are faster. To understand, take a rook. And try to
>: >generate moves as it slides along the rank. There are only 256 unique
>: >states for that rank of course, since there are exactly 8 squares. So
>
>: I don't understand why there are 256 states. Could you elaborate?
>

>Because a rank has 8 squares, and any of the 8 squares can be empty
>or occupied. which gives 256 possible ways to organize a rank with
>empty and occupied squares (since there are 2 states, and 8 squares,
>we get 2^8 combinations or 256).
>
>

>: >to generate rook moves, sliding along a rank, I create an array of

>: >bitmaps "rank_attacks[64][256]". the 64 is for the 64 squares on the
>: >board, the 256 is for the state of the particular rank I am generating
>: >moves for. I simply take the rank in question, slide the bitmap to
>: >make that rank's 8 bits the rightmost 8 bits in the word, then AND this
>
>: Why do you slide the bitmap? This isn't clear to me either.
>

>You nened the 8 bits for a rank,file or diagonal to be adjacent to
>each other, and since they are going to be used as an array index,
>they have to be in the right-end of a word. hence the shift right
>and then then AND with 0xff.
>
>

>: >with 255. I now have the 8 bits representing the state of the rank the

>: >rook is on. Call this "rank_stuff" I now fetch
>: >
>
>: Can you describe the "state of the rank"? Conceptually what does this
>: represent?
>

>occupied/empty squares. if you know which squares are occupied and
>which are empty, you can figure out where a sliding piece can move to.
>You don't need to know what is on each square, just whether they are
>empty or not.
>

>: >rank_attacks[square][rank_stuff]

James Long

unread,

Sep 12, 1997, 3:00:00 AM9/12/97

to

Stuart Cracraft wrote:
>

> >: >: I understand how to generate moves using bitboards for non-sliding
> >: >: pieces and pawns.
> >: >
> >: >: But I don't understand how to generates moves using bitboards for
> >: >: sliding pieces.
> >: >

<snip>

Stuart, I use a far more primitive approach in Tristram to generate
moves for sliding pieces. It is much slower than the approach used
by Hyatt and others, but may be easier for you to understand.
I simply start with a BITBOARD of 0, and OR in squares that
are empty and "in bounds". For example, to generate a BITBOARD
of squares a bishop could move to, I execute the following function:

BITBOARD bmoves(int sq)
{

int c,tsq;
BITBOARD attacked=0;

/* first, check the upleft diagonal */

for (c=1;c<=7;c++) {
tsq=sq-(c<<3)-c;
if (tsq<0) break;
if (rdist(sq,tsq) != fdist(sq,tsq)) break;
attacked |= bboard[tsq];
if (Square(tsq) != empty) break;
}

/* second, check the downright diagonal */

for (c=1;c<=7;c++) {
tsq=sq+(c<<3)+c;
if (tsq>63) break;
if (rdist(sq,tsq) != fdist(sq,tsq)) break;
attacked |= bboard[tsq];
if (Square(tsq) != empty) break;
}

/* third, check the upright diagonal */

for (c=1;c<=7;c++) {
tsq=sq-(c<<2)-(c<<1)-c;
if (tsq<0) break;
if (rdist(sq,tsq) != fdist(sq,tsq)) break;
attacked |= bboard[tsq];
if (Square(tsq) != empty) break;
}

/* finally, check the downleft diagonal */

for (c=1;c<=7;c++) {
tsq=sq+(c<<2)+(c<<1)+c;
if (tsq>63) break;
if (rdist(sq,tsq) != fdist(sq,tsq)) break;
attacked |= bboard[tsq];
if (Square(tsq) != empty) break;
}

return attacked;
}

Note that A8=0, H8=7, A1=56, A8=63, and "sq" is the square
the bishop is sitting on when the function is called.

Like I said, a bit primitive and slow, but easy to understand.
Hope this helps.

James

James Long

unread,

Sep 12, 1997, 3:00:00 AM9/12/97

to

Stuart Cracraft wrote:
>
> On 9 Sep 1997 03:48:22 GMT, hy...@crafty.cis.uab.edu (Robert Hyatt)
> wrote:
>
> >Stuart Cracraft (crac...@earthlink.net) wrote:
> >: On 5 Sep 1997 16:33:00 GMT, hy...@crafty.cis.uab.edu (Robert Hyatt)
> >: wrote:
> >
> >: >Stuart Cracraft (crac...@earthlink.net) wrote:
> >: >: Hi,
> >: >

> >: >: I understand how to generate moves using bitboards for non-sliding
> >: >: pieces and pawns.
> >: >
> >: >: But I don't understand how to generates moves using bitboards for
> >: >: sliding pieces.
> >: >

> >: >: The best I can think of is to take the ray and and it with the
> >: >: compliment of the friendly pieces bitmboard. Then calculate the
> >: >: first set bit in that bitboard, if any, which is furthest away from
> >: >: the current piece and then retrieve the bitboard for all the square
> >: >: between the two inclusive and that becomes the legal moves
> >: >: available on that array. Iterate for all rays then combine to
> >: >: produce pseudo-legals.
> >: >
> >: >: But all of that is a lot of calculation compared to calculating the
> >: >: moves for non-sliding pieces. Anything faster available?
> >: >
> >: >: --Stuart
> >: >
> >: >: P.S. Also, what are rotated bitboards and what are they used for?
> >: >
> >: >Rotated bitmaps are faster. To understand, take a rook. And try to
> >: >generate moves as it slides along the rank. There are only 256 unique
> >: >states for that rank of course, since there are exactly 8 squares. So
> >
> >: I don't understand why there are 256 states. Could you elaborate?
> >
> >Because a rank has 8 squares, and any of the 8 squares can be empty
> >or occupied. which gives 256 possible ways to organize a rank with
> >empty and occupied squares (since there are 2 states, and 8 squares,
> >we get 2^8 combinations or 256).
>

> Doesn't this ignore the color of the occupied squares? A rook on a
> rank with 0, 1, or 2 blockers (one blocker on each side) would
> generate a total of 3 * (8 + (8 * 7) + (8 * 7 * 6)) = 1200 states
> when color is taken into account.

You mean the color of the piece on the square? Yes....by definition,
a BITBOARD is a boolean representation of some condition of the
chessboard. For multiliple conditions, you'd have to use multiple
BITBOARDs. Say one BITBOARD for "all pieces", another for "white
pieces",
etc. You can only represent two states with a binary number.

Stuart Cracraft

unread,

Sep 13, 1997, 3:00:00 AM9/13/97

to

>
>

Robert Hyatt

unread,

Sep 13, 1997, 3:00:00 AM9/13/97

to

Stuart Cracraft (crac...@earthlink.net) wrote:
: On 9 Sep 1997 03:48:22 GMT, hy...@crafty.cis.uab.edu (Robert Hyatt)
: wrote:

Doesn't matter at all. A piece that slides attacks thru empty squares and
the attacks stop at the first occupied square in either direction, regardless
of the color of the piece on that square. If you are generating captures,
you control this by something like this:

target=~WhitePieces;

(assuming we are generating moves for white, and WhitePieces has a one
set for any white piece or pawn)

then, after using the lookup described previously, you simply and that
attack bitmap with the above, which cleverly scrubs off captures of your
own pieces, but leaves the attacks for empty squares and enemy pieces.
For generating captures, (for white pieces) you simply:

target=BlackPieces;

look up the attack bitmap again, AND it with target, and you only have
bits set for black pieces you can capture on this sliding ray... This
is *really* fast because there is no sliding down each ray until you hit
a piece, so that most of the loop iterations are wasted. Here there are
*no* iterations unless there are legal captures, where the 1 bits for
those captures need to be converted to "to" squares in a loop...