Computer Chess Club Archives


Search

Terms

Messages

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

Author: Alessandro Damiani

Date: 09:55:07 11/20/02

Go up one level in this thread


On November 20, 2002 at 09:37:11, Steffan Westcott wrote:

>On November 20, 2002 at 07:35:46, Sune Fischer wrote:
>
>>You are right that would save time, but I wonder if not the book keeping becomes
>>very complex. There seem to be two conflicting issues at work here, doing the
>>least amount of effort and get a good move ordering.
>>
>>What I don't understand is how you do your move ordering (SEE or MVV/LVA) for
>>captures, how do you access the history table without "to" and "from" squares,
>>that kind of thing.
>>
>>I guess if you do something really simple like: Attack(Whitepawns)&BlackQueens,
>>then you can generate that move(s) only and try that, no move ordering needed.
>>But there are 5 pieces and each can attack eachother, so that must be 25
>>different checks.
>>
>>What am I missing here?
>
>
>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 for indexing the history table, I index it using a move hash value, not the
>from/to square indices. It is merely a different hashing scheme than the
>traditional [from][to] scheme.
>
>Cheers,
>Steffan

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



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