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: >>> >>>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 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! Alessandro
This page took 0.01 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.