Author: Wylie Garvin
Date: 22:01:32 01/23/02
Go up one level in this thread
On January 24, 2002 at 00:54:17, Wylie Garvin wrote:
>On January 23, 2002 at 14:25:03, Russell Reagan wrote:
>
>>On January 22, 2002 at 23:34:10, Tom Likens wrote:
>>
>>>
>>>Russell,
>>>
>>>I think a better example would be the attack of a knight on the king.
>>>Your example of a bishop attack leaves out the minor :) problem of
>>>interposing pieces between the bishop and the king. Your test reveals
>>>a *potential* attack on the king by an enemy bishop.
>>>
>>>regards,
>>>--tom
>>>
>>
>>That is true, and in practice you would not do it like this. You would do
>>something like computing the diagonal state, and passing that to a lookup table
>>which would give you the appropriate attack bitboard for the bishop. You're
>>right that the knight example probably would have been better to explain the
>>underlying concept of how this works.
>>
>>Russell
>
>In another thread, people are talking about the use of assembler insn BSF (and
>its counterpart BSR) on x86 processors for a lowbit() function.
>
>Here's something neat (I think, anyway! ;).
>
>These efficient instructions let you do all your sliding piece calculations
>WITHOUT rotated bitboards, and WITHOUT any large tables (which degrade memory
>performance) and even without "reversed" bitboards, etc.
>
>How? Imagine you AND the "all pieces" bitboard with the "northeast diagonal ray
>from square N". If you use lowbit()/highbit() with this bitboard, you know the
>square number where the ray ends, i.e. the piece which the sliding piece could
>capture.
>
>I've been writing move generators entirely in assembly that are based on this
>technique. They only need only a 4K table (actually 3K in my implementation) of
>the bitboards for the rays in each direction from each square.
>
>Another trick: before starting, I take the "all pieces" bitboard & OR it with a
>"squares-at-the-edge-of-the-board" bitboard. I also place the SOURCE SQUARE in
>my ray mask table, if the mask would *otherwise* be empty. This allows the
>BSF/BSR to *always* find a bit. I add all the bits found in this fashion (i.e.
>up to 8) to a mask, which must be ANDed with the sntm pieces, since you can't
>capture your own pieces. This step incidentally clears the bit for the source
>square, if it happened to be set.
>
>cheers,
>wylie
Sorry, I just realized, I should have specified: this procedure gives you a
mask that you can use for generating bq/rq *captures*. If you are generating
non-captures, you can do other things, like:
- walk the squares of the ray from source square until the "found" square,
generating moves as you go.
- take the ray mask for the *opposite* direction, originating at the "found"
square. Repeat for the ray in the opposite direction. AND these two masks
together, and you have the "occupancy" mask which would be returned by a large
table if you used the rotated-bitboard approach.
I don't know for certain which of these methods I will use. Further reductions
in table size are possible; I actually designed an assembler move generator that
used only about 1.6K for all its tables. It's probably slower though, and the
size difference from a 3K table is irrelevant. I will probably use the "and
opposite ray masks together" method because it gives you a bitboard; I may later
find other uses for this bitboard besides generating moves (such as square
control or something). So far, my actual programming efforts have been directed
at efficient move generation/move making. I haven't written any evaluation code
yet! Since my engine will be written entirely in assembly, I expect it to take
practically forever. What better hobby could one ask for?? =)
wylie
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.