Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Natural move generation with bitboards (was Re:significant math)

Author: Steffan Westcott

Date: 14:57:12 11/20/02

Go up one level in this thread


On November 20, 2002 at 12:55:07, Alessandro Damiani wrote:

>On November 20, 2002 at 09:37:11, Steffan Westcott wrote:
>>
>>Sune,
>>
>>I perhaps spend a bit more effort than most on immediate move ordering when the
>>other heurisitics (transposition table, history, killers etc) are exhausted. I
>>have a high degree of overlap between (fundamental) position evaluation and SME
>>(Static Move Evaluation, a generalisation of SEE where the initial move is not
>>necessarily a capture).
>>
>>Your example, of testing for instances of the pattern P x Q, is not far off the
>>mark. The patterns I use for SME are *ahem* somewhat more complex, and mostly
>>resemble those of interest for standard SEE. The patterns are ordered (from best
>>to worst) and tested for matches on the board _when_needed_. It essentially
>>implements a static (predetermined) sequence of move types to try, ordered by
>>position features that can be discovered quickly without doing a search.
>>Optimisations are possible to skip patterns if they are known that they will not
>>currently match anything. For example, if no enemy queen is currently attacked,
>>all patterns ? x Q can be skipped.
>>
>
>As a bitboarder I am very interested in this topic. Very interesting idea,
>Steffan!
>
>Let's take a look at the following example.
>
>[D]4r1k1/2q2pp1/p1p4p/Pp1b4/1P6/2N1PN2/4QPPP/3R2K1 w - - 0 1
>
>We only look at the white knight on c3 for the time being. By using conventional
>(non flood-fill) attack detection one needs to know the from-square, which is c3
>here. But this square is got by serializing the pieces-bitboard. How do you know
>the from-square related to its attack squares without serializing? I remember
>that with flood-fill all squares attacked by a piece-type (all knights) can be
>determined, but the information 'from-square' is lost. Or do i miss something?
>
>With your idea, for the knight on c3 the (non ordered) movelist would be the
>bitboard of all squares attacked by the knight:
>
>::::::::
>::::::::
>::::::::
>:#:#::::
>#:::#:::
>::::::::
>#:::#:::
>:#:#::::
>
>But we need to know the relation (set of to-squares, from-square). How do we
>handle this without extracting the from-square from the pieces-bitboard (=
>serializing). Perhaps I am expecting too much from parallesim and the entry in
>the movelist is really the tuple (from-square, set of to-squares)? ;)
>
>Alessandro

Alessandro,

My 'movelist' state variable (preserved between visits of the current search
node) is a fixed sized data structure. It mainly comprises bitboard fields with
specific interpretations for each, usually the destination square of a specific
move type. After initialisation, there is a 1-1 relationship between a set bit
in a bitboard and a unique move on the board. As each move is searched, its bit
is reset so that it is searched only once. Promotions, castling and en passant
require special handling.

For the 1-1 relationship to work, a sufficient way of classifying move types is
to specify the piece type and its move direction. For example, a move type is
"upward rook move". It is in fact sufficient to specify just the move direction.

To turn to your example, there are 8 bitboards devoted to knight moves, one for
each direction (1 o'clock, 2 o'clock, 4 o'clock, etc). Using the knight attack
bitboard isn't sufficient to uniquely identify knight moves, since several
knights could attack the same square simultaneously.

Cheers,
Steffan



This page took 0.08 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.