Author: Gerd Isenberg
Date: 07:34:32 08/24/04
Go up one level in this thread
On August 24, 2004 at 09:44:17, Tony Werten wrote:
>On August 24, 2004 at 09:14:52, Gerd Isenberg wrote:
>
>>On August 24, 2004 at 07:06:14, Tony Werten wrote:
>>
>>>On August 24, 2004 at 06:01:01, Gerd Isenberg wrote:
>>>
>>>>Hi all,
>>>>
>>>>only a vague idea about the possible use of Kogge-Stone-Fill Algorithms...
>>>>
>>>>See Steffan Westcott's original routines:
>>>>http://chessprogramming.org/cccsearch/ccc.php?art_id=261956
>>>>
>>>>The idea is to use multiple bitwise combined generators but only one propagator
>>>>(empty squares) per direction. So with four generators one may get up to 2**4 ==
>>>>16 target sets.
>>>>
>>>>Consider this compact 256-bit board representation with four bitboards and
>>>>therefore four bits per square:
>>>>
>>>>g0,g1,g2,gB
>>>>
>>>>Three corresponding bits in the three bitboards g0-g2 determine piece if any,
>>>>e.g. in this way (g0 == sliding piece):
>>>>
>>>>gb g2 g1 g0
>>>> 0 0 0 empty square
>>>> 0 0 1 not used or redundant single rook, see below
>>>> 0 1 0 pawn
>>>> 0 1 1 bishop
>>>> 1 0 0 knight
>>>> 1 0 1 rook
>>>> 1 1 0 king
>>>> 1 1 1 queen
>>>>
>>>>pB determines black pieces.
>>>>
>>>>allPieces = g0 | g1 | g2;
>>>>white = allPieces& ~gb;
>>>>
>>>>pawns = ~g0 & g1 & ~g2;
>>>>bishops = g0 & g1 & ~g2;
>>>>knights = ~g0 & ~g1 & g2;
>>>>rooks = g0 & ~g1 & g2;
>>>>kings = ~g0 & g1 & g2;
>>>>queens = g0 & g1 & g2;
>>>>
>>>>Now if you do eight (for each queen direction) Kogge-Stone-Fills with these four
>>>>bitboards as generators (or two 128-bit XMM words), you have all possible
>>>>sliding attacks from all pieces as if they are queens.
>>>>
>>>>The resulting vector of 8*4 = 32 bitboards provides all attack information
>>>>needed for move generation and eval, e.g. all pinned piece detected, remove
>>>>checkers, checking target squares for bishops or rooks, target squares for
>>>>attacking rooks or knights by bishop etc ...
>>>
>>>Hmm, aren't there easier things for doing this ?
>>
>>Probably - as i said a vague idea, i'm not sure. It requires some huge register
>>file (G5, Itanium) or some "fast" memory for the combined attacks.
>>I like the idea with minimal 256-bit board representation and minimal incemental
>>update during make(unmake) move with all unique move indizies instead of from/to
>>squares and separate piece/captured piece information ;-)
>>The idea is to do all eight kogge-stone fills only once per node only for all
>>pieces and to extract the piece wise attack informations by three "and" or
>>"notand".
>>
>>{g0,g1,g2,gb} or g[4] -> 8 KoggeStones produce
>>0 fillUp {g[4]}
>>1 fillRightUp {g[4]}
>>2 fillRight {g[4]}
>>3 fillRightDown {g[4]}
>>4 fillDown {g[4]}
>>5 fillLeftDown {g[4]}
>>6 fillLeft {g[4]}
>>7 fillLeftUp {g[4]}
>>==> combined[8][4] // 8==direction, 4==piecebits
>>
>>Since you have eight disjoint directions it is probably cheaper to detect pinned
>>pieces and remove checkers this way:
>>(i like it to have the pinned direction as well)
>>
>>pinnedByBlackOrBlackRemoveCheckers[ver] = allPieces & (
>> (asBRookOrQueen(combined[up]) & asWKing(combined[down]) )
>> | (asBRookOrQueen(combined[down]) & asWKing(combined[up]) )
>> );
>>
>>pinnedByBlackOrBlackRemoveCheckers[hor] = allPieces & (
>> (asBRookOrQueen(combined[left]) & asWKing(combined[right]) )
>> | (asBRookOrQueen(combined[right]) & asWKing(combined[left]) )
>> );
>>
>>pinnedByBlackOrBlackRemoveCheckers[dia1] = allPieces & (
>> (asBBishopOrQueen(combined[leftUp]) & asWKing(combined[rightDown]) )
>> | (asBBishopOrQueen(combined[rightDown])& asWKing(combined[leftUp]) )
>> );
>>
>>pinnedByBlackOrBlackRemoveCheckers[dia2] = allPieces & (
>> (asBBishopOrQueen(combined[leftDown]) & asWKing(combined[rightUp]) )
>> | (asBBishopOrQueen(combined[rightUp]) & asWKing(combined[leftDown]) )
>> );
>>
>>
>>
>>>
>>>checking squares:
>>>
>>>BishopCheckingSquare=bishop_attacks(bishopsq) & bishop_attacks(kingsq)
>>>( you can use for kingsq whatever piecesquare you want )
>>
>>
>>Yes, but bishop_attacks requires four disjoint kogge-stones or two rotated
>>lookups. And as far i can see your code handles only one bishop.
>>
>>
>>>
>>>pieces pinned by bishop:
>>
>>I am not quite sure about your the polymorph bishop_attacks(sq,all_pieces).
>>Is it a kogge Stone with ~all_pieces as propagator?
>>Or is it the intersection of bishop attacks from sq and all_pieces?
>>So i have some problems to follow your pinned piece code ;-(
>>Can you elaborate a bit more on that?
>>Looks interesting.
>
>In normal language :)
>
>Find all the squares the bishop is attacking (direct attacks)
>
>Find the pieces that are under attack and remove them from the pieces board.
>
>Find all the squares the bishop is attacking now.
>
>Remove the original squares you were attacking.
>
>The squares left are the squares you attack indirect. And them with opponent
>pieces and you get the pieces under indirect attack.
Ok, i have it now.
My "feeling" with up to eight disjoint direction wise attacks is, that some
things are cheaper, e.g. movegen of pseudo pinned pieces like queen/rook pinned
to own king by rook etc.
>
>Now do the expensive stuff. ( Most of the time this BB will be empty so it
>doesn't matter ) If it's not an upattack then do a SEE, look if the "blocking
>piece" is yours or mine etc.
>
>I'm starting to get the hang of this BB stuff :)
>
>A question though.
>
>I have brought the size of the lookup tables for move generation down to 5KB (
>at some extra lookup cost ie indirect tables ) What do you think (speed wise) ?
>Is this small enough or should I completely forget about the tables and generate
>every attack with the fill routines ? (except for knights I guess )
That's the question - it depends on the design and infrastructure of the
program, and probably on the target architecture (x86-32/64, G5, Itanium). 5KB
lookup might be negligible, but you may have more computation, dependencies and
stalls...
As i switched from rotated lookup to mmx dump7/Kogge-Stone fill in my current
32-bit program, i found it slightly faster due to legal move generation and
faster pinned piece detection by passing rook/queen bishop/queen bitboards
directly to fill routines.
Setwise Fill-Algos with AMD64 register files might have the advantage to process
several directions simulataniously, and to keep the pipes and alus really busy,
but is therefore not so hyperthreading friendly.
Also, as already mentioned, disjoint directions like left and right attacks
keeps some additional usefull informations for a lot of funny things...
That's the reason i come up with this idea to calculate this 8*4 combined attack
vector once per node with eight kogge-stone fills...
I really intend to use fill routines for knights and kings too instead of a
simple array[64] square lookup, because of my bitboard centric dogma,
almost no bitscan at all ;-)
Gerd
<snip>
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.