Author: Tony Werten
Date: 07:31:40 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.
>
>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 :)
No I don't :(
This way is silly. You should do this stuff from the kingsquare off coarse.
Tony
>
>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.