Author: Tony Werten
Date: 07:39:52 08/24/04
Go up one level in this thread
On August 24, 2004 at 10:31:40, Tony Werten wrote:
>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.
Or not ? Maybe with the fill routines you only have to do it twice. Once for all
rookmovers, once for all bishopmovers. I don't think overlapping will be a
problem and you have the advantage of finding all "pinned on" pieces.
This bitboard stuff gives me headaches :(
Tony
>
>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.