Computer Chess Club Archives




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

Author: Alessandro Damiani

Date: 02:55:59 11/21/02

Go up one level in this thread

On November 20, 2002 at 17:57:12, Steffan Westcott wrote:

>On November 20, 2002 at 12:55:07, Alessandro Damiani wrote:
>>On November 20, 2002 at 09:37:11, Steffan Westcott wrote:
>>>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,
>>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)? ;)
>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.

Ah, now I see. It is like what we do for pawn captures, where the pawn-bitboard
is shifted to the left-up (for white pawns) and ANDed with black pieces. Here we
do like what you say: we use the to-square and the direction of the pawn-capture
to get the move.

And for sliding pieces? The distance between the from- and the to-square is not
fixed. In the worst case, for each to-square there are 7 from-squares for one
direction. Do you keep one bitboard for each distance in one direction, ordered
from 1 to 7? Just my first thought.

Now I am thinking about my move ordering and how it is implemented with your
idea........................I take a pizza Quattro Stagioni and a coke, thanks.
Oops! *loool*

Thanks, Steffan!


This page took 0.02 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.