Author: Tony Werten
Date: 06:44:17 08/24/04
Go up one level in this thread
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.
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 )
Tony
>
>Thanks,
>Gerd
>
>>
>>direct_attacks_squares=bishop_attacks(sq,all_pieces)
>>
>>less_pieces=all_pieces & ~(direct_attacks_squares);
>>indirect_attacks_squares=bishop_attacks(sq,less_pieces)
>> & ~(direct_attacks_squares)
>>
>>pinned_pieces=indirect_attacks_squares
>> & less_pieces & ~(own_pieces)
>>
>>
>>Tony
>>
>>
>>>
>>>Since Kogge-Stone fill works setwise, one may have some problems to associate
>>>one member of a target directionwise attack set to the piece (rook/bishop/queen)
>>>attacking this square in this particular direction. More than one queen or
>>>light/dark colored bishop per side is uncommon and good predictable by some
>>>conditional jumps, but with rooks that is quite common.
>>>
>>>Therefore the idea to isolate the least significant rook per side before doing
>>>the fill cycles and to get disjoint target sets per rook. Additional effort to
>>>map source from target squares is only necessary if more than two rooks per side
>>>are involved.
>>>
>>>Cheers,
>>>Gerd
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.